1 /* A type-safe hash map. 2 Copyright (C) 2014-2016 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 template<typename KeyId, typename Value, 25 typename Traits> 26 class GTY((user)) hash_map 27 { 28 typedef typename Traits::key_type Key; 29 struct hash_entry 30 { 31 Key m_key; 32 Value m_value; 33 34 typedef hash_entry value_type; 35 typedef Key compare_type; 36 37 static hashval_t hash (const hash_entry &e) 38 { 39 return Traits::hash (e.m_key); 40 } 41 42 static bool equal (const hash_entry &a, const Key &b) 43 { 44 return Traits::equal_keys (a.m_key, b); 45 } 46 47 static void remove (hash_entry &e) { Traits::remove (e); } 48 49 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); } 50 51 static bool is_deleted (const hash_entry &e) 52 { 53 return Traits::is_deleted (e); 54 } 55 56 static void mark_empty (hash_entry &e) { Traits::mark_empty (e); } 57 static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); } 58 59 static void ggc_mx (hash_entry &e) 60 { 61 gt_ggc_mx (e.m_key); 62 gt_ggc_mx (e.m_value); 63 } 64 65 static void pch_nx (hash_entry &e) 66 { 67 gt_pch_nx (e.m_key); 68 gt_pch_nx (e.m_value); 69 } 70 71 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c) 72 { 73 pch_nx_helper (e.m_key, op, c); 74 pch_nx_helper (e.m_value, op, c); 75 } 76 77 private: 78 template<typename T> 79 static void 80 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie) 81 { 82 gt_pch_nx (&x, op, cookie); 83 } 84 85 static void 86 pch_nx_helper (int, gt_pointer_operator, void *) 87 { 88 } 89 90 static void 91 pch_nx_helper (unsigned int, gt_pointer_operator, void *) 92 { 93 } 94 95 static void 96 pch_nx_helper (bool, gt_pointer_operator, void *) 97 { 98 } 99 100 template<typename T> 101 static void 102 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie) 103 { 104 op (&x, cookie); 105 } 106 }; 107 108 public: 109 explicit hash_map (size_t n = 13, bool ggc = false, 110 bool gather_mem_stats = GATHER_STATISTICS 111 CXX_MEM_STAT_INFO) 112 : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {} 113 114 explicit hash_map (const hash_map &h, bool ggc = false, 115 bool gather_mem_stats = GATHER_STATISTICS 116 CXX_MEM_STAT_INFO) 117 : m_table (h.m_table, ggc, gather_mem_stats, 118 HASH_MAP_ORIGIN PASS_MEM_STAT) {} 119 120 /* Create a hash_map in ggc memory. */ 121 static hash_map *create_ggc (size_t size, 122 bool gather_mem_stats = GATHER_STATISTICS 123 CXX_MEM_STAT_INFO) 124 { 125 hash_map *map = ggc_alloc<hash_map> (); 126 new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT); 127 return map; 128 } 129 130 /* If key k isn't already in the map add key k with value v to the map, and 131 return false. Otherwise set the value of the entry for key k to be v and 132 return true. */ 133 134 bool put (const Key &k, const Value &v) 135 { 136 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 137 INSERT); 138 bool existed = !hash_entry::is_empty (*e); 139 if (!existed) 140 e->m_key = k; 141 142 e->m_value = v; 143 return existed; 144 } 145 146 /* if the passed in key is in the map return its value otherwise NULL. */ 147 148 Value *get (const Key &k) 149 { 150 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k)); 151 return Traits::is_empty (e) ? NULL : &e.m_value; 152 } 153 154 /* Return a reference to the value for the passed in key, creating the entry 155 if it doesn't already exist. If existed is not NULL then it is set to false 156 if the key was not previously in the map, and true otherwise. */ 157 158 Value &get_or_insert (const Key &k, bool *existed = NULL) 159 { 160 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 161 INSERT); 162 bool ins = Traits::is_empty (*e); 163 if (ins) 164 e->m_key = k; 165 166 if (existed != NULL) 167 *existed = !ins; 168 169 return e->m_value; 170 } 171 172 void remove (const Key &k) 173 { 174 m_table.remove_elt_with_hash (k, Traits::hash (k)); 175 } 176 177 /* Call the call back on each pair of key and value with the passed in 178 arg. */ 179 180 template<typename Arg, bool (*f)(const typename Traits::key_type &, 181 const Value &, Arg)> 182 void traverse (Arg a) const 183 { 184 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 185 iter != m_table.end (); ++iter) 186 f ((*iter).m_key, (*iter).m_value, a); 187 } 188 189 template<typename Arg, bool (*f)(const typename Traits::key_type &, 190 Value *, Arg)> 191 void traverse (Arg a) const 192 { 193 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 194 iter != m_table.end (); ++iter) 195 if (!f ((*iter).m_key, &(*iter).m_value, a)) 196 break; 197 } 198 199 size_t elements () const { return m_table.elements (); } 200 201 void empty () { m_table.empty(); } 202 203 class iterator 204 { 205 public: 206 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) : 207 m_iter (iter) {} 208 209 iterator &operator++ () 210 { 211 ++m_iter; 212 return *this; 213 } 214 215 std::pair<Key, Value> operator* () 216 { 217 hash_entry &e = *m_iter; 218 return std::pair<Key, Value> (e.m_key, e.m_value); 219 } 220 221 bool 222 operator != (const iterator &other) const 223 { 224 return m_iter != other.m_iter; 225 } 226 227 private: 228 typename hash_table<hash_entry>::iterator m_iter; 229 }; 230 231 /* Standard iterator retrieval methods. */ 232 233 iterator begin () const { return iterator (m_table.begin ()); } 234 iterator end () const { return iterator (m_table.end ()); } 235 236 private: 237 238 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *); 239 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *); 240 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *); 241 242 hash_table<hash_entry> m_table; 243 }; 244 245 /* ggc marking routines. */ 246 247 template<typename K, typename V, typename H> 248 static inline void 249 gt_ggc_mx (hash_map<K, V, H> *h) 250 { 251 gt_ggc_mx (&h->m_table); 252 } 253 254 template<typename K, typename V, typename H> 255 static inline void 256 gt_pch_nx (hash_map<K, V, H> *h) 257 { 258 gt_pch_nx (&h->m_table); 259 } 260 261 template<typename K, typename V, typename H> 262 static inline void 263 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie) 264 { 265 op (&h->m_table.m_entries, cookie); 266 } 267 268 #endif 269