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 *p);
  48 };
  49
  50
  51 /* Remove doing nothing.  */
  52
  53 template <typename Type>
  54 inline void
  55 typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED)
  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 /* Remover and marker for entries in gc memory.  */
 125
 126 template<typename T>
 127 struct ggc_remove
 128 {
 129   static void remove (T &) {}
 130
 131   static void
 132   ggc_mx (T &p)
 133   {
 134     extern void gt_ggc_mx (T &);
 135     gt_ggc_mx (p);
 136   }
 137
 138   static void
 139   pch_nx (T &p)
 140   {
 141     extern void gt_pch_nx (T &);
 142     gt_pch_nx (p);
 143   }
 144
 145   static void
 146   pch_nx (T &p, gt_pointer_operator op, void *cookie)
 147   {
 148     op (&p, cookie);
 149   }
 150 };
 151
 152 /* Remover and marker for "cache" entries in gc memory.  These entries can
 153    be deleted if there are no non-cache references to the data.  */
 154
 155 template<typename T>
 156 struct ggc_cache_remove : ggc_remove<T>
 157 {
 158   /* Entries are weakly held because this is for caches.  */
 159   static void ggc_mx (T &) {}
 160
 161   static int
 162   keep_cache_entry (T &e)
 163   {
 164     return ggc_marked_p (e) ? -1 : 0;
 165   }
 166 };
 167
 168 /* Traits for pointer elements that should not be freed when an element
 169    is deleted.  */
 170
 171 template <typename T>
 172 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T> {};
 173
 174 /* Traits for pointer elements that should be freed via free() when an
 175    element is deleted.  */
 176
 177 template <typename T>
 178 struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
 179
 180 /* Traits for elements that point to gc memory.  The pointed-to data
 181    must be kept across collections.  */
 182
 183 template <typename T>
 184 struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
 185
 186 /* Traits for elements that point to gc memory.  The elements don't
 187    in themselves keep the pointed-to data alive and they can be deleted
 188    if the pointed-to data is going to be collected.  */
 189
 190 template <typename T>
 191 struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
 192
 193 #endif