gcc/hash-traits.h

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