Line data Source code
1 : /**
2 : Copyright (c) 2020-2022 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : #include "SPMemPoolStruct.h"
25 : #include "SPTime.h"
26 :
27 : namespace STAPPLER_VERSIONIZED stappler::mempool::custom {
28 :
29 : constexpr auto INITIAL_MAX = 15; /* tunable == 2^n - 1 */
30 :
31 6145 : static HashEntry **alloc_array(HashTable *ht, uint32_t max) {
32 6145 : return (HashEntry **)ht->pool->calloc(max + 1, sizeof(*ht->array));
33 : }
34 :
35 6146 : void HashTable::init(HashTable *ht, Pool *pool) {
36 6146 : auto now = Time::now().toMicros();
37 6145 : ht->pool = pool;
38 6145 : ht->free = NULL;
39 6145 : ht->count = 0;
40 6145 : ht->max = INITIAL_MAX;
41 6145 : ht->seed = (unsigned int)((now >> 32) ^ now ^ (uintptr_t)pool ^ (uintptr_t)ht ^ (uintptr_t)&now) - 1;
42 6145 : ht->array = alloc_array(ht, ht->max);
43 6143 : ht->hash_func = nullptr;
44 6143 : }
45 :
46 6146 : HashTable * HashTable::make(Pool *pool) {
47 6146 : HashTable *ht = (HashTable *)pool->palloc(sizeof(HashTable));
48 6146 : init(ht, pool);
49 6143 : return ht;
50 : }
51 :
52 0 : HashTable * HashTable::make(Pool *pool, HashFunc hash_func) {
53 0 : HashTable *ht = make(pool);
54 0 : ht->hash_func = hash_func;
55 0 : return ht;
56 : }
57 :
58 0 : HashIndex * HashIndex::next() {
59 0 : _self = _next;
60 0 : while (!_self) {
61 0 : if (index > ht->max) {
62 0 : return nullptr;
63 : }
64 0 : _self = ht->array[index++];
65 : }
66 0 : _next = _self->next;
67 0 : return this;
68 : }
69 :
70 0 : void HashIndex::self(const void **key, size_t *klen, void **val) {
71 0 : if (key) *key = _self->key;
72 0 : if (klen) *klen = _self->klen;
73 0 : if (val) *val = (void *)_self->val;
74 0 : }
75 :
76 0 : HashIndex * HashTable::first(Pool *p) {
77 : HashIndex *hi;
78 0 : if (p) {
79 0 : hi = (HashIndex *)p->palloc(sizeof(*hi));
80 : } else {
81 0 : hi = &iterator;
82 : }
83 :
84 0 : hi->ht = this;
85 0 : hi->index = 0;
86 0 : hi->_self = nullptr;
87 0 : hi->_next = nullptr;
88 0 : return hi->next();
89 : }
90 :
91 0 : static void expand_array(HashTable *ht) {
92 : HashIndex *hi;
93 : HashEntry **new_array;
94 : uint32_t new_max;
95 :
96 0 : new_max = ht->max * 2 + 1;
97 0 : new_array = alloc_array(ht, new_max);
98 0 : for (hi = ht->first(nullptr); hi; hi = hi->next()) {
99 0 : uint32_t i = hi->_self->hash & new_max;
100 0 : hi->_self->next = new_array[i];
101 0 : new_array[i] = hi->_self;
102 : }
103 0 : ht->array = new_array;
104 0 : ht->max = new_max;
105 0 : }
106 :
107 232459 : static uint32_t s_hashfunc_default(const char *char_key, size_t *klen, uint32_t hash) {
108 232459 : if (*klen == maxOf<size_t>()) {
109 130664 : *klen = strlen(char_key);
110 : }
111 :
112 232458 : return hash::hash32(char_key, *klen, 0);
113 : }
114 :
115 232460 : static HashEntry **find_entry(HashTable *ht, const void *key, size_t klen, const void *val) {
116 : HashEntry **hep, *he;
117 : unsigned int hash;
118 :
119 232460 : if (ht->hash_func) {
120 0 : hash = ht->hash_func((const char *)key, &klen);
121 : } else {
122 232460 : hash = s_hashfunc_default((const char *)key, &klen, ht->seed);
123 : }
124 :
125 : /* scan linked list */
126 302174 : for (hep = &ht->array[hash & ht->max], he = *hep; he; hep = &he->next, he = *hep) {
127 243788 : if (he->hash == hash && he->klen == klen && memcmp(he->key, key, klen) == 0) {
128 174103 : break;
129 : }
130 : }
131 232489 : if (he || !val) {
132 213999 : return hep;
133 : }
134 :
135 : /* add a new entry for non-NULL values */
136 18490 : if ((he = ht->free) != NULL) {
137 574 : ht->free = he->next;
138 : } else {
139 17916 : he = (HashEntry *)ht->pool->palloc(sizeof(*he));
140 : }
141 18489 : he->next = NULL;
142 18489 : he->hash = hash;
143 18489 : he->key = key;
144 18489 : he->klen = klen;
145 18489 : he->val = val;
146 18489 : *hep = he;
147 18489 : ht->count++;
148 18489 : return hep;
149 : }
150 :
151 0 : HashTable * HashTable::copy(Pool *pool) const {
152 : HashTable *ht;
153 : HashEntry *new_vals;
154 : uint32_t i, j;
155 :
156 0 : ht = (HashTable *)pool->palloc(sizeof(HashTable) + sizeof(*ht->array) * (max + 1) +sizeof(HashEntry) * count);
157 0 : ht->pool = pool;
158 0 : ht->free = nullptr;
159 0 : ht->count = count;
160 0 : ht->max = max;
161 0 : ht->seed = seed;
162 0 : ht->hash_func = hash_func;
163 0 : ht->array = (HashEntry **)((char *)ht + sizeof(HashTable));
164 :
165 0 : new_vals = (HashEntry *)((char *)(ht) + sizeof(HashTable) + sizeof(*ht->array) * (max + 1));
166 0 : j = 0;
167 0 : for (i = 0; i <= ht->max; i++) {
168 0 : HashEntry **new_entry = &(ht->array[i]);
169 0 : HashEntry *orig_entry = array[i];
170 0 : while (orig_entry) {
171 0 : *new_entry = &new_vals[j++];
172 0 : (*new_entry)->hash = orig_entry->hash;
173 0 : (*new_entry)->key = orig_entry->key;
174 0 : (*new_entry)->klen = orig_entry->klen;
175 0 : (*new_entry)->val = orig_entry->val;
176 0 : new_entry = &((*new_entry)->next);
177 0 : orig_entry = orig_entry->next;
178 : }
179 0 : *new_entry = nullptr;
180 : }
181 0 : return ht;
182 : }
183 :
184 208283 : void *HashTable::get(const void *key, size_t klen) {
185 : HashEntry *he;
186 208283 : he = *find_entry(this, key, klen, NULL);
187 208304 : if (he) {
188 168477 : return (void *)he->val;
189 : } else {
190 39827 : return NULL;
191 : }
192 : }
193 :
194 24180 : void HashTable::set(const void *key, size_t klen, const void *val) {
195 : HashEntry **hep;
196 24180 : hep = find_entry(this, key, klen, val);
197 24182 : if (*hep) {
198 24107 : if (!val) {
199 : /* delete entry */
200 5625 : HashEntry *old = *hep;
201 5625 : *hep = (*hep)->next;
202 5625 : old->next = this->free;
203 5625 : this->free = old;
204 5625 : --this->count;
205 : } else {
206 : /* replace entry */
207 18482 : (*hep)->val = val;
208 : /* check that the collision rate isn't too high */
209 18482 : if (this->count > this->max) {
210 0 : expand_array(this);
211 : }
212 : }
213 : }
214 : /* else key not present and val==NULL */
215 24182 : }
216 :
217 0 : size_t HashTable::size() const {
218 0 : return count;
219 : }
220 :
221 0 : void HashTable::clear() {
222 : HashIndex *hi;
223 0 : for (hi = first(nullptr); hi; hi = hi->next()) {
224 0 : set(hi->_self->key, hi->_self->klen, NULL);
225 : }
226 0 : }
227 :
228 0 : HashTable *HashTable::merge(Pool *p, const HashTable *ov) const {
229 0 : return merge(p, ov, nullptr, nullptr);
230 : }
231 :
232 0 : HashTable *HashTable::merge(Pool *p, const HashTable *overlay, merge_fn merger, const void *data) const {
233 : HashTable *res;
234 0 : HashEntry *new_vals = nullptr;
235 : HashEntry *iter;
236 : HashEntry *ent;
237 : uint32_t i, j, k, hash;
238 :
239 0 : res = (HashTable *)p->palloc(sizeof(HashTable));
240 0 : res->pool = p;
241 0 : res->free = NULL;
242 0 : res->hash_func = this->hash_func;
243 0 : res->count = this->count;
244 0 : res->max = (overlay->max > this->max) ? overlay->max : this->max;
245 0 : if (this->count + overlay->count > res->max) {
246 0 : res->max = res->max * 2 + 1;
247 : }
248 0 : res->seed = this->seed;
249 0 : res->array = alloc_array(res, res->max);
250 0 : if (this->count + overlay->count) {
251 0 : new_vals = (HashEntry *)p->palloc(sizeof(HashEntry) * (this->count + overlay->count));
252 : }
253 0 : j = 0;
254 0 : for (k = 0; k <= this->max; k++) {
255 0 : for (iter = this->array[k]; iter; iter = iter->next) {
256 0 : i = iter->hash & res->max;
257 0 : new_vals[j].klen = iter->klen;
258 0 : new_vals[j].key = iter->key;
259 0 : new_vals[j].val = iter->val;
260 0 : new_vals[j].hash = iter->hash;
261 0 : new_vals[j].next = res->array[i];
262 0 : res->array[i] = &new_vals[j];
263 0 : j++;
264 : }
265 : }
266 :
267 0 : for (k = 0; k <= overlay->max; k++) {
268 0 : for (iter = overlay->array[k]; iter; iter = iter->next) {
269 0 : if (res->hash_func) {
270 0 : hash = res->hash_func((const char *)iter->key, &iter->klen);
271 : } else {
272 0 : hash = s_hashfunc_default((const char *)iter->key, &iter->klen, res->seed);
273 : }
274 0 : i = hash & res->max;
275 0 : for (ent = res->array[i]; ent; ent = ent->next) {
276 0 : if ((ent->klen == iter->klen) && (memcmp(ent->key, iter->key, iter->klen) == 0)) {
277 0 : if (merger) {
278 0 : ent->val = (*merger)(p, iter->key, iter->klen, iter->val, ent->val, data);
279 : } else {
280 0 : ent->val = iter->val;
281 : }
282 0 : break;
283 : }
284 : }
285 0 : if (!ent) {
286 0 : new_vals[j].klen = iter->klen;
287 0 : new_vals[j].key = iter->key;
288 0 : new_vals[j].val = iter->val;
289 0 : new_vals[j].hash = hash;
290 0 : new_vals[j].next = res->array[i];
291 0 : res->array[i] = &new_vals[j];
292 0 : res->count++;
293 0 : j++;
294 : }
295 : }
296 : }
297 0 : return res;
298 : }
299 :
300 0 : bool HashTable::foreach(foreach_fn comp, void *rec) const {
301 : HashIndex hix;
302 : HashIndex *hi;
303 0 : bool rv, dorv = false;
304 :
305 0 : hix.ht = (HashTable *)this;
306 0 : hix.index = 0;
307 0 : hix._self = nullptr;
308 0 : hix._next = nullptr;
309 :
310 0 : if ((hi = hix.next())) {
311 : /* Scan the entire table */
312 : do {
313 0 : rv = comp(rec, hi->_self->key, hi->_self->klen, hi->_self->val);
314 0 : } while (rv && (hi = hi->next()));
315 :
316 0 : if (rv) {
317 0 : dorv = true;
318 : }
319 : }
320 0 : return dorv;
321 : }
322 :
323 : }
|
