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
get_hash_code(char * a)39 get_hash_code (char *a)
40 {
41 return (int) (crc64 (a, strlen (a)) & 0x7fffffff);
42 }
43
44 template<> inline bool
is_equals(char * a,char * b)45 is_equals (char *a, char *b)
46 {
47 return dbe_strcmp (a, b) == 0;
48 }
49
50 template<> inline char *
copy_key(char * a)51 copy_key (char *a)
52 {
53 return dbe_strdup (a);
54 }
55
56 template<> inline void
delete_key(char * a)57 delete_key (char *a)
58 {
59 return free (a);
60 }
61
62 template<> inline int
get_hash_code(uint64_t a)63 get_hash_code (uint64_t a)
64 {
65 return (int) (a & 0x7fffffff);
66 }
67
68 template<> inline bool
is_equals(uint64_t a,uint64_t b)69 is_equals (uint64_t a, uint64_t b)
70 {
71 return a == b;
72 }
73
74 template<> inline uint64_t
copy_key(uint64_t a)75 copy_key (uint64_t a)
76 {
77 return a;
78 }
79
80 template<> inline void
delete_key(uint64_t a)81 delete_key (uint64_t a)
82 {
83 a = a;
84 }
85
86 template<> inline int
get_hash_code(Histable * a)87 get_hash_code (Histable* a)
88 {
89 return (int) (a->id & 0x7fffffff);
90 }
91
92 template<> inline bool
is_equals(Histable * a,Histable * b)93 is_equals (Histable* a, Histable* b)
94 {
95 return a == b;
96 }
97
98 template<> inline Histable*
copy_key(Histable * a)99 copy_key (Histable* a)
100 {
101 return a;
102 }
103
104 template<> inline void
delete_key(Histable * a)105 delete_key (Histable* a)
106 {
107 a->id = a->id;
108 }
109
110 template<> inline int
get_hash_code(MemObj * a)111 get_hash_code (MemObj* a)
112 {
113 return (int) (a->id & 0x7fffffff);
114 }
115
116 template<> inline bool
is_equals(MemObj * a,MemObj * b)117 is_equals (MemObj* a, MemObj* b)
118 {
119 return a == b;
120 }
121
122 template<> inline MemObj*
copy_key(MemObj * a)123 copy_key (MemObj* a)
124 {
125 return a;
126 }
127
128 template<> inline void
delete_key(MemObj * a)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
~HashMap()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
containsKey(Key_t key)155 containsKey (Key_t key)
156 {
157 Value_t p = get (key);
158 return p != NULL;
159 };
160
161 Vector<Value_t> *
values()162 values ()
163 {
164 return vals;
165 }
166
167 void
reset()168 reset ()
169 {
170 clear ();
171 }
172
173 int
get_phaseIdx()174 get_phaseIdx ()
175 {
176 return phaseIdx;
177 }
178
179 void
set_phaseIdx(int phase)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
hashCode(Key_t key)205 hashCode (Key_t key)
206 {
207 return get_hash_code (key) % hash_sz;
208 }
209
210 bool
equals(Key_t a,Key_t b)211 equals (Key_t a, Key_t b)
212 {
213 return is_equals (a, b);
214 }
215
216 Key_t
copy(Key_t key)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>
HashMap(int initialCapacity)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
clear()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
resize()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
get(Key_t key)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> *
values(Key_t key)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
get(const Key_t key,Value_t val)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
remove(Key_t key)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
put(Key_t key,Value_t val)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 *
dump()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