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