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     template<typename T>
 172       static void
 173       pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
 174         {
 175           op (&x, cookie);
 176         }
 177   };
 178
 179 public:
 180   explicit hash_map (size_t n = 13, bool ggc = false) : m_table (n, ggc) {}
 181
 182   /* Create a hash_map in ggc memory.  */
 183   static hash_map *create_ggc (size_t size)
 184     {
 185       hash_map *map = ggc_alloc<hash_map> ();
 186       new (map) hash_map (size, true);
 187       return map;
 188     }
 189
 190   /* If key k isn't already in the map add key k with value v to the map, and
 191      return false.  Otherwise set the value of the entry for key k to be v and
 192      return true.  */
 193
 194   bool put (const Key &k, const Value &v)
 195     {
 196       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 197                                                    INSERT);
 198       bool existed = !hash_entry::is_empty (*e);
 199       if (!existed)
 200         e->m_key = k;
 201
 202       e->m_value = v;
 203       return existed;
 204     }
 205
 206   /* if the passed in key is in the map return its value otherwise NULL.  */
 207
 208   Value *get (const Key &k)
 209     {
 210       hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
 211       return Traits::is_empty (e) ? NULL : &e.m_value;
 212     }
 213
 214   /* Return a reference to the value for the passed in key, creating the entry
 215      if it doesn't already exist.  If existed is not NULL then it is set to false
 216      if the key was not previously in the map, and true otherwise.  */
 217
 218   Value &get_or_insert (const Key &k, bool *existed = NULL)
 219     {
 220       hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
 221                                                    INSERT);
 222       bool ins = Traits::is_empty (*e);
 223       if (ins)
 224         e->m_key = k;
 225
 226       if (existed != NULL)
 227         *existed = !ins;
 228
 229       return e->m_value;
 230     }
 231
 232   void remove (const Key &k)
 233     {
 234       m_table.remove_elt_with_hash (k, Traits::hash (k));
 235     }
 236
 237   /* Call the call back on each pair of key and value with the passed in
 238      arg.  */
 239
 240   template<typename Arg, bool (*f)(const Key &, const Value &, Arg)>
 241   void traverse (Arg a) const
 242     {
 243       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 244            iter != m_table.end (); ++iter)
 245         f ((*iter).m_key, (*iter).m_value, a);
 246     }
 247
 248   template<typename Arg, bool (*f)(const Key &, Value *, Arg)>
 249   void traverse (Arg a) const
 250     {
 251       for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
 252            iter != m_table.end (); ++iter)
 253         if (!f ((*iter).m_key, &(*iter).m_value, a))
 254           break;
 255     }
 256
 257 private:
 258
 259   template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
 260   template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
 261       template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
 262
 263   hash_table<hash_entry> m_table;
 264 };
 265
 266 /* ggc marking routines.  */
 267
 268 template<typename K, typename V, typename H>
 269 static inline void
 270 gt_ggc_mx (hash_map<K, V, H> *h)
 271 {
 272   gt_ggc_mx (&h->m_table);
 273 }
 274
 275 template<typename K, typename V, typename H>
 276 static inline void
 277 gt_pch_nx (hash_map<K, V, H> *h)
 278 {
 279   gt_pch_nx (&h->m_table);
 280 }
 281
 282 template<typename K, typename V, typename H>
 283 static inline void
 284 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
 285 {
 286   op (&h->m_table.m_entries, cookie);
 287 }
 288
 289 #endif