xref: /netbsd-src/external/gpl3/gcc/dist/gcc/hash-map.h (revision bdc22b2e01993381dcefeff2bc9b56ca75a4235c)
1 /* A type-safe hash map.
2    Copyright (C) 2014-2016 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_map_h
22 #define hash_map_h
23 
24 template<typename KeyId, typename Value,
25 	 typename Traits>
26 class GTY((user)) hash_map
27 {
28   typedef typename Traits::key_type Key;
29   struct hash_entry
30   {
31     Key m_key;
32     Value m_value;
33 
34     typedef hash_entry value_type;
35     typedef Key compare_type;
36 
37     static hashval_t hash (const hash_entry &e)
38       {
39        	return Traits::hash (e.m_key);
40       }
41 
42     static bool equal (const hash_entry &a, const Key &b)
43        	{
44 	  return Traits::equal_keys (a.m_key, b);
45        	}
46 
47     static void remove (hash_entry &e) { Traits::remove (e); }
48 
49     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
50 
51     static bool is_deleted (const hash_entry &e)
52       {
53        	return Traits::is_deleted (e);
54       }
55 
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); }
58 
59     static void ggc_mx (hash_entry &e)
60       {
61 	gt_ggc_mx (e.m_key);
62 	gt_ggc_mx (e.m_value);
63       }
64 
65     static void pch_nx (hash_entry &e)
66       {
67 	gt_pch_nx (e.m_key);
68 	gt_pch_nx (e.m_value);
69       }
70 
71     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
72       {
73 	pch_nx_helper (e.m_key, op, c);
74 	pch_nx_helper (e.m_value, op, c);
75       }
76 
77   private:
78     template<typename T>
79     static void
80       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
81 	{
82 	  gt_pch_nx (&x, op, cookie);
83 	}
84 
85     static void
86       pch_nx_helper (int, gt_pointer_operator, void *)
87 	{
88 	}
89 
90     static void
91       pch_nx_helper (unsigned int, gt_pointer_operator, void *)
92 	{
93 	}
94 
95     static void
96       pch_nx_helper (bool, gt_pointer_operator, void *)
97 	{
98 	}
99 
100     template<typename T>
101       static void
102       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
103 	{
104 	  op (&x, cookie);
105 	}
106   };
107 
108 public:
109   explicit hash_map (size_t n = 13, bool ggc = false,
110 		     bool gather_mem_stats = GATHER_STATISTICS
111 		     CXX_MEM_STAT_INFO)
112     : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {}
113 
114   explicit hash_map (const hash_map &h, bool ggc = false,
115 		     bool gather_mem_stats = GATHER_STATISTICS
116 		     CXX_MEM_STAT_INFO)
117     : m_table (h.m_table, ggc, gather_mem_stats,
118 	       HASH_MAP_ORIGIN PASS_MEM_STAT) {}
119 
120   /* Create a hash_map in ggc memory.  */
121   static hash_map *create_ggc (size_t size,
122 			       bool gather_mem_stats = GATHER_STATISTICS
123 			       CXX_MEM_STAT_INFO)
124     {
125       hash_map *map = ggc_alloc<hash_map> ();
126       new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT);
127       return map;
128     }
129 
130   /* If key k isn't already in the map add key k with value v to the map, and
131      return false.  Otherwise set the value of the entry for key k to be v and
132      return true.  */
133 
134   bool put (const Key &k, const Value &v)
135     {
136       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
137 						   INSERT);
138       bool existed = !hash_entry::is_empty (*e);
139       if (!existed)
140 	e->m_key = k;
141 
142       e->m_value = v;
143       return existed;
144     }
145 
146   /* if the passed in key is in the map return its value otherwise NULL.  */
147 
148   Value *get (const Key &k)
149     {
150       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
151       return Traits::is_empty (e) ? NULL : &e.m_value;
152     }
153 
154   /* Return a reference to the value for the passed in key, creating the entry
155      if it doesn't already exist.  If existed is not NULL then it is set to false
156      if the key was not previously in the map, and true otherwise.  */
157 
158   Value &get_or_insert (const Key &k, bool *existed = NULL)
159     {
160       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
161 						   INSERT);
162       bool ins = Traits::is_empty (*e);
163       if (ins)
164 	e->m_key = k;
165 
166       if (existed != NULL)
167 	*existed = !ins;
168 
169       return e->m_value;
170     }
171 
172   void remove (const Key &k)
173     {
174       m_table.remove_elt_with_hash (k, Traits::hash (k));
175     }
176 
177   /* Call the call back on each pair of key and value with the passed in
178      arg.  */
179 
180   template<typename Arg, bool (*f)(const typename Traits::key_type &,
181 				   const Value &, Arg)>
182   void traverse (Arg a) const
183     {
184       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
185 	   iter != m_table.end (); ++iter)
186 	f ((*iter).m_key, (*iter).m_value, a);
187     }
188 
189   template<typename Arg, bool (*f)(const typename Traits::key_type &,
190 				   Value *, Arg)>
191   void traverse (Arg a) const
192     {
193       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
194 	   iter != m_table.end (); ++iter)
195 	if (!f ((*iter).m_key, &(*iter).m_value, a))
196 	  break;
197     }
198 
199   size_t elements () const { return m_table.elements (); }
200 
201   void empty () { m_table.empty(); }
202 
203   class iterator
204   {
205   public:
206     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
207       m_iter (iter) {}
208 
209     iterator &operator++ ()
210     {
211       ++m_iter;
212       return *this;
213     }
214 
215     std::pair<Key, Value> operator* ()
216     {
217       hash_entry &e = *m_iter;
218       return std::pair<Key, Value> (e.m_key, e.m_value);
219     }
220 
221     bool
222     operator != (const iterator &other) const
223     {
224       return m_iter != other.m_iter;
225     }
226 
227   private:
228     typename hash_table<hash_entry>::iterator m_iter;
229   };
230 
231   /* Standard iterator retrieval methods.  */
232 
233   iterator  begin () const { return iterator (m_table.begin ()); }
234   iterator end () const { return iterator (m_table.end ()); }
235 
236 private:
237 
238   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
239   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
240       template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
241 
242   hash_table<hash_entry> m_table;
243 };
244 
245 /* ggc marking routines.  */
246 
247 template<typename K, typename V, typename H>
248 static inline void
249 gt_ggc_mx (hash_map<K, V, H> *h)
250 {
251   gt_ggc_mx (&h->m_table);
252 }
253 
254 template<typename K, typename V, typename H>
255 static inline void
256 gt_pch_nx (hash_map<K, V, H> *h)
257 {
258   gt_pch_nx (&h->m_table);
259 }
260 
261 template<typename K, typename V, typename H>
262 static inline void
263 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
264 {
265   op (&h->m_table.m_entries, cookie);
266 }
267 
268 #endif
269