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