PR sanitizer/65400
[official-gcc.git] / gcc / hash-map.h
blobe1dea91b54999b88f893aa77c790c708f45a1c8e
1 /* A type-safe hash map.
2 Copyright (C) 2014-2015 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_map_h
22 #define hash_map_h
24 #include <new>
25 #include <utility>
26 #include "hash-table.h"
28 /* implement default behavior for traits when types allow it. */
30 struct default_hashmap_traits
32 /* Hashes the passed in key. */
34 template<typename T>
35 static hashval_t
36 hash (T *p)
38 return uintptr_t(p) >> 3;
41 /* If the value converts to hashval_t just use it. */
43 template<typename T> static hashval_t hash (T v) { return v; }
45 /* Return true if the two keys passed as arguments are equal. */
47 template<typename T>
48 static bool
49 equal_keys (const T &a, const T &b)
51 return a == b;
54 /* Called to dispose of the key and value before marking the entry as
55 deleted. */
57 template<typename T> static void remove (T &v) { v.~T (); }
59 /* Mark the passed in entry as being deleted. */
61 template<typename T>
62 static void
63 mark_deleted (T &e)
65 mark_key_deleted (e.m_key);
68 /* Mark the passed in entry as being empty. */
70 template<typename T>
71 static void
72 mark_empty (T &e)
74 mark_key_empty (e.m_key);
77 /* Return true if the passed in entry is marked as deleted. */
79 template<typename T>
80 static bool
81 is_deleted (T &e)
83 return e.m_key == (void *)1;
86 /* Return true if the passed in entry is marked as empty. */
88 template<typename T> static bool is_empty (T &e) { return e.m_key == NULL; }
90 private:
91 template<typename T>
92 static void
93 mark_key_deleted (T *&k)
95 k = reinterpret_cast<T *> (1);
98 template<typename T>
99 static void
100 mark_key_empty (T *&k)
102 k = static_cast<T *> (0);
106 template<typename Key, typename Value,
107 typename Traits = default_hashmap_traits>
108 class GTY((user)) hash_map
110 struct hash_entry
112 Key m_key;
113 Value m_value;
115 typedef hash_entry value_type;
116 typedef Key compare_type;
117 typedef int store_values_directly;
119 static hashval_t hash (const hash_entry &e)
121 return Traits::hash (e.m_key);
124 static bool equal (const hash_entry &a, const Key &b)
126 return Traits::equal_keys (a.m_key, b);
129 static void remove (hash_entry &e) { Traits::remove (e); }
131 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
133 static bool is_deleted (const hash_entry &e)
135 return Traits::is_deleted (e);
138 static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
139 static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
141 static void ggc_mx (hash_entry &e)
143 gt_ggc_mx (e.m_key);
144 gt_ggc_mx (e.m_value);
147 static void pch_nx (hash_entry &e)
149 gt_pch_nx (e.m_key);
150 gt_pch_nx (e.m_value);
153 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
155 pch_nx_helper (e.m_key, op, c);
156 pch_nx_helper (e.m_value, op, c);
159 private:
160 template<typename T>
161 static void
162 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
164 gt_pch_nx (&x, op, cookie);
167 static void
168 pch_nx_helper (int, gt_pointer_operator, void *)
172 static void
173 pch_nx_helper (unsigned int, gt_pointer_operator, void *)
177 static void
178 pch_nx_helper (bool, gt_pointer_operator, void *)
182 template<typename T>
183 static void
184 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
186 op (&x, cookie);
190 public:
191 explicit hash_map (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
193 /* Create a hash_map in ggc memory. */
194 static hash_map *create_ggc (size_t size)
196 hash_map *map = ggc_alloc<hash_map> ();
197 new (map) hash_map (size, true);
198 return map;
201 /* If key k isn't already in the map add key k with value v to the map, and
202 return false. Otherwise set the value of the entry for key k to be v and
203 return true. */
205 bool put (const Key &k, const Value &v)
207 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
208 INSERT);
209 bool existed = !hash_entry::is_empty (*e);
210 if (!existed)
211 e->m_key = k;
213 e->m_value = v;
214 return existed;
217 /* if the passed in key is in the map return its value otherwise NULL. */
219 Value *get (const Key &k)
221 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
222 return Traits::is_empty (e) ? NULL : &e.m_value;
225 /* Return a reference to the value for the passed in key, creating the entry
226 if it doesn't already exist. If existed is not NULL then it is set to false
227 if the key was not previously in the map, and true otherwise. */
229 Value &get_or_insert (const Key &k, bool *existed = NULL)
231 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
232 INSERT);
233 bool ins = Traits::is_empty (*e);
234 if (ins)
235 e->m_key = k;
237 if (existed != NULL)
238 *existed = !ins;
240 return e->m_value;
243 void remove (const Key &k)
245 m_table.remove_elt_with_hash (k, Traits::hash (k));
248 /* Call the call back on each pair of key and value with the passed in
249 arg. */
251 template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
252 void traverse (Arg a) const
254 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
255 iter != m_table.end (); ++iter)
256 f ((*iter).m_key, (*iter).m_value, a);
259 template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
260 void traverse (Arg a) const
262 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
263 iter != m_table.end (); ++iter)
264 if (!f ((*iter).m_key, &(*iter).m_value, a))
265 break;
268 size_t elements () const { return m_table.elements (); }
270 class iterator
272 public:
273 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
274 m_iter (iter) {}
276 iterator &operator++ ()
278 ++m_iter;
279 return *this;
282 std::pair<Key, Value> operator* ()
284 hash_entry &e = *m_iter;
285 return std::pair<Key, Value> (e.m_key, e.m_value);
288 bool
289 operator != (const iterator &other) const
291 return m_iter != other.m_iter;
294 private:
295 typename hash_table<hash_entry>::iterator m_iter;
298 /* Standard iterator retrieval methods. */
300 iterator begin () const { return iterator (m_table.begin ()); }
301 iterator end () const { return iterator (m_table.end ()); }
303 private:
305 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
306 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
307 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
309 hash_table<hash_entry> m_table;
312 /* ggc marking routines. */
314 template<typename K, typename V, typename H>
315 static inline void
316 gt_ggc_mx (hash_map<K, V, H> *h)
318 gt_ggc_mx (&h->m_table);
321 template<typename K, typename V, typename H>
322 static inline void
323 gt_pch_nx (hash_map<K, V, H> *h)
325 gt_pch_nx (&h->m_table);
328 template<typename K, typename V, typename H>
329 static inline void
330 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
332 op (&h->m_table.m_entries, cookie);
335 #endif