gcc/hash-map.h

   1 /* A type-safe hash map.
   2    Copyright (C) 2014 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 "hash-table.h"
  25
  26 /* implement default behavior for traits when types allow it.  */
  27
  28 struct default_hashmap_traits
  29 {
  30   /* Hashes the passed in key.  */
  31
  32   template<typename T>
  33   static hashval_t
  34   hash (T *p)
  35     {
  36       return uintptr_t(p) >> 3;
  37     }
  38
  39   /* If the value converts to hashval_t just use it.  */
  40
  41   template<typename T> static hashval_t hash (T v) { return v; }
  42
  43   /* Return true if the two keys passed as arguments are equal.  */
  44
  45   template<typename T>
  46   static bool
  47   equal_keys (const T &a, const T &b)
  48     {
  49       return a == b;
  50     }
  51
  52   /* Called to dispose of the key and value before marking the entry as
  53      deleted.  */
  54
  55   template<typename T> static void remove (T &v) { v.~T (); }
  56
  57   /* Mark the passed in entry as being deleted.  */
  58
  59   template<typename T>
  60   static void
  61   mark_deleted (T &e)
  62     {
  63       mark_key_deleted (e.m_key);
  64     }
  65
  66   /* Mark the passed in entry as being empty.  */
  67
  68   template<typename T>
  69   static void
  70   mark_empty (T &e)
  71     {
  72       mark_key_empty (e.m_key);
  73     }
  74
  75   /* Return true if the passed in entry is marked as deleted.  */
  76
  77   template<typename T>
  78   static bool
  79   is_deleted (T &e)
  80     {
  81       return e.m_key == (void *)1;
  82     }
  83
  84   /* Return true if the passed in entry is marked as empty.  */
  85
  86   template<typename T> static bool is_empty (T &e) { return e.m_key == NULL; }
  87
  88 private:
  89   template<typename T>
  90   static void
  91   mark_key_deleted (T *&k)
  92     {
  93       k = reinterpret_cast<T *> (1);
  94     }
  95
  96   template<typename T>
  97   static void
  98   mark_key_empty (T *&k)
  99     {
 100       k = static_cast<T *> (0);
 101     }
 102 };
 103
 104 template<typename Key, typename Value,
 105          typename Traits = default_hashmap_traits>
 106 class hash_map
 107 {
 108   struct hash_entry
 109   {
 110     Key m_key;
 111     Value m_value;
 112
 113     typedef hash_entry value_type;
 114     typedef Key compare_type;
 115     typedef int store_values_directly;
 116
 117     static hashval_t hash (const hash_entry &e)
 118       {
 119         return Traits::hash (e.m_key);
 120       }
 121
 122     static bool equal (const hash_entry &a, const Key &b)
 123         {
 124           return Traits::equal_keys (a.m_key, b);
 125         }
 126
 127     static void remove (hash_entry &e) { Traits::remove (e); }
 128
 129     static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
 130
 131     static bool is_deleted (const hash_entry &e)
 132       {
 133         return Traits::is_deleted (e);
 134       }
 135
 136     static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
 137     static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
 138   };
 139
 140 public:
 141   explicit hash_map (size_t n = 13) : m_table (n) {}
 142
 143   /* If key k isn't already in the map add key k with value v to the map, and
 144      return false.  Otherwise set the value of the entry for key k to be v and
 145      return true.  */
 146
 147   bool put (const Key &k, const Value &v)
 148     {
 149       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 150                                                    INSERT);
 151       bool existed = !hash_entry::is_empty (*e);
 152       if (!existed)
 153         e->m_key = k;
 154
 155       e->m_value = v;
 156       return existed;
 157     }
 158
 159   /* if the passed in key is in the map return its value otherwise NULL.  */
 160
 161   Value *get (const Key &k)
 162     {
 163       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 164       return Traits::is_empty (e) ? NULL : &e.m_value;
 165     }
 166
 167   /* Return a reference to the value for the passed in key, creating the entry
 168      if it doesn't already exist.  If existed is not NULL then it is set to false
 169      if the key was not previously in the map, and true otherwise.  */
 170
 171   Value &get_or_insert (const Key &k, bool *existed = NULL)
 172     {
 173       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 174                                                    INSERT);
 175       bool ins = Traits::is_empty (*e);
 176       if (ins)
 177         e->m_key = k;
 178
 179       if (existed != NULL)
 180         *existed = !ins;
 181
 182       return e->m_value;
 183     }
 184
 185   void remove (const Key &k)
 186     {
 187       m_table.remove_elt_with_hash (k, Traits::hash (k));
 188     }
 189
 190   /* Call the call back on each pair of key and value with the passed in
 191      arg.  */
 192
 193   template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
 194   void traverse (Arg a) const
 195     {
 196       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 197            iter != m_table.end (); ++iter)
 198         f ((*iter).m_key, (*iter).m_value, a);
 199     }
 200
 201   template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
 202   void traverse (Arg a) const
 203     {
 204       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 205            iter != m_table.end (); ++iter)
 206         if (!f ((*iter).m_key, &(*iter).m_value, a))
 207           break;
 208     }
 209
 210 private:
 211   hash_table<hash_entry> m_table;
 212 };
 213
 214 #endif