gcc/hash-map-tests.c

   1 /* Unit tests for hash-map.h.
   2    Copyright (C) 2015-2021 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 "fixed-value.h"
  27 #include "alias.h"
  28 #include "flags.h"
  29 #include "symtab.h"
  30 #include "tree-core.h"
  31 #include "stor-layout.h"
  32 #include "tree.h"
  33 #include "stringpool.h"
  34 #include "selftest.h"
  35
  36 #if CHECKING_P
  37
  38 namespace selftest {
  39
  40 /* Construct a hash_map <const char *, int> and verify that
  41    various operations work correctly.  */
  42
  43 static void
  44 test_map_of_strings_to_int ()
  45 {
  46   hash_map <const char *, int> m;
  47
  48   const char *ostrich = "ostrich";
  49   const char *elephant = "elephant";
  50   const char *ant = "ant";
  51   const char *spider = "spider";
  52   const char *millipede = "Illacme plenipes";
  53   const char *eric = "half a bee";
  54
  55   /* A fresh hash_map should be empty.  */
  56   ASSERT_TRUE (m.is_empty ());
  57   ASSERT_EQ (NULL, m.get (ostrich));
  58
  59   /* Populate the hash_map.  */
  60   ASSERT_EQ (false, m.put (ostrich, 2));
  61   ASSERT_EQ (false, m.put (elephant, 4));
  62   ASSERT_EQ (false, m.put (ant, 6));
  63   ASSERT_EQ (false, m.put (spider, 8));
  64   ASSERT_EQ (false, m.put (millipede, 750));
  65   ASSERT_EQ (false, m.put (eric, 3));
  66
  67   /* Verify that we can recover the stored values.  */
  68   ASSERT_EQ (6, m.elements ());
  69   ASSERT_EQ (2, *m.get (ostrich));
  70   ASSERT_EQ (4, *m.get (elephant));
  71   ASSERT_EQ (6, *m.get (ant));
  72   ASSERT_EQ (8, *m.get (spider));
  73   ASSERT_EQ (750, *m.get (millipede));
  74   ASSERT_EQ (3, *m.get (eric));
  75
  76   /* Verify removing an item.  */
  77   m.remove (eric);
  78   ASSERT_EQ (5, m.elements ());
  79   ASSERT_EQ (NULL, m.get (eric));
  80
  81   m.remove (eric);
  82   ASSERT_EQ (5, m.elements ());
  83   ASSERT_EQ (NULL, m.get (eric));
  84
  85   /* A plain char * key is hashed based on its value (address), rather
  86      than the string it points to.  */
  87   char *another_ant = static_cast <char *> (xcalloc (4, 1));
  88   another_ant[0] = 'a';
  89   another_ant[1] = 'n';
  90   another_ant[2] = 't';
  91   another_ant[3] = 0;
  92   ASSERT_NE (ant, another_ant);
  93   unsigned prev_size = m.elements ();
  94   ASSERT_EQ (false, m.put (another_ant, 7));
  95   ASSERT_EQ (prev_size + 1, m.elements ());
  96
  97   /* Need to use string_hash or nofree_string_hash key types to hash
  98      based on the string contents.  */
  99   hash_map <nofree_string_hash, int> string_map;
 100   ASSERT_EQ (false, string_map.put (ant, 1));
 101   ASSERT_EQ (1, string_map.elements ());
 102   ASSERT_EQ (true, string_map.put (another_ant, 5));
 103   ASSERT_EQ (1, string_map.elements ());
 104
 105   free (another_ant);
 106 }
 107
 108 /* Construct a hash_map using int_hash and verify that
 109    various operations work correctly.  */
 110
 111 static void
 112 test_map_of_int_to_strings ()
 113 {
 114   const int EMPTY = -1;
 115   const int DELETED = -2;
 116   typedef int_hash <int, EMPTY, DELETED> int_hash_t;
 117   hash_map <int_hash_t, const char *> m;
 118
 119   const char *ostrich = "ostrich";
 120   const char *elephant = "elephant";
 121   const char *ant = "ant";
 122   const char *spider = "spider";
 123   const char *millipede = "Illacme plenipes";
 124   const char *eric = "half a bee";
 125
 126   /* A fresh hash_map should be empty.  */
 127   ASSERT_EQ (0, m.elements ());
 128   ASSERT_EQ (NULL, m.get (2));
 129
 130   /* Populate the hash_map.  */
 131   ASSERT_EQ (false, m.put (2, ostrich));
 132   ASSERT_EQ (false, m.put (4, elephant));
 133   ASSERT_EQ (false, m.put (6, ant));
 134   ASSERT_EQ (false, m.put (8, spider));
 135   ASSERT_EQ (false, m.put (750, millipede));
 136   ASSERT_EQ (false, m.put (3, eric));
 137
 138   /* Verify that we can recover the stored values.  */
 139   ASSERT_EQ (6, m.elements ());
 140   ASSERT_EQ (*m.get (2), ostrich);
 141   ASSERT_EQ (*m.get (4), elephant);
 142   ASSERT_EQ (*m.get (6), ant);
 143   ASSERT_EQ (*m.get (8), spider);
 144   ASSERT_EQ (*m.get (750), millipede);
 145   ASSERT_EQ (*m.get (3), eric);
 146 }
 147
 148 typedef class hash_map_test_val_t
 149 {
 150 public:
 151   static int ndefault;
 152   static int ncopy;
 153   static int nassign;
 154   static int ndtor;
 155
 156   hash_map_test_val_t ()
 157     : ptr (&ptr)
 158   {
 159     ++ndefault;
 160   }
 161
 162   hash_map_test_val_t (const hash_map_test_val_t &rhs)
 163     : ptr (&ptr)
 164   {
 165     ++ncopy;
 166     gcc_assert (rhs.ptr == &rhs.ptr);
 167   }
 168
 169   hash_map_test_val_t& operator= (const hash_map_test_val_t &rhs)
 170   {
 171     ++nassign;
 172     gcc_assert (ptr == &ptr);
 173     gcc_assert (rhs.ptr == &rhs.ptr);
 174     return *this;
 175   }
 176
 177   ~hash_map_test_val_t ()
 178   {
 179     gcc_assert (ptr == &ptr);
 180     ++ndtor;
 181   }
 182
 183   void *ptr;
 184 } val_t;
 185
 186 int val_t::ndefault;
 187 int val_t::ncopy;
 188 int val_t::nassign;
 189 int val_t::ndtor;
 190
 191 static void
 192 test_map_of_type_with_ctor_and_dtor ()
 193 {
 194   typedef hash_map <void *, val_t> Map;
 195
 196   {
 197     /* Test default ctor.  */
 198     Map m;
 199     (void)&m;
 200   }
 201
 202   ASSERT_TRUE (val_t::ndefault == 0);
 203   ASSERT_TRUE (val_t::ncopy == 0);
 204   ASSERT_TRUE (val_t::nassign == 0);
 205   ASSERT_TRUE (val_t::ndtor == 0);
 206
 207   {
 208     /* Test single insertion.  */
 209     Map m;
 210     void *p = &p;
 211     m.get_or_insert (p);
 212   }
 213
 214   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
 215
 216   {
 217     /* Test copy ctor.  */
 218     Map m1;
 219     void *p = &p;
 220     val_t &rv1 = m1.get_or_insert (p);
 221
 222     int ncopy = val_t::ncopy;
 223     int nassign = val_t::nassign;
 224
 225     Map m2 (m1);
 226     val_t *pv2 = m2.get (p);
 227
 228     ASSERT_TRUE (ncopy + 1 == val_t::ncopy);
 229     ASSERT_TRUE (nassign == val_t::nassign);
 230
 231     ASSERT_TRUE (&rv1 != pv2);
 232   }
 233
 234   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
 235
 236 #if 0   /* Avoid testing until bug 90959 is fixed.  */
 237   {
 238     /* Test copy assignment into an empty map.  */
 239     Map m1;
 240     void *p = &p;
 241     val_t &rv1 = m1.get_or_insert (p);
 242
 243     int ncopy = val_t::ncopy;
 244     int nassign = val_t::nassign;
 245
 246     Map m2;
 247     m2 = m1;
 248     val_t *pv2 = m2.get (p);
 249
 250     ASSERT_TRUE (ncopy == val_t::ncopy);
 251     ASSERT_TRUE (nassign + 1 == val_t::nassign);
 252
 253     ASSERT_TRUE (&rv1 != pv2);
 254   }
 255
 256   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
 257
 258 #endif
 259
 260   {
 261     Map m;
 262     void *p = &p, *q = &q;
 263     val_t &v1 = m.get_or_insert (p);
 264     val_t &v2 = m.get_or_insert (q);
 265
 266     ASSERT_TRUE (v1.ptr == &v1.ptr && &v2.ptr == v2.ptr);
 267   }
 268
 269   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
 270
 271   {
 272     Map m;
 273     void *p = &p, *q = &q;
 274     m.get_or_insert (p);
 275     m.remove (p);
 276     m.get_or_insert (q);
 277     m.remove (q);
 278
 279     ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
 280   }
 281
 282
 283   /* Verify basic construction and destruction of Value objects.  */
 284   {
 285     /* Configure, arbitrary.  */
 286     const size_t N_init = 0;
 287     const int N_elem = 28;
 288
 289     void *a[N_elem];
 290     for (size_t i = 0; i < N_elem; ++i)
 291       a[i] = &a[i];
 292
 293     val_t::ndefault = 0;
 294     val_t::ncopy = 0;
 295     val_t::nassign = 0;
 296     val_t::ndtor = 0;
 297     Map m (N_init);
 298     ASSERT_EQ (val_t::ndefault
 299                + val_t::ncopy
 300                + val_t::nassign
 301                + val_t::ndtor, 0);
 302
 303     for (int i = 0; i < N_elem; ++i)
 304       {
 305         m.get_or_insert (a[i]);
 306         ASSERT_EQ (val_t::ndefault, 1 + i);
 307         ASSERT_EQ (val_t::ncopy, 0);
 308         ASSERT_EQ (val_t::nassign, 0);
 309         ASSERT_EQ (val_t::ndtor, i);
 310
 311         m.remove (a[i]);
 312         ASSERT_EQ (val_t::ndefault, 1 + i);
 313         ASSERT_EQ (val_t::ncopy, 0);
 314         ASSERT_EQ (val_t::nassign, 0);
 315         ASSERT_EQ (val_t::ndtor, 1 + i);
 316       }
 317   }
 318 }
 319
 320 /* Verify aspects of 'hash_table::expand', in particular that it doesn't leak
 321    Value objects.  */
 322
 323 static void
 324 test_map_of_type_with_ctor_and_dtor_expand (bool remove_some_inline)
 325 {
 326   /* Configure, so that hash table expansion triggers a few times.  */
 327   const size_t N_init = 0;
 328   const int N_elem = 70;
 329   size_t expand_c_expected = 4;
 330   size_t expand_c = 0;
 331
 332   /* For stability of this testing, we need all Key values 'k' to produce
 333      unique hash values 'Traits::hash (k)', as otherwise the dynamic
 334      insert/remove behavior may diverge across different architectures.  This
 335      is, for example, a problem when using the standard 'pointer_hash::hash',
 336      which is simply doing a 'k >> 3' operation, which is fine on 64-bit
 337      architectures, but on 32-bit architectures produces the same hash value
 338      for subsequent 'a[i] = &a[i]' array elements.  Therefore, use an
 339      'int_hash'.  */
 340
 341   int a[N_elem];
 342   for (size_t i = 0; i < N_elem; ++i)
 343     a[i] = i;
 344
 345   const int EMPTY = -1;
 346   const int DELETED = -2;
 347   typedef hash_map<int_hash<int, EMPTY, DELETED>, val_t> Map;
 348
 349   /* Note that we are starting with a fresh 'Map'.  Even if an existing one has
 350      been cleared out completely, there remain 'deleted' elements, and these
 351      would disturb the following logic, where we don't have access to the
 352      actual 'm_n_deleted' value.  */
 353   size_t m_n_deleted = 0;
 354
 355   val_t::ndefault = 0;
 356   val_t::ncopy = 0;
 357   val_t::nassign = 0;
 358   val_t::ndtor = 0;
 359   Map m (N_init);
 360
 361   /* In the following, in particular related to 'expand', we're adapting from
 362      the internal logic of 'hash_table', glossing over "some details" not
 363      relevant for this testing here.  */
 364
 365   /* Per 'hash_table::hash_table'.  */
 366   size_t m_size;
 367   {
 368     unsigned int size_prime_index_ = hash_table_higher_prime_index (N_init);
 369     m_size = prime_tab[size_prime_index_].prime;
 370   }
 371
 372   int n_expand_moved = 0;
 373
 374   for (int i = 0; i < N_elem; ++i)
 375     {
 376       size_t elts = m.elements ();
 377
 378       /* Per 'hash_table::find_slot_with_hash'.  */
 379       size_t m_n_elements = elts + m_n_deleted;
 380       bool expand = m_size * 3 <= m_n_elements * 4;
 381
 382       m.get_or_insert (a[i]);
 383       if (expand)
 384         {
 385           ++expand_c;
 386
 387           /* Per 'hash_table::expand'.  */
 388           {
 389             unsigned int nindex = hash_table_higher_prime_index (elts * 2);
 390             m_size = prime_tab[nindex].prime;
 391           }
 392           m_n_deleted = 0;
 393
 394           /* All non-deleted elements have been moved.  */
 395           n_expand_moved += i;
 396           if (remove_some_inline)
 397             n_expand_moved -= (i + 2) / 3;
 398         }
 399
 400       ASSERT_EQ (val_t::ndefault, 1 + i);
 401       ASSERT_EQ (val_t::ncopy, n_expand_moved);
 402       ASSERT_EQ (val_t::nassign, 0);
 403       if (remove_some_inline)
 404         ASSERT_EQ (val_t::ndtor, n_expand_moved + (i + 2) / 3);
 405       else
 406         ASSERT_EQ (val_t::ndtor, n_expand_moved);
 407
 408       /* Remove some inline.  This never triggers an 'expand' here, but via
 409          'm_n_deleted' does influence any following one.  */
 410       if (remove_some_inline
 411           && !(i % 3))
 412         {
 413           m.remove (a[i]);
 414           /* Per 'hash_table::remove_elt_with_hash'.  */
 415           m_n_deleted++;
 416
 417           ASSERT_EQ (val_t::ndefault, 1 + i);
 418           ASSERT_EQ (val_t::ncopy, n_expand_moved);
 419           ASSERT_EQ (val_t::nassign, 0);
 420           ASSERT_EQ (val_t::ndtor, n_expand_moved + 1 + (i + 2) / 3);
 421         }
 422     }
 423   ASSERT_EQ (expand_c, expand_c_expected);
 424
 425   int ndefault = val_t::ndefault;
 426   int ncopy = val_t::ncopy;
 427   int nassign = val_t::nassign;
 428   int ndtor = val_t::ndtor;
 429
 430   for (int i = 0; i < N_elem; ++i)
 431     {
 432       if (remove_some_inline
 433           && !(i % 3))
 434         continue;
 435
 436       m.remove (a[i]);
 437       ++ndtor;
 438       ASSERT_EQ (val_t::ndefault, ndefault);
 439       ASSERT_EQ (val_t::ncopy, ncopy);
 440       ASSERT_EQ (val_t::nassign, nassign);
 441       ASSERT_EQ (val_t::ndtor, ndtor);
 442     }
 443   ASSERT_EQ (val_t::ndefault + val_t::ncopy, val_t::ndtor);
 444 }
 445
 446 /* Test calling empty on a hash_map that has a key type with non-zero
 447    "empty" value.  */
 448
 449 static void
 450 test_nonzero_empty_key ()
 451 {
 452   typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
 453   hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
 454
 455   for (int i = 1; i != 32; ++i)
 456     x.put (i, i);
 457
 458   ASSERT_EQ (x.get (0), NULL);
 459   ASSERT_EQ (*x.get (1), 1);
 460
 461   x.empty ();
 462
 463   ASSERT_EQ (x.get (0), NULL);
 464   ASSERT_EQ (x.get (1), NULL);
 465 }
 466
 467 /* Run all of the selftests within this file.  */
 468
 469 void
 470 hash_map_tests_c_tests ()
 471 {
 472   test_map_of_strings_to_int ();
 473   test_map_of_int_to_strings ();
 474   test_map_of_type_with_ctor_and_dtor ();
 475   test_map_of_type_with_ctor_and_dtor_expand (false);
 476   test_map_of_type_with_ctor_and_dtor_expand (true);
 477   test_nonzero_empty_key ();
 478 }
 479
 480 } // namespace selftest
 481
 482 #endif /* CHECKING_P */