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