1/* Copyright (C) 2021-2024 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#ifndef _DBE_DEFAULTMAP_H
22#define _DBE_DEFAULTMAP_H
23
24#include <assert.h>
25#include <vec.h>
26#include <Map.h>
27
28template <typename Key_t, typename Value_t>
29class DefaultMap : public Map<Key_t, Value_t>
30{
31public:
32
33  DefaultMap ();
34  ~DefaultMap ();
35  void clear ();
36  void put (Key_t key, Value_t val);
37  Value_t get (Key_t key);
38  Value_t get (Key_t key, typename Map<Key_t, Value_t>::Relation rel);
39  Value_t remove (Key_t);
40  Vector<Key_t> *keySet ();
41  Vector<Value_t> *values ();
42
43private:
44
45  struct Entry
46  {
47    Key_t key;
48    Value_t val;
49  };
50
51  static const int CHUNK_SIZE;
52  static const int HTABLE_SIZE;
53
54  int entries;
55  int nchunks;
56  Entry **chunks;
57  Vector<Entry*> *index;
58  Entry **hashTable;
59};
60
61
62template <typename Key_t, typename Value_t>
63const int DefaultMap<Key_t, Value_t>::CHUNK_SIZE = 16384;
64template <typename Key_t, typename Value_t>
65const int DefaultMap<Key_t, Value_t>::HTABLE_SIZE = 1024;
66
67template <typename Key_t, typename Value_t>
68DefaultMap<Key_t, Value_t>::DefaultMap ()
69{
70  entries = 0;
71  nchunks = 0;
72  chunks = NULL;
73  index = new Vector<Entry*>;
74  hashTable = new Entry*[HTABLE_SIZE];
75  for (int i = 0; i < HTABLE_SIZE; i++)
76    hashTable[i] = NULL;
77}
78
79template <typename Key_t, typename Value_t>
80DefaultMap<Key_t, Value_t>::~DefaultMap ()
81{
82  for (int i = 0; i < nchunks; i++)
83    delete[] chunks[i];
84  delete[] chunks;
85  delete index;
86  delete[] hashTable;
87}
88
89template <typename Key_t, typename Value_t>
90void
91DefaultMap<Key_t, Value_t>::clear ()
92{
93  entries = 0;
94  index->reset ();
95  for (int i = 0; i < HTABLE_SIZE; i++)
96    hashTable[i] = NULL;
97}
98
99template <typename Key_t>
100inline unsigned
101hash (Key_t key)
102{
103  unsigned h = (unsigned) ((unsigned long) key);
104  h ^= (h >> 20) ^ (h >> 12);
105  return (h ^ (h >> 7) ^ (h >> 4));
106}
107
108template <typename Key_t, typename Value_t>
109void
110DefaultMap<Key_t, Value_t>::put (Key_t key, Value_t val)
111{
112  unsigned idx = hash (key) % HTABLE_SIZE;
113  Entry *entry = hashTable[idx];
114  if (entry && entry->key == key)
115    {
116      entry->val = val;
117      return;
118    }
119  int lo = 0;
120  int hi = entries - 1;
121  while (lo <= hi)
122    {
123      int md = (lo + hi) / 2;
124      entry = index->fetch (md);
125      int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0;
126      if (cmp < 0)
127	lo = md + 1;
128      else if (cmp > 0)
129	hi = md - 1;
130      else
131	{
132	  entry->val = val;
133	  return;
134	}
135    }
136  if (entries >= nchunks * CHUNK_SIZE)
137    {
138      nchunks++;
139      // Reallocate Entry chunk array
140      Entry **new_chunks = new Entry*[nchunks];
141      for (int i = 0; i < nchunks - 1; i++)
142	new_chunks[i] = chunks[i];
143      delete[] chunks;
144      chunks = new_chunks;
145
146      // Allocate new chunk for entries.
147      chunks[nchunks - 1] = new Entry[CHUNK_SIZE];
148    }
149  entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE];
150  entry->key = key;
151  entry->val = val;
152  index->insert (lo, entry);
153  hashTable[idx] = entry;
154  entries++;
155}
156
157template <typename Key_t, typename Value_t>
158Value_t
159DefaultMap<Key_t, Value_t>::get (Key_t key)
160{
161  unsigned idx = hash (key) % HTABLE_SIZE;
162  Entry *entry = hashTable[idx];
163  if (entry && entry->key == key)
164    return entry->val;
165
166  int lo = 0;
167  int hi = entries - 1;
168  while (lo <= hi)
169    {
170      int md = (lo + hi) / 2;
171      entry = index->fetch (md);
172      int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0;
173      if (cmp < 0)
174	lo = md + 1;
175      else if (cmp > 0)
176	hi = md - 1;
177      else
178	{
179	  hashTable[idx] = entry;
180	  return entry->val;
181	}
182    }
183  return (Value_t) 0;
184}
185
186template <typename Key_t, typename Value_t>
187Value_t
188DefaultMap<Key_t, Value_t>::get (Key_t key,
189				 typename Map<Key_t, Value_t>::Relation rel)
190{
191  if (rel != Map<Key_t, Value_t>::REL_EQ)
192    return (Value_t) 0;
193  return get (key);
194}
195
196template <typename Key_t, typename Value_t>
197Value_t
198DefaultMap<Key_t, Value_t>::remove (Key_t)
199{
200  // Not implemented
201  if (1)
202    assert (0);
203  return (Value_t) 0;
204}
205
206template <typename Key_t, typename Value_t>
207Vector<Value_t> *
208DefaultMap<Key_t, Value_t>::values ()
209{
210  Vector<Value_t> *vals = new Vector<Value_t>(entries);
211  for (int i = 0; i < entries; ++i)
212    {
213      Entry *entry = index->fetch (i);
214      vals->append (entry->val);
215    }
216  return vals;
217}
218
219template <typename Key_t, typename Value_t>
220Vector<Key_t> *
221DefaultMap<Key_t, Value_t>::keySet ()
222{
223  Vector<Key_t> *keys = new Vector<Key_t>(entries);
224  for (int i = 0; i < entries; ++i)
225    {
226      Entry *entry = index->fetch (i);
227      keys->append (entry->key);
228    }
229  return keys;
230}
231
232#endif
233