[gcc r13-2286] Rearrange unbounded_hashmap_traits

[gcc r13-2286] Rearrange unbounded_hashmap_traits

[Richard Sandiford]

https://gcc.gnu.org/g:8c6952abc8ceff1a25b78506315959240cb73d41

commit r13-2286-g8c6952abc8ceff1a25b78506315959240cb73d41
Author: Richard Sandiford <richard.sandiford@arm.com>
Date:   Tue Aug 30 15:43:47 2022 +0100

    Rearrange unbounded_hashmap_traits
    
    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.

Diff:
---
 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<H,Value>
   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 <typename Value>
+template <typename Key, typename Value>
 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 <typename T> static inline void remove (T &);
   static const bool empty_zero_p = default_hash_traits <Value>::empty_zero_p;
   template <typename T> static inline bool is_empty (const T &);
@@ -121,42 +126,59 @@ struct unbounded_hashmap_traits
   template <typename T> static inline void mark_deleted (T &);
 };
 
-template <typename Value>
+template <typename Key, typename Value>
+inline hashval_t
+unbounded_hashmap_traits <Key, Value>
+::hash (const typename Key::value_type &key)
+{
+  return Key::hash (key);
+}
+
+template <typename Key, typename Value>
+inline bool
+unbounded_hashmap_traits <Key, Value>
+::equal_keys (const typename Key::value_type &x,
+	      const typename Key::compare_type &y)
+{
+  return Key::equal (x, y);
+}
+
+template <typename Key, typename Value>
 template <typename T>
 inline void
-unbounded_hashmap_traits <Value>::remove (T &entry)
+unbounded_hashmap_traits <Key, Value>::remove (T &entry)
 {
   default_hash_traits <Value>::remove (entry.m_value);
 }
 
-template <typename Value>
+template <typename Key, typename Value>
 template <typename T>
 inline bool
-unbounded_hashmap_traits <Value>::is_empty (const T &entry)
+unbounded_hashmap_traits <Key, Value>::is_empty (const T &entry)
 {
   return default_hash_traits <Value>::is_empty (entry.m_value);
 }
 
-template <typename Value>
+template <typename Key, typename Value>
 template <typename T>
 inline bool
-unbounded_hashmap_traits <Value>::is_deleted (const T &entry)
+unbounded_hashmap_traits <Key, Value>::is_deleted (const T &entry)
 {
   return default_hash_traits <Value>::is_deleted (entry.m_value);
 }
 
-template <typename Value>
+template <typename Key, typename Value>
 template <typename T>
 inline void
-unbounded_hashmap_traits <Value>::mark_empty (T &entry)
+unbounded_hashmap_traits <Key, Value>::mark_empty (T &entry)
 {
   default_hash_traits <Value>::mark_empty (entry.m_value);
 }
 
-template <typename Value>
+template <typename Key, typename Value>
 template <typename T>
 inline void
-unbounded_hashmap_traits <Value>::mark_deleted (T &entry)
+unbounded_hashmap_traits <Key, Value>::mark_deleted (T &entry)
 {
   default_hash_traits <Value>::mark_deleted (entry.m_value);
 }
@@ -166,25 +188,7 @@ unbounded_hashmap_traits <Value>::mark_deleted (T &entry)
    slots.  */
 
 template <typename Key, typename Value>
-struct unbounded_int_hashmap_traits : unbounded_hashmap_traits <Value>
-{
-  typedef Key key_type;
-  static inline hashval_t hash (Key);
-  static inline bool equal_keys (Key, Key);
-};
-
-template <typename Key, typename Value>
-inline hashval_t
-unbounded_int_hashmap_traits <Key, Value>::hash (Key k)
-{
-  return k;
-}
-
-template <typename Key, typename Value>
-inline bool
-unbounded_int_hashmap_traits <Key, Value>::equal_keys (Key k1, Key k2)
-{
-  return k1 == k2;
-}
+using unbounded_int_hashmap_traits
+  = unbounded_hashmap_traits <int_hash_base <Key>, 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 <Type>::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 <typename Type, Type Empty, Type Deleted = Empty>
-struct int_hash : typed_noop_remove <Type>
+template <typename Type>
+struct int_hash_base : typed_noop_remove <Type>
 {
   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 <typename Type, Type Empty, Type Deleted>
+template <typename Type>
 inline hashval_t
-int_hash <Type, Empty, Deleted>::hash (value_type x)
+int_hash_base <Type>::hash (value_type x)
 {
   return x;
 }
 
-template <typename Type, Type Empty, Type Deleted>
+template <typename Type>
 inline bool
-int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
+int_hash_base <Type>::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 <typename Type, Type Empty, Type Deleted = Empty>
+struct int_hash : int_hash_base <Type>
+{
+  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 <typename Type, Type Empty, Type Deleted>
 inline void
 int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)