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 /* Pointer hasher based on pointer equality.  Other types of pointer hash
  61    can inherit this and override the hash and equal functions with some
  62    other form of equality (such as string equality).  */
  63
  64 template <typename Type>
  65 struct pointer_hash
  66 {
  67   typedef Type *value_type;
  68   typedef Type *compare_type;
  69
  70   static inline hashval_t hash (const value_type &);
  71   static inline bool equal (const value_type &existing,
  72                             const compare_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>
  80 inline hashval_t
  81 pointer_hash <Type>::hash (const value_type &candidate)
  82 {
  83   /* This is a really poor hash function, but it is what the current code uses,
  84      so I am reusing it to avoid an additional axis in testing.  */
  85   return (hashval_t) ((intptr_t)candidate >> 3);
  86 }
  87
  88 template <typename Type>
  89 inline bool
  90 pointer_hash <Type>::equal (const value_type &existing,
  91                            const compare_type &candidate)
  92 {
  93   return existing == candidate;
  94 }
  95
  96 template <typename Type>
  97 inline void
  98 pointer_hash <Type>::mark_deleted (Type *&e)
  99 {
 100   e = reinterpret_cast<Type *> (1);
 101 }
 102
 103 template <typename Type>
 104 inline void
 105 pointer_hash <Type>::mark_empty (Type *&e)
 106 {
 107   e = NULL;
 108 }
 109
 110 template <typename Type>
 111 inline bool
 112 pointer_hash <Type>::is_deleted (Type *e)
 113 {
 114   return e == reinterpret_cast<Type *> (1);
 115 }
 116
 117 template <typename Type>
 118 inline bool
 119 pointer_hash <Type>::is_empty (Type *e)
 120 {
 121   return e == NULL;
 122 }
 123
 124 /* Hasher for "const char *" strings, using string rather than pointer
 125    equality.  */
 126
 127 struct string_hash : pointer_hash <const char>
 128 {
 129   static inline hashval_t hash (const char *);
 130   static inline bool equal (const char *, const char *);
 131 };
 132
 133 inline hashval_t
 134 string_hash::hash (const char *id)
 135 {
 136   return htab_hash_string (id);
 137 }
 138
 139 inline bool
 140 string_hash::equal (const char *id1, const char *id2)
 141 {
 142   return strcmp (id1, id2) == 0;
 143 }
 144
 145 /* Remover and marker for entries in gc memory.  */
 146
 147 template<typename T>
 148 struct ggc_remove
 149 {
 150   static void remove (T &) {}
 151
 152   static void
 153   ggc_mx (T &p)
 154   {
 155     extern void gt_ggc_mx (T &);
 156     gt_ggc_mx (p);
 157   }
 158
 159   static void
 160   pch_nx (T &p)
 161   {
 162     extern void gt_pch_nx (T &);
 163     gt_pch_nx (p);
 164   }
 165
 166   static void
 167   pch_nx (T &p, gt_pointer_operator op, void *cookie)
 168   {
 169     op (&p, cookie);
 170   }
 171 };
 172
 173 /* Remover and marker for "cache" entries in gc memory.  These entries can
 174    be deleted if there are no non-cache references to the data.  */
 175
 176 template<typename T>
 177 struct ggc_cache_remove : ggc_remove<T>
 178 {
 179   /* Entries are weakly held because this is for caches.  */
 180   static void ggc_mx (T &) {}
 181
 182   static int
 183   keep_cache_entry (T &e)
 184   {
 185     return ggc_marked_p (e) ? -1 : 0;
 186   }
 187 };
 188
 189 /* Traits for pointer elements that should not be freed when an element
 190    is deleted.  */
 191
 192 template <typename T>
 193 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
 194
 195 /* Traits for pointer elements that should be freed via free() when an
 196    element is deleted.  */
 197
 198 template <typename T>
 199 struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
 200
 201 /* Traits for elements that point to gc memory.  The pointed-to data
 202    must be kept across collections.  */
 203
 204 template <typename T>
 205 struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
 206
 207 /* Traits for elements that point to gc memory.  The elements don't
 208    in themselves keep the pointed-to data alive and they can be deleted
 209    if the pointed-to data is going to be collected.  */
 210
 211 template <typename T>
 212 struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
 213
 214 /* Traits for string elements that should not be freed when an element
 215    is deleted.  */
 216
 217 struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
 218
 219 template <typename T> struct default_hash_traits;
 220
 221 template <typename T>
 222 struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
 223
 224 #endif