gcc/ordered-hash-map-tests.cc

   1 /* Unit tests for ordered-hash-map.h.
   2    Copyright (C) 2015-2023 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 "ordered-hash-map.h"
  35 #include "selftest.h"
  36
  37 #if CHECKING_P
  38
  39 namespace selftest {
  40
  41 /* Populate *OUT_KVS with the key/value pairs of M.  */
  42
  43 template <typename HashMap, typename Key, typename Value>
  44 static void
  45 get_kv_pairs (const HashMap &m,
  46               auto_vec<std::pair<Key, Value> > *out_kvs)
  47 {
  48   for (typename HashMap::iterator iter = m.begin ();
  49        iter != m.end ();
  50        ++iter)
  51     out_kvs->safe_push (std::make_pair ((*iter).first, (*iter).second));
  52 }
  53
  54 /* Construct an ordered_hash_map <const char *, int> and verify that
  55    various operations work correctly.  */
  56
  57 static void
  58 test_map_of_strings_to_int ()
  59 {
  60   ordered_hash_map <const char *, int> m;
  61   bool existed;
  62
  63   const char *ostrich = "ostrich";
  64   const char *elephant = "elephant";
  65   const char *ant = "ant";
  66   const char *spider = "spider";
  67   const char *millipede = "Illacme plenipes";
  68   const char *eric = "half a bee";
  69
  70   /* A fresh hash_map should be empty.  */
  71   ASSERT_EQ (0, m.elements ());
  72   ASSERT_EQ (NULL, m.get (ostrich));
  73
  74   /* Populate the hash_map.  */
  75   ASSERT_EQ (false, m.put (ostrich, 2));
  76   ASSERT_EQ (false, m.put (elephant, 4));
  77   ASSERT_EQ (false, m.put (ant, 6));
  78   existed = true;
  79   int &value = m.get_or_insert (spider, &existed);
  80   value = 8;
  81   ASSERT_EQ (false, existed);
  82   ASSERT_EQ (false, m.put (millipede, 750));
  83   ASSERT_EQ (false, m.put (eric, 3));
  84
  85
  86   /* Verify that we can recover the stored values.  */
  87   ASSERT_EQ (6, m.elements ());
  88   ASSERT_EQ (2, *m.get (ostrich));
  89   ASSERT_EQ (4, *m.get (elephant));
  90   ASSERT_EQ (6, *m.get (ant));
  91   ASSERT_EQ (8, *m.get (spider));
  92   existed = false;
  93   ASSERT_EQ (750, m.get_or_insert (millipede, &existed));
  94   ASSERT_EQ (true, existed);
  95   ASSERT_EQ (3, *m.get (eric));
  96
  97   /* Verify that the order of insertion is preserved.  */
  98   auto_vec<std::pair<const char *, int> > kvs;
  99   get_kv_pairs (m, &kvs);
 100   ASSERT_EQ (kvs.length (), 6);
 101   ASSERT_EQ (kvs[0].first, ostrich);
 102   ASSERT_EQ (kvs[0].second, 2);
 103   ASSERT_EQ (kvs[1].first, elephant);
 104   ASSERT_EQ (kvs[1].second, 4);
 105   ASSERT_EQ (kvs[2].first, ant);
 106   ASSERT_EQ (kvs[2].second, 6);
 107   ASSERT_EQ (kvs[3].first, spider);
 108   ASSERT_EQ (kvs[3].second, 8);
 109   ASSERT_EQ (kvs[4].first, millipede);
 110   ASSERT_EQ (kvs[4].second, 750);
 111   ASSERT_EQ (kvs[5].first, eric);
 112   ASSERT_EQ (kvs[5].second, 3);
 113 }
 114
 115 /* Construct an ordered_hash_map using int_hash and verify that various
 116    operations work correctly.  */
 117
 118 static void
 119 test_map_of_int_to_strings ()
 120 {
 121   const int EMPTY = -1;
 122   const int DELETED = -2;
 123   bool existed;
 124   typedef int_hash <int, EMPTY, DELETED> int_hash_t;
 125   ordered_hash_map <int_hash_t, const char *> m;
 126
 127   const char *ostrich = "ostrich";
 128   const char *elephant = "elephant";
 129   const char *ant = "ant";
 130   const char *spider = "spider";
 131   const char *millipede = "Illacme plenipes";
 132   const char *eric = "half a bee";
 133
 134   /* A fresh hash_map should be empty.  */
 135   ASSERT_EQ (0, m.elements ());
 136   ASSERT_EQ (NULL, m.get (2));
 137
 138   /* Populate the hash_map.  */
 139   ASSERT_EQ (false, m.put (2, ostrich));
 140   ASSERT_EQ (false, m.put (4, elephant));
 141   ASSERT_EQ (false, m.put (6, ant));
 142   const char* &value = m.get_or_insert (8, &existed);
 143   value = spider;
 144   ASSERT_EQ (false, existed);
 145   ASSERT_EQ (false, m.put (750, millipede));
 146   ASSERT_EQ (false, m.put (3, eric));
 147
 148   /* Verify that we can recover the stored values.  */
 149   ASSERT_EQ (6, m.elements ());
 150   ASSERT_EQ (*m.get (2), ostrich);
 151   ASSERT_EQ (*m.get (4), elephant);
 152   ASSERT_EQ (*m.get (6), ant);
 153   ASSERT_EQ (*m.get (8), spider);
 154   ASSERT_EQ (m.get_or_insert (750, &existed), millipede);
 155   ASSERT_EQ (existed, TRUE);
 156   ASSERT_EQ (*m.get (3), eric);
 157
 158   /* Verify that the order of insertion is preserved.  */
 159   auto_vec<std::pair<int, const char *> > kvs;
 160   get_kv_pairs (m, &kvs);
 161   ASSERT_EQ (kvs.length (), 6);
 162   ASSERT_EQ (kvs[0].first, 2);
 163   ASSERT_EQ (kvs[0].second, ostrich);
 164   ASSERT_EQ (kvs[1].first, 4);
 165   ASSERT_EQ (kvs[1].second, elephant);
 166   ASSERT_EQ (kvs[2].first, 6);
 167   ASSERT_EQ (kvs[2].second, ant);
 168   ASSERT_EQ (kvs[3].first, 8);
 169   ASSERT_EQ (kvs[3].second, spider);
 170   ASSERT_EQ (kvs[4].first, 750);
 171   ASSERT_EQ (kvs[4].second, millipede);
 172   ASSERT_EQ (kvs[5].first, 3);
 173   ASSERT_EQ (kvs[5].second, eric);
 174 }
 175
 176 /* Verify that we can remove items from an ordered_hash_map.  */
 177
 178 static void
 179 test_removal ()
 180 {
 181   ordered_hash_map <const char *, int> m;
 182
 183   const char *ostrich = "ostrich";
 184   ASSERT_EQ (false, m.put (ostrich, 2));
 185
 186   ASSERT_EQ (1, m.elements ());
 187   ASSERT_EQ (2, *m.get (ostrich));
 188
 189   {
 190     auto_vec<std::pair<const char *, int> > kvs;
 191     get_kv_pairs (m, &kvs);
 192     ASSERT_EQ (kvs.length (), 1);
 193     ASSERT_EQ (kvs[0].first, ostrich);
 194     ASSERT_EQ (kvs[0].second, 2);
 195   }
 196
 197   m.remove (ostrich);
 198
 199   ASSERT_EQ (0, m.elements ());
 200   {
 201     auto_vec<std::pair<const char *, int> > kvs;
 202     get_kv_pairs (m, &kvs);
 203     ASSERT_EQ (kvs.length (), 0);
 204   }
 205
 206   /* Reinsertion (with a different value).  */
 207   ASSERT_EQ (false, m.put (ostrich, 42));
 208   ASSERT_EQ (1, m.elements ());
 209   ASSERT_EQ (42, *m.get (ostrich));
 210   {
 211     auto_vec<std::pair<const char *, int> > kvs;
 212     get_kv_pairs (m, &kvs);
 213     ASSERT_EQ (kvs.length (), 1);
 214     ASSERT_EQ (kvs[0].first, ostrich);
 215     ASSERT_EQ (kvs[0].second, 42);
 216   }
 217 }
 218
 219 /* Verify that ordered_hash_map's copy-ctor works.  */
 220
 221 static void
 222 test_copy_ctor ()
 223 {
 224   ordered_hash_map <const char *, int> m;
 225
 226   const char *ostrich = "ostrich";
 227   ASSERT_EQ (false, m.put (ostrich, 2));
 228
 229   ASSERT_EQ (1, m.elements ());
 230   ASSERT_EQ (2, *m.get (ostrich));
 231
 232   ordered_hash_map <const char *, int> copy (m);
 233   ASSERT_EQ (1, copy.elements ());
 234   ASSERT_EQ (2, *copy.get (ostrich));
 235
 236   /* Remove from source.  */
 237   m.remove (ostrich);
 238   ASSERT_EQ (0, m.elements ());
 239
 240   /* Copy should be unaffected.  */
 241   ASSERT_EQ (1, copy.elements ());
 242   ASSERT_EQ (2, *copy.get (ostrich));
 243 }
 244
 245 /* Run all of the selftests within this file.  */
 246
 247 void
 248 ordered_hash_map_tests_cc_tests ()
 249 {
 250   test_map_of_strings_to_int ();
 251   test_map_of_int_to_strings ();
 252   test_removal ();
 253   test_copy_ctor ();
 254 }
 255
 256 } // namespace selftest
 257
 258 #endif /* CHECKING_P */