1/* A type-safe hash set.
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_set_h
22#define hash_set_h
23
24#include "hash-table.h"
25
26/* implement default behavior for traits when types allow it.  */
27
28struct default_hashset_traits
29{
30  /* Hashes the passed in key.  */
31
32  template<typename T>
33  static hashval_t
34  hash (T *p)
35    {
36      return uintptr_t(p) >> 3;
37    }
38
39  template<typename T> static hashval_t hash(const T &v) { return v; }
40
41  /* Return true if the two keys passed as arguments are equal.  */
42
43  template<typename T>
44  static bool
45  equal (const T &a, const T &b)
46    {
47      return a == b;
48    }
49
50  /* Called to dispose of the key before marking the entry as deleted.  */
51
52  template<typename T> static void remove (T &v) { v.~T (); }
53
54  /* Mark the passed in entry as being deleted.  */
55
56  template<typename T>
57  static void
58  mark_deleted (T *&e)
59    {
60      e = reinterpret_cast<void *> (1);
61    }
62
63  /* Mark the passed in entry as being empty.  */
64
65  template<typename T>
66  static void
67  mark_empty (T *&e)
68    {
69      e = NULL;
70    }
71
72  /* Return true if the passed in entry is marked as deleted.  */
73
74  template<typename T>
75  static bool
76  is_deleted (T *e)
77    {
78      return e == reinterpret_cast<void *> (1);
79    }
80
81  /* Return true if the passed in entry is marked as empty.  */
82
83  template<typename T> static bool is_empty (T *e) { return e == NULL; }
84
85  /* ggc walking routine, mark all objects refered to by this one.  */
86
87  template<typename T>
88  static void
89  ggc_mx (T &x)
90    {
91      extern void gt_ggc_mx (T &);
92      gt_ggc_mx (x);
93    }
94
95  /* pch walking routine, note all objects refered to by this element.  */
96
97  template<typename T>
98  static void
99  pch_nx (T &x)
100    {
101      extern void gt_pch_nx (T &);
102      gt_pch_nx (x);
103    }
104};
105
106template<typename Key, typename Traits = default_hashset_traits>
107class hash_set
108{
109  struct hash_entry
110  {
111    Key m_key;
112
113    typedef hash_entry value_type;
114    typedef Key compare_type;
115    typedef int store_values_directly;
116
117    static hashval_t hash (const hash_entry &e)
118      {
119       	return Traits::hash (e.m_key);
120      }
121
122    static bool equal (const hash_entry &a, const Key &b)
123       	{
124	  return Traits::equal (a.m_key, b);
125       	}
126
127    static void remove (hash_entry &e) { Traits::remove (e.m_key); }
128
129    static void
130    mark_deleted (hash_entry &e)
131      {
132       	Traits::mark_deleted (e.m_key);
133      }
134
135    static bool is_deleted (const hash_entry &e)
136      {
137       	return Traits::is_deleted (e.m_key);
138      }
139
140    static void
141    mark_empty (hash_entry &e)
142      {
143	Traits::mark_empty (e.m_key);
144      }
145
146    static bool
147    is_empty (const hash_entry &e)
148      {
149	return Traits::is_empty (e.m_key);
150      }
151
152    static void ggc_mx (hash_entry &e)
153      {
154	Traits::ggc_mx (e.m_key);
155      }
156
157    static void pch_nx (hash_entry &e)
158      {
159	Traits::pch_nx (e.m_key);
160      }
161
162    static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
163      {
164	pch_nx_helper (e.m_key, op, c);
165      }
166
167  private:
168    template<typename T>
169    static void
170      pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
171	{
172	  gt_pch_nx (&x, op, cookie);
173	}
174
175    template<typename T>
176      static void
177      pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
178	{
179	  op (&x, cookie);
180	}
181  };
182
183public:
184  explicit hash_set (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
185
186  /* Create a hash_set in gc memory with space for at least n elements.  */
187
188  static hash_set *
189    create_ggc (size_t n)
190      {
191	hash_set *set = ggc_alloc<hash_set> ();
192	new (set) hash_set (n, true);
193	return set;
194      }
195
196  /* If key k isn't already in the map add it to the map, and
197     return false.  Otherwise return true.  */
198
199  bool add (const Key &k)
200    {
201      hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
202						   INSERT);
203      bool existed = !hash_entry::is_empty (*e);
204      if (!existed)
205	e->m_key = k;
206
207      return existed;
208    }
209
210  /* if the passed in key is in the map return its value otherwise NULL.  */
211
212  bool contains (const Key &k)
213    {
214      hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
215      return !Traits::is_empty (e.m_key);
216    }
217
218  /* Call the call back on each pair of key and value with the passed in
219     arg.  */
220
221  template<typename Arg, bool (*f)(const Key &, Arg)>
222  void traverse (Arg a) const
223    {
224      for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
225	   iter != m_table.end (); ++iter)
226	f ((*iter).m_key, a);
227    }
228
229  /* Return the number of elements in the set.  */
230
231  size_t elements () const { return m_table.elements (); }
232
233private:
234
235  template<typename T, typename U> friend void gt_ggc_mx (hash_set<T, U> *);
236  template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *);
237      template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, gt_pointer_operator, void *);
238
239  hash_table<hash_entry> m_table;
240};
241
242/* ggc marking routines.  */
243
244template<typename K, typename H>
245static inline void
246gt_ggc_mx (hash_set<K, H> *h)
247{
248  gt_ggc_mx (&h->m_table);
249}
250
251template<typename K, typename H>
252static inline void
253gt_pch_nx (hash_set<K, H> *h)
254{
255  gt_pch_nx (&h->m_table);
256}
257
258template<typename K, typename H>
259static inline void
260gt_pch_nx (hash_set<K, H> *h, gt_pointer_operator op, void *cookie)
261{
262  op (&h->m_table.m_entries, cookie);
263}
264
265#endif
266