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 #include <new>
  25 #include <utility>
  26 #include "hash-table.h"
  27 #include "hash-map-traits.h"
  28 #include "mem-stats.h"
  29 #include "vec.h"
  30
  31 template<typename Key, typename Value,
  32          typename Traits>
  33 class GTY((user)) hash_map
  34 {
  35   struct hash_entry
  36   {
  37     Key m_key;
  38     Value m_value;
  39
  40     typedef hash_entry value_type;
  41     typedef Key compare_type;
  42
  43     static hashval_t hash (const hash_entry &e)
  44       {
  45         return Traits::hash (e.m_key);
  46       }
  47
  48     static bool equal (const hash_entry &a, const Key &b)
  49         {
  50           return Traits::equal_keys (a.m_key, b);
  51         }
  52
  53     static void remove (hash_entry &e) { Traits::remove (e); }
  54
  55     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
  56
  57     static bool is_deleted (const hash_entry &e)
  58       {
  59         return Traits::is_deleted (e);
  60       }
  61
  62     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
  63     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
  64
  65     static void ggc_mx (hash_entry &e)
  66       {
  67         gt_ggc_mx (e.m_key);
  68         gt_ggc_mx (e.m_value);
  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   private:
  84     template<typename T>
  85     static void
  86       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
  87         {
  88           gt_pch_nx (&x, op, cookie);
  89         }
  90
  91     static void
  92       pch_nx_helper (int, gt_pointer_operator, void *)
  93         {
  94         }
  95
  96     static void
  97       pch_nx_helper (unsigned int, gt_pointer_operator, void *)
  98         {
  99         }
 100
 101     static void
 102       pch_nx_helper (bool, gt_pointer_operator, void *)
 103         {
 104         }
 105
 106     template<typename T>
 107       static void
 108       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 109         {
 110           op (&x, cookie);
 111         }
 112   };
 113
 114 public:
 115   explicit hash_map (size_t n = 13, bool ggc = false,
 116                      bool gather_mem_stats = true CXX_MEM_STAT_INFO)
 117     : m_table (n, ggc, gather_mem_stats, HASH_MAP PASS_MEM_STAT) {}
 118
 119   /* Create a hash_map in ggc memory.  */
 120   static hash_map *create_ggc (size_t size, bool gather_mem_stats = true
 121                                CXX_MEM_STAT_INFO)
 122     {
 123       hash_map *map = ggc_alloc<hash_map> ();
 124       new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT);
 125       return map;
 126     }
 127
 128   /* If key k isn't already in the map add key k with value v to the map, and
 129      return false.  Otherwise set the value of the entry for key k to be v and
 130      return true.  */
 131
 132   bool put (const Key &k, const Value &v)
 133     {
 134       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 135                                                    INSERT);
 136       bool existed = !hash_entry::is_empty (*e);
 137       if (!existed)
 138         e->m_key = k;
 139
 140       e->m_value = v;
 141       return existed;
 142     }
 143
 144   /* if the passed in key is in the map return its value otherwise NULL.  */
 145
 146   Value *get (const Key &k)
 147     {
 148       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 149       return Traits::is_empty (e) ? NULL : &e.m_value;
 150     }
 151
 152   /* Return a reference to the value for the passed in key, creating the entry
 153      if it doesn't already exist.  If existed is not NULL then it is set to false
 154      if the key was not previously in the map, and true otherwise.  */
 155
 156   Value &get_or_insert (const Key &k, bool *existed = NULL)
 157     {
 158       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 159                                                    INSERT);
 160       bool ins = Traits::is_empty (*e);
 161       if (ins)
 162         e->m_key = k;
 163
 164       if (existed != NULL)
 165         *existed = !ins;
 166
 167       return e->m_value;
 168     }
 169
 170   void remove (const Key &k)
 171     {
 172       m_table.remove_elt_with_hash (k, Traits::hash (k));
 173     }
 174
 175   /* Call the call back on each pair of key and value with the passed in
 176      arg.  */
 177
 178   template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
 179   void traverse (Arg a) const
 180     {
 181       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 182            iter != m_table.end (); ++iter)
 183         f ((*iter).m_key, (*iter).m_value, a);
 184     }
 185
 186   template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
 187   void traverse (Arg a) const
 188     {
 189       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 190            iter != m_table.end (); ++iter)
 191         if (!f ((*iter).m_key, &(*iter).m_value, a))
 192           break;
 193     }
 194
 195   size_t elements () const { return m_table.elements (); }
 196
 197   class iterator
 198   {
 199   public:
 200     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 201       m_iter (iter) {}
 202
 203     iterator &operator++ ()
 204     {
 205       ++m_iter;
 206       return *this;
 207     }
 208
 209     std::pair<Key, Value> operator* ()
 210     {
 211       hash_entry &e = *m_iter;
 212       return std::pair<Key, Value> (e.m_key, e.m_value);
 213     }
 214
 215     bool
 216     operator != (const iterator &other) const
 217     {
 218       return m_iter != other.m_iter;
 219     }
 220
 221   private:
 222     typename hash_table<hash_entry>::iterator m_iter;
 223   };
 224
 225   /* Standard iterator retrieval methods.  */
 226
 227   iterator  begin () const { return iterator (m_table.begin ()); }
 228   iterator end () const { return iterator (m_table.end ()); }
 229
 230 private:
 231
 232   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 233   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 234       template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 235
 236   hash_table<hash_entry> m_table;
 237 };
 238
 239 /* ggc marking routines.  */
 240
 241 template<typename K, typename V, typename H>
 242 static inline void
 243 gt_ggc_mx (hash_map<K, V, H> *h)
 244 {
 245   gt_ggc_mx (&h->m_table);
 246 }
 247
 248 template<typename K, typename V, typename H>
 249 static inline void
 250 gt_pch_nx (hash_map<K, V, H> *h)
 251 {
 252   gt_pch_nx (&h->m_table);
 253 }
 254
 255 template<typename K, typename V, typename H>
 256 static inline void
 257 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 258 {
 259   op (&h->m_table.m_entries, cookie);
 260 }
 261
 262 #endif