1/* Unit tests for hash-set.h.
2   Copyright (C) 2015-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#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "tm.h"
24#include "opts.h"
25#include "hash-set.h"
26#include "selftest.h"
27
28#if CHECKING_P
29
30namespace selftest {
31
32/* Construct a hash_set <const char *> and verify that various operations
33   work correctly.  */
34
35static void
36test_set_of_strings ()
37{
38  hash_set <const char *> s;
39  ASSERT_EQ (0, s.elements ());
40
41  const char *red = "red";
42  const char *green = "green";
43  const char *blue = "blue";
44
45  ASSERT_EQ (false, s.contains (red));
46
47  for (hash_set<const char *>::iterator it = s.begin (); it != s.end (); ++it)
48    ASSERT_EQ (true, false);
49
50  /* Populate the hash_set.  */
51  ASSERT_EQ (false, s.add (red));
52  ASSERT_EQ (false, s.add (green));
53  ASSERT_EQ (false, s.add (blue));
54  ASSERT_EQ (true, s.add (green));
55
56  /* Verify that the values are now within the set.  */
57  ASSERT_EQ (true, s.contains (red));
58  ASSERT_EQ (true, s.contains (green));
59  ASSERT_EQ (true, s.contains (blue));
60  ASSERT_EQ (3, s.elements ());
61
62  /* Test removal.  */
63  s.remove (red);
64  ASSERT_EQ (false, s.contains (red));
65  ASSERT_EQ (true, s.contains (green));
66  ASSERT_EQ (true, s.contains (blue));
67  ASSERT_EQ (2, s.elements ());
68
69  s.remove (red);
70  ASSERT_EQ (false, s.contains (red));
71  ASSERT_EQ (true, s.contains (green));
72  ASSERT_EQ (true, s.contains (blue));
73  ASSERT_EQ (2, s.elements ());
74
75  int seen = 0;
76  for (hash_set<const char *>::iterator it = s.begin (); it != s.end (); ++it)
77    {
78      int n = *it == green;
79      if (n == 0)
80	ASSERT_EQ (*it, blue);
81      ASSERT_EQ (seen & (1 << n), 0);
82      seen |= 1 << n;
83    }
84  ASSERT_EQ (seen, 3);
85
86  hash_set <const char *, true> t;
87  ASSERT_EQ (0, t.elements ());
88
89  ASSERT_EQ (false, t.contains (red));
90
91  for (hash_set<const char *, true>::iterator it = t.begin ();
92       it != t.end (); ++it)
93    ASSERT_EQ (true, false);
94
95  /* Populate the hash_set.  */
96  ASSERT_EQ (false, t.add (red));
97  ASSERT_EQ (false, t.add (green));
98  ASSERT_EQ (false, t.add (blue));
99  ASSERT_EQ (true, t.add (green));
100
101  /* Verify that the values are now within the set.  */
102  ASSERT_EQ (true, t.contains (red));
103  ASSERT_EQ (true, t.contains (green));
104  ASSERT_EQ (true, t.contains (blue));
105  ASSERT_EQ (3, t.elements ());
106
107  seen = 0;
108  for (hash_set<const char *, true>::iterator it = t.begin ();
109       it != t.end (); ++it)
110    {
111      int n = 2;
112      if (*it == green)
113	n = 0;
114      else if (*it == blue)
115	n = 1;
116      else
117	ASSERT_EQ (*it, red);
118      ASSERT_EQ (seen & (1 << n), 0);
119      seen |= 1 << n;
120    }
121  ASSERT_EQ (seen, 7);
122
123  /* Test removal.  */
124  t.remove (red);
125  ASSERT_EQ (false, t.contains (red));
126  ASSERT_EQ (true, t.contains (green));
127  ASSERT_EQ (true, t.contains (blue));
128  ASSERT_EQ (2, t.elements ());
129
130  t.remove (red);
131  ASSERT_EQ (false, t.contains (red));
132  ASSERT_EQ (true, t.contains (green));
133  ASSERT_EQ (true, t.contains (blue));
134  ASSERT_EQ (2, t.elements ());
135}
136
137typedef class hash_set_test_value_t
138{
139public:
140  static int ndefault;
141  static int ncopy;
142  static int nassign;
143  static int ndtor;
144
145  hash_set_test_value_t (int v = 1): pval (&val), val (v)
146  {
147    ++ndefault;
148  }
149
150  hash_set_test_value_t (const hash_set_test_value_t &rhs)
151    : pval (&val), val (rhs.val)
152  {
153    ++ncopy;
154  }
155
156  hash_set_test_value_t& operator= (const hash_set_test_value_t &rhs)
157    {
158     ++nassign;
159     val = rhs.val;
160     return *this;
161    }
162
163  ~hash_set_test_value_t ()
164    {
165     /* Verify that the value hasn't been corrupted.  */
166     gcc_assert (*pval > 0);
167     gcc_assert (pval == &val);
168     *pval = -3;
169     ++ndtor;
170    }
171
172  int *pval;
173  int val;
174} val_t;
175
176int val_t::ndefault;
177int val_t::ncopy;
178int val_t::nassign;
179int val_t::ndtor;
180
181struct value_hash_traits: int_hash<int, -1, -2>
182{
183  typedef int_hash<int, -1, -2> base_type;
184  typedef val_t                 value_type;
185  typedef value_type            compare_type;
186
187  static hashval_t hash (const value_type &v)
188  {
189    return base_type::hash (v.val);
190  }
191
192  static bool equal (const value_type &a, const compare_type &b)
193  {
194    return base_type::equal (a.val, b.val);
195  }
196
197  static void mark_deleted (value_type &v)
198  {
199    base_type::mark_deleted (v.val);
200  }
201
202  static const bool empty_zero_p = false;
203
204  static void mark_empty (value_type &v)
205  {
206    base_type::mark_empty (v.val);
207  }
208
209  static bool is_deleted (const value_type &v)
210  {
211    return base_type::is_deleted (v.val);
212  }
213
214  static bool is_empty (const value_type &v)
215  {
216    return base_type::is_empty (v.val);
217  }
218
219  static void remove (value_type &v)
220  {
221    v.~value_type ();
222  }
223};
224
225static void
226test_set_of_type_with_ctor_and_dtor ()
227{
228  typedef hash_set <val_t, false, value_hash_traits> Set;
229
230  {
231    Set s;
232    (void)&s;
233  }
234
235  ASSERT_TRUE (val_t::ndefault == 0);
236  ASSERT_TRUE (val_t::ncopy == 0);
237  ASSERT_TRUE (val_t::nassign == 0);
238  ASSERT_TRUE (val_t::ndtor == 0);
239
240  {
241    Set s;
242    ASSERT_EQ (false, s.add (val_t ()));
243    ASSERT_EQ (true, 1 == s.elements ());
244  }
245
246  ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
247
248  {
249    Set s;
250    ASSERT_EQ (false, s.add (val_t ()));
251    ASSERT_EQ (true, s.add (val_t ()));
252    ASSERT_EQ (true, 1 == s.elements ());
253  }
254
255  ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
256
257  {
258    Set s;
259    val_t v1 (1), v2 (2), v3 (3);
260    int ndefault = val_t::ndefault;
261    int nassign = val_t::nassign;
262
263    ASSERT_EQ (false, s.add (v1));
264    ASSERT_EQ (true, s.contains (v1));
265    ASSERT_EQ (true, 1 == s.elements ());
266
267    ASSERT_EQ (false, s.add (v2));
268    ASSERT_EQ (true, s.contains (v2));
269    ASSERT_EQ (true, 2 == s.elements ());
270
271    ASSERT_EQ (false, s.add (v3));
272    ASSERT_EQ (true, s.contains (v3));
273    ASSERT_EQ (true, 3 == s.elements ());
274
275    ASSERT_EQ (true, s.add (v2));
276    ASSERT_EQ (true, s.contains (v2));
277    ASSERT_EQ (true, 3 == s.elements ());
278
279    s.remove (v2);
280    ASSERT_EQ (true, 2 == s.elements ());
281    s.remove (v3);
282    ASSERT_EQ (true, 1 == s.elements ());
283
284    /* Verify that no default ctors or assignment operators have
285       been called.  */
286    ASSERT_EQ (true, ndefault == val_t::ndefault);
287    ASSERT_EQ (true, nassign == val_t::nassign);
288  }
289
290  ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
291}
292
293/* Run all of the selftests within this file.  */
294
295void
296hash_set_tests_cc_tests ()
297{
298  test_set_of_strings ();
299  test_set_of_type_with_ctor_and_dtor ();
300}
301
302} // namespace selftest
303
304#endif /* #if CHECKING_P */
305