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