gcc/hash-map.h

   1 /* A type-safe hash map.
   2    Copyright (C) 2014-2017 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 pch_nx (hash_entry &e)
  66       {
  67         gt_pch_nx (e.m_key);
  68         gt_pch_nx (e.m_value);
  69       }
  70
  71     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
  72       {
  73         pch_nx_helper (e.m_key, op, c);
  74         pch_nx_helper (e.m_value, op, c);
  75       }
  76
  77   private:
  78     template<typename T>
  79     static void
  80       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
  81         {
  82           gt_pch_nx (&x, op, cookie);
  83         }
  84
  85     static void
  86       pch_nx_helper (int, gt_pointer_operator, void *)
  87         {
  88         }
  89
  90     static void
  91       pch_nx_helper (unsigned int, gt_pointer_operator, void *)
  92         {
  93         }
  94
  95     static void
  96       pch_nx_helper (bool, gt_pointer_operator, void *)
  97         {
  98         }
  99
 100     template<typename T>
 101       static void
 102       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 103         {
 104           op (&x, cookie);
 105         }
 106   };
 107
 108 public:
 109   explicit hash_map (size_t n = 13, bool ggc = false,
 110                      bool gather_mem_stats = GATHER_STATISTICS
 111                      CXX_MEM_STAT_INFO)
 112     : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {}
 113
 114   explicit hash_map (const hash_map &h, bool ggc = false,
 115                      bool gather_mem_stats = GATHER_STATISTICS
 116                      CXX_MEM_STAT_INFO)
 117     : m_table (h.m_table, ggc, gather_mem_stats,
 118                HASH_MAP_ORIGIN PASS_MEM_STAT) {}
 119
 120   /* Create a hash_map in ggc memory.  */
 121   static hash_map *create_ggc (size_t size,
 122                                bool gather_mem_stats = GATHER_STATISTICS
 123                                CXX_MEM_STAT_INFO)
 124     {
 125       hash_map *map = ggc_alloc<hash_map> ();
 126       new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT);
 127       return map;
 128     }
 129
 130   /* If key k isn't already in the map add key k with value v to the map, and
 131      return false.  Otherwise set the value of the entry for key k to be v and
 132      return true.  */
 133
 134   bool put (const Key &k, const Value &v)
 135     {
 136       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 137                                                    INSERT);
 138       bool existed = !hash_entry::is_empty (*e);
 139       if (!existed)
 140         e->m_key = k;
 141
 142       e->m_value = v;
 143       return existed;
 144     }
 145
 146   /* if the passed in key is in the map return its value otherwise NULL.  */
 147
 148   Value *get (const Key &k)
 149     {
 150       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 151       return Traits::is_empty (e) ? NULL : &e.m_value;
 152     }
 153
 154   /* Return a reference to the value for the passed in key, creating the entry
 155      if it doesn't already exist.  If existed is not NULL then it is set to false
 156      if the key was not previously in the map, and true otherwise.  */
 157
 158   Value &get_or_insert (const Key &k, bool *existed = NULL)
 159     {
 160       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 161                                                    INSERT);
 162       bool ins = Traits::is_empty (*e);
 163       if (ins)
 164         e->m_key = k;
 165
 166       if (existed != NULL)
 167         *existed = !ins;
 168
 169       return e->m_value;
 170     }
 171
 172   void remove (const Key &k)
 173     {
 174       m_table.remove_elt_with_hash (k, Traits::hash (k));
 175     }
 176
 177   /* Call the call back on each pair of key and value with the passed in
 178      arg.  */
 179
 180   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 181                                    const Value &, Arg)>
 182   void traverse (Arg a) const
 183     {
 184       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 185            iter != m_table.end (); ++iter)
 186         f ((*iter).m_key, (*iter).m_value, a);
 187     }
 188
 189   template<typename Arg, bool (*f)(const typename Traits::key_type &,
 190                                    Value *, Arg)>
 191   void traverse (Arg a) const
 192     {
 193       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 194            iter != m_table.end (); ++iter)
 195         if (!f ((*iter).m_key, &(*iter).m_value, a))
 196           break;
 197     }
 198
 199   size_t elements () const { return m_table.elements (); }
 200
 201   void empty () { m_table.empty(); }
 202
 203   class iterator
 204   {
 205   public:
 206     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 207       m_iter (iter) {}
 208
 209     iterator &operator++ ()
 210     {
 211       ++m_iter;
 212       return *this;
 213     }
 214
 215     std::pair<Key, Value> operator* ()
 216     {
 217       hash_entry &e = *m_iter;
 218       return std::pair<Key, Value> (e.m_key, e.m_value);
 219     }
 220
 221     bool
 222     operator != (const iterator &other) const
 223     {
 224       return m_iter != other.m_iter;
 225     }
 226
 227   private:
 228     typename hash_table<hash_entry>::iterator m_iter;
 229   };
 230
 231   /* Standard iterator retrieval methods.  */
 232
 233   iterator  begin () const { return iterator (m_table.begin ()); }
 234   iterator end () const { return iterator (m_table.end ()); }
 235
 236 private:
 237
 238   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 239   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 240       template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 241
 242   hash_table<hash_entry> m_table;
 243 };
 244
 245 /* ggc marking routines.  */
 246
 247 template<typename K, typename V, typename H>
 248 static inline void
 249 gt_ggc_mx (hash_map<K, V, H> *h)
 250 {
 251   gt_ggc_mx (&h->m_table);
 252 }
 253
 254 template<typename K, typename V, typename H>
 255 static inline void
 256 gt_pch_nx (hash_map<K, V, H> *h)
 257 {
 258   gt_pch_nx (&h->m_table);
 259 }
 260
 261 template<typename K, typename V, typename H>
 262 static inline void
 263 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 264 {
 265   op (&h->m_table.m_entries, cookie);
 266 }
 267
 268 #endif