* config/i386/i386.h (TARGET_SUPPORTS_WIDE_INT): New define.
[official-gcc.git] / gcc / hash-map.h
blob4cca702a0e2f768a938a69017bcf5821a993c4a6
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;
118 static hashval_t hash (const hash_entry &e)
120 return Traits::hash (e.m_key);
123 static bool equal (const hash_entry &a, const Key &b)
125 return Traits::equal_keys (a.m_key, b);
128 static void remove (hash_entry &e) { Traits::remove (e); }
130 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
132 static bool is_deleted (const hash_entry &e)
134 return Traits::is_deleted (e);
137 static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
138 static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
140 static void ggc_mx (hash_entry &e)
142 gt_ggc_mx (e.m_key);
143 gt_ggc_mx (e.m_value);
146 static void pch_nx (hash_entry &e)
148 gt_pch_nx (e.m_key);
149 gt_pch_nx (e.m_value);
152 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
154 pch_nx_helper (e.m_key, op, c);
155 pch_nx_helper (e.m_value, op, c);
158 private:
159 template<typename T>
160 static void
161 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
163 gt_pch_nx (&x, op, cookie);
166 static void
167 pch_nx_helper (int, gt_pointer_operator, void *)
171 static void
172 pch_nx_helper (unsigned int, gt_pointer_operator, void *)
176 static void
177 pch_nx_helper (bool, gt_pointer_operator, void *)
181 template<typename T>
182 static void
183 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
185 op (&x, cookie);
189 public:
190 explicit hash_map (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
192 /* Create a hash_map in ggc memory. */
193 static hash_map *create_ggc (size_t size)
195 hash_map *map = ggc_alloc<hash_map> ();
196 new (map) hash_map (size, true);
197 return map;
200 /* If key k isn't already in the map add key k with value v to the map, and
201 return false. Otherwise set the value of the entry for key k to be v and
202 return true. */
204 bool put (const Key &k, const Value &v)
206 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
207 INSERT);
208 bool existed = !hash_entry::is_empty (*e);
209 if (!existed)
210 e->m_key = k;
212 e->m_value = v;
213 return existed;
216 /* if the passed in key is in the map return its value otherwise NULL. */
218 Value *get (const Key &k)
220 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
221 return Traits::is_empty (e) ? NULL : &e.m_value;
224 /* Return a reference to the value for the passed in key, creating the entry
225 if it doesn't already exist. If existed is not NULL then it is set to false
226 if the key was not previously in the map, and true otherwise. */
228 Value &get_or_insert (const Key &k, bool *existed = NULL)
230 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
231 INSERT);
232 bool ins = Traits::is_empty (*e);
233 if (ins)
234 e->m_key = k;
236 if (existed != NULL)
237 *existed = !ins;
239 return e->m_value;
242 void remove (const Key &k)
244 m_table.remove_elt_with_hash (k, Traits::hash (k));
247 /* Call the call back on each pair of key and value with the passed in
248 arg. */
250 template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
251 void traverse (Arg a) const
253 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
254 iter != m_table.end (); ++iter)
255 f ((*iter).m_key, (*iter).m_value, a);
258 template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
259 void traverse (Arg a) const
261 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
262 iter != m_table.end (); ++iter)
263 if (!f ((*iter).m_key, &(*iter).m_value, a))
264 break;
267 size_t elements () const { return m_table.elements (); }
269 class iterator
271 public:
272 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
273 m_iter (iter) {}
275 iterator &operator++ ()
277 ++m_iter;
278 return *this;
281 std::pair<Key, Value> operator* ()
283 hash_entry &e = *m_iter;
284 return std::pair<Key, Value> (e.m_key, e.m_value);
287 bool
288 operator != (const iterator &other) const
290 return m_iter != other.m_iter;
293 private:
294 typename hash_table<hash_entry>::iterator m_iter;
297 /* Standard iterator retrieval methods. */
299 iterator begin () const { return iterator (m_table.begin ()); }
300 iterator end () const { return iterator (m_table.end ()); }
302 private:
304 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
305 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
306 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
308 hash_table<hash_entry> m_table;
311 /* ggc marking routines. */
313 template<typename K, typename V, typename H>
314 static inline void
315 gt_ggc_mx (hash_map<K, V, H> *h)
317 gt_ggc_mx (&h->m_table);
320 template<typename K, typename V, typename H>
321 static inline void
322 gt_pch_nx (hash_map<K, V, H> *h)
324 gt_pch_nx (&h->m_table);
327 template<typename K, typename V, typename H>
328 static inline void
329 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
331 op (&h->m_table.m_entries, cookie);
334 #endif