gcc/hash-set-tests.cc

   1 /* Unit tests for hash-set.h.
   2    Copyright (C) 2015-2024 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along 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
  30 namespace selftest {
  31
  32 /* Construct a hash_set <const char *> and verify that various operations
  33    work correctly.  */
  34
  35 static void
  36 test_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
 137 typedef class hash_set_test_value_t
 138 {
 139 public:
 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
 176 int val_t::ndefault;
 177 int val_t::ncopy;
 178 int val_t::nassign;
 179 int val_t::ndtor;
 180
 181 struct 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
 225 static void
 226 test_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
 295 void
 296 hash_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 */