From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id C6AA438515D5 for ; Thu, 25 Aug 2022 13:06:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C6AA438515D5 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 245C8D6E for ; Thu, 25 Aug 2022 06:06:11 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.62]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 34ADE3F71A for ; Thu, 25 Aug 2022 06:06:06 -0700 (PDT) From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: [PATCH 4/6] Rearrange unbounded_hashmap_traits References: Date: Thu, 25 Aug 2022 14:06:04 +0100 In-Reply-To: (Richard Sandiford's message of "Thu, 25 Aug 2022 14:04:47 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Status: No, score=-50.5 required=5.0 tests=BAYES_00,GIT_PATCH_0,KAM_DMARC_NONE,KAM_DMARC_STATUS,KAM_LAZY_DOMAIN_SECURITY,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: int_hash combines two kinds of operation: (1) hashing and equality of integers (2) using spare integer encodings to represent empty and deleted slots (1) is really independent of (2), and could be useful in cases where no spare integer encodings are available. This patch adds a base class (int_hash_base) for (1) and makes int_hash inherit from it. If we follow a similar style for future hashes, we can make unbounded_hashmap_traits take the "base" hash for the key as a template parameter, rather than requiring every type of key to have a separate derivative of unbounded_hashmap_traits. A later patch applies this to vector keys. No functional change intended. gcc/ * hash-traits.h (int_hash_base): New struct, split out from... (int_hash): ...this class, which now inherits from int_hash_base. * hash-map-traits.h (unbounded_hashmap_traits): Take a template parameter for the key that provides hash and equality functions. (unbounded_int_hashmap_traits): Turn into a type alias of unbounded_hashmap_traits. --- gcc/hash-map-traits.h | 74 +++++++++++++++++++++++-------------------- gcc/hash-traits.h | 42 ++++++++++++++---------- 2 files changed, 65 insertions(+), 51 deletions(-) diff --git a/gcc/hash-map-traits.h b/gcc/hash-map-traits.h index fad0c7d52c5..d729d358070 100644 --- a/gcc/hash-map-traits.h +++ b/gcc/hash-map-traits.h @@ -105,14 +105,19 @@ struct simple_cache_map_traits: public simple_hashmap_traits static const bool maybe_mx = false; }; -/* Implement traits for a hash_map with values of type Value for cases - in which the key cannot represent empty and deleted slots. Instead - record empty and deleted entries in Value. Derived classes must - implement the hash and equal_keys functions. */ +/* Implement traits for a hash_map with keys of type Key and values of + type Value for cases in which the key cannot represent empty and + deleted slots. Instead record empty and deleted entries in Value. */ -template +template struct unbounded_hashmap_traits { + typedef typename Key::value_type key_type; + + static hashval_t hash (const typename Key::value_type &); + static bool equal_keys (const typename Key::value_type &, + const typename Key::compare_type &); + template static inline void remove (T &); static const bool empty_zero_p = default_hash_traits ::empty_zero_p; template static inline bool is_empty (const T &); @@ -121,42 +126,59 @@ struct unbounded_hashmap_traits template static inline void mark_deleted (T &); }; -template +template +inline hashval_t +unbounded_hashmap_traits +::hash (const typename Key::value_type &key) +{ + return Key::hash (key); +} + +template +inline bool +unbounded_hashmap_traits +::equal_keys (const typename Key::value_type &x, + const typename Key::compare_type &y) +{ + return Key::equal (x, y); +} + +template template inline void -unbounded_hashmap_traits ::remove (T &entry) +unbounded_hashmap_traits ::remove (T &entry) { default_hash_traits ::remove (entry.m_value); } -template +template template inline bool -unbounded_hashmap_traits ::is_empty (const T &entry) +unbounded_hashmap_traits ::is_empty (const T &entry) { return default_hash_traits ::is_empty (entry.m_value); } -template +template template inline bool -unbounded_hashmap_traits ::is_deleted (const T &entry) +unbounded_hashmap_traits ::is_deleted (const T &entry) { return default_hash_traits ::is_deleted (entry.m_value); } -template +template template inline void -unbounded_hashmap_traits ::mark_empty (T &entry) +unbounded_hashmap_traits ::mark_empty (T &entry) { default_hash_traits ::mark_empty (entry.m_value); } -template +template template inline void -unbounded_hashmap_traits ::mark_deleted (T &entry) +unbounded_hashmap_traits ::mark_deleted (T &entry) { default_hash_traits ::mark_deleted (entry.m_value); } @@ -166,25 +188,7 @@ unbounded_hashmap_traits ::mark_deleted (T &entry) slots. */ template -struct unbounded_int_hashmap_traits : unbounded_hashmap_traits -{ - typedef Key key_type; - static inline hashval_t hash (Key); - static inline bool equal_keys (Key, Key); -}; - -template -inline hashval_t -unbounded_int_hashmap_traits ::hash (Key k) -{ - return k; -} - -template -inline bool -unbounded_int_hashmap_traits ::equal_keys (Key k1, Key k2) -{ - return k1 == k2; -} +using unbounded_int_hashmap_traits + = unbounded_hashmap_traits , Value>; #endif // HASH_MAP_TRAITS_H diff --git a/gcc/hash-traits.h b/gcc/hash-traits.h index bef0bd42d04..55b81eb0f9e 100644 --- a/gcc/hash-traits.h +++ b/gcc/hash-traits.h @@ -85,41 +85,51 @@ typed_noop_remove ::remove (Type &) { } +/* Base traits for integer type Type, providing just the hash and + comparison functionality. */ -/* Hasher for integer type Type in which Empty is a spare value that can be - used to mark empty slots. If Deleted != Empty then Deleted is another - spare value that can be used for deleted slots; if Deleted == Empty then - hash table entries cannot be deleted. */ - -template -struct int_hash : typed_noop_remove +template +struct int_hash_base : typed_noop_remove { typedef Type value_type; typedef Type compare_type; static inline hashval_t hash (value_type); static inline bool equal (value_type existing, value_type candidate); - static inline void mark_deleted (Type &); - static const bool empty_zero_p = Empty == 0; - static inline void mark_empty (Type &); - static inline bool is_deleted (Type); - static inline bool is_empty (Type); }; -template +template inline hashval_t -int_hash ::hash (value_type x) +int_hash_base ::hash (value_type x) { return x; } -template +template inline bool -int_hash ::equal (value_type x, value_type y) +int_hash_base ::equal (value_type x, value_type y) { return x == y; } +/* Hasher for integer type Type in which Empty is a spare value that can be + used to mark empty slots. If Deleted != Empty then Deleted is another + spare value that can be used for deleted slots; if Deleted == Empty then + hash table entries cannot be deleted. */ + +template +struct int_hash : int_hash_base +{ + typedef Type value_type; + typedef Type compare_type; + + static inline void mark_deleted (Type &); + static const bool empty_zero_p = Empty == 0; + static inline void mark_empty (Type &); + static inline bool is_deleted (Type); + static inline bool is_empty (Type); +}; + template inline void int_hash ::mark_deleted (Type &x) -- 2.25.1