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
 118     static hashval_t hash (const hash_entry &e)
 119       {
 120         return Traits::hash (e.m_key);
 121       }
 122
 123     static bool equal (const hash_entry &a, const Key &b)
 124         {
 125           return Traits::equal_keys (a.m_key, b);
 126         }
 127
 128     static void remove (hash_entry &e) { Traits::remove (e); }
 129
 130     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
 131
 132     static bool is_deleted (const hash_entry &e)
 133       {
 134         return Traits::is_deleted (e);
 135       }
 136
 137     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
 138     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
 139
 140     static void ggc_mx (hash_entry &e)
 141       {
 142         gt_ggc_mx (e.m_key);
 143         gt_ggc_mx (e.m_value);
 144       }
 145
 146     static void pch_nx (hash_entry &e)
 147       {
 148         gt_pch_nx (e.m_key);
 149         gt_pch_nx (e.m_value);
 150       }
 151
 152     static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
 153       {
 154         pch_nx_helper (e.m_key, op, c);
 155         pch_nx_helper (e.m_value, op, c);
 156       }
 157
 158   private:
 159     template<typename T>
 160     static void
 161       pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
 162         {
 163           gt_pch_nx (&x, op, cookie);
 164         }
 165
 166     static void
 167       pch_nx_helper (int, gt_pointer_operator, void *)
 168         {
 169         }
 170
 171     static void
 172       pch_nx_helper (unsigned int, gt_pointer_operator, void *)
 173         {
 174         }
 175
 176     static void
 177       pch_nx_helper (bool, gt_pointer_operator, void *)
 178         {
 179         }
 180
 181     template<typename T>
 182       static void
 183       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 184         {
 185           op (&x, cookie);
 186         }
 187   };
 188
 189 public:
 190   explicit hash_map (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
 191
 192   /* Create a hash_map in ggc memory.  */
 193   static hash_map *create_ggc (size_t size)
 194     {
 195       hash_map *map = ggc_alloc<hash_map> ();
 196       new (map) hash_map (size, true);
 197       return map;
 198     }
 199
 200   /* If key k isn't already in the map add key k with value v to the map, and
 201      return false.  Otherwise set the value of the entry for key k to be v and
 202      return true.  */
 203
 204   bool put (const Key &k, const Value &v)
 205     {
 206       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 207                                                    INSERT);
 208       bool existed = !hash_entry::is_empty (*e);
 209       if (!existed)
 210         e->m_key = k;
 211
 212       e->m_value = v;
 213       return existed;
 214     }
 215
 216   /* if the passed in key is in the map return its value otherwise NULL.  */
 217
 218   Value *get (const Key &k)
 219     {
 220       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 221       return Traits::is_empty (e) ? NULL : &e.m_value;
 222     }
 223
 224   /* Return a reference to the value for the passed in key, creating the entry
 225      if it doesn't already exist.  If existed is not NULL then it is set to false
 226      if the key was not previously in the map, and true otherwise.  */
 227
 228   Value &get_or_insert (const Key &k, bool *existed = NULL)
 229     {
 230       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 231                                                    INSERT);
 232       bool ins = Traits::is_empty (*e);
 233       if (ins)
 234         e->m_key = k;
 235
 236       if (existed != NULL)
 237         *existed = !ins;
 238
 239       return e->m_value;
 240     }
 241
 242   void remove (const Key &k)
 243     {
 244       m_table.remove_elt_with_hash (k, Traits::hash (k));
 245     }
 246
 247   /* Call the call back on each pair of key and value with the passed in
 248      arg.  */
 249
 250   template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
 251   void traverse (Arg a) const
 252     {
 253       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 254            iter != m_table.end (); ++iter)
 255         f ((*iter).m_key, (*iter).m_value, a);
 256     }
 257
 258   template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
 259   void traverse (Arg a) const
 260     {
 261       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 262            iter != m_table.end (); ++iter)
 263         if (!f ((*iter).m_key, &(*iter).m_value, a))
 264           break;
 265     }
 266
 267   size_t elements () const { return m_table.elements (); }
 268
 269   class iterator
 270   {
 271   public:
 272     explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
 273       m_iter (iter) {}
 274
 275     iterator &operator++ ()
 276     {
 277       ++m_iter;
 278       return *this;
 279     }
 280
 281     std::pair<Key, Value> operator* ()
 282     {
 283       hash_entry &e = *m_iter;
 284       return std::pair<Key, Value> (e.m_key, e.m_value);
 285     }
 286
 287     bool
 288     operator != (const iterator &other) const
 289     {
 290       return m_iter != other.m_iter;
 291     }
 292
 293   private:
 294     typename hash_table<hash_entry>::iterator m_iter;
 295   };
 296
 297   /* Standard iterator retrieval methods.  */
 298
 299   iterator  begin () const { return iterator (m_table.begin ()); }
 300   iterator end () const { return iterator (m_table.end ()); }
 301
 302 private:
 303
 304   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 305   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 306       template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 307
 308   hash_table<hash_entry> m_table;
 309 };
 310
 311 /* ggc marking routines.  */
 312
 313 template<typename K, typename V, typename H>
 314 static inline void
 315 gt_ggc_mx (hash_map<K, V, H> *h)
 316 {
 317   gt_ggc_mx (&h->m_table);
 318 }
 319
 320 template<typename K, typename V, typename H>
 321 static inline void
 322 gt_pch_nx (hash_map<K, V, H> *h)
 323 {
 324   gt_pch_nx (&h->m_table);
 325 }
 326
 327 template<typename K, typename V, typename H>
 328 static inline void
 329 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 330 {
 331   op (&h->m_table.m_entries, cookie);
 332 }
 333
 334 #endif