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 template<typename KeyId, typename Value,
  36          typename Traits /* = simple_hashmap_traits<default_hash_traits<Key>,
  37                                                     Value> */>
  38 class GTY((user)) hash_map
  39 {
  40   typedef typename Traits::key_type Key;
  41   struct hash_entry
  42   {
  43     Key m_key;
  44     Value m_value;
  45
  46     typedef hash_entry value_type;
  47     typedef Key compare_type;
  48
  49     static hashval_t hash (const hash_entry &e)
  50       {
  51         return Traits::hash (e.m_key);
  52       }
  53
  54     static bool equal (const hash_entry &a, const Key &b)
  55         {
  56           return Traits::equal_keys (a.m_key, b);
  57         }
  58
  59     static void remove (hash_entry &e) { Traits::remove (e); }
  60
  61     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
  62
  63     static bool is_deleted (const hash_entry &e)
  64       {
  65         return Traits::is_deleted (e);
  66       }
  67
  68     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
  69     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
  70
  71     static void ggc_mx (hash_entry &e)
  72       {
  73         gt_ggc_mx (e.m_key);
  74         gt_ggc_mx (e.m_value);
  75       }
  76
  77     static void ggc_maybe_mx (hash_entry &e)
  78       {
  79         if (Traits::maybe_mx)
  80           ggc_mx (e);
  81       }
  82
  83     static void pch_nx (hash_entry &e)
  84       {
  85         gt_pch_nx (e.m_key);
  86         gt_pch_nx (e.m_value);
  87       }
  88
  89     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
  90       {
  91         pch_nx_helper (e.m_key, op, c);
  92         pch_nx_helper (e.m_value, op, c);
  93       }
  94
  95     static int keep_cache_entry (hash_entry &e)
  96       {
  97         return ggc_marked_p (e.m_key);
  98       }
  99
 100   private:
 101     template<typename T>
 102     static void
 103       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
 104         {
 105           gt_pch_nx (&x, op, cookie);
 106         }
 107
 108     static void
 109       pch_nx_helper (int, gt_pointer_operator, void *)
 110         {
 111         }
 112
 113     static void
 114       pch_nx_helper (unsigned int, gt_pointer_operator, void *)
 115         {
 116         }
 117
 118     static void
 119       pch_nx_helper (bool, gt_pointer_operator, void *)
 120         {
 121         }
 122
 123     template<typename T>
 124       static void
 125       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 126         {
 127           op (&x, cookie);
 128         }
 129   };
 130
 131 public:
 132   explicit hash_map (size_t n = 13, bool ggc = false,
 133                      bool sanitize_eq_and_hash = true,
 134                      bool gather_mem_stats = GATHER_STATISTICS
 135                      CXX_MEM_STAT_INFO)
 136     : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
 137                HASH_MAP_ORIGIN PASS_MEM_STAT)
 138   {
 139   }
 140
 141   explicit hash_map (const hash_map &h, bool ggc = false,
 142                      bool sanitize_eq_and_hash = true,
 143                      bool gather_mem_stats = GATHER_STATISTICS
 144                      CXX_MEM_STAT_INFO)
 145     : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats,
 146                HASH_MAP_ORIGIN PASS_MEM_STAT) {}
 147
 148   /* Create a hash_map in ggc memory.  */
 149   static hash_map *create_ggc (size_t size,
 150                                bool gather_mem_stats = GATHER_STATISTICS
 151                                CXX_MEM_STAT_INFO)
 152     {
 153       hash_map *map = ggc_alloc<hash_map> ();
 154       new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
 155       return map;
 156     }
 157
 158   /* If key k isn't already in the map add key k with value v to the map, and
 159      return false.  Otherwise set the value of the entry for key k to be v and
 160      return true.  */
 161
 162   bool put (const Key &k, const Value &v)
 163     {
 164       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 165                                                    INSERT);
 166       bool ins = hash_entry::is_empty (*e);
 167       if (ins)
 168         {
 169           e->m_key = k;
 170           new ((void *) &e->m_value) Value (v);
 171         }
 172       else
 173         e->m_value = v;
 174
 175       return !ins;
 176     }
 177
 178   /* if the passed in key is in the map return its value otherwise NULL.  */
 179
 180   Value *get (const Key &k)
 181     {
 182       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 183       return Traits::is_empty (e) ? NULL : &e.m_value;
 184     }
 185
 186   /* Return a reference to the value for the passed in key, creating the entry
 187      if it doesn't already exist.  If existed is not NULL then it is set to
 188      false if the key was not previously in the map, and true otherwise.  */
 189
 190   Value &get_or_insert (const Key &k, bool *existed = NULL)
 191     {
 192       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 193                                                    INSERT);
 194       bool ins = Traits::is_empty (*e);
 195       if (ins)
 196         {
 197           e->m_key = k;
 198           new ((void *)&e->m_value) Value ();
 199         }
 200
 201       if (existed != NULL)
 202         *existed = !ins;
 203
 204       return e->m_value;
 205     }
 206
 207   void remove (const Key &k)
 208     {
 209       m_table.remove_elt_with_hash (k, Traits::hash (k));
 210     }
 211
 212   /* Call the call back on each pair of key and value with the passed in
 213      arg.  */
 214
 215   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 216                                    const Value &, Arg)>
 217   void traverse (Arg a) const
 218     {
 219       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 220            iter != m_table.end (); ++iter)
 221         f ((*iter).m_key, (*iter).m_value, a);
 222     }
 223
 224   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 225                                    Value *, Arg)>
 226   void traverse (Arg a) const
 227     {
 228       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 229            iter != m_table.end (); ++iter)
 230         if (!f ((*iter).m_key, &(*iter).m_value, a))
 231           break;
 232     }
 233
 234   size_t elements () const { return m_table.elements (); }
 235
 236   void empty () { m_table.empty(); }
 237
 238   /* Return true when there are no elements in this hash map.  */
 239   bool is_empty () const { return m_table.is_empty (); }
 240
 241   class iterator
 242   {
 243   public:
 244     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 245       m_iter (iter) {}
 246
 247     iterator &operator++ ()
 248     {
 249       ++m_iter;
 250       return *this;
 251     }
 252
 253     /* Can't use std::pair here, because GCC before 4.3 don't handle
 254        std::pair where template parameters are references well.
 255        See PR86739.  */
 256     class reference_pair {
 257     public:
 258       const Key &first;
 259       Value &second;
 260
 261       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
 262
 263       template <typename K, typename V>
 264       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
 265     };
 266
 267     reference_pair operator* ()
 268     {
 269       hash_entry &e = *m_iter;
 270       return reference_pair (e.m_key, e.m_value);
 271     }
 272
 273     bool
 274     operator != (const iterator &other) const
 275     {
 276       return m_iter != other.m_iter;
 277     }
 278
 279   private:
 280     typename hash_table<hash_entry>::iterator m_iter;
 281   };
 282
 283   /* Standard iterator retrieval methods.  */
 284
 285   iterator  begin () const { return iterator (m_table.begin ()); }
 286   iterator end () const { return iterator (m_table.end ()); }
 287
 288 private:
 289
 290   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 291   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 292   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 293   template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
 294
 295   hash_table<hash_entry> m_table;
 296 };
 297
 298 /* ggc marking routines.  */
 299
 300 template<typename K, typename V, typename H>
 301 static inline void
 302 gt_ggc_mx (hash_map<K, V, H> *h)
 303 {
 304   gt_ggc_mx (&h->m_table);
 305 }
 306
 307 template<typename K, typename V, typename H>
 308 static inline void
 309 gt_pch_nx (hash_map<K, V, H> *h)
 310 {
 311   gt_pch_nx (&h->m_table);
 312 }
 313
 314 template<typename K, typename V, typename H>
 315 static inline void
 316 gt_cleare_cache (hash_map<K, V, H> *h)
 317 {
 318   if (h)
 319     gt_cleare_cache (&h->m_table);
 320 }
 321
 322 template<typename K, typename V, typename H>
 323 static inline void
 324 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 325 {
 326   op (&h->m_table.m_entries, cookie);
 327 }
 328
 329 #endif