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