1/* A type-safe hash map.
2   Copyright (C) 2014-2015 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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#include <new>
25#include <utility>
26#include "hash-table.h"
27
28/* implement default behavior for traits when types allow it.  */
29
30struct default_hashmap_traits
31{
32  /* Hashes the passed in key.  */
33
34  template<typename T>
35  static hashval_t
36  hash (T *p)
37    {
38      return uintptr_t(p) >> 3;
39    }
40
41  /* If the value converts to hashval_t just use it.  */
42
43  template<typename T> static hashval_t hash (T v) { return v; }
44
45  /* Return true if the two keys passed as arguments are equal.  */
46
47  template<typename T>
48  static bool
49  equal_keys (const T &a, const T &b)
50    {
51      return a == b;
52    }
53
54  /* Called to dispose of the key and value before marking the entry as
55     deleted.  */
56
57  template<typename T> static void remove (T &v) { v.~T (); }
58
59  /* Mark the passed in entry as being deleted.  */
60
61  template<typename T>
62  static void
63  mark_deleted (T &e)
64    {
65      mark_key_deleted (e.m_key);
66    }
67
68  /* Mark the passed in entry as being empty.  */
69
70  template<typename T>
71  static void
72  mark_empty (T &e)
73    {
74      mark_key_empty (e.m_key);
75    }
76
77  /* Return true if the passed in entry is marked as deleted.  */
78
79  template<typename T>
80  static bool
81  is_deleted (T &e)
82    {
83      return e.m_key == (void *)1;
84    }
85
86  /* Return true if the passed in entry is marked as empty.  */
87
88  template<typename T> static bool is_empty (T &e) { return e.m_key == NULL; }
89
90private:
91  template<typename T>
92  static void
93  mark_key_deleted (T *&k)
94    {
95      k = reinterpret_cast<T *> (1);
96    }
97
98  template<typename T>
99  static void
100  mark_key_empty (T *&k)
101    {
102      k = static_cast<T *> (0);
103    }
104};
105
106template<typename Key, typename Value,
107	 typename Traits = default_hashmap_traits>
108class GTY((user)) hash_map
109{
110  struct hash_entry
111  {
112    Key m_key;
113    Value m_value;
114
115    typedef hash_entry value_type;
116    typedef Key compare_type;
117    typedef int store_values_directly;
118
119    static hashval_t hash (const hash_entry &e)
120      {
121       	return Traits::hash (e.m_key);
122      }
123
124    static bool equal (const hash_entry &a, const Key &b)
125       	{
126	  return Traits::equal_keys (a.m_key, b);
127       	}
128
129    static void remove (hash_entry &e) { Traits::remove (e); }
130
131    static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
132
133    static bool is_deleted (const hash_entry &e)
134      {
135       	return Traits::is_deleted (e);
136      }
137
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); }
140
141    static void ggc_mx (hash_entry &e)
142      {
143	gt_ggc_mx (e.m_key);
144	gt_ggc_mx (e.m_value);
145      }
146
147    static void pch_nx (hash_entry &e)
148      {
149	gt_pch_nx (e.m_key);
150	gt_pch_nx (e.m_value);
151      }
152
153    static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
154      {
155	pch_nx_helper (e.m_key, op, c);
156	pch_nx_helper (e.m_value, op, c);
157      }
158
159  private:
160    template<typename T>
161    static void
162      pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
163	{
164	  gt_pch_nx (&x, op, cookie);
165	}
166
167    static void
168      pch_nx_helper (int, gt_pointer_operator, void *)
169	{
170	}
171
172    static void
173      pch_nx_helper (unsigned int, gt_pointer_operator, void *)
174	{
175	}
176
177    static void
178      pch_nx_helper (bool, gt_pointer_operator, void *)
179	{
180	}
181
182    template<typename T>
183      static void
184      pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
185	{
186	  op (&x, cookie);
187	}
188  };
189
190public:
191  explicit hash_map (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
192
193  /* Create a hash_map in ggc memory.  */
194  static hash_map *create_ggc (size_t size)
195    {
196      hash_map *map = ggc_alloc<hash_map> ();
197      new (map) hash_map (size, true);
198      return map;
199    }
200
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.  */
204
205  bool put (const Key &k, const Value &v)
206    {
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;
212
213      e->m_value = v;
214      return existed;
215    }
216
217  /* if the passed in key is in the map return its value otherwise NULL.  */
218
219  Value *get (const Key &k)
220    {
221      hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
222      return Traits::is_empty (e) ? NULL : &e.m_value;
223    }
224
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.  */
228
229  Value &get_or_insert (const Key &k, bool *existed = NULL)
230    {
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;
236
237      if (existed != NULL)
238	*existed = !ins;
239
240      return e->m_value;
241    }
242
243  void remove (const Key &k)
244    {
245      m_table.remove_elt_with_hash (k, Traits::hash (k));
246    }
247
248  /* Call the call back on each pair of key and value with the passed in
249     arg.  */
250
251  template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
252  void traverse (Arg a) const
253    {
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);
257    }
258
259  template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
260  void traverse (Arg a) const
261    {
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;
266    }
267
268  size_t elements () const { return m_table.elements (); }
269
270  class iterator
271  {
272  public:
273    explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
274      m_iter (iter) {}
275
276    iterator &operator++ ()
277    {
278      ++m_iter;
279      return *this;
280    }
281
282    std::pair<Key, Value> operator* ()
283    {
284      hash_entry &e = *m_iter;
285      return std::pair<Key, Value> (e.m_key, e.m_value);
286    }
287
288    bool
289    operator != (const iterator &other) const
290    {
291      return m_iter != other.m_iter;
292    }
293
294  private:
295    typename hash_table<hash_entry>::iterator m_iter;
296  };
297
298  /* Standard iterator retrieval methods.  */
299
300  iterator  begin () const { return iterator (m_table.begin ()); }
301  iterator end () const { return iterator (m_table.end ()); }
302
303private:
304
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 *);
308
309  hash_table<hash_entry> m_table;
310};
311
312/* ggc marking routines.  */
313
314template<typename K, typename V, typename H>
315static inline void
316gt_ggc_mx (hash_map<K, V, H> *h)
317{
318  gt_ggc_mx (&h->m_table);
319}
320
321template<typename K, typename V, typename H>
322static inline void
323gt_pch_nx (hash_map<K, V, H> *h)
324{
325  gt_pch_nx (&h->m_table);
326}
327
328template<typename K, typename V, typename H>
329static inline void
330gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
331{
332  op (&h->m_table.m_entries, cookie);
333}
334
335#endif
336