gcc/hash-map.h

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