Daily bump.
[official-gcc.git] / gcc / hash-set.h
blob0a500cb441ab3fe3565442bba0655259bfffa418
1 /* A type-safe hash set.
2 Copyright (C) 2014 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
21 #ifndef hash_set_h
22 #define hash_set_h
24 #include "hash-table.h"
26 /* implement default behavior for traits when types allow it. */
28 struct default_hashset_traits
30 /* Hashes the passed in key. */
32 template<typename T>
33 static hashval_t
34 hash (T *p)
36 return uintptr_t(p) >> 3;
39 template<typename T> static hashval_t hash(const T &v) { return v; }
41 /* Return true if the two keys passed as arguments are equal. */
43 template<typename T>
44 static bool
45 equal (const T &a, const T &b)
47 return a == b;
50 /* Called to dispose of the key before marking the entry as deleted. */
52 template<typename T> static void remove (T &v) { v.~T (); }
54 /* Mark the passed in entry as being deleted. */
56 template<typename T>
57 static void
58 mark_deleted (T *&e)
60 e = reinterpret_cast<void *> (1);
63 /* Mark the passed in entry as being empty. */
65 template<typename T>
66 static void
67 mark_empty (T *&e)
69 e = NULL;
72 /* Return true if the passed in entry is marked as deleted. */
74 template<typename T>
75 static bool
76 is_deleted (T *e)
78 return e == reinterpret_cast<void *> (1);
81 /* Return true if the passed in entry is marked as empty. */
83 template<typename T> static bool is_empty (T *e) { return e == NULL; }
85 /* ggc walking routine, mark all objects refered to by this one. */
87 template<typename T>
88 static void
89 ggc_mx (T &x)
91 extern void gt_ggc_mx (T &);
92 gt_ggc_mx (x);
95 /* pch walking routine, note all objects refered to by this element. */
97 template<typename T>
98 static void
99 pch_nx (T &x)
101 extern void gt_pch_nx (T &);
102 gt_pch_nx (x);
106 template<typename Key, typename Traits = default_hashset_traits>
107 class hash_set
109 struct hash_entry
111 Key m_key;
113 typedef hash_entry value_type;
114 typedef Key compare_type;
115 typedef int store_values_directly;
117 static hashval_t hash (const hash_entry &e)
119 return Traits::hash (e.m_key);
122 static bool equal (const hash_entry &a, const Key &b)
124 return Traits::equal (a.m_key, b);
127 static void remove (hash_entry &e) { Traits::remove (e.m_key); }
129 static void
130 mark_deleted (hash_entry &e)
132 Traits::mark_deleted (e.m_key);
135 static bool is_deleted (const hash_entry &e)
137 return Traits::is_deleted (e.m_key);
140 static void
141 mark_empty (hash_entry &e)
143 Traits::mark_empty (e.m_key);
146 static bool
147 is_empty (const hash_entry &e)
149 return Traits::is_empty (e.m_key);
152 static void ggc_mx (hash_entry &e)
154 Traits::ggc_mx (e.m_key);
157 static void pch_nx (hash_entry &e)
159 Traits::pch_nx (e.m_key);
162 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
164 pch_nx_helper (e.m_key, op, c);
167 private:
168 template<typename T>
169 static void
170 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
172 gt_pch_nx (&x, op, cookie);
175 template<typename T>
176 static void
177 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
179 op (&x, cookie);
183 public:
184 explicit hash_set (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
186 /* Create a hash_set in gc memory with space for at least n elements. */
188 static hash_set *
189 create_ggc (size_t n)
191 hash_set *set = ggc_alloc<hash_set> ();
192 new (set) hash_set (n, true);
193 return set;
196 /* If key k isn't already in the map add it to the map, and
197 return false. Otherwise return true. */
199 bool add (const Key &k)
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;
207 return existed;
210 /* if the passed in key is in the map return its value otherwise NULL. */
212 bool contains (const Key &k)
214 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
215 return !Traits::is_empty (e.m_key);
218 /* Call the call back on each pair of key and value with the passed in
219 arg. */
221 template<typename Arg, bool (*f)(const Key &, Arg)>
222 void traverse (Arg a) const
224 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
225 iter != m_table.end (); ++iter)
226 f ((*iter).m_key, a);
229 /* Return the number of elements in the set. */
231 size_t elements () const { return m_table.elements (); }
233 private:
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 *);
239 hash_table<hash_entry> m_table;
242 /* ggc marking routines. */
244 template<typename K, typename H>
245 static inline void
246 gt_ggc_mx (hash_set<K, H> *h)
248 gt_ggc_mx (&h->m_table);
251 template<typename K, typename H>
252 static inline void
253 gt_pch_nx (hash_set<K, H> *h)
255 gt_pch_nx (&h->m_table);
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)
262 op (&h->m_table.m_entries, cookie);
265 #endif