1 //
2 // Copyright 2020 Staysail Systems, Inc. <info@staysail.tech>
3 // Copyright 2018 Capitar IT Group BV <info@capitar.com>
4 //
5 // This software is supplied under the terms of the MIT License, a
6 // copy of which should be located in the distribution where this
7 // file was obtained (LICENSE.txt). A copy of the license may also be
8 // found online at https://opensource.org/licenses/MIT.
9 //
10
11 #include "core/nng_impl.h"
12
13 #include <string.h>
14
15 struct nni_id_entry {
16 uint32_t key;
17 uint32_t skips;
18 void * val;
19 };
20
21 void
nni_id_map_init(nni_id_map * m,uint32_t lo,uint32_t hi,bool randomize)22 nni_id_map_init(nni_id_map *m, uint32_t lo, uint32_t hi, bool randomize)
23 {
24 if (lo == 0) {
25 lo = 1;
26 }
27 if (hi == 0) {
28 hi = 0xffffffffu;
29 }
30 NNI_ASSERT(lo != 0);
31 NNI_ASSERT(hi > lo);
32 m->id_entries = NULL;
33 m->id_count = 0;
34 m->id_load = 0;
35 m->id_cap = 0;
36 m->id_max_load = 0;
37 m->id_min_load = 0; // never shrink below this
38 m->id_min_val = lo;
39 m->id_max_val = hi;
40 if (randomize) {
41 // NB: The range is inclusive.
42 m->id_dyn_val = nni_random() % ((hi - lo) + 1) + lo;
43 } else {
44 m->id_dyn_val = lo;
45 }
46 }
47
48 void
nni_id_map_fini(nni_id_map * m)49 nni_id_map_fini(nni_id_map *m)
50 {
51 if (m->id_entries != NULL) {
52 NNI_FREE_STRUCTS(m->id_entries, m->id_cap);
53 m->id_entries = NULL;
54 m->id_cap = m->id_count = 0;
55 m->id_load = m->id_min_load = m->id_max_load = 0;
56 }
57 }
58
59 // Inspired by Python dict implementation. This probe will visit every
60 // cell. We always hash consecutively assigned IDs. This requires that
61 // the capacity is always a power of two.
62 #define ID_NEXT(m, j) ((((j) *5) + 1) & (m->id_cap - 1))
63 #define ID_INDEX(m, j) ((j) & (m->id_cap - 1))
64
65 static size_t
id_find(nni_id_map * m,uint32_t id)66 id_find(nni_id_map *m, uint32_t id)
67 {
68 size_t index;
69 size_t start;
70 if (m->id_count == 0) {
71 return ((size_t) -1);
72 }
73
74 index = ID_INDEX(m, id);
75 start = index;
76 for (;;) {
77 // The value of ihe_key is only valid if ihe_val is not NULL.
78 if ((m->id_entries[index].key == id) &&
79 (m->id_entries[index].val != NULL)) {
80 return (index);
81 }
82 if (m->id_entries[index].skips == 0) {
83 return ((size_t) -1);
84 }
85 index = ID_NEXT(m, index);
86
87 if (index == start) {
88 break;
89 }
90 }
91
92 return ((size_t) -1);
93 }
94
95 void *
nni_id_get(nni_id_map * m,uint32_t id)96 nni_id_get(nni_id_map *m, uint32_t id)
97 {
98 size_t index;
99 if ((index = id_find(m, id)) == (size_t) -1) {
100 return (NULL);
101 }
102 return (m->id_entries[index].val);
103 }
104
105 static int
id_resize(nni_id_map * m)106 id_resize(nni_id_map *m)
107 {
108 size_t new_cap;
109 size_t old_cap;
110 nni_id_entry *new_entries;
111 nni_id_entry *old_entries;
112 uint32_t i;
113
114 if ((m->id_load < m->id_max_load) && (m->id_load >= m->id_min_load)) {
115 // No resize needed.
116 return (0);
117 }
118
119 old_cap = m->id_cap;
120 new_cap = 8;
121 while (new_cap < (m->id_count * 2)) {
122 new_cap *= 2;
123 }
124 if (new_cap == old_cap) {
125 // Same size.
126 return (0);
127 }
128
129 old_entries = m->id_entries;
130 new_entries = NNI_ALLOC_STRUCTS(new_entries, new_cap);
131 if (new_entries == NULL) {
132 return (NNG_ENOMEM);
133 }
134
135 m->id_entries = new_entries;
136 m->id_cap = new_cap;
137 m->id_load = 0;
138 if (new_cap > 8) {
139 m->id_min_load = new_cap / 8;
140 m->id_max_load = new_cap * 2 / 3;
141 } else {
142 m->id_min_load = 0;
143 m->id_max_load = 5;
144 }
145 for (i = 0; i < old_cap; i++) {
146 size_t index;
147 if (old_entries[i].val == NULL) {
148 continue;
149 }
150 index = old_entries[i].key & (new_cap - 1);
151 for (;;) {
152 // Increment the load unconditionally. It counts
153 // once for every item stored, plus once for each
154 // hashing operation we use to store the item (i.e.
155 // one for the item, plus once for each rehash.)
156 m->id_load++;
157 if (new_entries[index].val == NULL) {
158 // As we are hitting this entry for the first
159 // time, it won't have any skips.
160 NNI_ASSERT(new_entries[index].skips == 0);
161 new_entries[index].val = old_entries[i].val;
162 new_entries[index].key = old_entries[i].key;
163 break;
164 }
165 new_entries[index].skips++;
166 index = ID_NEXT(m, index);
167 }
168 }
169 if (old_cap != 0) {
170 NNI_FREE_STRUCTS(old_entries, old_cap);
171 }
172 return (0);
173 }
174
175 int
nni_id_remove(nni_id_map * m,uint32_t id)176 nni_id_remove(nni_id_map *m, uint32_t id)
177 {
178 size_t index;
179 size_t probe;
180
181 if ((index = id_find(m, id)) == (size_t) -1) {
182 return (NNG_ENOENT);
183 }
184
185 // Now we have found the index where the object exists. We are going
186 // to restart the search, until the index matches, to decrement the
187 // skips counter.
188 probe = ID_INDEX(m, id);
189
190 for (;;) {
191 nni_id_entry *entry;
192
193 // The load was increased once each hashing operation we used
194 // to place the the item. Decrement it accordingly.
195 m->id_load--;
196 entry = &m->id_entries[probe];
197 if (probe == index) {
198 entry->val = NULL;
199 entry->key = 0; // invalid key
200 break;
201 }
202 NNI_ASSERT(entry->skips > 0);
203 entry->skips--;
204 probe = ID_NEXT(m, probe);
205 }
206
207 m->id_count--;
208
209 // Shrink -- but it's ok if we can't.
210 (void) id_resize(m);
211
212 return (0);
213 }
214
215 int
nni_id_set(nni_id_map * m,uint32_t id,void * val)216 nni_id_set(nni_id_map *m, uint32_t id, void *val)
217 {
218 size_t index;
219 nni_id_entry *ent;
220
221 // Try to resize -- if we don't need to, this will be a no-op.
222 if (id_resize(m) != 0) {
223 return (NNG_ENOMEM);
224 }
225
226 // If it already exists, just overwrite the old value.
227 if ((index = id_find(m, id)) != (size_t) -1) {
228 ent = &m->id_entries[index];
229 ent->val = val;
230 return (0);
231 }
232
233 index = ID_INDEX(m, id);
234 for (;;) {
235 ent = &m->id_entries[index];
236
237 // Increment the load count. We do this each time time we
238 // rehash. This may over-count items that collide on the
239 // same rehashing, but this should just cause a table to
240 // grow sooner, which is probably a good thing.
241 m->id_load++;
242 if (ent->val == NULL) {
243 m->id_count++;
244 ent->key = id;
245 ent->val = val;
246 return (0);
247 }
248 // Record the skip count. This being non-zero informs
249 // that a rehash will be necessary. Without this we
250 // would need to scan the entire hash for the match.
251 ent->skips++;
252 index = ID_NEXT(m, index);
253 }
254 }
255
256 int
nni_id_alloc(nni_id_map * m,uint32_t * idp,void * val)257 nni_id_alloc(nni_id_map *m, uint32_t *idp, void *val)
258 {
259 uint32_t id;
260 int rv;
261
262 NNI_ASSERT(val != NULL);
263
264 // range is inclusive, so > to get +1 effect.
265 if (m->id_count > (m->id_max_val - m->id_min_val)) {
266 // Really more like ENOSPC.. the table is filled to max.
267 return (NNG_ENOMEM);
268 }
269
270 for (;;) {
271 id = m->id_dyn_val;
272 m->id_dyn_val++;
273 if (m->id_dyn_val > m->id_max_val) {
274 m->id_dyn_val = m->id_min_val;
275 }
276
277 if (id_find(m, id) == (size_t) -1) {
278 break;
279 }
280 }
281
282 rv = nni_id_set(m, id, val);
283 if (rv == 0) {
284 *idp = id;
285 }
286 return (rv);
287 }
288