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, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {}
 124
 125   explicit hash_map (const hash_map &h, bool ggc = false,
 126                      bool gather_mem_stats = GATHER_STATISTICS
 127                      CXX_MEM_STAT_INFO)
 128     : m_table (h.m_table, ggc, gather_mem_stats,
 129                HASH_MAP_ORIGIN PASS_MEM_STAT) {}
 130
 131   /* Create a hash_map in ggc memory.  */
 132   static hash_map *create_ggc (size_t size,
 133                                bool gather_mem_stats = GATHER_STATISTICS
 134                                CXX_MEM_STAT_INFO)
 135     {
 136       hash_map *map = ggc_alloc<hash_map> ();
 137       new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT);
 138       return map;
 139     }
 140
 141   /* If key k isn't already in the map add key k with value v to the map, and
 142      return false.  Otherwise set the value of the entry for key k to be v and
 143      return true.  */
 144
 145   bool put (const Key &k, const Value &v)
 146     {
 147       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 148                                                    INSERT);
 149       bool existed = !hash_entry::is_empty (*e);
 150       if (!existed)
 151         e->m_key = k;
 152
 153       e->m_value = v;
 154       return existed;
 155     }
 156
 157   /* if the passed in key is in the map return its value otherwise NULL.  */
 158
 159   Value *get (const Key &k)
 160     {
 161       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 162       return Traits::is_empty (e) ? NULL : &e.m_value;
 163     }
 164
 165   /* Return a reference to the value for the passed in key, creating the entry
 166      if it doesn't already exist.  If existed is not NULL then it is set to false
 167      if the key was not previously in the map, and true otherwise.  */
 168
 169   Value &get_or_insert (const Key &k, bool *existed = NULL)
 170     {
 171       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 172                                                    INSERT);
 173       bool ins = Traits::is_empty (*e);
 174       if (ins)
 175         e->m_key = k;
 176
 177       if (existed != NULL)
 178         *existed = !ins;
 179
 180       return e->m_value;
 181     }
 182
 183   void remove (const Key &k)
 184     {
 185       m_table.remove_elt_with_hash (k, Traits::hash (k));
 186     }
 187
 188   /* Call the call back on each pair of key and value with the passed in
 189      arg.  */
 190
 191   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 192                                    const Value &, Arg)>
 193   void traverse (Arg a) const
 194     {
 195       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 196            iter != m_table.end (); ++iter)
 197         f ((*iter).m_key, (*iter).m_value, a);
 198     }
 199
 200   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 201                                    Value *, Arg)>
 202   void traverse (Arg a) const
 203     {
 204       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 205            iter != m_table.end (); ++iter)
 206         if (!f ((*iter).m_key, &(*iter).m_value, a))
 207           break;
 208     }
 209
 210   size_t elements () const { return m_table.elements (); }
 211
 212   void empty () { m_table.empty(); }
 213
 214   class iterator
 215   {
 216   public:
 217     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 218       m_iter (iter) {}
 219
 220     iterator &operator++ ()
 221     {
 222       ++m_iter;
 223       return *this;
 224     }
 225
 226     /* Can't use std::pair here, because GCC before 4.3 don't handle
 227        std::pair where template parameters are references well.
 228        See PR86739.  */
 229     struct reference_pair {
 230       const Key &first;
 231       Value &second;
 232
 233       reference_pair (const Key &key, Value &value) : first (key), second (value) {}
 234
 235       template <typename K, typename V>
 236       operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
 237     };
 238
 239     reference_pair operator* ()
 240     {
 241       hash_entry &e = *m_iter;
 242       return reference_pair (e.m_key, e.m_value);
 243     }
 244
 245     bool
 246     operator != (const iterator &other) const
 247     {
 248       return m_iter != other.m_iter;
 249     }
 250
 251   private:
 252     typename hash_table<hash_entry>::iterator m_iter;
 253   };
 254
 255   /* Standard iterator retrieval methods.  */
 256
 257   iterator  begin () const { return iterator (m_table.begin ()); }
 258   iterator end () const { return iterator (m_table.end ()); }
 259
 260 private:
 261
 262   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 263   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 264   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 265   template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
 266
 267   hash_table<hash_entry> m_table;
 268 };
 269
 270 /* ggc marking routines.  */
 271
 272 template<typename K, typename V, typename H>
 273 static inline void
 274 gt_ggc_mx (hash_map<K, V, H> *h)
 275 {
 276   gt_ggc_mx (&h->m_table);
 277 }
 278
 279 template<typename K, typename V, typename H>
 280 static inline void
 281 gt_pch_nx (hash_map<K, V, H> *h)
 282 {
 283   gt_pch_nx (&h->m_table);
 284 }
 285
 286 template<typename K, typename V, typename H>
 287 static inline void
 288 gt_cleare_cache (hash_map<K, V, H> *h)
 289 {
 290   if (h)
 291     gt_cleare_cache (&h->m_table);
 292 }
 293
 294 template<typename K, typename V, typename H>
 295 static inline void
 296 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 297 {
 298   op (&h->m_table.m_entries, cookie);
 299 }
 300
 301 #endif