gcc/hash-map-tests.c

   1 /* Unit tests for hash-map.h.
   2    Copyright (C) 2015-2020 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 /* Test calling empty on a hash_map that has a key type with non-zero
 284    "empty" value.  */
 285
 286 static void
 287 test_nonzero_empty_key ()
 288 {
 289   typedef int_hash<int, INT_MIN, INT_MAX> IntHash;
 290   hash_map<int, int, simple_hashmap_traits<IntHash, int> > x;
 291
 292   for (int i = 1; i != 32; ++i)
 293     x.put (i, i);
 294
 295   ASSERT_EQ (x.get (0), NULL);
 296   ASSERT_EQ (*x.get (1), 1);
 297
 298   x.empty ();
 299
 300   ASSERT_EQ (x.get (0), NULL);
 301   ASSERT_EQ (x.get (1), NULL);
 302 }
 303
 304 /* Run all of the selftests within this file.  */
 305
 306 void
 307 hash_map_tests_c_tests ()
 308 {
 309   test_map_of_strings_to_int ();
 310   test_map_of_int_to_strings ();
 311   test_map_of_type_with_ctor_and_dtor ();
 312   test_nonzero_empty_key ();
 313 }
 314
 315 } // namespace selftest
 316
 317 #endif /* CHECKING_P */