1 /* A type-safe hash map. 2 Copyright (C) 2014-2018 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 ggc_maybe_mx (hash_entry &e) 66 { 67 if (Traits::maybe_mx) 68 ggc_mx (e); 69 } 70 71 static void pch_nx (hash_entry &e) 72 { 73 gt_pch_nx (e.m_key); 74 gt_pch_nx (e.m_value); 75 } 76 77 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c) 78 { 79 pch_nx_helper (e.m_key, op, c); 80 pch_nx_helper (e.m_value, op, c); 81 } 82 83 static int keep_cache_entry (hash_entry &e) 84 { 85 return ggc_marked_p (e.m_key); 86 } 87 88 private: 89 template<typename T> 90 static void 91 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie) 92 { 93 gt_pch_nx (&x, op, cookie); 94 } 95 96 static void 97 pch_nx_helper (int, gt_pointer_operator, void *) 98 { 99 } 100 101 static void 102 pch_nx_helper (unsigned int, gt_pointer_operator, void *) 103 { 104 } 105 106 static void 107 pch_nx_helper (bool, gt_pointer_operator, void *) 108 { 109 } 110 111 template<typename T> 112 static void 113 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie) 114 { 115 op (&x, cookie); 116 } 117 }; 118 119 public: 120 explicit hash_map (size_t n = 13, bool ggc = false, 121 bool gather_mem_stats = GATHER_STATISTICS 122 CXX_MEM_STAT_INFO) 123 : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {} 124 125 explicit hash_map (const hash_map &h, bool ggc = false, 126 bool gather_mem_stats = GATHER_STATISTICS 127 CXX_MEM_STAT_INFO) 128 : m_table (h.m_table, ggc, gather_mem_stats, 129 HASH_MAP_ORIGIN PASS_MEM_STAT) {} 130 131 /* Create a hash_map in ggc memory. */ 132 static hash_map *create_ggc (size_t size, 133 bool gather_mem_stats = GATHER_STATISTICS 134 CXX_MEM_STAT_INFO) 135 { 136 hash_map *map = ggc_alloc<hash_map> (); 137 new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT); 138 return map; 139 } 140 141 /* If key k isn't already in the map add key k with value v to the map, and 142 return false. Otherwise set the value of the entry for key k to be v and 143 return true. */ 144 145 bool put (const Key &k, const Value &v) 146 { 147 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 148 INSERT); 149 bool existed = !hash_entry::is_empty (*e); 150 if (!existed) 151 e->m_key = k; 152 153 e->m_value = v; 154 return existed; 155 } 156 157 /* if the passed in key is in the map return its value otherwise NULL. */ 158 159 Value *get (const Key &k) 160 { 161 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k)); 162 return Traits::is_empty (e) ? NULL : &e.m_value; 163 } 164 165 /* Return a reference to the value for the passed in key, creating the entry 166 if it doesn't already exist. If existed is not NULL then it is set to false 167 if the key was not previously in the map, and true otherwise. */ 168 169 Value &get_or_insert (const Key &k, bool *existed = NULL) 170 { 171 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 172 INSERT); 173 bool ins = Traits::is_empty (*e); 174 if (ins) 175 e->m_key = k; 176 177 if (existed != NULL) 178 *existed = !ins; 179 180 return e->m_value; 181 } 182 183 void remove (const Key &k) 184 { 185 m_table.remove_elt_with_hash (k, Traits::hash (k)); 186 } 187 188 /* Call the call back on each pair of key and value with the passed in 189 arg. */ 190 191 template<typename Arg, bool (*f)(const typename Traits::key_type &, 192 const Value &, Arg)> 193 void traverse (Arg a) const 194 { 195 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 196 iter != m_table.end (); ++iter) 197 f ((*iter).m_key, (*iter).m_value, a); 198 } 199 200 template<typename Arg, bool (*f)(const typename Traits::key_type &, 201 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 size_t elements () const { return m_table.elements (); } 211 212 void empty () { m_table.empty(); } 213 214 class iterator 215 { 216 public: 217 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) : 218 m_iter (iter) {} 219 220 iterator &operator++ () 221 { 222 ++m_iter; 223 return *this; 224 } 225 226 std::pair<Key, Value> operator* () 227 { 228 hash_entry &e = *m_iter; 229 return std::pair<Key, Value> (e.m_key, e.m_value); 230 } 231 232 bool 233 operator != (const iterator &other) const 234 { 235 return m_iter != other.m_iter; 236 } 237 238 private: 239 typename hash_table<hash_entry>::iterator m_iter; 240 }; 241 242 /* Standard iterator retrieval methods. */ 243 244 iterator begin () const { return iterator (m_table.begin ()); } 245 iterator end () const { return iterator (m_table.end ()); } 246 247 private: 248 249 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *); 250 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *); 251 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *); 252 template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *); 253 254 hash_table<hash_entry> m_table; 255 }; 256 257 /* ggc marking routines. */ 258 259 template<typename K, typename V, typename H> 260 static inline void 261 gt_ggc_mx (hash_map<K, V, H> *h) 262 { 263 gt_ggc_mx (&h->m_table); 264 } 265 266 template<typename K, typename V, typename H> 267 static inline void 268 gt_pch_nx (hash_map<K, V, H> *h) 269 { 270 gt_pch_nx (&h->m_table); 271 } 272 273 template<typename K, typename V, typename H> 274 static inline void 275 gt_cleare_cache (hash_map<K, V, H> *h) 276 { 277 if (h) 278 gt_cleare_cache (&h->m_table); 279 } 280 281 template<typename K, typename V, typename H> 282 static inline void 283 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie) 284 { 285 op (&h->m_table.m_entries, cookie); 286 } 287 288 #endif 289