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 <new>
  25 #include "hash-table.h"
  26
  27 /* implement default behavior for traits when types allow it.  */
  28
  29 struct default_hashmap_traits
  30 {
  31   /* Hashes the passed in key.  */
  32
  33   template<typename T>
  34   static hashval_t
  35   hash (T *p)
  36     {
  37       return uintptr_t(p) >> 3;
  38     }
  39
  40   /* If the value converts to hashval_t just use it.  */
  41
  42   template<typename T> static hashval_t hash (T v) { return v; }
  43
  44   /* Return true if the two keys passed as arguments are equal.  */
  45
  46   template<typename T>
  47   static bool
  48   equal_keys (const T &a, const T &b)
  49     {
  50       return a == b;
  51     }
  52
  53   /* Called to dispose of the key and value before marking the entry as
  54      deleted.  */
  55
  56   template<typename T> static void remove (T &v) { v.~T (); }
  57
  58   /* Mark the passed in entry as being deleted.  */
  59
  60   template<typename T>
  61   static void
  62   mark_deleted (T &e)
  63     {
  64       mark_key_deleted (e.m_key);
  65     }
  66
  67   /* Mark the passed in entry as being empty.  */
  68
  69   template<typename T>
  70   static void
  71   mark_empty (T &e)
  72     {
  73       mark_key_empty (e.m_key);
  74     }
  75
  76   /* Return true if the passed in entry is marked as deleted.  */
  77
  78   template<typename T>
  79   static bool
  80   is_deleted (T &e)
  81     {
  82       return e.m_key == (void *)1;
  83     }
  84
  85   /* Return true if the passed in entry is marked as empty.  */
  86
  87   template<typename T> static bool is_empty (T &e) { return e.m_key == NULL; }
  88
  89 private:
  90   template<typename T>
  91   static void
  92   mark_key_deleted (T *&k)
  93     {
  94       k = reinterpret_cast<T *> (1);
  95     }
  96
  97   template<typename T>
  98   static void
  99   mark_key_empty (T *&k)
 100     {
 101       k = static_cast<T *> (0);
 102     }
 103 };
 104
 105 template<typename Key, typename Value,
 106          typename Traits = default_hashmap_traits>
 107 class GTY((user)) hash_map
 108 {
 109   struct hash_entry
 110   {
 111     Key m_key;
 112     Value m_value;
 113
 114     typedef hash_entry value_type;
 115     typedef Key compare_type;
 116     typedef int store_values_directly;
 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 private:
 268
 269   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 270   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 271       template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 272
 273   hash_table<hash_entry> m_table;
 274 };
 275
 276 /* ggc marking routines.  */
 277
 278 template<typename K, typename V, typename H>
 279 static inline void
 280 gt_ggc_mx (hash_map<K, V, H> *h)
 281 {
 282   gt_ggc_mx (&h->m_table);
 283 }
 284
 285 template<typename K, typename V, typename H>
 286 static inline void
 287 gt_pch_nx (hash_map<K, V, H> *h)
 288 {
 289   gt_pch_nx (&h->m_table);
 290 }
 291
 292 template<typename K, typename V, typename H>
 293 static inline void
 294 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 295 {
 296   op (&h->m_table.m_entries, cookie);
 297 }
 298
 299 #endif