gcc/hash-traits.h

   1 /* Traits for hashable types.
   2    Copyright (C) 2014-2022 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef hash_traits_h
  21 #define hash_traits_h
  22
  23 /* Helpful type for removing with free.  */
  24
  25 template <typename Type>
  26 struct typed_free_remove
  27 {
  28   static inline void remove (Type *p);
  29 };
  30
  31 template <typename Type>
  32 struct typed_const_free_remove
  33 {
  34   static inline void remove (const Type *p);
  35 };
  36
  37 /* Remove with free.  */
  38
  39 template <typename Type>
  40 inline void
  41 typed_free_remove <Type>::remove (Type *p)
  42 {
  43   free (p);
  44 }
  45
  46 template <typename Type>
  47 inline void
  48 typed_const_free_remove <Type>::remove (const Type *p)
  49 {
  50   free (const_cast <Type *> (p));
  51 }
  52
  53 /* Helpful type for removing with delete.  */
  54
  55 template <typename Type>
  56 struct typed_delete_remove
  57 {
  58   static inline void remove (Type *p);
  59 };
  60
  61
  62 /* Remove with delete.  */
  63
  64 template <typename Type>
  65 inline void
  66 typed_delete_remove <Type>::remove (Type *p)
  67 {
  68   delete p;
  69 }
  70
  71 /* Helpful type for a no-op remove.  */
  72
  73 template <typename Type>
  74 struct typed_noop_remove
  75 {
  76   static inline void remove (Type &);
  77 };
  78
  79
  80 /* Remove doing nothing.  */
  81
  82 template <typename Type>
  83 inline void
  84 typed_noop_remove <Type>::remove (Type &)
  85 {
  86 }
  87
  88
  89 /* Hasher for integer type Type in which Empty is a spare value that can be
  90    used to mark empty slots.  If Deleted != Empty then Deleted is another
  91    spare value that can be used for deleted slots; if Deleted == Empty then
  92    hash table entries cannot be deleted.  */
  93
  94 template <typename Type, Type Empty, Type Deleted = Empty>
  95 struct int_hash : typed_noop_remove <Type>
  96 {
  97   typedef Type value_type;
  98   typedef Type compare_type;
  99
 100   static inline hashval_t hash (value_type);
 101   static inline bool equal (value_type existing, value_type candidate);
 102   static inline void mark_deleted (Type &);
 103   static const bool empty_zero_p = Empty == 0;
 104   static inline void mark_empty (Type &);
 105   static inline bool is_deleted (Type);
 106   static inline bool is_empty (Type);
 107 };
 108
 109 template <typename Type, Type Empty, Type Deleted>
 110 inline hashval_t
 111 int_hash <Type, Empty, Deleted>::hash (value_type x)
 112 {
 113   return x;
 114 }
 115
 116 template <typename Type, Type Empty, Type Deleted>
 117 inline bool
 118 int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
 119 {
 120   return x == y;
 121 }
 122
 123 template <typename Type, Type Empty, Type Deleted>
 124 inline void
 125 int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
 126 {
 127   gcc_assert (Empty != Deleted);
 128   x = Deleted;
 129 }
 130
 131 template <typename Type, Type Empty, Type Deleted>
 132 inline void
 133 int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
 134 {
 135   x = Empty;
 136 }
 137
 138 template <typename Type, Type Empty, Type Deleted>
 139 inline bool
 140 int_hash <Type, Empty, Deleted>::is_deleted (Type x)
 141 {
 142   return Empty != Deleted && x == Deleted;
 143 }
 144
 145 template <typename Type, Type Empty, Type Deleted>
 146 inline bool
 147 int_hash <Type, Empty, Deleted>::is_empty (Type x)
 148 {
 149   return x == Empty;
 150 }
 151
 152 /* Pointer hasher based on pointer equality.  Other types of pointer hash
 153    can inherit this and override the hash and equal functions with some
 154    other form of equality (such as string equality).  */
 155
 156 template <typename Type>
 157 struct pointer_hash
 158 {
 159   typedef Type *value_type;
 160   typedef Type *compare_type;
 161
 162   static inline hashval_t hash (const value_type &);
 163   static inline bool equal (const value_type &existing,
 164                             const compare_type &candidate);
 165   static inline void mark_deleted (Type *&);
 166   static const bool empty_zero_p = true;
 167   static inline void mark_empty (Type *&);
 168   static inline bool is_deleted (Type *);
 169   static inline bool is_empty (Type *);
 170 };
 171
 172 template <typename Type>
 173 inline hashval_t
 174 pointer_hash <Type>::hash (const value_type &candidate)
 175 {
 176   /* This is a really poor hash function, but it is what the current code uses,
 177      so I am reusing it to avoid an additional axis in testing.  */
 178   return (hashval_t) ((intptr_t)candidate >> 3);
 179 }
 180
 181 template <typename Type>
 182 inline bool
 183 pointer_hash <Type>::equal (const value_type &existing,
 184                            const compare_type &candidate)
 185 {
 186   return existing == candidate;
 187 }
 188
 189 template <typename Type>
 190 inline void
 191 pointer_hash <Type>::mark_deleted (Type *&e)
 192 {
 193   e = reinterpret_cast<Type *> (1);
 194 }
 195
 196 template <typename Type>
 197 inline void
 198 pointer_hash <Type>::mark_empty (Type *&e)
 199 {
 200   e = NULL;
 201 }
 202
 203 template <typename Type>
 204 inline bool
 205 pointer_hash <Type>::is_deleted (Type *e)
 206 {
 207   return e == reinterpret_cast<Type *> (1);
 208 }
 209
 210 template <typename Type>
 211 inline bool
 212 pointer_hash <Type>::is_empty (Type *e)
 213 {
 214   return e == NULL;
 215 }
 216
 217 /* Hasher for "const char *" strings, using string rather than pointer
 218    equality.  */
 219
 220 struct string_hash : pointer_hash <const char>
 221 {
 222   static inline hashval_t hash (const char *);
 223   static inline bool equal (const char *, const char *);
 224 };
 225
 226 inline hashval_t
 227 string_hash::hash (const char *id)
 228 {
 229   return htab_hash_string (id);
 230 }
 231
 232 inline bool
 233 string_hash::equal (const char *id1, const char *id2)
 234 {
 235   return strcmp (id1, id2) == 0;
 236 }
 237
 238 /* Remover and marker for entries in gc memory.  */
 239
 240 template<typename T>
 241 struct ggc_remove
 242 {
 243   static void remove (T &) {}
 244
 245   static void
 246   ggc_mx (T &p)
 247   {
 248     extern void gt_ggc_mx (T &);
 249     gt_ggc_mx (p);
 250   }
 251
 252   /* Overridden in ggc_cache_remove.  */
 253   static void
 254   ggc_maybe_mx (T &p)
 255   {
 256     ggc_mx (p);
 257   }
 258
 259   static void
 260   pch_nx (T &p)
 261   {
 262     extern void gt_pch_nx (T &);
 263     gt_pch_nx (p);
 264   }
 265
 266   static void
 267   pch_nx (T &p, gt_pointer_operator op, void *cookie)
 268   {
 269     op (&p, NULL, cookie);
 270   }
 271 };
 272
 273 /* Remover and marker for "cache" entries in gc memory.  These entries can
 274    be deleted if there are no non-cache references to the data.  */
 275
 276 template<typename T>
 277 struct ggc_cache_remove : ggc_remove<T>
 278 {
 279   /* Entries are weakly held because this is for caches.  */
 280   static void ggc_maybe_mx (T &) {}
 281
 282   static int
 283   keep_cache_entry (T &e)
 284   {
 285     return ggc_marked_p (e) ? -1 : 0;
 286   }
 287 };
 288
 289 /* Traits for pointer elements that should not be freed when an element
 290    is deleted.  */
 291
 292 template <typename T>
 293 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
 294
 295 /* Traits for pointer elements that should be freed via free() when an
 296    element is deleted.  */
 297
 298 template <typename T>
 299 struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
 300
 301 /* Traits for pointer elements that should be freed via delete operand when an
 302    element is deleted.  */
 303
 304 template <typename T>
 305 struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {};
 306
 307 /* Traits for elements that point to gc memory.  The pointed-to data
 308    must be kept across collections.  */
 309
 310 template <typename T>
 311 struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
 312
 313 /* Traits for elements that point to gc memory.  The elements don't
 314    in themselves keep the pointed-to data alive and they can be deleted
 315    if the pointed-to data is going to be collected.  */
 316
 317 template <typename T>
 318 struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
 319
 320 /* Traits for string elements that should be freed when an element is
 321    deleted.  */
 322
 323 struct free_string_hash : string_hash, typed_const_free_remove <char> {};
 324
 325 /* Traits for string elements that should not be freed when an element
 326    is deleted.  */
 327
 328 struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
 329
 330 /* Traits for pairs of values, using the first to record empty and
 331    deleted slots.  */
 332
 333 template <typename T1, typename T2>
 334 struct pair_hash
 335 {
 336   typedef std::pair <typename T1::value_type,
 337                      typename T2::value_type> value_type;
 338   typedef std::pair <typename T1::compare_type,
 339                      typename T2::compare_type> compare_type;
 340
 341   static inline hashval_t hash (const value_type &);
 342   static inline bool equal (const value_type &, const compare_type &);
 343   static inline void remove (value_type &);
 344   static inline void mark_deleted (value_type &);
 345   static const bool empty_zero_p = T1::empty_zero_p;
 346   static inline void mark_empty (value_type &);
 347   static inline bool is_deleted (const value_type &);
 348   static inline bool is_empty (const value_type &);
 349 };
 350
 351 template <typename T1, typename T2>
 352 inline hashval_t
 353 pair_hash <T1, T2>::hash (const value_type &x)
 354 {
 355   return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second));
 356 }
 357
 358 template <typename T1, typename T2>
 359 inline bool
 360 pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
 361 {
 362   return T1::equal (x.first, y.first) && T2::equal (x.second, y.second);
 363 }
 364
 365 template <typename T1, typename T2>
 366 inline void
 367 pair_hash <T1, T2>::remove (value_type &x)
 368 {
 369   T1::remove (x.first);
 370   T2::remove (x.second);
 371 }
 372
 373 template <typename T1, typename T2>
 374 inline void
 375 pair_hash <T1, T2>::mark_deleted (value_type &x)
 376 {
 377   T1::mark_deleted (x.first);
 378 }
 379
 380 template <typename T1, typename T2>
 381 inline void
 382 pair_hash <T1, T2>::mark_empty (value_type &x)
 383 {
 384   T1::mark_empty (x.first);
 385 }
 386
 387 template <typename T1, typename T2>
 388 inline bool
 389 pair_hash <T1, T2>::is_deleted (const value_type &x)
 390 {
 391   return T1::is_deleted (x.first);
 392 }
 393
 394 template <typename T1, typename T2>
 395 inline bool
 396 pair_hash <T1, T2>::is_empty (const value_type &x)
 397 {
 398   return T1::is_empty (x.first);
 399 }
 400
 401 template <typename T> struct default_hash_traits : T {};
 402
 403 template <typename T>
 404 struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
 405
 406 #endif