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