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