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