sdcc/support/cpp/gcc/hash-map.h

   1 /* A type-safe hash map.
   2    Copyright (C) 2014-2022 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
  21 #ifndef hash_map_h
  22 #define hash_map_h
  23
  24 /* Class hash_map is a hash-value based container mapping objects of
  25    KeyId type to those of the Value type.
  26    Both KeyId and Value may be non-trivial (non-POD) types provided
  27    a suitabe Traits class.  A few default Traits specializations are
  28    provided for basic types such as integers, pointers, and std::pair.
  29    Inserted elements are value-initialized either to zero for POD types
  30    or by invoking their default ctor.  Removed elements are destroyed
  31    by invoking their dtor.   On hash_map destruction all elements are
  32    removed.  Objects of hash_map type are copy-constructible but not
  33    assignable.  */
  34
  35 const size_t default_hash_map_size = 13;
  36 template<typename KeyId, typename Value,
  37          typename Traits /* = simple_hashmap_traits<default_hash_traits<Key>,
  38                                                     Value> */>
  39 class GTY((user)) hash_map
  40 {
  41   typedef typename Traits::key_type Key;
  42   struct hash_entry
  43   {
  44     Key m_key;
  45     Value m_value;
  46
  47     typedef hash_entry value_type;
  48     typedef Key compare_type;
  49
  50     static hashval_t hash (const hash_entry &e)
  51       {
  52         return Traits::hash (e.m_key);
  53       }
  54
  55     static bool equal (const hash_entry &a, const Key &b)
  56         {
  57           return Traits::equal_keys (a.m_key, b);
  58         }
  59
  60     static void remove (hash_entry &e) { Traits::remove (e); }
  61
  62     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
  63
  64     static bool is_deleted (const hash_entry &e)
  65       {
  66         return Traits::is_deleted (e);
  67       }
  68
  69     static const bool empty_zero_p = Traits::empty_zero_p;
  70     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
  71     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
  72
  73     static void ggc_mx (hash_entry &e)
  74       {
  75         gt_ggc_mx (e.m_key);
  76         gt_ggc_mx (e.m_value);
  77       }
  78
  79     static void ggc_maybe_mx (hash_entry &e)
  80       {
  81         if (Traits::maybe_mx)
  82           ggc_mx (e);
  83       }
  84
  85     static void pch_nx (hash_entry &e)
  86       {
  87         gt_pch_nx (e.m_key);
  88         gt_pch_nx (e.m_value);
  89       }
  90
  91     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
  92       {
  93         pch_nx_helper (e.m_key, op, c);
  94         pch_nx_helper (e.m_value, op, c);
  95       }
  96
  97     static int keep_cache_entry (hash_entry &e)
  98       {
  99         return ggc_marked_p (e.m_key);
 100       }
 101
 102   private:
 103     template<typename T>
 104     static void
 105       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
 106         {
 107           gt_pch_nx (&x, op, cookie);
 108         }
 109
 110     template<typename T>
 111       static void
 112       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 113         {
 114           op (&x, NULL, cookie);
 115         }
 116
 117     /* The overloads below should match those in ggc.h.  */
 118 #define DEFINE_PCH_HELPER(T)                    \
 119     static void pch_nx_helper (T, gt_pointer_operator, void *) { }
 120
 121     DEFINE_PCH_HELPER (bool);
 122     DEFINE_PCH_HELPER (char);
 123     DEFINE_PCH_HELPER (signed char);
 124     DEFINE_PCH_HELPER (unsigned char);
 125     DEFINE_PCH_HELPER (short);
 126     DEFINE_PCH_HELPER (unsigned short);
 127     DEFINE_PCH_HELPER (int);
 128     DEFINE_PCH_HELPER (unsigned int);
 129     DEFINE_PCH_HELPER (long);
 130     DEFINE_PCH_HELPER (unsigned long);
 131     DEFINE_PCH_HELPER (long long);
 132     DEFINE_PCH_HELPER (unsigned long long);
 133
 134 #undef DEFINE_PCH_HELPER
 135   };
 136
 137 public:
 138   explicit hash_map (size_t n = default_hash_map_size, bool ggc = false,
 139                      bool sanitize_eq_and_hash = true,
 140                      bool gather_mem_stats = GATHER_STATISTICS
 141                      CXX_MEM_STAT_INFO)
 142     : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
 143                HASH_MAP_ORIGIN PASS_MEM_STAT)
 144   {
 145   }
 146
 147   explicit hash_map (const hash_map &h, bool ggc = false,
 148                      bool sanitize_eq_and_hash = true,
 149                      bool gather_mem_stats = GATHER_STATISTICS
 150                      CXX_MEM_STAT_INFO)
 151     : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats,
 152                HASH_MAP_ORIGIN PASS_MEM_STAT) {}
 153
 154   /* Create a hash_map in ggc memory.  */
 155   static hash_map *create_ggc (size_t size = default_hash_map_size,
 156                                bool gather_mem_stats = GATHER_STATISTICS
 157                                CXX_MEM_STAT_INFO)
 158     {
 159       hash_map *map = ggc_alloc<hash_map> ();
 160       new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
 161       return map;
 162     }
 163
 164   /* If key k isn't already in the map add key k with value v to the map, and
 165      return false.  Otherwise set the value of the entry for key k to be v and
 166      return true.  */
 167
 168   bool put (const Key &k, const Value &v)
 169     {
 170 #if 1 //sdcpp
 171                  gcc_assert(false);
 172                  (void) k;
 173                  (void) v;
 174 #else // sdcpp
 175       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 176                                                    INSERT);
 177       bool ins = hash_entry::is_empty (*e);
 178       if (ins)
 179         {
 180           e->m_key = k;
 181           new ((void *) &e->m_value) Value (v);
 182         }
 183       else
 184         e->m_value = v;
 185
 186       return !ins;
 187 #endif // sdcpp
 188     }
 189
 190   /* If the passed in key is in the map return pointer to its value
 191      otherwise NULL.  */
 192
 193   Value *get (const Key &k)
 194     {
 195       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 196       return Traits::is_empty (e) ? NULL : &e.m_value;
 197     }
 198
 199   /* Return a reference to the value for the passed in key, creating the entry
 200      if it doesn't already exist.  If existed is not NULL then it is set to
 201      false if the key was not previously in the map, and true otherwise.  */
 202
 203   Value &get_or_insert (const Key &k, bool *existed = NULL)
 204     {
 205       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 206                                                    INSERT);
 207       bool ins = Traits::is_empty (*e);
 208       if (ins)
 209         {
 210           e->m_key = k;
 211           new ((void *)&e->m_value) Value ();
 212         }
 213
 214       if (existed != NULL)
 215         *existed = !ins;
 216
 217       return e->m_value;
 218     }
 219
 220   void remove (const Key &k)
 221     {
 222       m_table.remove_elt_with_hash (k, Traits::hash (k));
 223     }
 224
 225   /* Call the call back on each pair of key and value with the passed in
 226      arg until either the call back returns false or all pairs have been seen.
 227      The traversal is unordered.  */
 228
 229   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 230                                    const Value &, Arg)>
 231   void traverse (Arg a) const
 232     {
 233       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 234            iter != m_table.end (); ++iter)
 235         if (!f ((*iter).m_key, (*iter).m_value, a))
 236           break;
 237     }
 238
 239   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 240                                    Value *, Arg)>
 241   void traverse (Arg a) const
 242     {
 243       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 244            iter != m_table.end (); ++iter)
 245         if (!f ((*iter).m_key, &(*iter).m_value, a))
 246           break;
 247     }
 248
 249   size_t elements () const { return m_table.elements (); }
 250
 251   void empty () { m_table.empty(); }
 252
 253   /* Return true when there are no elements in this hash map.  */
 254   bool is_empty () const { return m_table.is_empty (); }
 255
 256   class iterator
 257   {
 258   public:
 259     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 260       m_iter (iter) {}
 261
 262     iterator &operator++ ()
 263     {
 264       ++m_iter;
 265       return *this;
 266     }
 267
 268     /* Can't use std::pair here, because GCC before 4.3 don't handle
 269        std::pair where template parameters are references well.
 270        See PR86739.  */
 271     class reference_pair {
 272     public:
 273       const Key &first;
 274       Value &second;
 275
 276       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
 277
 278       template <typename K, typename V>
 279       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
 280     };
 281
 282     reference_pair operator* ()
 283     {
 284       hash_entry &e = *m_iter;
 285       return reference_pair (e.m_key, e.m_value);
 286     }
 287
 288     bool operator== (const iterator &other) const
 289     {
 290       return m_iter == other.m_iter;
 291     }
 292
 293     bool operator != (const iterator &other) const
 294     {
 295       return m_iter != other.m_iter;
 296     }
 297
 298   private:
 299     typename hash_table<hash_entry>::iterator m_iter;
 300   };
 301
 302   /* Standard iterator retrieval methods.  */
 303
 304   iterator  begin () const { return iterator (m_table.begin ()); }
 305   iterator end () const { return iterator (m_table.end ()); }
 306
 307 private:
 308
 309   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 310   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 311   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 312   template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
 313
 314   hash_table<hash_entry> m_table;
 315 };
 316
 317 /* ggc marking routines.  */
 318
 319 template<typename K, typename V, typename H>
 320 static inline void
 321 gt_ggc_mx (hash_map<K, V, H> *h)
 322 {
 323   gt_ggc_mx (&h->m_table);
 324 }
 325
 326 template<typename K, typename V, typename H>
 327 static inline void
 328 gt_pch_nx (hash_map<K, V, H> *h)
 329 {
 330   gt_pch_nx (&h->m_table);
 331 }
 332
 333 template<typename K, typename V, typename H>
 334 static inline void
 335 gt_cleare_cache (hash_map<K, V, H> *h)
 336 {
 337   if (h)
 338     gt_cleare_cache (&h->m_table);
 339 }
 340
 341 template<typename K, typename V, typename H>
 342 static inline void
 343 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 344 {
 345   op (&h->m_table.m_entries, NULL, cookie);
 346 }
 347
 348 enum hm_alloc { hm_heap = false, hm_ggc = true };
 349 template<bool ggc, typename K, typename V, typename H>
 350 inline hash_map<K,V,H> *
 351 hash_map_maybe_create (hash_map<K,V,H> *&h,
 352                        size_t size = default_hash_map_size)
 353 {
 354   if (!h)
 355     {
 356       if (ggc)
 357         h = hash_map<K,V,H>::create_ggc (size);
 358       else
 359         h = new hash_map<K,V,H> (size);
 360     }
 361   return h;
 362 }
 363
 364 /* Like h->get, but handles null h.  */
 365 template<typename K, typename V, typename H>
 366 inline V*
 367 hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
 368 {
 369   return h ? h->get (k) : NULL;
 370 }
 371
 372 /* Like h->get, but handles null h.  */
 373 template<bool ggc, typename K, typename V, typename H>
 374 inline V&
 375 hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
 376                              size_t size = default_hash_map_size)
 377 {
 378   return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
 379 }
 380
 381 /* Like h->put, but handles null h.  */
 382 template<bool ggc, typename K, typename V, typename H>
 383 inline bool
 384 hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
 385                    size_t size = default_hash_map_size)
 386 {
 387   return hash_map_maybe_create<ggc> (h, size)->put (k, v);
 388 }
 389
 390 #endif