gcc/hash-traits.h

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