gcc/hash-map.h

   1 /* A type-safe hash map.
   2    Copyright (C) 2014-2020 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     static void
 111       pch_nx_helper (int, gt_pointer_operator, void *)
 112         {
 113         }
 114
 115     static void
 116       pch_nx_helper (unsigned int, gt_pointer_operator, void *)
 117         {
 118         }
 119
 120     static void
 121       pch_nx_helper (bool, gt_pointer_operator, void *)
 122         {
 123         }
 124
 125     template<typename T>
 126       static void
 127       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 128         {
 129           op (&x, cookie);
 130         }
 131   };
 132
 133 public:
 134   explicit hash_map (size_t n = default_hash_map_size, bool ggc = false,
 135                      bool sanitize_eq_and_hash = true,
 136                      bool gather_mem_stats = GATHER_STATISTICS
 137                      CXX_MEM_STAT_INFO)
 138     : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
 139                HASH_MAP_ORIGIN PASS_MEM_STAT)
 140   {
 141   }
 142
 143   explicit hash_map (const hash_map &h, bool ggc = false,
 144                      bool sanitize_eq_and_hash = true,
 145                      bool gather_mem_stats = GATHER_STATISTICS
 146                      CXX_MEM_STAT_INFO)
 147     : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats,
 148                HASH_MAP_ORIGIN PASS_MEM_STAT) {}
 149
 150   /* Create a hash_map in ggc memory.  */
 151   static hash_map *create_ggc (size_t size = default_hash_map_size,
 152                                bool gather_mem_stats = GATHER_STATISTICS
 153                                CXX_MEM_STAT_INFO)
 154     {
 155       hash_map *map = ggc_alloc<hash_map> ();
 156       new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
 157       return map;
 158     }
 159
 160   /* If key k isn't already in the map add key k with value v to the map, and
 161      return false.  Otherwise set the value of the entry for key k to be v and
 162      return true.  */
 163
 164   bool put (const Key &k, const Value &v)
 165     {
 166       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 167                                                    INSERT);
 168       bool ins = hash_entry::is_empty (*e);
 169       if (ins)
 170         {
 171           e->m_key = k;
 172           new ((void *) &e->m_value) Value (v);
 173         }
 174       else
 175         e->m_value = v;
 176
 177       return !ins;
 178     }
 179
 180   /* If the passed in key is in the map return pointer to its value
 181      otherwise NULL.  */
 182
 183   Value *get (const Key &k)
 184     {
 185       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 186       return Traits::is_empty (e) ? NULL : &e.m_value;
 187     }
 188
 189   /* Return a reference to the value for the passed in key, creating the entry
 190      if it doesn't already exist.  If existed is not NULL then it is set to
 191      false if the key was not previously in the map, and true otherwise.  */
 192
 193   Value &get_or_insert (const Key &k, bool *existed = NULL)
 194     {
 195       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 196                                                    INSERT);
 197       bool ins = Traits::is_empty (*e);
 198       if (ins)
 199         {
 200           e->m_key = k;
 201           new ((void *)&e->m_value) Value ();
 202         }
 203
 204       if (existed != NULL)
 205         *existed = !ins;
 206
 207       return e->m_value;
 208     }
 209
 210   void remove (const Key &k)
 211     {
 212       m_table.remove_elt_with_hash (k, Traits::hash (k));
 213     }
 214
 215   /* Call the call back on each pair of key and value with the passed in
 216      arg.  */
 217
 218   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 219                                    const Value &, Arg)>
 220   void traverse (Arg a) const
 221     {
 222       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 223            iter != m_table.end (); ++iter)
 224         f ((*iter).m_key, (*iter).m_value, a);
 225     }
 226
 227   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 228                                    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   size_t elements () const { return m_table.elements (); }
 238
 239   void empty () { m_table.empty(); }
 240
 241   /* Return true when there are no elements in this hash map.  */
 242   bool is_empty () const { return m_table.is_empty (); }
 243
 244   class iterator
 245   {
 246   public:
 247     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 248       m_iter (iter) {}
 249
 250     iterator &operator++ ()
 251     {
 252       ++m_iter;
 253       return *this;
 254     }
 255
 256     /* Can't use std::pair here, because GCC before 4.3 don't handle
 257        std::pair where template parameters are references well.
 258        See PR86739.  */
 259     class reference_pair {
 260     public:
 261       const Key &first;
 262       Value &second;
 263
 264       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
 265
 266       template <typename K, typename V>
 267       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
 268     };
 269
 270     reference_pair operator* ()
 271     {
 272       hash_entry &e = *m_iter;
 273       return reference_pair (e.m_key, e.m_value);
 274     }
 275
 276     bool
 277     operator != (const iterator &other) const
 278     {
 279       return m_iter != other.m_iter;
 280     }
 281
 282   private:
 283     typename hash_table<hash_entry>::iterator m_iter;
 284   };
 285
 286   /* Standard iterator retrieval methods.  */
 287
 288   iterator  begin () const { return iterator (m_table.begin ()); }
 289   iterator end () const { return iterator (m_table.end ()); }
 290
 291 private:
 292
 293   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 294   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 295   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 296   template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
 297
 298   hash_table<hash_entry> m_table;
 299 };
 300
 301 /* ggc marking routines.  */
 302
 303 template<typename K, typename V, typename H>
 304 static inline void
 305 gt_ggc_mx (hash_map<K, V, H> *h)
 306 {
 307   gt_ggc_mx (&h->m_table);
 308 }
 309
 310 template<typename K, typename V, typename H>
 311 static inline void
 312 gt_pch_nx (hash_map<K, V, H> *h)
 313 {
 314   gt_pch_nx (&h->m_table);
 315 }
 316
 317 template<typename K, typename V, typename H>
 318 static inline void
 319 gt_cleare_cache (hash_map<K, V, H> *h)
 320 {
 321   if (h)
 322     gt_cleare_cache (&h->m_table);
 323 }
 324
 325 template<typename K, typename V, typename H>
 326 static inline void
 327 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 328 {
 329   op (&h->m_table.m_entries, cookie);
 330 }
 331
 332 enum hm_alloc { hm_heap = false, hm_ggc = true };
 333 template<bool ggc, typename K, typename V, typename H>
 334 inline hash_map<K,V,H> *
 335 hash_map_maybe_create (hash_map<K,V,H> *&h,
 336                        size_t size = default_hash_map_size)
 337 {
 338   if (!h)
 339     {
 340       if (ggc)
 341         h = hash_map<K,V,H>::create_ggc (size);
 342       else
 343         h = new hash_map<K,V,H> (size);
 344     }
 345   return h;
 346 }
 347
 348 /* Like h->get, but handles null h.  */
 349 template<typename K, typename V, typename H>
 350 inline V*
 351 hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
 352 {
 353   return h ? h->get (k) : NULL;
 354 }
 355
 356 /* Like h->get, but handles null h.  */
 357 template<bool ggc, typename K, typename V, typename H>
 358 inline V&
 359 hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
 360                              size_t size = default_hash_map_size)
 361 {
 362   return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
 363 }
 364
 365 /* Like h->put, but handles null h.  */
 366 template<bool ggc, typename K, typename V, typename H>
 367 inline bool
 368 hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
 369                    size_t size = default_hash_map_size)
 370 {
 371   return hash_map_maybe_create<ggc> (h, size)->put (k, v);
 372 }
 373
 374 #endif