1/* A type-safe hash map.
2   Copyright (C) 2014-2022 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    template<typename T>
111      static void
112      pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
113	{
114	  op (&x, NULL, cookie);
115	}
116
117    /* The overloads below should match those in ggc.h.  */
118#define DEFINE_PCH_HELPER(T)			\
119    static void pch_nx_helper (T, gt_pointer_operator, void *) { }
120
121    DEFINE_PCH_HELPER (bool);
122    DEFINE_PCH_HELPER (char);
123    DEFINE_PCH_HELPER (signed char);
124    DEFINE_PCH_HELPER (unsigned char);
125    DEFINE_PCH_HELPER (short);
126    DEFINE_PCH_HELPER (unsigned short);
127    DEFINE_PCH_HELPER (int);
128    DEFINE_PCH_HELPER (unsigned int);
129    DEFINE_PCH_HELPER (long);
130    DEFINE_PCH_HELPER (unsigned long);
131    DEFINE_PCH_HELPER (long long);
132    DEFINE_PCH_HELPER (unsigned long long);
133
134#undef DEFINE_PCH_HELPER
135  };
136
137public:
138  explicit hash_map (size_t n = default_hash_map_size, bool ggc = false,
139		     bool sanitize_eq_and_hash = true,
140		     bool gather_mem_stats = GATHER_STATISTICS
141		     CXX_MEM_STAT_INFO)
142    : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
143	       HASH_MAP_ORIGIN PASS_MEM_STAT)
144  {
145  }
146
147  explicit hash_map (const hash_map &h, bool ggc = false,
148		     bool sanitize_eq_and_hash = true,
149		     bool gather_mem_stats = GATHER_STATISTICS
150		     CXX_MEM_STAT_INFO)
151    : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats,
152	       HASH_MAP_ORIGIN PASS_MEM_STAT) {}
153
154  /* Create a hash_map in ggc memory.  */
155  static hash_map *create_ggc (size_t size = default_hash_map_size,
156			       bool gather_mem_stats = GATHER_STATISTICS
157			       CXX_MEM_STAT_INFO)
158    {
159      hash_map *map = ggc_alloc<hash_map> ();
160      new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
161      return map;
162    }
163
164  /* If key k isn't already in the map add key k with value v to the map, and
165     return false.  Otherwise set the value of the entry for key k to be v and
166     return true.  */
167
168  bool put (const Key &k, const Value &v)
169    {
170      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
171						   INSERT);
172      bool ins = hash_entry::is_empty (*e);
173      if (ins)
174	{
175	  e->m_key = k;
176	  new ((void *) &e->m_value) Value (v);
177	}
178      else
179	e->m_value = v;
180
181      return !ins;
182    }
183
184  /* If the passed in key is in the map return pointer to its value
185     otherwise NULL.  */
186
187  Value *get (const Key &k)
188    {
189      hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
190      return Traits::is_empty (e) ? NULL : &e.m_value;
191    }
192
193  /* Return a reference to the value for the passed in key, creating the entry
194     if it doesn't already exist.  If existed is not NULL then it is set to
195     false if the key was not previously in the map, and true otherwise.  */
196
197  Value &get_or_insert (const Key &k, bool *existed = NULL)
198    {
199      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
200						   INSERT);
201      bool ins = Traits::is_empty (*e);
202      if (ins)
203	{
204	  e->m_key = k;
205	  new ((void *)&e->m_value) Value ();
206	}
207
208      if (existed != NULL)
209	*existed = !ins;
210
211      return e->m_value;
212    }
213
214  void remove (const Key &k)
215    {
216      m_table.remove_elt_with_hash (k, Traits::hash (k));
217    }
218
219  /* Call the call back on each pair of key and value with the passed in
220     arg until either the call back returns false or all pairs have been seen.
221     The traversal is unordered.  */
222
223  template<typename Arg, bool (*f)(const typename Traits::key_type &,
224				   const Value &, Arg)>
225  void traverse (Arg a) const
226    {
227      for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
228	   iter != m_table.end (); ++iter)
229	if (!f ((*iter).m_key, (*iter).m_value, a))
230	  break;
231    }
232
233  template<typename Arg, bool (*f)(const typename Traits::key_type &,
234				   Value *, Arg)>
235  void traverse (Arg a) const
236    {
237      for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
238	   iter != m_table.end (); ++iter)
239	if (!f ((*iter).m_key, &(*iter).m_value, a))
240	  break;
241    }
242
243  size_t elements () const { return m_table.elements (); }
244
245  void empty () { m_table.empty(); }
246
247  /* Return true when there are no elements in this hash map.  */
248  bool is_empty () const { return m_table.is_empty (); }
249
250  class iterator
251  {
252  public:
253    explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
254      m_iter (iter) {}
255
256    iterator &operator++ ()
257    {
258      ++m_iter;
259      return *this;
260    }
261
262    /* Can't use std::pair here, because GCC before 4.3 don't handle
263       std::pair where template parameters are references well.
264       See PR86739.  */
265    class reference_pair {
266    public:
267      const Key &first;
268      Value &second;
269
270      reference_pair (const Key &key, Value &value) : first (key), second (value) {}
271
272      template <typename K, typename V>
273      operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
274    };
275
276    reference_pair operator* ()
277    {
278      hash_entry &e = *m_iter;
279      return reference_pair (e.m_key, e.m_value);
280    }
281
282    bool operator== (const iterator &other) const
283    {
284      return m_iter == other.m_iter;
285    }
286
287    bool operator != (const iterator &other) const
288    {
289      return m_iter != other.m_iter;
290    }
291
292  private:
293    typename hash_table<hash_entry>::iterator m_iter;
294  };
295
296  /* Standard iterator retrieval methods.  */
297
298  iterator  begin () const { return iterator (m_table.begin ()); }
299  iterator end () const { return iterator (m_table.end ()); }
300
301private:
302
303  template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
304  template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
305  template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
306  template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
307
308  hash_table<hash_entry> m_table;
309};
310
311/* ggc marking routines.  */
312
313template<typename K, typename V, typename H>
314static inline void
315gt_ggc_mx (hash_map<K, V, H> *h)
316{
317  gt_ggc_mx (&h->m_table);
318}
319
320template<typename K, typename V, typename H>
321static inline void
322gt_pch_nx (hash_map<K, V, H> *h)
323{
324  gt_pch_nx (&h->m_table);
325}
326
327template<typename K, typename V, typename H>
328static inline void
329gt_cleare_cache (hash_map<K, V, H> *h)
330{
331  if (h)
332    gt_cleare_cache (&h->m_table);
333}
334
335template<typename K, typename V, typename H>
336static inline void
337gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
338{
339  op (&h->m_table.m_entries, NULL, cookie);
340}
341
342enum hm_alloc { hm_heap = false, hm_ggc = true };
343template<bool ggc, typename K, typename V, typename H>
344inline hash_map<K,V,H> *
345hash_map_maybe_create (hash_map<K,V,H> *&h,
346		       size_t size = default_hash_map_size)
347{
348  if (!h)
349    {
350      if (ggc)
351	h = hash_map<K,V,H>::create_ggc (size);
352      else
353	h = new hash_map<K,V,H> (size);
354    }
355  return h;
356}
357
358/* Like h->get, but handles null h.  */
359template<typename K, typename V, typename H>
360inline V*
361hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
362{
363  return h ? h->get (k) : NULL;
364}
365
366/* Like h->get, but handles null h.  */
367template<bool ggc, typename K, typename V, typename H>
368inline V&
369hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
370			     size_t size = default_hash_map_size)
371{
372  return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
373}
374
375/* Like h->put, but handles null h.  */
376template<bool ggc, typename K, typename V, typename H>
377inline bool
378hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
379		   size_t size = default_hash_map_size)
380{
381  return hash_map_maybe_create<ggc> (h, size)->put (k, v);
382}
383
384#endif
385