gcc/hash-map.h

   1 /* A type-safe hash map.
   2    Copyright (C) 2014-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
  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       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 171                                                    INSERT);
 172       bool ins = Traits::is_empty (*e);
 173       if (ins)
 174         {
 175           e->m_key = k;
 176           new ((void *)&e->m_value) Value (v);
 177           gcc_checking_assert (!Traits::is_empty (*e)
 178                                && !Traits::is_deleted (*e));
 179         }
 180       else
 181         e->m_value = v;
 182
 183       return !ins;
 184     }
 185
 186   /* If the passed in key is in the map return pointer to its value
 187      otherwise NULL.  */
 188
 189   Value *get (const Key &k)
 190     {
 191       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 192       return Traits::is_empty (e) ? NULL : &e.m_value;
 193     }
 194
 195   /* Return a reference to the value for the passed in key, creating the entry
 196      if it doesn't already exist.  If existed is not NULL then it is set to
 197      false if the key was not previously in the map, and true otherwise.  */
 198
 199   Value &get_or_insert (const Key &k, bool *existed = NULL)
 200     {
 201       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 202                                                    INSERT);
 203       bool ins = Traits::is_empty (*e);
 204       if (ins)
 205         {
 206           e->m_key = k;
 207           new ((void *)&e->m_value) Value ();
 208           gcc_checking_assert (!Traits::is_empty (*e)
 209                                && !Traits::is_deleted (*e));
 210         }
 211
 212       if (existed != NULL)
 213         *existed = !ins;
 214
 215       return e->m_value;
 216     }
 217
 218   void remove (const Key &k)
 219     {
 220       m_table.remove_elt_with_hash (k, Traits::hash (k));
 221     }
 222
 223   /* Call the call back on each pair of key and value with the passed in
 224      arg until either the call back returns false or all pairs have been seen.
 225      The traversal is unordered.  */
 226
 227   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 228                                    const Value &, Arg)>
 229   void traverse (Arg a) const
 230     {
 231       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 232            iter != m_table.end (); ++iter)
 233         if (!f ((*iter).m_key, (*iter).m_value, a))
 234           break;
 235     }
 236
 237   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 238                                    Value *, Arg)>
 239   void traverse (Arg a) const
 240     {
 241       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 242            iter != m_table.end (); ++iter)
 243         if (!f ((*iter).m_key, &(*iter).m_value, a))
 244           break;
 245     }
 246
 247   size_t elements () const { return m_table.elements (); }
 248
 249   void empty () { m_table.empty(); }
 250
 251   /* Return true when there are no elements in this hash map.  */
 252   bool is_empty () const { return m_table.is_empty (); }
 253
 254   class iterator
 255   {
 256   public:
 257     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 258       m_iter (iter) {}
 259
 260     iterator &operator++ ()
 261     {
 262       ++m_iter;
 263       return *this;
 264     }
 265
 266     /* Can't use std::pair here, because GCC before 4.3 don't handle
 267        std::pair where template parameters are references well.
 268        See PR86739.  */
 269     class reference_pair {
 270     public:
 271       const Key &first;
 272       Value &second;
 273
 274       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
 275
 276       template <typename K, typename V>
 277       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
 278     };
 279
 280     reference_pair operator* ()
 281     {
 282       hash_entry &e = *m_iter;
 283       return reference_pair (e.m_key, e.m_value);
 284     }
 285
 286     bool operator== (const iterator &other) const
 287     {
 288       return m_iter == other.m_iter;
 289     }
 290
 291     bool operator != (const iterator &other) const
 292     {
 293       return m_iter != other.m_iter;
 294     }
 295
 296   private:
 297     typename hash_table<hash_entry>::iterator m_iter;
 298   };
 299
 300   /* Standard iterator retrieval methods.  */
 301
 302   iterator  begin () const { return iterator (m_table.begin ()); }
 303   iterator end () const { return iterator (m_table.end ()); }
 304
 305 private:
 306
 307   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 308   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 309   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 310   template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
 311
 312   hash_table<hash_entry> m_table;
 313 };
 314
 315 /* ggc marking routines.  */
 316
 317 template<typename K, typename V, typename H>
 318 static inline void
 319 gt_ggc_mx (hash_map<K, V, H> *h)
 320 {
 321   gt_ggc_mx (&h->m_table);
 322 }
 323
 324 template<typename K, typename V, typename H>
 325 static inline void
 326 gt_pch_nx (hash_map<K, V, H> *h)
 327 {
 328   gt_pch_nx (&h->m_table);
 329 }
 330
 331 template<typename K, typename V, typename H>
 332 static inline void
 333 gt_cleare_cache (hash_map<K, V, H> *h)
 334 {
 335   if (h)
 336     gt_cleare_cache (&h->m_table);
 337 }
 338
 339 template<typename K, typename V, typename H>
 340 static inline void
 341 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 342 {
 343   op (&h->m_table.m_entries, NULL, cookie);
 344 }
 345
 346 enum hm_alloc { hm_heap = false, hm_ggc = true };
 347 template<bool ggc, typename K, typename V, typename H>
 348 inline hash_map<K,V,H> *
 349 hash_map_maybe_create (hash_map<K,V,H> *&h,
 350                        size_t size = default_hash_map_size)
 351 {
 352   if (!h)
 353     {
 354       if (ggc)
 355         h = hash_map<K,V,H>::create_ggc (size);
 356       else
 357         h = new hash_map<K,V,H> (size);
 358     }
 359   return h;
 360 }
 361
 362 /* Like h->get, but handles null h.  */
 363 template<typename K, typename V, typename H>
 364 inline V*
 365 hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
 366 {
 367   return h ? h->get (k) : NULL;
 368 }
 369
 370 /* Like h->get, but handles null h.  */
 371 template<bool ggc, typename K, typename V, typename H>
 372 inline V&
 373 hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
 374                              size_t size = default_hash_map_size)
 375 {
 376   return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
 377 }
 378
 379 /* Like h->put, but handles null h.  */
 380 template<bool ggc, typename K, typename V, typename H>
 381 inline bool
 382 hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
 383                    size_t size = default_hash_map_size)
 384 {
 385   return hash_map_maybe_create<ggc> (h, size)->put (k, v);
 386 }
 387
 388 #endif