]>
Commit | Line | Data |
---|---|---|
fd67aa11 | 1 | /* Copyright (C) 2021-2024 Free Software Foundation, Inc. |
bb368aad VM |
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 |