1 /* Copyright (C) 2021 Free Software Foundation, Inc.
4 This file is part of GNU Binutils.
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)
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.
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. */
22 * String Map implementation.
25 #ifndef _DBE_STRINGMAP_H
26 #define _DBE_STRINGMAP_H
33 template <typename Value_t>
34 class StringMap : public Map<const char*, Value_t>
38 StringMap (int htable_size = 1024, int chunk_size = 16384);
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 ();
51 hash (const char *key)
53 return (unsigned) crc64 (key, strlen (key));
62 int CHUNK_SIZE, HTABLE_SIZE;
66 Vector<Entry*> *index;
70 template <typename Value_t>
71 StringMap<Value_t>::StringMap (int htable_size, int chunk_size)
73 HTABLE_SIZE = htable_size;
74 CHUNK_SIZE = chunk_size;
78 index = new Vector<Entry*>;
79 hashTable = new Entry*[HTABLE_SIZE];
80 for (int i = 0; i < HTABLE_SIZE; i++)
84 template <typename Value_t>
85 StringMap<Value_t>::~StringMap ()
87 for (int i = 0; i < entries; ++i)
89 Entry *entry = index->fetch (i);
92 for (int i = 0; i < nchunks; i++)
99 template <typename Value_t>
101 StringMap<Value_t>::clear ()
103 for (int i = 0; i < entries; ++i)
105 Entry *entry = index->fetch (i);
110 for (int i = 0; i < HTABLE_SIZE; i++)
114 template <typename Value_t>
116 StringMap<Value_t>::put (const char *key, Value_t val)
118 unsigned idx = hash (key) % HTABLE_SIZE;
119 Entry *entry = hashTable[idx];
120 if (entry && strcmp (entry->key, key) == 0)
126 int hi = entries - 1;
129 int md = (lo + hi) / 2;
130 entry = index->fetch (md);
131 int cmp = strcmp (entry->key, key);
142 if (entries >= nchunks * CHUNK_SIZE)
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];
153 // Allocate new chunk for entries.
154 chunks[nchunks - 1] = new Entry[CHUNK_SIZE];
156 entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE];
157 entry->key = strdup (key);
159 index->insert (lo, entry);
160 hashTable[idx] = entry;
164 template <typename Value_t>
166 StringMap<Value_t>::get (const char *key)
168 unsigned idx = hash (key) % HTABLE_SIZE;
169 Entry *entry = hashTable[idx];
170 if (entry && strcmp (entry->key, key) == 0)
173 int hi = entries - 1;
176 int md = (lo + hi) / 2;
177 entry = index->fetch (md);
178 int cmp = strcmp (entry->key, key);
185 hashTable[idx] = entry;
192 template <typename Value_t>
194 StringMap<Value_t>::get (const char *key, typename Map<const char*,
195 Value_t>::Relation rel)
197 if (rel != Map<const char*, Value_t>::REL_EQ)
202 template <typename Value_t>
204 StringMap<Value_t>::remove (const char*)
212 template <typename Value_t>
214 StringMap<Value_t>::values ()
216 Vector<Value_t> *vals = new Vector<Value_t>(entries);
217 for (int i = 0; i < entries; ++i)
219 Entry *entry = index->fetch (i);
220 vals->append (entry->val);
225 template <typename Value_t>
226 Vector<const char*> *
227 StringMap<Value_t>::keySet ()
229 Vector<const char*> *keys = new Vector<const char*>(entries);
230 for (int i = 0; i < entries; ++i)
232 Entry *entry = index->fetch (i);
233 keys->append (entry->key);