1/* Copyright (C) 2021 Free Software Foundation, Inc. 2 Contributed by Oracle. 3 4 This file is part of GNU Binutils. 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, 51 Franklin Street - Fifth Floor, Boston, 19 MA 02110-1301, USA. */ 20 21// java.util.HashMap 22 23#ifndef _DBE_HASHMAP_H 24#define _DBE_HASHMAP_H 25 26#include "vec.h" 27#include "util.h" 28#include "StringBuilder.h" 29#include "Histable.h" 30#include "MemObject.h" 31 32template <typename Key_t> inline int get_hash_code (Key_t a); 33template <typename Key_t> inline bool is_equals (Key_t a, Key_t b); 34template <typename Key_t> inline Key_t copy_key (Key_t a); 35template <typename Key_t> inline void delete_key (Key_t a); 36 37// Specialization for char* 38template<> inline int 39get_hash_code (char *a) 40{ 41 return (int) (crc64 (a, strlen (a)) & 0x7fffffff); 42} 43 44template<> inline bool 45is_equals (char *a, char *b) 46{ 47 return dbe_strcmp (a, b) == 0; 48} 49 50template<> inline char * 51copy_key (char *a) 52{ 53 return dbe_strdup (a); 54} 55 56template<> inline void 57delete_key (char *a) 58{ 59 return free (a); 60} 61 62template<> inline int 63get_hash_code (uint64_t a) 64{ 65 return (int) (a & 0x7fffffff); 66} 67 68template<> inline bool 69is_equals (uint64_t a, uint64_t b) 70{ 71 return a == b; 72} 73 74template<> inline uint64_t 75copy_key (uint64_t a) 76{ 77 return a; 78} 79 80template<> inline void 81delete_key (uint64_t a) 82{ 83 a = a; 84} 85 86template<> inline int 87get_hash_code (Histable* a) 88{ 89 return (int) (a->id & 0x7fffffff); 90} 91 92template<> inline bool 93is_equals (Histable* a, Histable* b) 94{ 95 return a == b; 96} 97 98template<> inline Histable* 99copy_key (Histable* a) 100{ 101 return a; 102} 103 104template<> inline void 105delete_key (Histable* a) 106{ 107 a->id = a->id; 108} 109 110template<> inline int 111get_hash_code (MemObj* a) 112{ 113 return (int) (a->id & 0x7fffffff); 114} 115 116template<> inline bool 117is_equals (MemObj* a, MemObj* b) 118{ 119 return a == b; 120} 121 122template<> inline MemObj* 123copy_key (MemObj* a) 124{ 125 return a; 126} 127 128template<> inline void 129delete_key (MemObj* a) 130{ 131 a->id = a->id; 132} 133 134template <typename Key_t, typename Value_t> 135class HashMap 136{ 137public: 138 HashMap (int initialCapacity = 0); 139 140 ~HashMap () 141 { 142 clear (); 143 delete vals; 144 delete[] hashTable; 145 } 146 147 Value_t put (Key_t key, Value_t val); 148 Value_t get (Key_t key); 149 Value_t get (Key_t key, Value_t val); // Create a new map if key is not here 150 void clear (); 151 Value_t remove (Key_t); 152 Vector<Value_t> *values (Key_t key); // Return a list of values for 'key' 153 154 bool 155 containsKey (Key_t key) 156 { 157 Value_t p = get (key); 158 return p != NULL; 159 }; 160 161 Vector<Value_t> * 162 values () 163 { 164 return vals; 165 } 166 167 void 168 reset () 169 { 170 clear (); 171 } 172 173 int 174 get_phaseIdx () 175 { 176 return phaseIdx; 177 } 178 179 void 180 set_phaseIdx (int phase) 181 { 182 if (phase == 0) clear (); 183 phaseIdx = phase; 184 } 185 char *dump (); 186 187private: 188 189 enum 190 { 191 HASH_SIZE = 511, 192 MAX_HASH_SIZE = 1048575 193 }; 194 195 typedef struct Hash 196 { 197 Key_t key; 198 Value_t val; 199 struct Hash *next; 200 } Hash_t; 201 202 void resize (); 203 204 int 205 hashCode (Key_t key) 206 { 207 return get_hash_code (key) % hash_sz; 208 } 209 210 bool 211 equals (Key_t a, Key_t b) 212 { 213 return is_equals (a, b); 214 } 215 216 Key_t 217 copy (Key_t key) 218 { 219 return copy_key (key); 220 } 221 222 Hash_t **hashTable; 223 Vector<Value_t> *vals; 224 int phaseIdx; 225 int hash_sz; 226 int nelem; 227}; 228 229template <typename Key_t, typename Value_t> 230HashMap<Key_t, Value_t> 231::HashMap (int initialCapacity) 232{ 233 if (initialCapacity > 0) 234 vals = new Vector<Value_t>(initialCapacity); 235 else 236 vals = new Vector<Value_t>(); 237 phaseIdx = 0; 238 nelem = 0; 239 hash_sz = HASH_SIZE; 240 hashTable = new Hash_t*[hash_sz]; 241 for (int i = 0; i < hash_sz; i++) 242 hashTable[i] = NULL; 243} 244 245template <typename Key_t, typename Value_t> 246void 247HashMap<Key_t, Value_t>::clear () 248{ 249 vals->reset (); 250 phaseIdx = 0; 251 nelem = 0; 252 for (int i = 0; i < hash_sz; i++) 253 { 254 Hash_t *next; 255 for (Hash_t *p = hashTable[i]; p; p = next) 256 { 257 next = p->next; 258 delete_key (p->key); 259 delete p; 260 } 261 hashTable[i] = NULL; 262 } 263} 264 265template <typename Key_t, typename Value_t> 266void 267HashMap<Key_t, Value_t>::resize () 268{ 269 int old_hash_sz = hash_sz; 270 hash_sz = old_hash_sz * 2 + 1; 271 Hash_t **old_hash_table = hashTable; 272 hashTable = new Hash_t*[hash_sz]; 273 for (int i = 0; i < hash_sz; i++) 274 hashTable[i] = NULL; 275 nelem = 0; 276 for (int i = 0; i < old_hash_sz; i++) 277 { 278 if (old_hash_table[i] != NULL) 279 { 280 Hash_t *old_p; 281 Hash_t *p = old_hash_table[i]; 282 while (p != NULL) 283 { 284 put (p->key, p->val); 285 old_p = p; 286 p = p->next; 287 delete old_p; 288 } 289 } 290 } 291 delete[] old_hash_table; 292} 293 294template <typename Key_t, typename Value_t> 295Value_t 296HashMap<Key_t, Value_t>::get (Key_t key) 297{ 298 int hash_code = hashCode (key); 299 for (Hash_t *p = hashTable[hash_code]; p; p = p->next) 300 if (equals (key, p->key)) 301 return p->val; 302 return NULL; 303} 304 305template <typename Key_t, typename Value_t> 306Vector<Value_t> * 307HashMap<Key_t, Value_t>::values (Key_t key) 308{ 309 Vector<Value_t> *list = new Vector<Value_t>(); 310 int hash_code = hashCode (key); 311 for (Hash_t *p = hashTable[hash_code]; p; p = p->next) 312 { 313 if (equals (key, p->key)) 314 list->append (p->val); 315 } 316 return list; 317} 318 319template <typename Key_t, typename Value_t> 320Value_t 321HashMap<Key_t, Value_t>::get (const Key_t key, Value_t val) 322{ 323 int hash_code = hashCode (key); 324 Hash_t *p, *first = NULL; 325 for (p = hashTable[hash_code]; p; p = p->next) 326 { 327 if (equals (key, p->key)) 328 { 329 if (first == NULL) 330 first = p; 331 if (val == p->val) 332 return first->val; // Always return the first value 333 } 334 } 335 vals->append (val); 336 p = new Hash_t (); 337 p->val = val; 338 p->key = copy (key); 339 if (first) 340 { 341 p->next = first->next; 342 first->next = p; 343 return first->val; // Always return the first value 344 } 345 else 346 { 347 p->next = hashTable[hash_code]; 348 hashTable[hash_code] = p; 349 return val; 350 } 351} 352 353template <typename Key_t, typename Value_t> 354Value_t 355HashMap<Key_t, Value_t>::remove (Key_t key) 356{ 357 int hash_code = hashCode (key); 358 Value_t val = NULL; 359 for (Hash_t *prev = NULL, *p = hashTable[hash_code]; p != NULL;) 360 { 361 if (equals (key, p->key)) 362 { 363 if (prev == NULL) 364 hashTable[hash_code] = p->next; 365 else 366 prev->next = p->next; 367 if (val == NULL) 368 val = p->val; 369 delete_key (p->key); 370 delete p; 371 } 372 else 373 { 374 prev = p; 375 p = p->next; 376 } 377 } 378 return val; 379} 380 381template <typename Key_t, typename Value_t> 382Value_t 383HashMap<Key_t, Value_t>::put (Key_t key, Value_t val) 384{ 385 int hash_code = hashCode (key); 386 vals->append (val); 387 for (Hash_t *p = hashTable[hash_code]; p != NULL; p = p->next) 388 { 389 if (equals (key, p->key)) 390 { 391 Value_t v = p->val; 392 p->val = val; 393 return v; 394 } 395 } 396 Hash_t *p = new Hash_t (); 397 p->val = val; 398 p->key = copy (key); 399 p->next = hashTable[hash_code]; 400 hashTable[hash_code] = p; 401 nelem++; 402 if (nelem == hash_sz) 403 resize (); 404 return val; 405} 406 407template <typename Key_t, typename Value_t> 408char * 409HashMap<Key_t, Value_t>::dump () 410{ 411 StringBuilder sb; 412 char buf[128]; 413 snprintf (buf, sizeof (buf), "HashMap: size=%d ##########\n", vals->size ()); 414 sb.append (buf); 415 for (int i = 0; i < hash_sz; i++) 416 { 417 if (hashTable[i] == NULL) 418 continue; 419 snprintf (buf, sizeof (buf), "%3d:", i); 420 sb.append (buf); 421 char *s = NTXT (" "); 422 for (Hash_t *p = hashTable[i]; p; p = p->next) 423 { 424 sb.append (s); 425 s = NTXT (" "); 426 sb.append (p->key); 427 snprintf (buf, sizeof (buf), " --> 0x%p '%s'\n", 428 p->val, p->val->get_name ()); 429 sb.append (buf); 430 } 431 } 432 return sb.toString (); 433} 434 435#endif // _DBE_HASHMAP_H 436