1 /* Copyright (C) 2021-2023 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
28 template <typename Key_t, typename Value_t>
29 class DefaultMap : public Map<Key_t, Value_t>
30 {
31 public:
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
43 private:
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
62 template <typename Key_t, typename Value_t>
63 const int DefaultMap<Key_t, Value_t>::CHUNK_SIZE = 16384;
64 template <typename Key_t, typename Value_t>
65 const int DefaultMap<Key_t, Value_t>::HTABLE_SIZE = 1024;
66
67 template <typename Key_t, typename Value_t>
68 DefaultMap<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
79 template <typename Key_t, typename Value_t>
80 DefaultMap<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
89 template <typename Key_t, typename Value_t>
90 void
91 DefaultMap<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
99 template <typename Key_t>
100 inline unsigned
101 hash (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
108 template <typename Key_t, typename Value_t>
109 void
110 DefaultMap<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
157 template <typename Key_t, typename Value_t>
158 Value_t
159 DefaultMap<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
186 template <typename Key_t, typename Value_t>
187 Value_t
188 DefaultMap<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
196 template <typename Key_t, typename Value_t>
197 Value_t
198 DefaultMap<Key_t, Value_t>::remove (Key_t)
199 {
200 // Not implemented
201 if (1)
202 assert (0);
203 return (Value_t) 0;
204 }
205
206 template <typename Key_t, typename Value_t>
207 Vector<Value_t> *
208 DefaultMap<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
219 template <typename Key_t, typename Value_t>
220 Vector<Key_t> *
221 DefaultMap<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