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 /* Base traits for integer type Type, providing just the hash and
  89    comparison functionality.  */
  90
  91 template <typename Type>
  92 struct int_hash_base : typed_noop_remove <Type>
  93 {
  94   typedef Type value_type;
  95   typedef Type compare_type;
  96
  97   static inline hashval_t hash (value_type);
  98   static inline bool equal (value_type existing, value_type candidate);
  99 };
 100
 101 template <typename Type>
 102 inline hashval_t
 103 int_hash_base <Type>::hash (value_type x)
 104 {
 105   return x;
 106 }
 107
 108 template <typename Type>
 109 inline bool
 110 int_hash_base <Type>::equal (value_type x, value_type y)
 111 {
 112   return x == y;
 113 }
 114
 115 /* Hasher for integer type Type in which Empty is a spare value that can be
 116    used to mark empty slots.  If Deleted != Empty then Deleted is another
 117    spare value that can be used for deleted slots; if Deleted == Empty then
 118    hash table entries cannot be deleted.  */
 119
 120 template <typename Type, Type Empty, Type Deleted = Empty>
 121 struct int_hash : int_hash_base <Type>
 122 {
 123   typedef Type value_type;
 124   typedef Type compare_type;
 125
 126   static inline void mark_deleted (Type &);
 127   static const bool empty_zero_p = Empty == 0;
 128   static inline void mark_empty (Type &);
 129   static inline bool is_deleted (Type);
 130   static inline bool is_empty (Type);
 131 };
 132
 133 template <typename Type, Type Empty, Type Deleted>
 134 inline void
 135 int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
 136 {
 137   gcc_assert (Empty != Deleted);
 138   x = Deleted;
 139 }
 140
 141 template <typename Type, Type Empty, Type Deleted>
 142 inline void
 143 int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
 144 {
 145   x = Empty;
 146 }
 147
 148 template <typename Type, Type Empty, Type Deleted>
 149 inline bool
 150 int_hash <Type, Empty, Deleted>::is_deleted (Type x)
 151 {
 152   return Empty != Deleted && x == Deleted;
 153 }
 154
 155 template <typename Type, Type Empty, Type Deleted>
 156 inline bool
 157 int_hash <Type, Empty, Deleted>::is_empty (Type x)
 158 {
 159   return x == Empty;
 160 }
 161
 162 /* Pointer hasher based on pointer equality.  Other types of pointer hash
 163    can inherit this and override the hash and equal functions with some
 164    other form of equality (such as string equality).  */
 165
 166 template <typename Type>
 167 struct pointer_hash
 168 {
 169   typedef Type *value_type;
 170   typedef Type *compare_type;
 171
 172   static inline hashval_t hash (const value_type &);
 173   static inline bool equal (const value_type &existing,
 174                             const compare_type &candidate);
 175   static inline void mark_deleted (Type *&);
 176   static const bool empty_zero_p = true;
 177   static inline void mark_empty (Type *&);
 178   static inline bool is_deleted (Type *);
 179   static inline bool is_empty (Type *);
 180 };
 181
 182 template <typename Type>
 183 inline hashval_t
 184 pointer_hash <Type>::hash (const value_type &candidate)
 185 {
 186   /* This is a really poor hash function, but it is what the current code uses,
 187      so I am reusing it to avoid an additional axis in testing.  */
 188   return (hashval_t) ((intptr_t)candidate >> 3);
 189 }
 190
 191 template <typename Type>
 192 inline bool
 193 pointer_hash <Type>::equal (const value_type &existing,
 194                            const compare_type &candidate)
 195 {
 196   return existing == candidate;
 197 }
 198
 199 template <typename Type>
 200 inline void
 201 pointer_hash <Type>::mark_deleted (Type *&e)
 202 {
 203   e = reinterpret_cast<Type *> (1);
 204 }
 205
 206 template <typename Type>
 207 inline void
 208 pointer_hash <Type>::mark_empty (Type *&e)
 209 {
 210   e = NULL;
 211 }
 212
 213 template <typename Type>
 214 inline bool
 215 pointer_hash <Type>::is_deleted (Type *e)
 216 {
 217   return e == reinterpret_cast<Type *> (1);
 218 }
 219
 220 template <typename Type>
 221 inline bool
 222 pointer_hash <Type>::is_empty (Type *e)
 223 {
 224   return e == NULL;
 225 }
 226
 227 /* Hasher for "const char *" strings, using string rather than pointer
 228    equality.  */
 229
 230 struct string_hash : pointer_hash <const char>
 231 {
 232   static inline hashval_t hash (const char *);
 233   static inline bool equal (const char *, const char *);
 234 };
 235
 236 inline hashval_t
 237 string_hash::hash (const char *id)
 238 {
 239   return htab_hash_string (id);
 240 }
 241
 242 inline bool
 243 string_hash::equal (const char *id1, const char *id2)
 244 {
 245   return strcmp (id1, id2) == 0;
 246 }
 247
 248 /* Remover and marker for entries in gc memory.  */
 249
 250 template<typename T>
 251 struct ggc_remove
 252 {
 253   static void remove (T &) {}
 254
 255   static void
 256   ggc_mx (T &p)
 257   {
 258     extern void gt_ggc_mx (T &);
 259     gt_ggc_mx (p);
 260   }
 261
 262   /* Overridden in ggc_cache_remove.  */
 263   static void
 264   ggc_maybe_mx (T &p)
 265   {
 266     ggc_mx (p);
 267   }
 268
 269   static void
 270   pch_nx (T &p)
 271   {
 272     extern void gt_pch_nx (T &);
 273     gt_pch_nx (p);
 274   }
 275
 276   static void
 277   pch_nx (T &p, gt_pointer_operator op, void *cookie)
 278   {
 279     op (&p, NULL, cookie);
 280   }
 281 };
 282
 283 /* Remover and marker for "cache" entries in gc memory.  These entries can
 284    be deleted if there are no non-cache references to the data.  */
 285
 286 template<typename T>
 287 struct ggc_cache_remove : ggc_remove<T>
 288 {
 289   /* Entries are weakly held because this is for caches.  */
 290   static void ggc_maybe_mx (T &) {}
 291
 292   static int
 293   keep_cache_entry (T &e)
 294   {
 295     return ggc_marked_p (e) ? -1 : 0;
 296   }
 297 };
 298
 299 /* Traits for pointer elements that should not be freed when an element
 300    is deleted.  */
 301
 302 template <typename T>
 303 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
 304
 305 /* Traits for pointer elements that should be freed via free() when an
 306    element is deleted.  */
 307
 308 template <typename T>
 309 struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
 310
 311 /* Traits for pointer elements that should be freed via delete operand when an
 312    element is deleted.  */
 313
 314 template <typename T>
 315 struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {};
 316
 317 /* Traits for elements that point to gc memory.  The pointed-to data
 318    must be kept across collections.  */
 319
 320 template <typename T>
 321 struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
 322
 323 /* Traits for elements that point to gc memory.  The elements don't
 324    in themselves keep the pointed-to data alive and they can be deleted
 325    if the pointed-to data is going to be collected.  */
 326
 327 template <typename T>
 328 struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
 329
 330 /* Traits for string elements that should be freed when an element is
 331    deleted.  */
 332
 333 struct free_string_hash : string_hash, typed_const_free_remove <char> {};
 334
 335 /* Traits for string elements that should not be freed when an element
 336    is deleted.  */
 337
 338 struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
 339
 340 /* Traits for pairs of values, using the first to record empty and
 341    deleted slots.  */
 342
 343 template <typename T1, typename T2>
 344 struct pair_hash
 345 {
 346   typedef std::pair <typename T1::value_type,
 347                      typename T2::value_type> value_type;
 348   typedef std::pair <typename T1::compare_type,
 349                      typename T2::compare_type> compare_type;
 350
 351   static inline hashval_t hash (const value_type &);
 352   static inline bool equal (const value_type &, const compare_type &);
 353   static inline void remove (value_type &);
 354   static inline void mark_deleted (value_type &);
 355   static const bool empty_zero_p = T1::empty_zero_p;
 356   static inline void mark_empty (value_type &);
 357   static inline bool is_deleted (const value_type &);
 358   static inline bool is_empty (const value_type &);
 359 };
 360
 361 template <typename T1, typename T2>
 362 inline hashval_t
 363 pair_hash <T1, T2>::hash (const value_type &x)
 364 {
 365   return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second));
 366 }
 367
 368 template <typename T1, typename T2>
 369 inline bool
 370 pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
 371 {
 372   return T1::equal (x.first, y.first) && T2::equal (x.second, y.second);
 373 }
 374
 375 template <typename T1, typename T2>
 376 inline void
 377 pair_hash <T1, T2>::remove (value_type &x)
 378 {
 379   T1::remove (x.first);
 380   T2::remove (x.second);
 381 }
 382
 383 template <typename T1, typename T2>
 384 inline void
 385 pair_hash <T1, T2>::mark_deleted (value_type &x)
 386 {
 387   T1::mark_deleted (x.first);
 388 }
 389
 390 template <typename T1, typename T2>
 391 inline void
 392 pair_hash <T1, T2>::mark_empty (value_type &x)
 393 {
 394   T1::mark_empty (x.first);
 395 }
 396
 397 template <typename T1, typename T2>
 398 inline bool
 399 pair_hash <T1, T2>::is_deleted (const value_type &x)
 400 {
 401   return T1::is_deleted (x.first);
 402 }
 403
 404 template <typename T1, typename T2>
 405 inline bool
 406 pair_hash <T1, T2>::is_empty (const value_type &x)
 407 {
 408   return T1::is_empty (x.first);
 409 }
 410
 411 /* Base traits for vectors, providing just the hash and comparison
 412    functionality.  Type gives the corresponding traits for the element
 413    type.  */
 414
 415 template <typename Type>
 416 struct vec_hash_base
 417 {
 418   typedef vec<typename Type::value_type> value_type;
 419   typedef vec<typename Type::compare_type> compare_type;
 420
 421   static inline hashval_t hash (value_type);
 422   static inline bool equal (value_type, compare_type);
 423 };
 424
 425 template <typename Type>
 426 inline hashval_t
 427 vec_hash_base <Type>::hash (value_type x)
 428 {
 429   inchash::hash hstate;
 430   hstate.add_int (x.length ());
 431   for (auto &value : x)
 432     hstate.merge_hash (Type::hash (value));
 433   return hstate.end ();
 434 }
 435
 436 template <typename Type>
 437 inline bool
 438 vec_hash_base <Type>::equal (value_type x, compare_type y)
 439 {
 440   if (x.length () != y.length ())
 441     return false;
 442   for (unsigned int i = 0; i < x.length (); ++i)
 443     if (!Type::equal (x[i], y[i]))
 444       return false;
 445   return true;
 446 }
 447
 448 /* Traits for vectors whose contents should be freed normally.  */
 449
 450 template <typename Type>
 451 struct vec_free_hash_base : vec_hash_base <Type>
 452 {
 453   static void remove (typename vec_hash_base <Type>::value_type &);
 454 };
 455
 456 template <typename Type>
 457 void
 458 vec_free_hash_base <Type>
 459 ::remove (typename vec_hash_base <Type>::value_type &x)
 460 {
 461   for (auto &value : x)
 462     Type::remove (x);
 463   x.release ();
 464 }
 465
 466 template <typename T> struct default_hash_traits : T {};
 467
 468 template <typename T>
 469 struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
 470
 471 #endif