Debian Codegraph @

ext/sparse/ctrie.c

raw
1 /*
2 * ctrie.c - Compact Trie
3 *
4 * Copyright (c) 2009-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #include "ctrie.h"
35
36 /*
37 * Constructor
38 */
39
40 CompactTrie *MakeCompactTrie(void)
41 {
42 CompactTrie *t = SCM_NEW(CompactTrie);
43 CompactTrieInit(t);
44 return t;
45 }
46
47 void CompactTrieInit(CompactTrie *t)
48 {
49 t->numEntries = 0;
50 t->root = NULL;
51 }
52
53 /*
54 * Nodes
55 */
56 #define KEY2INDEX(key, level) (((key)>>((level)*TRIE_SHIFT)) & TRIE_MASK)
57
58 #define NODE_HAS_ARC(node, ind) SCM_BITS_TEST_IN_WORD(node->emap, (ind))
59 #define NODE_ARC_SET(node, ind) SCM_BITS_SET_IN_WORD(node->emap, (ind))
60 #define NODE_ARC_RESET(node, ind) SCM_BITS_RESET_IN_WORD(node->emap, (ind))
61 #define NODE_EMPTY_P(node) (node->emap == NULL)
62 #define NODE_NCHILDREN(node) Scm__CountBitsInWord(node->emap)
63
64 #define NODE_ARC_IS_LEAF(node, ind) SCM_BITS_TEST_IN_WORD(node->lmap, (ind))
65 #define NODE_LEAF_SET(node, ind) SCM_BITS_SET_IN_WORD(node->lmap, (ind))
66 #define NODE_LEAF_RESET(node, ind) SCM_BITS_RESET_IN_WORD(node->lmap, (ind))
67
68 #define NODE_INDEX2OFF(node, ind) Scm__CountBitsBelow(node->emap, (ind))
69
70 #define NODE_ENTRY(node, off) ((node)->entries[(off)])
71
72 #define KEY_MASK(key) /* empty */
73
74 /* When extending the node, we increase the number of entries by this
75 number instead of increasing every word, to avoid too frequent
76 reallocation. Must be a power of two. */
77 #define NODE_SIZE_INCR 2
78
79 static Node *make_node(int nentry)
80 {
81 int nalloc = (nentry+NODE_SIZE_INCR-1)&(~(NODE_SIZE_INCR-1));
82 /* SCM_NEW2 returns zero cleared chunk. */
83 return SCM_NEW2(Node*, sizeof(Node) + sizeof(void*)*(nalloc-2));
84 }
85
86 static Node *node_insert(Node *orig, u_long ind, void *entry, int leafp)
87 {
88 int size = NODE_NCHILDREN(orig);
89 int insertpoint = Scm__CountBitsBelow(orig->emap, ind);
90
91 if (size&(NODE_SIZE_INCR-1)) {
92 /* we have one more room */
93 NODE_ARC_SET(orig, ind);
94 if (leafp) NODE_LEAF_SET(orig, ind);
95 if (insertpoint < size) {
96 for (int i=size-1; i>=insertpoint; i--) {
97 orig->entries[i+1] = orig->entries[i];
98 }
99 }
100 orig->entries[insertpoint] = entry;
101 return orig;
102 } else {
103 /* we need to extend the node */
104 Node *newn = make_node(size+NODE_SIZE_INCR);
105 newn->emap = orig->emap;
106 newn->lmap = orig->lmap;
107 NODE_ARC_SET(newn, ind);
108 if (leafp) NODE_LEAF_SET(newn, ind);
109 int i = 0;
110 for (; i<insertpoint; i++) newn->entries[i] = orig->entries[i];
111 newn->entries[insertpoint] = entry;
112 for (; i<size; i++) newn->entries[i+1] = orig->entries[i];
113 return newn;
114 }
115 }
116
117 /* returns # of children left */
118 static int node_delete(Node *orig, u_long ind)
119 {
120 int size = NODE_NCHILDREN(orig);
121 int deletepoint = Scm__CountBitsBelow(orig->emap, ind);
122
123 /* TODO: shrink node */
124 NODE_ARC_RESET(orig, ind);
125 NODE_LEAF_RESET(orig, ind);
126 for (int i=deletepoint; i<size-1; i++) {
127 orig->entries[i] = orig->entries[i+1];
128 }
129 return size-1;
130 }
131
132 /*
133 * Leaves
134 */
135
136 static Leaf *new_leaf(u_long key, Leaf *(*creator)(void*), void *data)
137 {
138 Leaf *l = creator(data);
139 leaf_key_set(l, key);
140 return l;
141 }
142
143 /*
144 * Search
145 */
146 static Leaf *get_rec(Node *n, u_long key, int level)
147 {
148 u_long ind = KEY2INDEX(key, level);
149 if (!NODE_HAS_ARC(n, ind)) return NULL;
150 if (NODE_ARC_IS_LEAF(n, ind)) {
151 Leaf *l = (Leaf*)NODE_ENTRY(n, NODE_INDEX2OFF(n, ind));
152 if (leaf_key(l) == key) return l;
153 else return NULL;
154 } else {
155 return get_rec((Node*)NODE_ENTRY(n, NODE_INDEX2OFF(n, ind)),
156 key, level+1);
157 }
158 }
159
160 Leaf *CompactTrieGet(CompactTrie *ct, u_long key)
161 {
162 KEY_MASK(key);
163 if (ct->root == NULL) return NULL;
164 else return get_rec(ct->root, key, 0);
165 }
166
167 /*
168 * Search, and if not found, create
169 */
170 static Node *add_rec(CompactTrie *ct, Node *n, u_long key, int level,
171 Leaf **result, Leaf *(*creator)(void*), void *data)
172
173 {
174 u_long ind = KEY2INDEX(key, level);
175
176 if (!NODE_HAS_ARC(n, ind)) {
177 Leaf *l = new_leaf(key, creator, data);
178 *result = l;
179 ct->numEntries++;
180 return node_insert(n, ind, (void*)l, TRUE);
181 }
182 else if (!NODE_ARC_IS_LEAF(n, ind)) {
183 u_long off = NODE_INDEX2OFF(n, ind);
184 Node *orig = (Node*)NODE_ENTRY(n, off);
185 Node *m = add_rec(ct, orig, key, level+1, result, creator, data);
186 if (m != orig) NODE_ENTRY(n, off) = m;
187 return n;
188 }
189 else {
190 u_long off = NODE_INDEX2OFF(n, ind);
191 Leaf *l0 = (Leaf*)NODE_ENTRY(n, off);
192 u_long k0 = leaf_key(l0);
193
194 if (key == k0) { *result = l0; return n; }
195 u_long i0 = KEY2INDEX(leaf_key(l0), level+1);
196 Node *m = make_node(NODE_SIZE_INCR);
197 NODE_ARC_SET(m, i0);
198 NODE_LEAF_SET(m, i0);
199 NODE_ENTRY(m, 0) = l0;
200 NODE_ENTRY(n, off) = add_rec(ct, m, key, level+1, result, creator, data);
201 NODE_LEAF_RESET(n, ind);
202 return n;
203 }
204 }
205
206 Leaf *CompactTrieAdd(CompactTrie *ct, u_long key,
207 Leaf *(*creator)(void*), void *data)
208 {
209 KEY_MASK(key);
210 if (ct->root == NULL) {
211 Leaf *l = new_leaf(key, creator, data);
212 ct->root = make_node(NODE_SIZE_INCR);
213 ct->numEntries = 1;
214 NODE_ARC_SET(ct->root, key&TRIE_MASK);
215 NODE_LEAF_SET(ct->root, key&TRIE_MASK);
216 NODE_ENTRY(ct->root, 0) = l;
217 return l;
218 } else {
219 Leaf *e = NULL;
220 Node *p = add_rec(ct, ct->root, key, 0, &e, creator, data);
221 if (p != ct->root) ct->root = p;
222 return e;
223 }
224 }
225
226 /*
227 * Delete and clear
228 */
229
230 /* Usually returns the node N, but if deletion of the leaf made N have
231 a leaf as a single child, returns it so that the node itself is
232 eliminated. That is, if the return value != n, the returned pointer
233 always points to a leaf.
234 */
235 void *del_rec(CompactTrie *ct, Node *n, u_long key, int level,
236 Leaf **deleted_leaf)
237 {
238 u_long ind = KEY2INDEX(key, level);
239
240 if (NODE_HAS_ARC(n, ind)) {
241 u_long off = NODE_INDEX2OFF(n, ind);
242 if (!NODE_ARC_IS_LEAF(n, ind)) {
243 Node *orig = (Node*)NODE_ENTRY(n, off);
244 void *m = del_rec(ct, orig, key, level+1, deleted_leaf);
245 if (m != (void*)orig) {
246 if (NODE_NCHILDREN(n) == 1 && level > 0) return m;
247 NODE_ENTRY(n, off) = m;
248 NODE_LEAF_SET(n, ind);
249 }
250 } else {
251 Leaf *l0 = (Leaf*)NODE_ENTRY(n, off);
252 u_long k0 = leaf_key(l0);
253 if (key == k0) {
254 /* We found the leaf to delete. If deletion of the leaf
255 causes this node to have only one leaf, we tell the
256 parent to skip this node. */
257 int nc = node_delete(n, ind);
258 *deleted_leaf = l0;
259 ct->numEntries--;
260 if (nc == 1 && n->lmap != 0 && level > 0) {
261 return NODE_ENTRY(n, 0); /* the only leaf */
262 } else if (nc == 0) {
263 /* this only happens when N is root. */
264 SCM_ASSERT(level == 0);
265 return NULL;
266 }
267 }
268 }
269 }
270 return n;
271 }
272
273 Leaf *CompactTrieDelete(CompactTrie *ct, u_long key)
274 {
275 Leaf *e = NULL;
276 KEY_MASK(key);
277 if (ct->root == NULL) return NULL;
278 ct->root = (Node*)del_rec(ct, ct->root, key, 0, &e);
279 return e;
280 }
281
282 /* 'init' can smash all the contents, but if you want to be more GC-friendly,
283 this one clears up all the freed chunks. */
284 static void clear_rec(CompactTrie *ct, Node *n,
285 void (*clearer)(Leaf*, void*),
286 void *data)
287 {
288 int size = Scm__CountBitsInWord(n->emap);
289 char is_leaf[MAX_NODE_SIZE];
290
291 for (int i=0, off=0; i<MAX_NODE_SIZE; i++) {
292 if (NODE_HAS_ARC(n, i)) {
293 if (NODE_ARC_IS_LEAF(n, i)) is_leaf[off++] = TRUE;
294 else is_leaf[off++] = FALSE;
295 }
296 }
297 for (int i=0; i<size; i++) {
298 if (is_leaf[i]) clearer((Leaf*)NODE_ENTRY(n, i), data);
299 else clear_rec(ct, (Node*)NODE_ENTRY(n, i), clearer, data);
300 NODE_ENTRY(n, i) = NULL;
301 }
302 n->emap = n->lmap = 0;
303 }
304
305 void CompactTrieClear(CompactTrie *ct,
306 void (*clearer)(Leaf*, void*),
307 void *data)
308 {
309 Node *n = ct->root;
310 ct->numEntries = 0;
311 ct->root = NULL;
312 if (n) clear_rec(ct, n, clearer, data);
313 }
314
315 /*
316 * Key finding
317 */
318 static Leaf *next_rec(Node *n, u_long key, int level, int over)
319 {
320 u_int ind = over? 0 : KEY2INDEX(key, level);
321
322 for (u_int i = ind; i < MAX_NODE_SIZE; i++) {
323 if (!NODE_HAS_ARC(n, i)) continue;
324 if (NODE_ARC_IS_LEAF(n, i)) {
325 if (!over && i == ind) continue;
326 return (Leaf*)NODE_ENTRY(n, NODE_INDEX2OFF(n, i));
327 } else {
328 Leaf *l = next_rec((Node*)NODE_ENTRY(n, NODE_INDEX2OFF(n, i)),
329 key, level+1, (over || (i > ind)));
330 if (l) return l;
331 }
332 }
333 return NULL;
334 }
335
336 Leaf *CompactTrieNextLeaf(CompactTrie *ct, u_long key)
337 {
338 KEY_MASK(key);
339 if (ct->root) return next_rec(ct->root, key, 0, FALSE);
340 else return NULL;
341 }
342
343 /* Find leaves with minimum and maximum key. Note: minkey==0 or maxkey==0
344 situation only occurs when another thread is modifying the same trie.
345 We don't guarantee correct operation under the race condition, but
346 we don't want SEGV as well, so we just return NULL in such case.
347 */
348 static Leaf *first_rec(Node *n)
349 {
350 int minkey;
351 if (n->emap == 0) return NULL; /* for safety in MT situation */
352 minkey = Scm__LowestBitNumber(n->emap);
353 if (NODE_ARC_IS_LEAF(n, minkey)) {
354 return (Leaf*)NODE_ENTRY(n, NODE_INDEX2OFF(n, minkey));
355 } else {
356 return first_rec((Node*)NODE_ENTRY(n, NODE_INDEX2OFF(n, minkey)));
357 }
358 }
359
360 Leaf *CompactTrieFirstLeaf(CompactTrie *ct)
361 {
362 if (ct->root) return first_rec(ct->root);
363 else return NULL;
364 }
365
366 static Leaf *last_rec(Node *n)
367 {
368 if (n->emap == 0) return NULL; /* for safety in MT situation */
369 int maxkey = Scm__HighestBitNumber(n->emap);
370 if (NODE_ARC_IS_LEAF(n, maxkey)) {
371 return (Leaf*)NODE_ENTRY(n, NODE_INDEX2OFF(n, maxkey));
372 } else {
373 return last_rec((Node*)NODE_ENTRY(n, NODE_INDEX2OFF(n, maxkey)));
374 }
375 }
376
377 Leaf *CompactTrieLastLeaf(CompactTrie *ct)
378 {
379 if (ct->root) return last_rec(ct->root);
380 else return NULL;
381 }
382
383 /*
384 * Copy.
385 * It is recommended that the caller first clear the dst. The original
386 * tree in dst is detached but otherwise remains intact, and may not be
387 * friendly to GC.
388 */
389 static Node *copy_rec(const Node *s, Leaf *(*copy)(Leaf*, void*), void *data)
390 {
391 int size = Scm__CountBitsInWord(s->emap);
392 Node *d = make_node(size);
393 d->emap = s->emap;
394 d->lmap = s->lmap;
395 for (int i=0, off=0; i<MAX_NODE_SIZE && off < size; i++) {
396 if (!NODE_HAS_ARC(s, i)) continue;
397 if (NODE_ARC_IS_LEAF(s, i)) {
398 NODE_ENTRY(d,off) = copy((Leaf*)NODE_ENTRY(s,off), data);
399 } else {
400 NODE_ENTRY(d,off) = copy_rec((Node*)NODE_ENTRY(s,off), copy, data);
401 }
402 off++;
403 }
404 return d;
405 }
406
407 void CompactTrieCopy(CompactTrie *dst, const CompactTrie *src,
408 Leaf *(*copy)(Leaf*, void*), void *data)
409 {
410 if (src->root) dst->root = copy_rec(src->root, copy, data);
411 else dst->root = NULL;
412 dst->numEntries = src->numEntries;
413 }
414
415 /*
416 * Iterator
417 */
418 void CompactTrieIterInit(CompactTrieIter *it, CompactTrie *ct)
419 {
420 it->trie = ct;
421 it->key = 0;
422 it->begin = TRUE;
423 it->end = FALSE;
424 }
425
426 Leaf *CompactTrieIterNext(CompactTrieIter *it)
427 {
428 Leaf *l;
429 if (it->end) return NULL;
430 if (it->begin) {
431 l = CompactTrieFirstLeaf(it->trie);
432 it->begin = FALSE;
433 } else {
434 l = CompactTrieNextLeaf(it->trie, it->key);
435 }
436 if (l) it->key = leaf_key(l);
437 else it->end = TRUE;
438 return l;
439 }
440
441 /*
442 * Debug dump
443 */
444 static char digit32(u_int n)
445 {
446 return (n < 10)? (char)(n+'0') : (char)(n-10+'a');
447 }
448
449 #define BUF_SIZE 14
450
451 static char *key_dump(u_long key, char *buf) /* buf must be BUF_SIZE length */
452 {
453 buf[BUF_SIZE-1] = '\0';
454 for (int i=0; i<BUF_SIZE-1; i++) {
455 buf[BUF_SIZE-i-2] = digit32(key&TRIE_MASK);
456 key >>= TRIE_SHIFT;
457 }
458 return buf;
459 }
460
461 static void leaf_dump(ScmPort *out, Leaf *self, int indent,
462 void (*dumper)(ScmPort*, Leaf*, int, void*), void *data)
463 {
464 char keybuf[BUF_SIZE];
465 Scm_Printf(out, "LEAF(%s,%x) ", key_dump(leaf_key(self), keybuf),
466 leaf_key(self));
467 if (dumper) dumper(out, self, indent, data);
468 Scm_Printf(out, "\n");
469 }
470
471 static void node_dump(ScmPort *out, Node *n, int level,
472 void (*dumper)(ScmPort*, Leaf*, int, void*), void *data)
473 {
474 Scm_Printf(out, "NODE(%p)\n", n);
475 for (int i=0; i<MAX_NODE_SIZE; i++) {
476 if (!NODE_HAS_ARC(n, i)) continue;
477 Scm_Printf(out, " %*s%c:", level*2, "", digit32(i));
478 if (NODE_ARC_IS_LEAF(n, i)) {
479 leaf_dump(out, (Leaf*)NODE_ENTRY(n, NODE_INDEX2OFF(n, i)),
480 level*2+1, dumper, data);
481 } else {
482 node_dump(out, (Node*)NODE_ENTRY(n, NODE_INDEX2OFF(n, i)),
483 level+1, dumper, data);
484 }
485 }
486 }
487
488 void CompactTrieDump(ScmPort *out, const CompactTrie *ct,
489 void (*dumper)(ScmPort*, Leaf*, int, void*), void *data)
490 {
491 Scm_Printf(out, "CompactTrie(%p, nentries=%d):\n", ct, ct->numEntries);
492 if (ct->root == NULL) {
493 Scm_Putz("(empty)\n", -1, out);
494 } else {
495 node_dump(out, ct->root, 0, dumper, data);
496 }
497 }
498
499 /* returns # of leaves under this subtree. */
500 static u_int check_rec(Node *n, int level,
501 void (*checker)(Leaf*, ScmObj), ScmObj obj)
502 {
503 int direct_leaves = 0, total_leaves = 0;
504 int off = 0;
505 for (int i=0; i<MAX_NODE_SIZE; i++) {
506 if (NODE_HAS_ARC(n, i)) {
507 if (NODE_ARC_IS_LEAF(n, i)) {
508 direct_leaves++;
509 total_leaves++;
510 if (checker) checker((Leaf*)NODE_ENTRY(n, off), obj);
511 } else {
512 total_leaves +=
513 check_rec((Node*)NODE_ENTRY(n, off), level+1, checker, obj);
514 }
515 off++;
516 }
517 }
518 if (off == 0) Scm_Error("%S: encountered an empty node", obj);
519 if (off == 1 && direct_leaves == 1 && level > 0) {
520 Scm_Error("%S: non-root node has only one leaf and no other subtrees",
521 obj);
522 }
523 return total_leaves;
524 }
525
526 void CompactTrieCheck(const CompactTrie *ct, ScmObj obj,
527 void (*checker)(Leaf*, ScmObj))
528 {
529 if (ct->root == NULL) {
530 if (ct->numEntries != 0) {
531 Scm_Error("%S: ct->root is NULL but numEntries is %d",
532 obj, ct->numEntries);
533 }
534 } else {
535 u_int num_leaves = check_rec(ct->root, 0, checker, obj);
536 if (ct->numEntries != num_leaves) {
537 Scm_Error("%S: # of leafs (%d) and numEntries (%d) don't agree",
538 obj, num_leaves, ct->numEntries);
539 }
540 }
541 }