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 32 template <typename Key_t> inline int get_hash_code (Key_t a); 33 template <typename Key_t> inline bool is_equals (Key_t a, Key_t b); 34 template <typename Key_t> inline Key_t copy_key (Key_t a); 35 template <typename Key_t> inline void delete_key (Key_t a); 36 37 // Specialization for char* 38 template<> inline int 39 get_hash_code (char *a) 40 { 41 return (int) (crc64 (a, strlen (a)) & 0x7fffffff); 42 } 43 44 template<> inline bool 45 is_equals (char *a, char *b) 46 { 47 return dbe_strcmp (a, b) == 0; 48 } 49 50 template<> inline char * 51 copy_key (char *a) 52 { 53 return dbe_strdup (a); 54 } 55 56 template<> inline void 57 delete_key (char *a) 58 { 59 return free (a); 60 } 61 62 template<> inline int 63 get_hash_code (uint64_t a) 64 { 65 return (int) (a & 0x7fffffff); 66 } 67 68 template<> inline bool 69 is_equals (uint64_t a, uint64_t b) 70 { 71 return a == b; 72 } 73 74 template<> inline uint64_t 75 copy_key (uint64_t a) 76 { 77 return a; 78 } 79 80 template<> inline void 81 delete_key (uint64_t a) 82 { 83 a = a; 84 } 85 86 template<> inline int 87 get_hash_code (Histable* a) 88 { 89 return (int) (a->id & 0x7fffffff); 90 } 91 92 template<> inline bool 93 is_equals (Histable* a, Histable* b) 94 { 95 return a == b; 96 } 97 98 template<> inline Histable* 99 copy_key (Histable* a) 100 { 101 return a; 102 } 103 104 template<> inline void 105 delete_key (Histable* a) 106 { 107 a->id = a->id; 108 } 109 110 template<> inline int 111 get_hash_code (MemObj* a) 112 { 113 return (int) (a->id & 0x7fffffff); 114 } 115 116 template<> inline bool 117 is_equals (MemObj* a, MemObj* b) 118 { 119 return a == b; 120 } 121 122 template<> inline MemObj* 123 copy_key (MemObj* a) 124 { 125 return a; 126 } 127 128 template<> inline void 129 delete_key (MemObj* a) 130 { 131 a->id = a->id; 132 } 133 134 template <typename Key_t, typename Value_t> 135 class HashMap 136 { 137 public: 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 187 private: 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 229 template <typename Key_t, typename Value_t> 230 HashMap<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 245 template <typename Key_t, typename Value_t> 246 void 247 HashMap<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 265 template <typename Key_t, typename Value_t> 266 void 267 HashMap<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 294 template <typename Key_t, typename Value_t> 295 Value_t 296 HashMap<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 305 template <typename Key_t, typename Value_t> 306 Vector<Value_t> * 307 HashMap<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 319 template <typename Key_t, typename Value_t> 320 Value_t 321 HashMap<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 353 template <typename Key_t, typename Value_t> 354 Value_t 355 HashMap<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 381 template <typename Key_t, typename Value_t> 382 Value_t 383 HashMap<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 407 template <typename Key_t, typename Value_t> 408 char * 409 HashMap<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