1/* A type-safe hash map.
2   Copyright (C) 2014-2020 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/* Class hash_map is a hash-value based container mapping objects of
25   KeyId type to those of the Value type.
26   Both KeyId and Value may be non-trivial (non-POD) types provided
27   a suitabe Traits class.  A few default Traits specializations are
28   provided for basic types such as integers, pointers, and std::pair.
29   Inserted elements are value-initialized either to zero for POD types
30   or by invoking their default ctor.  Removed elements are destroyed
31   by invoking their dtor.   On hash_map destruction all elements are
32   removed.  Objects of hash_map type are copy-constructible but not
33   assignable.  */
34
35const size_t default_hash_map_size = 13;
36template<typename KeyId, typename Value,
37	 typename Traits /* = simple_hashmap_traits<default_hash_traits<Key>,
38			                            Value> */>
39class GTY((user)) hash_map
40{
41  typedef typename Traits::key_type Key;
42  struct hash_entry
43  {
44    Key m_key;
45    Value m_value;
46
47    typedef hash_entry value_type;
48    typedef Key compare_type;
49
50    static hashval_t hash (const hash_entry &e)
51      {
52       	return Traits::hash (e.m_key);
53      }
54
55    static bool equal (const hash_entry &a, const Key &b)
56       	{
57	  return Traits::equal_keys (a.m_key, b);
58       	}
59
60    static void remove (hash_entry &e) { Traits::remove (e); }
61
62    static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
63
64    static bool is_deleted (const hash_entry &e)
65      {
66       	return Traits::is_deleted (e);
67      }
68
69    static const bool empty_zero_p = Traits::empty_zero_p;
70    static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
71    static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
72
73    static void ggc_mx (hash_entry &e)
74      {
75	gt_ggc_mx (e.m_key);
76	gt_ggc_mx (e.m_value);
77      }
78
79    static void ggc_maybe_mx (hash_entry &e)
80      {
81	if (Traits::maybe_mx)
82	  ggc_mx (e);
83      }
84
85    static void pch_nx (hash_entry &e)
86      {
87	gt_pch_nx (e.m_key);
88	gt_pch_nx (e.m_value);
89      }
90
91    static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
92      {
93	pch_nx_helper (e.m_key, op, c);
94	pch_nx_helper (e.m_value, op, c);
95      }
96
97    static int keep_cache_entry (hash_entry &e)
98      {
99	return ggc_marked_p (e.m_key);
100      }
101
102  private:
103    template<typename T>
104    static void
105      pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
106	{
107	  gt_pch_nx (&x, op, cookie);
108	}
109
110    static void
111      pch_nx_helper (int, gt_pointer_operator, void *)
112	{
113	}
114
115    static void
116      pch_nx_helper (unsigned int, gt_pointer_operator, void *)
117	{
118	}
119
120    static void
121      pch_nx_helper (bool, gt_pointer_operator, void *)
122	{
123	}
124
125    template<typename T>
126      static void
127      pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
128	{
129	  op (&x, cookie);
130	}
131  };
132
133public:
134  explicit hash_map (size_t n = default_hash_map_size, bool ggc = false,
135		     bool sanitize_eq_and_hash = true,
136		     bool gather_mem_stats = GATHER_STATISTICS
137		     CXX_MEM_STAT_INFO)
138    : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
139	       HASH_MAP_ORIGIN PASS_MEM_STAT)
140  {
141  }
142
143  explicit hash_map (const hash_map &h, bool ggc = false,
144		     bool sanitize_eq_and_hash = true,
145		     bool gather_mem_stats = GATHER_STATISTICS
146		     CXX_MEM_STAT_INFO)
147    : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats,
148	       HASH_MAP_ORIGIN PASS_MEM_STAT) {}
149
150  /* Create a hash_map in ggc memory.  */
151  static hash_map *create_ggc (size_t size = default_hash_map_size,
152			       bool gather_mem_stats = GATHER_STATISTICS
153			       CXX_MEM_STAT_INFO)
154    {
155      hash_map *map = ggc_alloc<hash_map> ();
156      new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
157      return map;
158    }
159
160  /* If key k isn't already in the map add key k with value v to the map, and
161     return false.  Otherwise set the value of the entry for key k to be v and
162     return true.  */
163
164  bool put (const Key &k, const Value &v)
165    {
166      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
167						   INSERT);
168      bool ins = hash_entry::is_empty (*e);
169      if (ins)
170	{
171	  e->m_key = k;
172	  new ((void *) &e->m_value) Value (v);
173	}
174      else
175	e->m_value = v;
176
177      return !ins;
178    }
179
180  /* if the passed in key is in the map return its value otherwise NULL.  */
181
182  Value *get (const Key &k)
183    {
184      hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
185      return Traits::is_empty (e) ? NULL : &e.m_value;
186    }
187
188  /* Return a reference to the value for the passed in key, creating the entry
189     if it doesn't already exist.  If existed is not NULL then it is set to
190     false if the key was not previously in the map, and true otherwise.  */
191
192  Value &get_or_insert (const Key &k, bool *existed = NULL)
193    {
194      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
195						   INSERT);
196      bool ins = Traits::is_empty (*e);
197      if (ins)
198	{
199	  e->m_key = k;
200	  new ((void *)&e->m_value) Value ();
201	}
202
203      if (existed != NULL)
204	*existed = !ins;
205
206      return e->m_value;
207    }
208
209  void remove (const Key &k)
210    {
211      m_table.remove_elt_with_hash (k, Traits::hash (k));
212    }
213
214  /* Call the call back on each pair of key and value with the passed in
215     arg.  */
216
217  template<typename Arg, bool (*f)(const typename Traits::key_type &,
218				   const Value &, Arg)>
219  void traverse (Arg a) const
220    {
221      for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
222	   iter != m_table.end (); ++iter)
223	f ((*iter).m_key, (*iter).m_value, a);
224    }
225
226  template<typename Arg, bool (*f)(const typename Traits::key_type &,
227				   Value *, Arg)>
228  void traverse (Arg a) const
229    {
230      for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
231	   iter != m_table.end (); ++iter)
232	if (!f ((*iter).m_key, &(*iter).m_value, a))
233	  break;
234    }
235
236  size_t elements () const { return m_table.elements (); }
237
238  void empty () { m_table.empty(); }
239
240  /* Return true when there are no elements in this hash map.  */
241  bool is_empty () const { return m_table.is_empty (); }
242
243  class iterator
244  {
245  public:
246    explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
247      m_iter (iter) {}
248
249    iterator &operator++ ()
250    {
251      ++m_iter;
252      return *this;
253    }
254
255    /* Can't use std::pair here, because GCC before 4.3 don't handle
256       std::pair where template parameters are references well.
257       See PR86739.  */
258    class reference_pair {
259    public:
260      const Key &first;
261      Value &second;
262
263      reference_pair (const Key &key, Value &value) : first (key), second (value) {}
264
265      template <typename K, typename V>
266      operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
267    };
268
269    reference_pair operator* ()
270    {
271      hash_entry &e = *m_iter;
272      return reference_pair (e.m_key, e.m_value);
273    }
274
275    bool
276    operator != (const iterator &other) const
277    {
278      return m_iter != other.m_iter;
279    }
280
281  private:
282    typename hash_table<hash_entry>::iterator m_iter;
283  };
284
285  /* Standard iterator retrieval methods.  */
286
287  iterator  begin () const { return iterator (m_table.begin ()); }
288  iterator end () const { return iterator (m_table.end ()); }
289
290private:
291
292  template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
293  template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
294  template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
295  template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
296
297  hash_table<hash_entry> m_table;
298};
299
300/* ggc marking routines.  */
301
302template<typename K, typename V, typename H>
303static inline void
304gt_ggc_mx (hash_map<K, V, H> *h)
305{
306  gt_ggc_mx (&h->m_table);
307}
308
309template<typename K, typename V, typename H>
310static inline void
311gt_pch_nx (hash_map<K, V, H> *h)
312{
313  gt_pch_nx (&h->m_table);
314}
315
316template<typename K, typename V, typename H>
317static inline void
318gt_cleare_cache (hash_map<K, V, H> *h)
319{
320  if (h)
321    gt_cleare_cache (&h->m_table);
322}
323
324template<typename K, typename V, typename H>
325static inline void
326gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
327{
328  op (&h->m_table.m_entries, cookie);
329}
330
331enum hm_alloc { hm_heap = false, hm_ggc = true };
332template<bool ggc, typename K, typename V, typename H>
333inline hash_map<K,V,H> *
334hash_map_maybe_create (hash_map<K,V,H> *&h,
335		       size_t size = default_hash_map_size)
336{
337  if (!h)
338    {
339      if (ggc)
340	h = hash_map<K,V,H>::create_ggc (size);
341      else
342	h = new hash_map<K,V,H> (size);
343    }
344  return h;
345}
346
347/* Like h->get, but handles null h.  */
348template<typename K, typename V, typename H>
349inline V*
350hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
351{
352  return h ? h->get (k) : NULL;
353}
354
355/* Like h->get, but handles null h.  */
356template<bool ggc, typename K, typename V, typename H>
357inline V&
358hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
359			     size_t size = default_hash_map_size)
360{
361  return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
362}
363
364/* Like h->put, but handles null h.  */
365template<bool ggc, typename K, typename V, typename H>
366inline bool
367hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
368		   size_t size = default_hash_map_size)
369{
370  return hash_map_maybe_create<ggc> (h, size)->put (k, v);
371}
372
373#endif
374