| 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 |
} |