Daily bump.
[official-gcc.git] / gcc / hash-map.h
blob59794eb10428abdfa81cc80144e9251bda635c6e
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 template<typename KeyId, typename Value,
25 typename Traits>
26 class GTY((user)) hash_map
28 typedef typename Traits::key_type Key;
29 struct hash_entry
31 Key m_key;
32 Value m_value;
34 typedef hash_entry value_type;
35 typedef Key compare_type;
37 static hashval_t hash (const hash_entry &e)
39 return Traits::hash (e.m_key);
42 static bool equal (const hash_entry &a, const Key &b)
44 return Traits::equal_keys (a.m_key, b);
47 static void remove (hash_entry &e) { Traits::remove (e); }
49 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
51 static bool is_deleted (const hash_entry &e)
53 return Traits::is_deleted (e);
56 static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
57 static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
59 static void ggc_mx (hash_entry &e)
61 gt_ggc_mx (e.m_key);
62 gt_ggc_mx (e.m_value);
65 static void pch_nx (hash_entry &e)
67 gt_pch_nx (e.m_key);
68 gt_pch_nx (e.m_value);
71 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
73 pch_nx_helper (e.m_key, op, c);
74 pch_nx_helper (e.m_value, op, c);
77 private:
78 template<typename T>
79 static void
80 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
82 gt_pch_nx (&x, op, cookie);
85 static void
86 pch_nx_helper (int, gt_pointer_operator, void *)
90 static void
91 pch_nx_helper (unsigned int, gt_pointer_operator, void *)
95 static void
96 pch_nx_helper (bool, gt_pointer_operator, void *)
100 template<typename T>
101 static void
102 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
104 op (&x, cookie);
108 public:
109 explicit hash_map (size_t n = 13, bool ggc = false,
110 bool gather_mem_stats = true CXX_MEM_STAT_INFO)
111 : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {}
113 /* Create a hash_map in ggc memory. */
114 static hash_map *create_ggc (size_t size, bool gather_mem_stats = true
115 CXX_MEM_STAT_INFO)
117 hash_map *map = ggc_alloc<hash_map> ();
118 new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT);
119 return map;
122 /* If key k isn't already in the map add key k with value v to the map, and
123 return false. Otherwise set the value of the entry for key k to be v and
124 return true. */
126 bool put (const Key &k, const Value &v)
128 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
129 INSERT);
130 bool existed = !hash_entry::is_empty (*e);
131 if (!existed)
132 e->m_key = k;
134 e->m_value = v;
135 return existed;
138 /* if the passed in key is in the map return its value otherwise NULL. */
140 Value *get (const Key &k)
142 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
143 return Traits::is_empty (e) ? NULL : &e.m_value;
146 /* Return a reference to the value for the passed in key, creating the entry
147 if it doesn't already exist. If existed is not NULL then it is set to false
148 if the key was not previously in the map, and true otherwise. */
150 Value &get_or_insert (const Key &k, bool *existed = NULL)
152 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
153 INSERT);
154 bool ins = Traits::is_empty (*e);
155 if (ins)
156 e->m_key = k;
158 if (existed != NULL)
159 *existed = !ins;
161 return e->m_value;
164 void remove (const Key &k)
166 m_table.remove_elt_with_hash (k, Traits::hash (k));
169 /* Call the call back on each pair of key and value with the passed in
170 arg. */
172 template<typename Arg, bool (*f)(const typename Traits::key_type &,
173 const Value &, Arg)>
174 void traverse (Arg a) const
176 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
177 iter != m_table.end (); ++iter)
178 f ((*iter).m_key, (*iter).m_value, a);
181 template<typename Arg, bool (*f)(const typename Traits::key_type &,
182 Value *, Arg)>
183 void traverse (Arg a) const
185 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
186 iter != m_table.end (); ++iter)
187 if (!f ((*iter).m_key, &(*iter).m_value, a))
188 break;
191 size_t elements () const { return m_table.elements (); }
193 class iterator
195 public:
196 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
197 m_iter (iter) {}
199 iterator &operator++ ()
201 ++m_iter;
202 return *this;
205 std::pair<Key, Value> operator* ()
207 hash_entry &e = *m_iter;
208 return std::pair<Key, Value> (e.m_key, e.m_value);
211 bool
212 operator != (const iterator &other) const
214 return m_iter != other.m_iter;
217 private:
218 typename hash_table<hash_entry>::iterator m_iter;
221 /* Standard iterator retrieval methods. */
223 iterator begin () const { return iterator (m_table.begin ()); }
224 iterator end () const { return iterator (m_table.end ()); }
226 private:
228 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
229 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
230 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
232 hash_table<hash_entry> m_table;
235 /* ggc marking routines. */
237 template<typename K, typename V, typename H>
238 static inline void
239 gt_ggc_mx (hash_map<K, V, H> *h)
241 gt_ggc_mx (&h->m_table);
244 template<typename K, typename V, typename H>
245 static inline void
246 gt_pch_nx (hash_map<K, V, H> *h)
248 gt_pch_nx (&h->m_table);
251 template<typename K, typename V, typename H>
252 static inline void
253 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
255 op (&h->m_table.m_entries, cookie);
258 #endif