gcc/hash-set-tests.c

   1 /* Unit tests for hash-set.h.
   2    Copyright (C) 2015-2019 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 void mark_empty (value_type &v)
 203   {
 204     base_type::mark_empty (v.val);
 205   }
 206
 207   static bool is_deleted (const value_type &v)
 208   {
 209     return base_type::is_deleted (v.val);
 210   }
 211
 212   static bool is_empty (const value_type &v)
 213   {
 214     return base_type::is_empty (v.val);
 215   }
 216
 217   static void remove (value_type &v)
 218   {
 219     v.~value_type ();
 220   }
 221 };
 222
 223 static void
 224 test_set_of_type_with_ctor_and_dtor ()
 225 {
 226   typedef hash_set <val_t, false, value_hash_traits> Set;
 227
 228   {
 229     Set s;
 230     (void)&s;
 231   }
 232
 233   ASSERT_TRUE (val_t::ndefault == 0);
 234   ASSERT_TRUE (val_t::ncopy == 0);
 235   ASSERT_TRUE (val_t::nassign == 0);
 236   ASSERT_TRUE (val_t::ndtor == 0);
 237
 238   {
 239     Set s;
 240     ASSERT_EQ (false, s.add (val_t ()));
 241     ASSERT_EQ (true, 1 == s.elements ());
 242   }
 243
 244   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
 245
 246   {
 247     Set s;
 248     ASSERT_EQ (false, s.add (val_t ()));
 249     ASSERT_EQ (true, s.add (val_t ()));
 250     ASSERT_EQ (true, 1 == s.elements ());
 251   }
 252
 253   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
 254
 255   {
 256     Set s;
 257     val_t v1 (1), v2 (2), v3 (3);
 258     int ndefault = val_t::ndefault;
 259     int nassign = val_t::nassign;
 260
 261     ASSERT_EQ (false, s.add (v1));
 262     ASSERT_EQ (true, s.contains (v1));
 263     ASSERT_EQ (true, 1 == s.elements ());
 264
 265     ASSERT_EQ (false, s.add (v2));
 266     ASSERT_EQ (true, s.contains (v2));
 267     ASSERT_EQ (true, 2 == s.elements ());
 268
 269     ASSERT_EQ (false, s.add (v3));
 270     ASSERT_EQ (true, s.contains (v3));
 271     ASSERT_EQ (true, 3 == s.elements ());
 272
 273     ASSERT_EQ (true, s.add (v2));
 274     ASSERT_EQ (true, s.contains (v2));
 275     ASSERT_EQ (true, 3 == s.elements ());
 276
 277     s.remove (v2);
 278     ASSERT_EQ (true, 2 == s.elements ());
 279     s.remove (v3);
 280     ASSERT_EQ (true, 1 == s.elements ());
 281
 282     /* Verify that no default ctors or assignment operators have
 283        been called.  */
 284     ASSERT_EQ (true, ndefault == val_t::ndefault);
 285     ASSERT_EQ (true, nassign == val_t::nassign);
 286   }
 287
 288   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
 289 }
 290
 291 /* Run all of the selftests within this file.  */
 292
 293 void
 294 hash_set_tests_c_tests ()
 295 {
 296   test_set_of_strings ();
 297   test_set_of_type_with_ctor_and_dtor ();
 298 }
 299
 300 } // namespace selftest
 301
 302 #endif /* #if CHECKING_P */