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
  28 /* implement default behavior for traits when types allow it.  */
  29
  30 struct default_hashmap_traits
  31 {
  32   /* Hashes the passed in key.  */
  33
  34   template<typename T>
  35   static hashval_t
  36   hash (T *p)
  37     {
  38       return uintptr_t(p) >> 3;
  39     }
  40
  41   /* If the value converts to hashval_t just use it.  */
  42
  43   template<typename T> static hashval_t hash (T v) { return v; }
  44
  45   /* Return true if the two keys passed as arguments are equal.  */
  46
  47   template<typename T>
  48   static bool
  49   equal_keys (const T &a, const T &b)
  50     {
  51       return a == b;
  52     }
  53
  54   /* Called to dispose of the key and value before marking the entry as
  55      deleted.  */
  56
  57   template<typename T> static void remove (T &v) { v.~T (); }
  58
  59   /* Mark the passed in entry as being deleted.  */
  60
  61   template<typename T>
  62   static void
  63   mark_deleted (T &e)
  64     {
  65       mark_key_deleted (e.m_key);
  66     }
  67
  68   /* Mark the passed in entry as being empty.  */
  69
  70   template<typename T>
  71   static void
  72   mark_empty (T &e)
  73     {
  74       mark_key_empty (e.m_key);
  75     }
  76
  77   /* Return true if the passed in entry is marked as deleted.  */
  78
  79   template<typename T>
  80   static bool
  81   is_deleted (T &e)
  82     {
  83       return e.m_key == (void *)1;
  84     }
  85
  86   /* Return true if the passed in entry is marked as empty.  */
  87
  88   template<typename T> static bool is_empty (T &e) { return e.m_key == NULL; }
  89
  90 private:
  91   template<typename T>
  92   static void
  93   mark_key_deleted (T *&k)
  94     {
  95       k = reinterpret_cast<T *> (1);
  96     }
  97
  98   template<typename T>
  99   static void
 100   mark_key_empty (T *&k)
 101     {
 102       k = static_cast<T *> (0);
 103     }
 104 };
 105
 106 template<typename Key, typename Value,
 107          typename Traits = default_hashmap_traits>
 108 class GTY((user)) hash_map
 109 {
 110   struct hash_entry
 111   {
 112     Key m_key;
 113     Value m_value;
 114
 115     typedef hash_entry value_type;
 116     typedef Key compare_type;
 117     typedef int store_values_directly;
 118
 119     static hashval_t hash (const hash_entry &e)
 120       {
 121         return Traits::hash (e.m_key);
 122       }
 123
 124     static bool equal (const hash_entry &a, const Key &b)
 125         {
 126           return Traits::equal_keys (a.m_key, b);
 127         }
 128
 129     static void remove (hash_entry &e) { Traits::remove (e); }
 130
 131     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
 132
 133     static bool is_deleted (const hash_entry &e)
 134       {
 135         return Traits::is_deleted (e);
 136       }
 137
 138     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
 139     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
 140
 141     static void ggc_mx (hash_entry &e)
 142       {
 143         gt_ggc_mx (e.m_key);
 144         gt_ggc_mx (e.m_value);
 145       }
 146
 147     static void pch_nx (hash_entry &e)
 148       {
 149         gt_pch_nx (e.m_key);
 150         gt_pch_nx (e.m_value);
 151       }
 152
 153     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
 154       {
 155         pch_nx_helper (e.m_key, op, c);
 156         pch_nx_helper (e.m_value, op, c);
 157       }
 158
 159   private:
 160     template<typename T>
 161     static void
 162       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
 163         {
 164           gt_pch_nx (&x, op, cookie);
 165         }
 166
 167     static void
 168       pch_nx_helper (int, gt_pointer_operator, void *)
 169         {
 170         }
 171
 172     static void
 173       pch_nx_helper (unsigned int, gt_pointer_operator, void *)
 174         {
 175         }
 176
 177     static void
 178       pch_nx_helper (bool, gt_pointer_operator, void *)
 179         {
 180         }
 181
 182     template<typename T>
 183       static void
 184       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 185         {
 186           op (&x, cookie);
 187         }
 188   };
 189
 190 public:
 191   explicit hash_map (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
 192
 193   /* Create a hash_map in ggc memory.  */
 194   static hash_map *create_ggc (size_t size)
 195     {
 196       hash_map *map = ggc_alloc<hash_map> ();
 197       new (map) hash_map (size, true);
 198       return map;
 199     }
 200
 201   /* If key k isn't already in the map add key k with value v to the map, and
 202      return false.  Otherwise set the value of the entry for key k to be v and
 203      return true.  */
 204
 205   bool put (const Key &k, const Value &v)
 206     {
 207       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 208                                                    INSERT);
 209       bool existed = !hash_entry::is_empty (*e);
 210       if (!existed)
 211         e->m_key = k;
 212
 213       e->m_value = v;
 214       return existed;
 215     }
 216
 217   /* if the passed in key is in the map return its value otherwise NULL.  */
 218
 219   Value *get (const Key &k)
 220     {
 221       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 222       return Traits::is_empty (e) ? NULL : &e.m_value;
 223     }
 224
 225   /* Return a reference to the value for the passed in key, creating the entry
 226      if it doesn't already exist.  If existed is not NULL then it is set to false
 227      if the key was not previously in the map, and true otherwise.  */
 228
 229   Value &get_or_insert (const Key &k, bool *existed = NULL)
 230     {
 231       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 232                                                    INSERT);
 233       bool ins = Traits::is_empty (*e);
 234       if (ins)
 235         e->m_key = k;
 236
 237       if (existed != NULL)
 238         *existed = !ins;
 239
 240       return e->m_value;
 241     }
 242
 243   void remove (const Key &k)
 244     {
 245       m_table.remove_elt_with_hash (k, Traits::hash (k));
 246     }
 247
 248   /* Call the call back on each pair of key and value with the passed in
 249      arg.  */
 250
 251   template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
 252   void traverse (Arg a) const
 253     {
 254       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 255            iter != m_table.end (); ++iter)
 256         f ((*iter).m_key, (*iter).m_value, a);
 257     }
 258
 259   template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
 260   void traverse (Arg a) const
 261     {
 262       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 263            iter != m_table.end (); ++iter)
 264         if (!f ((*iter).m_key, &(*iter).m_value, a))
 265           break;
 266     }
 267
 268   size_t elements () const { return m_table.elements (); }
 269
 270   class iterator
 271   {
 272   public:
 273     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 274       m_iter (iter) {}
 275
 276     iterator &operator++ ()
 277     {
 278       ++m_iter;
 279       return *this;
 280     }
 281
 282     std::pair<Key, Value> operator* ()
 283     {
 284       hash_entry &e = *m_iter;
 285       return std::pair<Key, Value> (e.m_key, e.m_value);
 286     }
 287
 288     bool
 289     operator != (const iterator &other) const
 290     {
 291       return m_iter != other.m_iter;
 292     }
 293
 294   private:
 295     typename hash_table<hash_entry>::iterator m_iter;
 296   };
 297
 298   /* Standard iterator retrieval methods.  */
 299
 300   iterator  begin () const { return iterator (m_table.begin ()); }
 301   iterator end () const { return iterator (m_table.end ()); }
 302
 303 private:
 304
 305   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 306   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 307       template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 308
 309   hash_table<hash_entry> m_table;
 310 };
 311
 312 /* ggc marking routines.  */
 313
 314 template<typename K, typename V, typename H>
 315 static inline void
 316 gt_ggc_mx (hash_map<K, V, H> *h)
 317 {
 318   gt_ggc_mx (&h->m_table);
 319 }
 320
 321 template<typename K, typename V, typename H>
 322 static inline void
 323 gt_pch_nx (hash_map<K, V, H> *h)
 324 {
 325   gt_pch_nx (&h->m_table);
 326 }
 327
 328 template<typename K, typename V, typename H>
 329 static inline void
 330 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 331 {
 332   op (&h->m_table.m_entries, cookie);
 333 }
 334
 335 #endif