gcc/hash-set.h

   1 /* A type-safe hash set.
   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
  21 #ifndef hash_set_h
  22 #define hash_set_h
  23
  24 /* implement default behavior for traits when types allow it.  */
  25
  26 struct default_hashset_traits
  27 {
  28   /* Hashes the passed in key.  */
  29
  30   template<typename T>
  31   static hashval_t
  32   hash (T *p)
  33     {
  34       return uintptr_t (p) >> 3;
  35     }
  36
  37   template<typename T> static hashval_t hash(const T &v) { return v; }
  38
  39   /* Return true if the two keys passed as arguments are equal.  */
  40
  41   template<typename T>
  42   static bool
  43   equal (const T &a, const T &b)
  44     {
  45       return a == b;
  46     }
  47
  48   /* Called to dispose of the key before marking the entry as deleted.  */
  49
  50   template<typename T> static void remove (T &v) { v.~T (); }
  51
  52   /* Mark the passed in entry as being deleted.  */
  53
  54   template<typename T>
  55   static void
  56   mark_deleted (T *&e)
  57     {
  58       e = reinterpret_cast<void *> (1);
  59     }
  60
  61   /* Mark the passed in entry as being empty.  */
  62
  63   template<typename T>
  64   static void
  65   mark_empty (T *&e)
  66     {
  67       e = NULL;
  68     }
  69
  70   /* Return true if the passed in entry is marked as deleted.  */
  71
  72   template<typename T>
  73   static bool
  74   is_deleted (T *e)
  75     {
  76       return e == reinterpret_cast<void *> (1);
  77     }
  78
  79   /* Return true if the passed in entry is marked as empty.  */
  80
  81   template<typename T> static bool is_empty (T *e) { return e == NULL; }
  82
  83   /* ggc walking routine, mark all objects refered to by this one.  */
  84
  85   template<typename T>
  86   static void
  87   ggc_mx (T &x)
  88     {
  89       extern void gt_ggc_mx (T &);
  90       gt_ggc_mx (x);
  91     }
  92
  93   /* pch walking routine, note all objects refered to by this element.  */
  94
  95   template<typename T>
  96   static void
  97   pch_nx (T &x)
  98     {
  99       extern void gt_pch_nx (T &);
 100       gt_pch_nx (x);
 101     }
 102 };
 103
 104 template<typename Key, typename Traits = default_hashset_traits>
 105 class hash_set
 106 {
 107   struct hash_entry
 108   {
 109     Key m_key;
 110
 111     typedef hash_entry value_type;
 112     typedef Key compare_type;
 113
 114     static hashval_t hash (const hash_entry &e)
 115       {
 116         return Traits::hash (e.m_key);
 117       }
 118
 119     static bool equal (const hash_entry &a, const Key &b)
 120         {
 121           return Traits::equal (a.m_key, b);
 122         }
 123
 124     static void remove (hash_entry &e) { Traits::remove (e.m_key); }
 125
 126     static void
 127     mark_deleted (hash_entry &e)
 128       {
 129         Traits::mark_deleted (e.m_key);
 130       }
 131
 132     static bool is_deleted (const hash_entry &e)
 133       {
 134         return Traits::is_deleted (e.m_key);
 135       }
 136
 137     static void
 138     mark_empty (hash_entry &e)
 139       {
 140         Traits::mark_empty (e.m_key);
 141       }
 142
 143     static bool
 144     is_empty (const hash_entry &e)
 145       {
 146         return Traits::is_empty (e.m_key);
 147       }
 148
 149     static void ggc_mx (hash_entry &e)
 150       {
 151         Traits::ggc_mx (e.m_key);
 152       }
 153
 154     static void pch_nx (hash_entry &e)
 155       {
 156         Traits::pch_nx (e.m_key);
 157       }
 158
 159     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
 160       {
 161         pch_nx_helper (e.m_key, op, c);
 162       }
 163
 164   private:
 165     template<typename T>
 166     static void
 167       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
 168         {
 169           gt_pch_nx (&x, op, cookie);
 170         }
 171
 172     template<typename T>
 173       static void
 174       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 175         {
 176           op (&x, cookie);
 177         }
 178   };
 179
 180 public:
 181   explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO)
 182     : m_table (n, ggc, true, HASH_SET_ORIGIN PASS_MEM_STAT) {}
 183
 184   /* Create a hash_set in gc memory with space for at least n elements.  */
 185
 186   static hash_set *
 187     create_ggc (size_t n)
 188       {
 189         hash_set *set = ggc_alloc<hash_set> ();
 190         new (set) hash_set (n, true);
 191         return set;
 192       }
 193
 194   /* If key k isn't already in the map add it to the map, and
 195      return false.  Otherwise return true.  */
 196
 197   bool add (const Key &k)
 198     {
 199       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 200                                                    INSERT);
 201       bool existed = !hash_entry::is_empty (*e);
 202       if (!existed)
 203         e->m_key = k;
 204
 205       return existed;
 206     }
 207
 208   /* if the passed in key is in the map return its value otherwise NULL.  */
 209
 210   bool contains (const Key &k)
 211     {
 212       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 213       return !Traits::is_empty (e.m_key);
 214     }
 215
 216   /* Call the call back on each pair of key and value with the passed in
 217      arg.  */
 218
 219   template<typename Arg, bool (*f)(const Key &, Arg)>
 220   void traverse (Arg a) const
 221     {
 222       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 223            iter != m_table.end (); ++iter)
 224         f ((*iter).m_key, a);
 225     }
 226
 227   /* Return the number of elements in the set.  */
 228
 229   size_t elements () const { return m_table.elements (); }
 230
 231 private:
 232
 233   template<typename T, typename U> friend void gt_ggc_mx (hash_set<T, U> *);
 234   template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *);
 235       template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, gt_pointer_operator, void *);
 236
 237   hash_table<hash_entry> m_table;
 238 };
 239
 240 /* ggc marking routines.  */
 241
 242 template<typename K, typename H>
 243 static inline void
 244 gt_ggc_mx (hash_set<K, H> *h)
 245 {
 246   gt_ggc_mx (&h->m_table);
 247 }
 248
 249 template<typename K, typename H>
 250 static inline void
 251 gt_pch_nx (hash_set<K, H> *h)
 252 {
 253   gt_pch_nx (&h->m_table);
 254 }
 255
 256 template<typename K, typename H>
 257 static inline void
 258 gt_pch_nx (hash_set<K, H> *h, gt_pointer_operator op, void *cookie)
 259 {
 260   op (&h->m_table.m_entries, cookie);
 261 }
 262
 263 #endif