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