gcc/hash-map.h

   1 /* A type-safe hash map.
   2    Copyright (C) 2014-2021 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, 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.  */
 221
 222   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 223                                    const Value &, Arg)>
 224   void traverse (Arg a) const
 225     {
 226       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 227            iter != m_table.end (); ++iter)
 228         f ((*iter).m_key, (*iter).m_value, a);
 229     }
 230
 231   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 232                                    Value *, Arg)>
 233   void traverse (Arg a) const
 234     {
 235       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 236            iter != m_table.end (); ++iter)
 237         if (!f ((*iter).m_key, &(*iter).m_value, a))
 238           break;
 239     }
 240
 241   size_t elements () const { return m_table.elements (); }
 242
 243   void empty () { m_table.empty(); }
 244
 245   /* Return true when there are no elements in this hash map.  */
 246   bool is_empty () const { return m_table.is_empty (); }
 247
 248   class iterator
 249   {
 250   public:
 251     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 252       m_iter (iter) {}
 253
 254     iterator &operator++ ()
 255     {
 256       ++m_iter;
 257       return *this;
 258     }
 259
 260     /* Can't use std::pair here, because GCC before 4.3 don't handle
 261        std::pair where template parameters are references well.
 262        See PR86739.  */
 263     class reference_pair {
 264     public:
 265       const Key &first;
 266       Value &second;
 267
 268       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
 269
 270       template <typename K, typename V>
 271       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
 272     };
 273
 274     reference_pair operator* ()
 275     {
 276       hash_entry &e = *m_iter;
 277       return reference_pair (e.m_key, e.m_value);
 278     }
 279
 280     bool operator== (const iterator &other) const
 281     {
 282       return m_iter == other.m_iter;
 283     }
 284
 285     bool operator != (const iterator &other) const
 286     {
 287       return m_iter != other.m_iter;
 288     }
 289
 290   private:
 291     typename hash_table<hash_entry>::iterator m_iter;
 292   };
 293
 294   /* Standard iterator retrieval methods.  */
 295
 296   iterator  begin () const { return iterator (m_table.begin ()); }
 297   iterator end () const { return iterator (m_table.end ()); }
 298
 299 private:
 300
 301   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 302   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 303   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 304   template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
 305
 306   hash_table<hash_entry> m_table;
 307 };
 308
 309 /* ggc marking routines.  */
 310
 311 template<typename K, typename V, typename H>
 312 static inline void
 313 gt_ggc_mx (hash_map<K, V, H> *h)
 314 {
 315   gt_ggc_mx (&h->m_table);
 316 }
 317
 318 template<typename K, typename V, typename H>
 319 static inline void
 320 gt_pch_nx (hash_map<K, V, H> *h)
 321 {
 322   gt_pch_nx (&h->m_table);
 323 }
 324
 325 template<typename K, typename V, typename H>
 326 static inline void
 327 gt_cleare_cache (hash_map<K, V, H> *h)
 328 {
 329   if (h)
 330     gt_cleare_cache (&h->m_table);
 331 }
 332
 333 template<typename K, typename V, typename H>
 334 static inline void
 335 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 336 {
 337   op (&h->m_table.m_entries, cookie);
 338 }
 339
 340 enum hm_alloc { hm_heap = false, hm_ggc = true };
 341 template<bool ggc, typename K, typename V, typename H>
 342 inline hash_map<K,V,H> *
 343 hash_map_maybe_create (hash_map<K,V,H> *&h,
 344                        size_t size = default_hash_map_size)
 345 {
 346   if (!h)
 347     {
 348       if (ggc)
 349         h = hash_map<K,V,H>::create_ggc (size);
 350       else
 351         h = new hash_map<K,V,H> (size);
 352     }
 353   return h;
 354 }
 355
 356 /* Like h->get, but handles null h.  */
 357 template<typename K, typename V, typename H>
 358 inline V*
 359 hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
 360 {
 361   return h ? h->get (k) : NULL;
 362 }
 363
 364 /* Like h->get, but handles null h.  */
 365 template<bool ggc, typename K, typename V, typename H>
 366 inline V&
 367 hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
 368                              size_t size = default_hash_map_size)
 369 {
 370   return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
 371 }
 372
 373 /* Like h->put, but handles null h.  */
 374 template<bool ggc, typename K, typename V, typename H>
 375 inline bool
 376 hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
 377                    size_t size = default_hash_map_size)
 378 {
 379   return hash_map_maybe_create<ggc> (h, size)->put (k, v);
 380 }
 381
 382 #endif