gcc/hash-set.h

   1 /* A type-safe hash set.
   2    Copyright (C) 2014 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     typedef int store_values_directly;
 116
 117     static hashval_t hash (const hash_entry &e)
 118       {
 119         return Traits::hash (e.m_key);
 120       }
 121
 122     static bool equal (const hash_entry &a, const Key &b)
 123         {
 124           return Traits::equal (a.m_key, b);
 125         }
 126
 127     static void remove (hash_entry &e) { Traits::remove (e.m_key); }
 128
 129     static void
 130     mark_deleted (hash_entry &e)
 131       {
 132         Traits::mark_deleted (e.m_key);
 133       }
 134
 135     static bool is_deleted (const hash_entry &e)
 136       {
 137         return Traits::is_deleted (e.m_key);
 138       }
 139
 140     static void
 141     mark_empty (hash_entry &e)
 142       {
 143         Traits::mark_empty (e.m_key);
 144       }
 145
 146     static bool
 147     is_empty (const hash_entry &e)
 148       {
 149         return Traits::is_empty (e.m_key);
 150       }
 151
 152     static void ggc_mx (hash_entry &e)
 153       {
 154         Traits::ggc_mx (e.m_key);
 155       }
 156
 157     static void pch_nx (hash_entry &e)
 158       {
 159         Traits::pch_nx (e.m_key);
 160       }
 161
 162     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
 163       {
 164         pch_nx_helper (e.m_key, op, c);
 165       }
 166
 167   private:
 168     template<typename T>
 169     static void
 170       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
 171         {
 172           gt_pch_nx (&x, op, cookie);
 173         }
 174
 175     template<typename T>
 176       static void
 177       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 178         {
 179           op (&x, cookie);
 180         }
 181   };
 182
 183 public:
 184   explicit hash_set (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
 185
 186   /* Create a hash_set in gc memory with space for at least n elements.  */
 187
 188   static hash_set *
 189     create_ggc (size_t n)
 190       {
 191         hash_set *set = ggc_alloc<hash_set> ();
 192         new (set) hash_set (n, true);
 193         return set;
 194       }
 195
 196   /* If key k isn't already in the map add it to the map, and
 197      return false.  Otherwise return true.  */
 198
 199   bool add (const Key &k)
 200     {
 201       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 202                                                    INSERT);
 203       bool existed = !hash_entry::is_empty (*e);
 204       if (!existed)
 205         e->m_key = k;
 206
 207       return existed;
 208     }
 209
 210   /* if the passed in key is in the map return its value otherwise NULL.  */
 211
 212   bool contains (const Key &k)
 213     {
 214       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 215       return !Traits::is_empty (e.m_key);
 216     }
 217
 218   /* Call the call back on each pair of key and value with the passed in
 219      arg.  */
 220
 221   template<typename Arg, bool (*f)(const Key &, Arg)>
 222   void traverse (Arg a) const
 223     {
 224       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 225            iter != m_table.end (); ++iter)
 226         f ((*iter).m_key, a);
 227     }
 228
 229   /* Return the number of elements in the set.  */
 230
 231   size_t elements () const { return m_table.elements (); }
 232
 233 private:
 234
 235   template<typename T, typename U> friend void gt_ggc_mx (hash_set<T, U> *);
 236   template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *);
 237       template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, gt_pointer_operator, void *);
 238
 239   hash_table<hash_entry> m_table;
 240 };
 241
 242 /* ggc marking routines.  */
 243
 244 template<typename K, typename H>
 245 static inline void
 246 gt_ggc_mx (hash_set<K, H> *h)
 247 {
 248   gt_ggc_mx (&h->m_table);
 249 }
 250
 251 template<typename K, typename H>
 252 static inline void
 253 gt_pch_nx (hash_set<K, H> *h)
 254 {
 255   gt_pch_nx (&h->m_table);
 256 }
 257
 258 template<typename K, typename H>
 259 static inline void
 260 gt_pch_nx (hash_set<K, H> *h, gt_pointer_operator op, void *cookie)
 261 {
 262   op (&h->m_table.m_entries, cookie);
 263 }
 264
 265 #endif