gcc/hash-traits.h

   1 /* Traits for hashable types.
   2    Copyright (C) 2014-2015 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
  42 /* Helpful type for a no-op remove.  */
  43
  44 template <typename Type>
  45 struct typed_noop_remove
  46 {
  47   static inline void remove (Type &);
  48 };
  49
  50
  51 /* Remove doing nothing.  */
  52
  53 template <typename Type>
  54 inline void
  55 typed_noop_remove <Type>::remove (Type &)
  56 {
  57 }
  58
  59
  60 /* Hasher for integer type Type in which Empty is a spare value that can be
  61    used to mark empty slots.  If Deleted != Empty then Deleted is another
  62    spare value that can be used for deleted slots; if Deleted == Empty then
  63    hash table entries cannot be deleted.  */
  64
  65 template <typename Type, Type Empty, Type Deleted = Empty>
  66 struct int_hash : typed_noop_remove <Type>
  67 {
  68   typedef Type value_type;
  69   typedef Type compare_type;
  70
  71   static inline hashval_t hash (value_type);
  72   static inline bool equal (value_type existing, value_type candidate);
  73   static inline void mark_deleted (Type &);
  74   static inline void mark_empty (Type &);
  75   static inline bool is_deleted (Type);
  76   static inline bool is_empty (Type);
  77 };
  78
  79 template <typename Type, Type Empty, Type Deleted>
  80 inline hashval_t
  81 int_hash <Type, Empty, Deleted>::hash (value_type x)
  82 {
  83   return x;
  84 }
  85
  86 template <typename Type, Type Empty, Type Deleted>
  87 inline bool
  88 int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
  89 {
  90   return x == y;
  91 }
  92
  93 template <typename Type, Type Empty, Type Deleted>
  94 inline void
  95 int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
  96 {
  97   gcc_assert (Empty != Deleted);
  98   x = Deleted;
  99 }
 100
 101 template <typename Type, Type Empty, Type Deleted>
 102 inline void
 103 int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
 104 {
 105   x = Empty;
 106 }
 107
 108 template <typename Type, Type Empty, Type Deleted>
 109 inline bool
 110 int_hash <Type, Empty, Deleted>::is_deleted (Type x)
 111 {
 112   return Empty != Deleted && x == Deleted;
 113 }
 114
 115 template <typename Type, Type Empty, Type Deleted>
 116 inline bool
 117 int_hash <Type, Empty, Deleted>::is_empty (Type x)
 118 {
 119   return x == Empty;
 120 }
 121
 122 /* Pointer hasher based on pointer equality.  Other types of pointer hash
 123    can inherit this and override the hash and equal functions with some
 124    other form of equality (such as string equality).  */
 125
 126 template <typename Type>
 127 struct pointer_hash
 128 {
 129   typedef Type *value_type;
 130   typedef Type *compare_type;
 131
 132   static inline hashval_t hash (const value_type &);
 133   static inline bool equal (const value_type &existing,
 134                             const compare_type &candidate);
 135   static inline void mark_deleted (Type *&);
 136   static inline void mark_empty (Type *&);
 137   static inline bool is_deleted (Type *);
 138   static inline bool is_empty (Type *);
 139 };
 140
 141 template <typename Type>
 142 inline hashval_t
 143 pointer_hash <Type>::hash (const value_type &candidate)
 144 {
 145   /* This is a really poor hash function, but it is what the current code uses,
 146      so I am reusing it to avoid an additional axis in testing.  */
 147   return (hashval_t) ((intptr_t)candidate >> 3);
 148 }
 149
 150 template <typename Type>
 151 inline bool
 152 pointer_hash <Type>::equal (const value_type &existing,
 153                            const compare_type &candidate)
 154 {
 155   return existing == candidate;
 156 }
 157
 158 template <typename Type>
 159 inline void
 160 pointer_hash <Type>::mark_deleted (Type *&e)
 161 {
 162   e = reinterpret_cast<Type *> (1);
 163 }
 164
 165 template <typename Type>
 166 inline void
 167 pointer_hash <Type>::mark_empty (Type *&e)
 168 {
 169   e = NULL;
 170 }
 171
 172 template <typename Type>
 173 inline bool
 174 pointer_hash <Type>::is_deleted (Type *e)
 175 {
 176   return e == reinterpret_cast<Type *> (1);
 177 }
 178
 179 template <typename Type>
 180 inline bool
 181 pointer_hash <Type>::is_empty (Type *e)
 182 {
 183   return e == NULL;
 184 }
 185
 186 /* Hasher for "const char *" strings, using string rather than pointer
 187    equality.  */
 188
 189 struct string_hash : pointer_hash <const char>
 190 {
 191   static inline hashval_t hash (const char *);
 192   static inline bool equal (const char *, const char *);
 193 };
 194
 195 inline hashval_t
 196 string_hash::hash (const char *id)
 197 {
 198   return htab_hash_string (id);
 199 }
 200
 201 inline bool
 202 string_hash::equal (const char *id1, const char *id2)
 203 {
 204   return strcmp (id1, id2) == 0;
 205 }
 206
 207 /* Remover and marker for entries in gc memory.  */
 208
 209 template<typename T>
 210 struct ggc_remove
 211 {
 212   static void remove (T &) {}
 213
 214   static void
 215   ggc_mx (T &p)
 216   {
 217     extern void gt_ggc_mx (T &);
 218     gt_ggc_mx (p);
 219   }
 220
 221   static void
 222   pch_nx (T &p)
 223   {
 224     extern void gt_pch_nx (T &);
 225     gt_pch_nx (p);
 226   }
 227
 228   static void
 229   pch_nx (T &p, gt_pointer_operator op, void *cookie)
 230   {
 231     op (&p, cookie);
 232   }
 233 };
 234
 235 /* Remover and marker for "cache" entries in gc memory.  These entries can
 236    be deleted if there are no non-cache references to the data.  */
 237
 238 template<typename T>
 239 struct ggc_cache_remove : ggc_remove<T>
 240 {
 241   /* Entries are weakly held because this is for caches.  */
 242   static void ggc_mx (T &) {}
 243
 244   static int
 245   keep_cache_entry (T &e)
 246   {
 247     return ggc_marked_p (e) ? -1 : 0;
 248   }
 249 };
 250
 251 /* Traits for pointer elements that should not be freed when an element
 252    is deleted.  */
 253
 254 template <typename T>
 255 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
 256
 257 /* Traits for pointer elements that should be freed via free() when an
 258    element is deleted.  */
 259
 260 template <typename T>
 261 struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
 262
 263 /* Traits for elements that point to gc memory.  The pointed-to data
 264    must be kept across collections.  */
 265
 266 template <typename T>
 267 struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
 268
 269 /* Traits for elements that point to gc memory.  The elements don't
 270    in themselves keep the pointed-to data alive and they can be deleted
 271    if the pointed-to data is going to be collected.  */
 272
 273 template <typename T>
 274 struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
 275
 276 /* Traits for string elements that should not be freed when an element
 277    is deleted.  */
 278
 279 struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
 280
 281 template <typename T> struct default_hash_traits : T {};
 282
 283 template <typename T>
 284 struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
 285
 286 #endif