commit aca6b2c
default
·
2024-06-12 05:55:40 +0000 UTC
parent 84fc8d7
Backport from xs (faster dicts).
2 files changed,
+168,
-84
M
xs.h
M
xs.h
+167,
-83
1@@ -1040,12 +1040,29 @@ xs_keyval *xs_keyval_make(xs_keyval *keyval, const xs_str *key, const xs_val *va
2
3 /** dicts **/
4
5+typedef struct {
6+ int value_offset; /* offset to value (from dict start) */
7+ int next; /* next node in sequential search */
8+ int child[4]; /* child nodes in hashed search */
9+ char key[]; /* C string key */
10+} ditem_hdr;
11+
12+typedef struct {
13+ int size; /* size of full dict (_XS_TYPE_SIZE) */
14+ int first; /* first node for sequential search */
15+ int root; /* root node for hashed search */
16+ ditem_hdr ditems[]; /* the ditems */
17+} dict_hdr;
18+
19+
20 xs_dict *xs_dict_new(void)
21 /* creates a new dict */
22 {
23- int sz = 1 + _XS_TYPE_SIZE + 1;
24+ /* size of dict */
25+ int sz = 1 + sizeof(dict_hdr);
26+
27 xs_dict *d = xs_realloc(NULL, sz);
28- memset(d, XSTYPE_EOM, sz);
29+ memset(d, '\0', sz);
30
31 d[0] = XSTYPE_DICT;
32 _xs_put_size(d, sz);
33@@ -1053,140 +1070,207 @@ xs_dict *xs_dict_new(void)
34 return d;
35 }
36
37-
38-xs_dict *_xs_dict_write_keyval(xs_dict *dict, int offset, const xs_str *key, const xs_val *value)
39-/* adds a new keyval to the dict */
40+static int *_xs_dict_locate(const xs_dict *dict, const char *key)
41+/* locates a ditem */
42 {
43- XS_ASSERT_TYPE(dict, XSTYPE_DICT);
44- XS_ASSERT_TYPE(key, XSTYPE_STRING);
45+ unsigned int h = xs_hash_func(key, strlen(key));
46
47- if (value == NULL)
48- value = xs_stock(XSTYPE_NULL);
49+ /* start from the root */
50+ dict_hdr *dh = (dict_hdr *)(dict + 1);
51+ int *off = &dh->root;
52
53- dict = xs_expand(dict, offset, xs_keyval_size(key, value));
54+ while (*off) {
55+ /* pointer to ditem */
56+ ditem_hdr *di = (ditem_hdr *)(dict + *off);
57
58- xs_keyval_make(&dict[offset], key, value);
59+ /* pointer to the key */
60+ const char *d_key = di->key;
61
62- return dict;
63-}
64+ if (strcmp(key, d_key) == 0)
65+ break;
66
67+ off = &di->child[h >> 30];
68+ h <<= 2;
69+ }
70
71-xs_dict *xs_dict_append(xs_dict *dict, const xs_str *key, const xs_val *value)
72-/* appends a memory block to the dict */
73-{
74- return _xs_dict_write_keyval(dict, xs_size(dict) - 1, key, value);
75+ return off;
76 }
77
78
79-xs_dict *xs_dict_prepend(xs_dict *dict, const xs_str *key, const xs_val *value)
80-/* prepends a memory block to the dict */
81+xs_dict *xs_dict_set(xs_dict *dict, const xs_str *key, const xs_val *value)
82+/* sets a key/value pair */
83 {
84- return _xs_dict_write_keyval(dict, 1 + _XS_TYPE_SIZE, key, value);
85-}
86+ if (value == NULL)
87+ value = xs_stock(XSTYPE_NULL);
88
89+ if (xs_type(dict) == XSTYPE_DICT) {
90+ int *o = _xs_dict_locate(dict, key);
91+ int end = xs_size(dict);
92
93-int xs_dict_next(const xs_dict *dict, const xs_str **key, const xs_val **value, int *ctxt)
94-/* iterates a dict, with context */
95-{
96- if (xs_type(dict) != XSTYPE_DICT)
97- return 0;
98+ if (!*o) {
99+ /* ditem does not exist yet: append to the end */
100+ *o = end;
101
102- int goon = 1;
103+ int ksz = xs_size(key);
104+ int vsz = xs_size(value);
105+ int dsz = sizeof(ditem_hdr) + ksz + vsz;
106
107- char *p = (char *)dict;
108+ /* open room in the dict for the full ditem */
109+ dict = xs_expand(dict, end, dsz);
110
111- /* skip the start of the list */
112- if (*ctxt == 0)
113- *ctxt = 1 + _XS_TYPE_SIZE;
114+ dict_hdr *dh = (dict_hdr *)(dict + 1);
115
116- p += *ctxt;
117+ /* build the ditem */
118+ ditem_hdr *di = (ditem_hdr *)(dict + end);
119+ memset(di, '\0', dsz);
120
121- /* an element? */
122- if (xs_type(p) == XSTYPE_KEYVAL) {
123- p++;
124+ /* set the offset to the value */
125+ di->value_offset = end + sizeof(ditem_hdr) + ksz;
126
127- *key = p;
128- p += xs_size(*key);
129+ /* copy the key */
130+ memcpy(di->key, key, ksz);
131
132- *value = p;
133- p += xs_size(*value);
134- }
135- else {
136- /* end of list */
137- goon = 0;
138+ /* copy the value */
139+ memcpy(dict + di->value_offset, value, vsz);
140+
141+ /* chain to the sequential list */
142+ di->next = dh->first;
143+ dh->first = end;
144+ }
145+ else {
146+ /* ditem already exists */
147+ ditem_hdr *di = (ditem_hdr *)(dict + *o);
148+
149+ /* get pointer to the value offset */
150+ int *i = &di->value_offset;
151+
152+ /* deleted? recover offset */
153+ if (*i < 0)
154+ *i *= -1;
155+
156+ /* get old value */
157+ xs_val *o_value = dict + *i;
158+
159+ /* will new value fit over the old one? */
160+ if (xs_size(value) <= xs_size(o_value)) {
161+ /* just overwrite */
162+ /* (difference is leaked inside the dict) */
163+ memcpy(o_value, value, xs_size(value));
164+ }
165+ else {
166+ /* not enough room: new value will live at the end of the dict */
167+ /* (old value is leaked inside the dict) */
168+ *i = end;
169+
170+ dict = xs_insert(dict, end, value);
171+ }
172+ }
173 }
174
175- /* store back the pointer */
176- *ctxt = p - dict;
177+ return dict;
178+}
179
180- return goon;
181+
182+xs_dict *xs_dict_append(xs_dict *dict, const xs_str *key, const xs_val *value)
183+/* just an alias (for this implementation it's the same) */
184+{
185+ return xs_dict_set(dict, key, value);
186 }
187
188
189-const xs_val *xs_dict_get_def(const xs_dict *dict, const xs_str *key, const xs_val *def)
190-/* returns the value directed by key, or the default value */
191+xs_dict *xs_dict_prepend(xs_dict *dict, const xs_str *key, const xs_val *value)
192+/* just an alias (for this implementation it's the same) */
193 {
194- XS_ASSERT_TYPE(dict, XSTYPE_DICT);
195- XS_ASSERT_TYPE(key, XSTYPE_STRING);
196+ return xs_dict_set(dict, key, value);
197+}
198
199- const xs_str *k;
200- const xs_val *v;
201- int c = 0;
202
203- while (xs_dict_next(dict, &k, &v, &c)) {
204- if (strcmp(k, key) == 0)
205- return v;
206+xs_dict *xs_dict_del(xs_dict *dict, const xs_str *key)
207+/* deletes a key/value pair */
208+{
209+ if (xs_type(dict) == XSTYPE_DICT) {
210+ int *o = _xs_dict_locate(dict, key);
211+
212+ if (*o) {
213+ /* found ditem */
214+ ditem_hdr *di = (ditem_hdr *)(dict + *o);
215+
216+ /* deleted ditems have a negative value offset */
217+ di->value_offset *= -1;
218+ }
219 }
220
221- return (xs_val *)def;
222+ return dict;
223 }
224
225
226-xs_dict *xs_dict_del(xs_dict *dict, const xs_str *key)
227-/* deletes a key */
228+const xs_val *xs_dict_get_def(const xs_dict *dict, const xs_str *key, const xs_str *def)
229+/* gets a value by key, or returns def */
230 {
231- XS_ASSERT_TYPE(dict, XSTYPE_DICT);
232- XS_ASSERT_TYPE(key, XSTYPE_STRING);
233-
234- const xs_str *k;
235- const xs_val *v;
236- int c = 0;
237+ if (xs_type(dict) == XSTYPE_DICT) {
238+ int *o = _xs_dict_locate(dict, key);
239
240- while (xs_dict_next(dict, &k, &v, &c)) {
241- if (strcmp(k, key) == 0) {
242- /* the address of the item is just behind the key */
243- char *i = (char *)k - 1;
244+ if (*o) {
245+ /* found ditem */
246+ ditem_hdr *di = (ditem_hdr *)(dict + *o);
247
248- dict = xs_collapse(dict, i - dict, xs_size(i));
249- break;
250+ if (di->value_offset > 0)
251+ return dict + di->value_offset;
252 }
253 }
254
255- return dict;
256+ return def;
257 }
258
259
260-xs_dict *xs_dict_set(xs_dict *dict, const xs_str *key, const xs_val *data)
261-/* sets (replaces) a key */
262+int xs_dict_next(const xs_dict *dict, const xs_str **key, const xs_val **value, int *ctxt)
263+/* dict iterator, with context */
264 {
265- XS_ASSERT_TYPE(dict, XSTYPE_DICT);
266- XS_ASSERT_TYPE(key, XSTYPE_STRING);
267+ if (xs_type(dict) != XSTYPE_DICT)
268+ return 0;
269
270- /* delete the possibly existing key */
271- dict = xs_dict_del(dict, key);
272+ if (*ctxt == 0) {
273+ /* at the beginning: get the first sequential item */
274+ const dict_hdr *dh = (dict_hdr *)(dict + 1);
275+ *ctxt = dh->first;
276+ }
277
278- /* add the data */
279- dict = xs_dict_append(dict, key, data);
280+ *value = NULL;
281
282- return dict;
283+ while (*value == NULL && *ctxt > 0) {
284+ const ditem_hdr *di = (ditem_hdr *)(dict + *ctxt);
285+
286+ /* get value */
287+ if (di->value_offset > 0) {
288+ *value = (xs_val *)(dict + di->value_offset);
289+
290+ /* get key */
291+ *key = (xs_str *)&di->key;
292+ }
293+
294+ /* get offset to next ditem */
295+ *ctxt = di->next ? di->next : -1;
296+ }
297+
298+ return *value != NULL;
299 }
300
301
302 xs_dict *xs_dict_gc(xs_dict *dict)
303 /* collects garbage (leaked values) inside a dict */
304 {
305- /* this kind of dicts does not get garbage */
306- return dict;
307+ xs_dict *nd = xs_dict_new();
308+ const xs_str *k;
309+ const xs_val *v;
310+ int c = 0;
311+
312+ /* shamelessly create a new dict with the same content */
313+ while (xs_dict_next(dict, &k, &v, &c))
314+ nd = xs_dict_set(nd, k, v);
315+
316+ xs_free(dict);
317+
318+ return nd;
319 }
320
321
+1,
-1
1@@ -1 +1 @@
2-/* efb85fa3768a86f1609c520f0c86e8f87239b695 2024-05-27T08:24:40+02:00 */
3+/* 4595e864ae31bc59cca0fff38bd2bac798c2b038 2024-06-08T19:50:32+02:00 */