gcc/hash-map.h

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