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