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 Key &, const Value &, Arg)>
 173   void traverse (Arg a) const
 174     {
 175       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 176            iter != m_table.end (); ++iter)
 177         f ((*iter).m_key, (*iter).m_value, a);
 178     }
 179
 180   template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
 181   void traverse (Arg a) const
 182     {
 183       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 184            iter != m_table.end (); ++iter)
 185         if (!f ((*iter).m_key, &(*iter).m_value, a))
 186           break;
 187     }
 188
 189   size_t elements () const { return m_table.elements (); }
 190
 191   class iterator
 192   {
 193   public:
 194     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 195       m_iter (iter) {}
 196
 197     iterator &operator++ ()
 198     {
 199       ++m_iter;
 200       return *this;
 201     }
 202
 203     std::pair<Key, Value> operator* ()
 204     {
 205       hash_entry &e = *m_iter;
 206       return std::pair<Key, Value> (e.m_key, e.m_value);
 207     }
 208
 209     bool
 210     operator != (const iterator &other) const
 211     {
 212       return m_iter != other.m_iter;
 213     }
 214
 215   private:
 216     typename hash_table<hash_entry>::iterator m_iter;
 217   };
 218
 219   /* Standard iterator retrieval methods.  */
 220
 221   iterator  begin () const { return iterator (m_table.begin ()); }
 222   iterator end () const { return iterator (m_table.end ()); }
 223
 224 private:
 225
 226   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 227   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 228       template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 229
 230   hash_table<hash_entry> m_table;
 231 };
 232
 233 /* ggc marking routines.  */
 234
 235 template<typename K, typename V, typename H>
 236 static inline void
 237 gt_ggc_mx (hash_map<K, V, H> *h)
 238 {
 239   gt_ggc_mx (&h->m_table);
 240 }
 241
 242 template<typename K, typename V, typename H>
 243 static inline void
 244 gt_pch_nx (hash_map<K, V, H> *h)
 245 {
 246   gt_pch_nx (&h->m_table);
 247 }
 248
 249 template<typename K, typename V, typename H>
 250 static inline void
 251 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 252 {
 253   op (&h->m_table.m_entries, cookie);
 254 }
 255
 256 #endif