]> Git Repo - binutils.git/blob - gprofng/src/StringMap.h
Automatic date update in version.in
[binutils.git] / gprofng / src / StringMap.h
1 /* Copyright (C) 2021 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
This page took 0.036063 seconds and 4 git commands to generate.