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 /* Hasher for entry in gc memory.  */
 125
 126 template<typename T>
 127 struct ggc_hasher
 128 {
 129   typedef T value_type;
 130   typedef T compare_type;
 131
 132   static void remove (T &) {}
 133
 134   static void
 135   ggc_mx (T &p)
 136   {
 137     extern void gt_ggc_mx (T &);
 138     gt_ggc_mx (p);
 139   }
 140
 141   static void
 142   pch_nx (T &p)
 143   {
 144     extern void gt_pch_nx (T &);
 145     gt_pch_nx (p);
 146   }
 147
 148   static void
 149   pch_nx (T &p, gt_pointer_operator op, void *cookie)
 150   {
 151     op (&p, cookie);
 152   }
 153 };
 154
 155 /* Hasher for cache entry in gc memory.  */
 156
 157 template<typename T>
 158 struct ggc_cache_hasher : ggc_hasher<T>
 159 {
 160   /* Entries are weakly held because this is for caches.  */
 161   static void ggc_mx (T &) {}
 162
 163   static int
 164   keep_cache_entry (T &e)
 165   {
 166     return ggc_marked_p (e) ? -1 : 0;
 167   }
 168 };
 169
 170 /* Traits for pointer elements that should not be freed when an element
 171    is deleted.  */
 172
 173 template <typename T>
 174 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T> {};
 175
 176 #endif