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