1 /* $NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $ */
2
3 /*-
4 * Copyright (c)2011 YAMAMOTO Takashi,
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29 /*
30 * radixtree.c
31 *
32 * this is an implementation of radix tree, whose keys are uint64_t and leafs
33 * are user provided pointers.
34 *
35 * leaf nodes are just void * and this implementation doesn't care about
36 * what they actually point to. however, this implementation has an assumption
37 * about their alignment. specifically, this implementation assumes that their
38 * 2 LSBs are zero and uses them internally.
39 *
40 * intermediate nodes are automatically allocated and freed internally and
41 * basically users don't need to care about them. only radix_tree_insert_node
42 * function can allocate memory for intermediate nodes and thus can fail for
43 * ENOMEM.
44 *
45 * efficiency:
46 * it's designed to work efficiently with dense index distribution.
47 * the memory consumption (number of necessary intermediate nodes)
48 * heavily depends on index distribution. basically, more dense index
49 * distribution consumes less nodes per item.
50 * approximately,
51 * the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node.
52 * the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item.
53 *
54 * gang lookup:
55 * this implementation provides a way to lookup many nodes quickly via
56 * radix_tree_gang_lookup_node function and its varients.
57 *
58 * tags:
59 * this implementation provides tagging functionality to allow quick
60 * scanning of a subset of leaf nodes. leaf nodes are untagged when
61 * inserted into the tree and can be tagged by radix_tree_set_tag function.
62 * radix_tree_gang_lookup_tagged_node function and its variants returns
63 * only leaf nodes with the given tag. to reduce amount of nodes to visit for
64 * these functions, this implementation keeps tagging information in internal
65 * intermediate nodes and quickly skips uninterested parts of a tree.
66 */
67
68 #include <sys/cdefs.h>
69
70 #if defined(_KERNEL) || defined(_STANDALONE)
71 __KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $");
72 #include <sys/param.h>
73 #include <sys/errno.h>
74 #include <sys/pool.h>
75 #include <sys/radixtree.h>
76 #include <lib/libkern/libkern.h>
77 #if defined(_STANDALONE)
78 #include <lib/libsa/stand.h>
79 #endif /* defined(_STANDALONE) */
80 #else /* defined(_KERNEL) || defined(_STANDALONE) */
81 __RCSID("$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $");
82 #include <assert.h>
83 #include <errno.h>
84 #include <stdbool.h>
85 #include <stdlib.h>
86 #include <string.h>
87 #if 1
88 #define KASSERT assert
89 #else
90 #define KASSERT(a) /* nothing */
91 #endif
92 #endif /* defined(_KERNEL) || defined(_STANDALONE) */
93
94 #include <sys/radixtree.h>
95
96 #define RADIX_TREE_BITS_PER_HEIGHT 4 /* XXX tune */
97 #define RADIX_TREE_PTR_PER_NODE (1 << RADIX_TREE_BITS_PER_HEIGHT)
98 #define RADIX_TREE_MAX_HEIGHT (64 / RADIX_TREE_BITS_PER_HEIGHT)
99 #define RADIX_TREE_INVALID_HEIGHT (RADIX_TREE_MAX_HEIGHT + 1)
100 __CTASSERT((64 % RADIX_TREE_BITS_PER_HEIGHT) == 0);
101
102 __CTASSERT(((1 << RADIX_TREE_TAG_ID_MAX) & (sizeof(int) - 1)) == 0);
103 #define RADIX_TREE_TAG_MASK ((1 << RADIX_TREE_TAG_ID_MAX) - 1)
104
105 static inline void *
entry_ptr(void * p)106 entry_ptr(void *p)
107 {
108
109 return (void *)((uintptr_t)p & ~RADIX_TREE_TAG_MASK);
110 }
111
112 static inline unsigned int
entry_tagmask(void * p)113 entry_tagmask(void *p)
114 {
115
116 return (uintptr_t)p & RADIX_TREE_TAG_MASK;
117 }
118
119 static inline void *
entry_compose(void * p,unsigned int tagmask)120 entry_compose(void *p, unsigned int tagmask)
121 {
122
123 return (void *)((uintptr_t)p | tagmask);
124 }
125
126 static inline bool
entry_match_p(void * p,unsigned int tagmask)127 entry_match_p(void *p, unsigned int tagmask)
128 {
129
130 KASSERT(entry_ptr(p) != NULL || entry_tagmask(p) == 0);
131 if (p == NULL) {
132 return false;
133 }
134 if (tagmask == 0) {
135 return true;
136 }
137 return (entry_tagmask(p) & tagmask) != 0;
138 }
139
140 static inline unsigned int
tagid_to_mask(radix_tree_tagid_t id)141 tagid_to_mask(radix_tree_tagid_t id)
142 {
143
144 KASSERT(id >= 0);
145 KASSERT(id < RADIX_TREE_TAG_ID_MAX);
146 return 1U << id;
147 }
148
149 /*
150 * radix_tree_node: an intermediate node
151 *
152 * we don't care the type of leaf nodes. they are just void *.
153 */
154
155 struct radix_tree_node {
156 void *n_ptrs[RADIX_TREE_PTR_PER_NODE];
157 unsigned int n_nptrs; /* # of non-NULL pointers in n_ptrs */
158 };
159
160 /*
161 * any_children_tagmask:
162 *
163 * return OR'ed tagmask of the given node's children.
164 */
165
166 static unsigned int
any_children_tagmask(const struct radix_tree_node * n)167 any_children_tagmask(const struct radix_tree_node *n)
168 {
169 unsigned int mask;
170 int i;
171
172 mask = 0;
173 for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) {
174 mask |= (unsigned int)(uintptr_t)n->n_ptrs[i];
175 }
176 return mask & RADIX_TREE_TAG_MASK;
177 }
178
179 /*
180 * p_refs[0].pptr == &t->t_root
181 * :
182 * p_refs[n].pptr == &(*p_refs[n-1])->n_ptrs[x]
183 * :
184 * :
185 * p_refs[t->t_height].pptr == &leaf_pointer
186 */
187
188 struct radix_tree_path {
189 struct radix_tree_node_ref {
190 void **pptr;
191 } p_refs[RADIX_TREE_MAX_HEIGHT + 1]; /* +1 for the root ptr */
192 /*
193 * p_lastidx is either the index of the last valid element of p_refs[]
194 * or RADIX_TREE_INVALID_HEIGHT.
195 * RADIX_TREE_INVALID_HEIGHT means that radix_tree_lookup_ptr found
196 * that the height of the tree is not enough to cover the given index.
197 */
198 unsigned int p_lastidx;
199 };
200
201 static inline void **
path_pptr(const struct radix_tree * t,const struct radix_tree_path * p,unsigned int height)202 path_pptr(const struct radix_tree *t, const struct radix_tree_path *p,
203 unsigned int height)
204 {
205
206 KASSERT(height <= t->t_height);
207 return p->p_refs[height].pptr;
208 }
209
210 static inline struct radix_tree_node *
path_node(const struct radix_tree * t,const struct radix_tree_path * p,unsigned int height)211 path_node(const struct radix_tree * t, const struct radix_tree_path *p,
212 unsigned int height)
213 {
214
215 KASSERT(height <= t->t_height);
216 return entry_ptr(*path_pptr(t, p, height));
217 }
218
219 /*
220 * radix_tree_init_tree:
221 *
222 * initialize a tree.
223 */
224
225 void
radix_tree_init_tree(struct radix_tree * t)226 radix_tree_init_tree(struct radix_tree *t)
227 {
228
229 t->t_height = 0;
230 t->t_root = NULL;
231 }
232
233 /*
234 * radix_tree_init_tree:
235 *
236 * clean up a tree.
237 */
238
239 void
radix_tree_fini_tree(struct radix_tree * t)240 radix_tree_fini_tree(struct radix_tree *t)
241 {
242
243 KASSERT(t->t_root == NULL);
244 KASSERT(t->t_height == 0);
245 }
246
247 bool
radix_tree_empty_tree_p(struct radix_tree * t)248 radix_tree_empty_tree_p(struct radix_tree *t)
249 {
250
251 return t->t_root == NULL;
252 }
253
254 bool
radix_tree_empty_tagged_tree_p(struct radix_tree * t,radix_tree_tagid_t tagid)255 radix_tree_empty_tagged_tree_p(struct radix_tree *t, radix_tree_tagid_t tagid)
256 {
257 const unsigned int tagmask = tagid_to_mask(tagid);
258
259 return (entry_tagmask(t->t_root) & tagmask) == 0;
260 }
261
262 static void
radix_tree_node_init(struct radix_tree_node * n)263 radix_tree_node_init(struct radix_tree_node *n)
264 {
265
266 memset(n, 0, sizeof(*n));
267 }
268
269 #if defined(_KERNEL)
270 pool_cache_t radix_tree_node_cache __read_mostly;
271
272 static int
radix_tree_node_ctor(void * dummy,void * item,int flags)273 radix_tree_node_ctor(void *dummy, void *item, int flags)
274 {
275 struct radix_tree_node *n = item;
276
277 KASSERT(dummy == NULL);
278 radix_tree_node_init(n);
279 return 0;
280 }
281
282 /*
283 * radix_tree_init:
284 *
285 * initialize the subsystem.
286 */
287
288 void
radix_tree_init(void)289 radix_tree_init(void)
290 {
291
292 radix_tree_node_cache = pool_cache_init(sizeof(struct radix_tree_node),
293 0, 0, 0, "radix_tree_node", NULL, IPL_NONE, radix_tree_node_ctor,
294 NULL, NULL);
295 KASSERT(radix_tree_node_cache != NULL);
296 }
297 #endif /* defined(_KERNEL) */
298
299 static bool __unused
radix_tree_node_clean_p(const struct radix_tree_node * n)300 radix_tree_node_clean_p(const struct radix_tree_node *n)
301 {
302 unsigned int i;
303
304 if (n->n_nptrs != 0) {
305 return false;
306 }
307 for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) {
308 if (n->n_ptrs[i] != NULL) {
309 return false;
310 }
311 }
312 return true;
313 }
314
315 static struct radix_tree_node *
radix_tree_alloc_node(void)316 radix_tree_alloc_node(void)
317 {
318 struct radix_tree_node *n;
319
320 #if defined(_KERNEL)
321 n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT);
322 #else /* defined(_KERNEL) */
323 #if defined(_STANDALONE)
324 n = alloc(sizeof(*n));
325 #else /* defined(_STANDALONE) */
326 n = malloc(sizeof(*n));
327 #endif /* defined(_STANDALONE) */
328 if (n != NULL) {
329 radix_tree_node_init(n);
330 }
331 #endif /* defined(_KERNEL) */
332 KASSERT(n == NULL || radix_tree_node_clean_p(n));
333 return n;
334 }
335
336 static void
radix_tree_free_node(struct radix_tree_node * n)337 radix_tree_free_node(struct radix_tree_node *n)
338 {
339
340 KASSERT(radix_tree_node_clean_p(n));
341 #if defined(_KERNEL)
342 pool_cache_put(radix_tree_node_cache, n);
343 #elif defined(_STANDALONE)
344 dealloc(n, sizeof(*n));
345 #else
346 free(n);
347 #endif
348 }
349
350 static int
radix_tree_grow(struct radix_tree * t,unsigned int newheight)351 radix_tree_grow(struct radix_tree *t, unsigned int newheight)
352 {
353 const unsigned int tagmask = entry_tagmask(t->t_root);
354
355 KASSERT(newheight <= 64 / RADIX_TREE_BITS_PER_HEIGHT);
356 if (t->t_root == NULL) {
357 t->t_height = newheight;
358 return 0;
359 }
360 while (t->t_height < newheight) {
361 struct radix_tree_node *n;
362
363 n = radix_tree_alloc_node();
364 if (n == NULL) {
365 /*
366 * don't bother to revert our changes.
367 * the caller will likely retry.
368 */
369 return ENOMEM;
370 }
371 n->n_nptrs = 1;
372 n->n_ptrs[0] = t->t_root;
373 t->t_root = entry_compose(n, tagmask);
374 t->t_height++;
375 }
376 return 0;
377 }
378
379 /*
380 * radix_tree_lookup_ptr:
381 *
382 * an internal helper function used for various exported functions.
383 *
384 * return the pointer to store the node for the given index.
385 *
386 * if alloc is true, try to allocate the storage. (note for _KERNEL:
387 * in that case, this function can block.) if the allocation failed or
388 * alloc is false, return NULL.
389 *
390 * if path is not NULL, fill it for the caller's investigation.
391 *
392 * if tagmask is not zero, search only for nodes with the tag set.
393 * note that, however, this function doesn't check the tagmask for the leaf
394 * pointer. it's a caller's responsibility to investigate the value which
395 * is pointed by the returned pointer if necessary.
396 *
397 * while this function is a bit large, as it's called with some constant
398 * arguments, inlining might have benefits. anyway, a compiler will decide.
399 */
400
401 static inline void **
radix_tree_lookup_ptr(struct radix_tree * t,uint64_t idx,struct radix_tree_path * path,bool alloc,const unsigned int tagmask)402 radix_tree_lookup_ptr(struct radix_tree *t, uint64_t idx,
403 struct radix_tree_path *path, bool alloc, const unsigned int tagmask)
404 {
405 struct radix_tree_node *n;
406 int hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height;
407 int shift;
408 void **vpp;
409 const uint64_t mask = (UINT64_C(1) << RADIX_TREE_BITS_PER_HEIGHT) - 1;
410 struct radix_tree_node_ref *refs = NULL;
411
412 /*
413 * check unsupported combinations
414 */
415 KASSERT(tagmask == 0 || !alloc);
416 KASSERT(path == NULL || !alloc);
417 vpp = &t->t_root;
418 if (path != NULL) {
419 refs = path->p_refs;
420 refs->pptr = vpp;
421 }
422 n = NULL;
423 for (shift = 64 - RADIX_TREE_BITS_PER_HEIGHT; shift >= 0;) {
424 struct radix_tree_node *c;
425 void *entry;
426 const uint64_t i = (idx >> shift) & mask;
427
428 if (shift >= hshift) {
429 unsigned int newheight;
430
431 KASSERT(vpp == &t->t_root);
432 if (i == 0) {
433 shift -= RADIX_TREE_BITS_PER_HEIGHT;
434 continue;
435 }
436 if (!alloc) {
437 if (path != NULL) {
438 KASSERT((refs - path->p_refs) == 0);
439 path->p_lastidx =
440 RADIX_TREE_INVALID_HEIGHT;
441 }
442 return NULL;
443 }
444 newheight = shift / RADIX_TREE_BITS_PER_HEIGHT + 1;
445 if (radix_tree_grow(t, newheight)) {
446 return NULL;
447 }
448 hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height;
449 }
450 entry = *vpp;
451 c = entry_ptr(entry);
452 if (c == NULL ||
453 (tagmask != 0 &&
454 (entry_tagmask(entry) & tagmask) == 0)) {
455 if (!alloc) {
456 if (path != NULL) {
457 path->p_lastidx = refs - path->p_refs;
458 }
459 return NULL;
460 }
461 c = radix_tree_alloc_node();
462 if (c == NULL) {
463 return NULL;
464 }
465 *vpp = c;
466 if (n != NULL) {
467 KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE);
468 n->n_nptrs++;
469 }
470 }
471 n = c;
472 vpp = &n->n_ptrs[i];
473 if (path != NULL) {
474 refs++;
475 refs->pptr = vpp;
476 }
477 shift -= RADIX_TREE_BITS_PER_HEIGHT;
478 }
479 if (alloc) {
480 KASSERT(*vpp == NULL);
481 if (n != NULL) {
482 KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE);
483 n->n_nptrs++;
484 }
485 }
486 if (path != NULL) {
487 path->p_lastidx = refs - path->p_refs;
488 }
489 return vpp;
490 }
491
492 /*
493 * radix_tree_insert_node:
494 *
495 * insert the node at idx.
496 * it's illegal to insert NULL.
497 * it's illegal to insert a non-aligned pointer.
498 *
499 * this function returns ENOMEM if necessary memory allocation failed.
500 * otherwise, this function returns 0.
501 *
502 * note that inserting a node can involves memory allocation for intermediate
503 * nodes. if _KERNEL, it's done with no-sleep IPL_NONE memory allocation.
504 *
505 * for the newly inserted node, all tags are cleared.
506 */
507
508 int
radix_tree_insert_node(struct radix_tree * t,uint64_t idx,void * p)509 radix_tree_insert_node(struct radix_tree *t, uint64_t idx, void *p)
510 {
511 void **vpp;
512
513 KASSERT(p != NULL);
514 KASSERT(entry_compose(p, 0) == p);
515 vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0);
516 if (vpp == NULL) {
517 return ENOMEM;
518 }
519 KASSERT(*vpp == NULL);
520 *vpp = p;
521 return 0;
522 }
523
524 /*
525 * radix_tree_replace_node:
526 *
527 * replace a node at the given index with the given node.
528 * return the old node.
529 * it's illegal to try to replace a node which has not been inserted.
530 *
531 * this function doesn't change tags.
532 */
533
534 void *
radix_tree_replace_node(struct radix_tree * t,uint64_t idx,void * p)535 radix_tree_replace_node(struct radix_tree *t, uint64_t idx, void *p)
536 {
537 void **vpp;
538 void *oldp;
539
540 KASSERT(p != NULL);
541 KASSERT(entry_compose(p, 0) == p);
542 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
543 KASSERT(vpp != NULL);
544 oldp = *vpp;
545 KASSERT(oldp != NULL);
546 *vpp = entry_compose(p, entry_tagmask(*vpp));
547 return entry_ptr(oldp);
548 }
549
550 /*
551 * radix_tree_remove_node:
552 *
553 * remove the node at idx.
554 * it's illegal to try to remove a node which has not been inserted.
555 */
556
557 void *
radix_tree_remove_node(struct radix_tree * t,uint64_t idx)558 radix_tree_remove_node(struct radix_tree *t, uint64_t idx)
559 {
560 struct radix_tree_path path;
561 void **vpp;
562 void *oldp;
563 int i;
564
565 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
566 KASSERT(vpp != NULL);
567 oldp = *vpp;
568 KASSERT(oldp != NULL);
569 KASSERT(path.p_lastidx == t->t_height);
570 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
571 *vpp = NULL;
572 for (i = t->t_height - 1; i >= 0; i--) {
573 void *entry;
574 struct radix_tree_node ** const pptr =
575 (struct radix_tree_node **)path_pptr(t, &path, i);
576 struct radix_tree_node *n;
577
578 KASSERT(pptr != NULL);
579 entry = *pptr;
580 n = entry_ptr(entry);
581 KASSERT(n != NULL);
582 KASSERT(n->n_nptrs > 0);
583 n->n_nptrs--;
584 if (n->n_nptrs > 0) {
585 break;
586 }
587 radix_tree_free_node(n);
588 *pptr = NULL;
589 }
590 /*
591 * fix up height
592 */
593 if (i < 0) {
594 KASSERT(t->t_root == NULL);
595 t->t_height = 0;
596 }
597 /*
598 * update tags
599 */
600 for (; i >= 0; i--) {
601 void *entry;
602 struct radix_tree_node ** const pptr =
603 (struct radix_tree_node **)path_pptr(t, &path, i);
604 struct radix_tree_node *n;
605 unsigned int newmask;
606
607 KASSERT(pptr != NULL);
608 entry = *pptr;
609 n = entry_ptr(entry);
610 KASSERT(n != NULL);
611 KASSERT(n->n_nptrs > 0);
612 newmask = any_children_tagmask(n);
613 if (newmask == entry_tagmask(entry)) {
614 break;
615 }
616 *pptr = entry_compose(n, newmask);
617 }
618 /*
619 * XXX is it worth to try to reduce height?
620 * if we do that, make radix_tree_grow rollback its change as well.
621 */
622 return entry_ptr(oldp);
623 }
624
625 /*
626 * radix_tree_lookup_node:
627 *
628 * returns the node at idx.
629 * returns NULL if nothing is found at idx.
630 */
631
632 void *
radix_tree_lookup_node(struct radix_tree * t,uint64_t idx)633 radix_tree_lookup_node(struct radix_tree *t, uint64_t idx)
634 {
635 void **vpp;
636
637 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
638 if (vpp == NULL) {
639 return NULL;
640 }
641 return entry_ptr(*vpp);
642 }
643
644 static inline void
gang_lookup_init(struct radix_tree * t,uint64_t idx,struct radix_tree_path * path,const unsigned int tagmask)645 gang_lookup_init(struct radix_tree *t, uint64_t idx,
646 struct radix_tree_path *path, const unsigned int tagmask)
647 {
648 void **vpp;
649
650 vpp = radix_tree_lookup_ptr(t, idx, path, false, tagmask);
651 KASSERT(vpp == NULL ||
652 vpp == path_pptr(t, path, path->p_lastidx));
653 KASSERT(&t->t_root == path_pptr(t, path, 0));
654 KASSERT(path->p_lastidx == RADIX_TREE_INVALID_HEIGHT ||
655 path->p_lastidx == t->t_height ||
656 !entry_match_p(*path_pptr(t, path, path->p_lastidx), tagmask));
657 }
658
659 /*
660 * gang_lookup_scan:
661 *
662 * a helper routine for radix_tree_gang_lookup_node and its variants.
663 */
664
665 static inline unsigned int
666 __attribute__((__always_inline__))
gang_lookup_scan(struct radix_tree * t,struct radix_tree_path * path,void ** results,unsigned int maxresults,const unsigned int tagmask,bool reverse)667 gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path,
668 void **results, unsigned int maxresults, const unsigned int tagmask,
669 bool reverse)
670 {
671
672 /*
673 * we keep the path updated only for lastidx-1.
674 * vpp is what path_pptr(t, path, lastidx) would be.
675 */
676 void **vpp;
677 unsigned int nfound;
678 unsigned int lastidx;
679 /*
680 * set up scan direction dependant constants so that we can iterate
681 * n_ptrs as the following.
682 *
683 * for (i = first; i != guard; i += step)
684 * visit n->n_ptrs[i];
685 */
686 const int step = reverse ? -1 : 1;
687 const unsigned int first = reverse ? RADIX_TREE_PTR_PER_NODE - 1 : 0;
688 const unsigned int last = reverse ? 0 : RADIX_TREE_PTR_PER_NODE - 1;
689 const unsigned int guard = last + step;
690
691 KASSERT(maxresults > 0);
692 KASSERT(&t->t_root == path_pptr(t, path, 0));
693 lastidx = path->p_lastidx;
694 KASSERT(lastidx == RADIX_TREE_INVALID_HEIGHT ||
695 lastidx == t->t_height ||
696 !entry_match_p(*path_pptr(t, path, lastidx), tagmask));
697 nfound = 0;
698 if (lastidx == RADIX_TREE_INVALID_HEIGHT) {
699 if (reverse) {
700 lastidx = 0;
701 vpp = path_pptr(t, path, lastidx);
702 goto descend;
703 }
704 return 0;
705 }
706 vpp = path_pptr(t, path, lastidx);
707 while (/*CONSTCOND*/true) {
708 struct radix_tree_node *n;
709 unsigned int i;
710
711 if (entry_match_p(*vpp, tagmask)) {
712 KASSERT(lastidx == t->t_height);
713 /*
714 * record the matching non-NULL leaf.
715 */
716 results[nfound] = entry_ptr(*vpp);
717 nfound++;
718 if (nfound == maxresults) {
719 return nfound;
720 }
721 }
722 scan_siblings:
723 /*
724 * try to find the next matching non-NULL sibling.
725 */
726 if (lastidx == 0) {
727 /*
728 * the root has no siblings.
729 * we've done.
730 */
731 KASSERT(vpp == &t->t_root);
732 break;
733 }
734 n = path_node(t, path, lastidx - 1);
735 if (*vpp != NULL && n->n_nptrs == 1) {
736 /*
737 * optimization; if the node has only a single pointer
738 * and we've already visited it, there's no point to
739 * keep scanning in this node.
740 */
741 goto no_siblings;
742 }
743 for (i = vpp - n->n_ptrs + step; i != guard; i += step) {
744 KASSERT(i < RADIX_TREE_PTR_PER_NODE);
745 if (entry_match_p(n->n_ptrs[i], tagmask)) {
746 vpp = &n->n_ptrs[i];
747 break;
748 }
749 }
750 if (i == guard) {
751 no_siblings:
752 /*
753 * not found. go to parent.
754 */
755 lastidx--;
756 vpp = path_pptr(t, path, lastidx);
757 goto scan_siblings;
758 }
759 descend:
760 /*
761 * following the left-most (or right-most in the case of
762 * reverse scan) child node, decend until reaching the leaf or
763 * an non-matching entry.
764 */
765 while (entry_match_p(*vpp, tagmask) && lastidx < t->t_height) {
766 /*
767 * save vpp in the path so that we can come back to this
768 * node after finishing visiting children.
769 */
770 path->p_refs[lastidx].pptr = vpp;
771 n = entry_ptr(*vpp);
772 vpp = &n->n_ptrs[first];
773 lastidx++;
774 }
775 }
776 return nfound;
777 }
778
779 /*
780 * radix_tree_gang_lookup_node:
781 *
782 * search nodes starting from idx in the ascending order.
783 * results should be an array large enough to hold maxresults pointers.
784 * returns the number of nodes found, up to maxresults.
785 * returning less than maxresults means there are no more nodes.
786 *
787 * the result of this function is semantically equivalent to what could be
788 * obtained by repeated calls of radix_tree_lookup_node with increasing index.
789 * but this function is much faster when node indexes are distributed sparsely.
790 *
791 * note that this function doesn't return exact values of node indexes of
792 * found nodes. if they are important for a caller, it's the caller's
793 * responsibility to check them, typically by examinining the returned nodes
794 * using some caller-specific knowledge about them.
795 */
796
797 unsigned int
radix_tree_gang_lookup_node(struct radix_tree * t,uint64_t idx,void ** results,unsigned int maxresults)798 radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx,
799 void **results, unsigned int maxresults)
800 {
801 struct radix_tree_path path;
802
803 gang_lookup_init(t, idx, &path, 0);
804 return gang_lookup_scan(t, &path, results, maxresults, 0, false);
805 }
806
807 /*
808 * radix_tree_gang_lookup_node_reverse:
809 *
810 * same as radix_tree_gang_lookup_node except that this one scans the
811 * tree in the reverse order. ie. descending index values.
812 */
813
814 unsigned int
radix_tree_gang_lookup_node_reverse(struct radix_tree * t,uint64_t idx,void ** results,unsigned int maxresults)815 radix_tree_gang_lookup_node_reverse(struct radix_tree *t, uint64_t idx,
816 void **results, unsigned int maxresults)
817 {
818 struct radix_tree_path path;
819
820 gang_lookup_init(t, idx, &path, 0);
821 return gang_lookup_scan(t, &path, results, maxresults, 0, true);
822 }
823
824 /*
825 * radix_tree_gang_lookup_tagged_node:
826 *
827 * same as radix_tree_gang_lookup_node except that this one only returns
828 * nodes tagged with tagid.
829 */
830
831 unsigned int
radix_tree_gang_lookup_tagged_node(struct radix_tree * t,uint64_t idx,void ** results,unsigned int maxresults,radix_tree_tagid_t tagid)832 radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx,
833 void **results, unsigned int maxresults, radix_tree_tagid_t tagid)
834 {
835 struct radix_tree_path path;
836 const unsigned int tagmask = tagid_to_mask(tagid);
837
838 gang_lookup_init(t, idx, &path, tagmask);
839 return gang_lookup_scan(t, &path, results, maxresults, tagmask, false);
840 }
841
842 /*
843 * radix_tree_gang_lookup_tagged_node_reverse:
844 *
845 * same as radix_tree_gang_lookup_tagged_node except that this one scans the
846 * tree in the reverse order. ie. descending index values.
847 */
848
849 unsigned int
radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree * t,uint64_t idx,void ** results,unsigned int maxresults,radix_tree_tagid_t tagid)850 radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *t, uint64_t idx,
851 void **results, unsigned int maxresults, radix_tree_tagid_t tagid)
852 {
853 struct radix_tree_path path;
854 const unsigned int tagmask = tagid_to_mask(tagid);
855
856 gang_lookup_init(t, idx, &path, tagmask);
857 return gang_lookup_scan(t, &path, results, maxresults, tagmask, true);
858 }
859
860 /*
861 * radix_tree_get_tag:
862 *
863 * return if the tag is set for the node at the given index. (true if set)
864 * it's illegal to call this function for a node which has not been inserted.
865 */
866
867 bool
radix_tree_get_tag(struct radix_tree * t,uint64_t idx,radix_tree_tagid_t tagid)868 radix_tree_get_tag(struct radix_tree *t, uint64_t idx,
869 radix_tree_tagid_t tagid)
870 {
871 #if 1
872 const unsigned int tagmask = tagid_to_mask(tagid);
873 void **vpp;
874
875 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask);
876 if (vpp == NULL) {
877 return false;
878 }
879 KASSERT(*vpp != NULL);
880 return (entry_tagmask(*vpp) & tagmask) != 0;
881 #else
882 const unsigned int tagmask = tagid_to_mask(tagid);
883 void **vpp;
884
885 vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
886 KASSERT(vpp != NULL);
887 return (entry_tagmask(*vpp) & tagmask) != 0;
888 #endif
889 }
890
891 /*
892 * radix_tree_set_tag:
893 *
894 * set the tag for the node at the given index.
895 * it's illegal to call this function for a node which has not been inserted.
896 */
897
898 void
radix_tree_set_tag(struct radix_tree * t,uint64_t idx,radix_tree_tagid_t tagid)899 radix_tree_set_tag(struct radix_tree *t, uint64_t idx,
900 radix_tree_tagid_t tagid)
901 {
902 struct radix_tree_path path;
903 const unsigned int tagmask = tagid_to_mask(tagid);
904 void **vpp;
905 int i;
906
907 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
908 KASSERT(vpp != NULL);
909 KASSERT(*vpp != NULL);
910 KASSERT(path.p_lastidx == t->t_height);
911 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
912 for (i = t->t_height; i >= 0; i--) {
913 void ** const pptr = (void **)path_pptr(t, &path, i);
914 void *entry;
915
916 KASSERT(pptr != NULL);
917 entry = *pptr;
918 if ((entry_tagmask(entry) & tagmask) != 0) {
919 break;
920 }
921 *pptr = (void *)((uintptr_t)entry | tagmask);
922 }
923 }
924
925 /*
926 * radix_tree_clear_tag:
927 *
928 * clear the tag for the node at the given index.
929 * it's illegal to call this function for a node which has not been inserted.
930 */
931
932 void
radix_tree_clear_tag(struct radix_tree * t,uint64_t idx,radix_tree_tagid_t tagid)933 radix_tree_clear_tag(struct radix_tree *t, uint64_t idx,
934 radix_tree_tagid_t tagid)
935 {
936 struct radix_tree_path path;
937 const unsigned int tagmask = tagid_to_mask(tagid);
938 void **vpp;
939 int i;
940
941 vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
942 KASSERT(vpp != NULL);
943 KASSERT(*vpp != NULL);
944 KASSERT(path.p_lastidx == t->t_height);
945 KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
946 /*
947 * if already cleared, nothing to do
948 */
949 if ((entry_tagmask(*vpp) & tagmask) == 0) {
950 return;
951 }
952 /*
953 * clear the tag only if no children have the tag.
954 */
955 for (i = t->t_height; i >= 0; i--) {
956 void ** const pptr = (void **)path_pptr(t, &path, i);
957 void *entry;
958
959 KASSERT(pptr != NULL);
960 entry = *pptr;
961 KASSERT((entry_tagmask(entry) & tagmask) != 0);
962 *pptr = entry_compose(entry_ptr(entry),
963 entry_tagmask(entry) & ~tagmask);
964 /*
965 * check if we should proceed to process the next level.
966 */
967 if (0 < i) {
968 struct radix_tree_node *n = path_node(t, &path, i - 1);
969
970 if ((any_children_tagmask(n) & tagmask) != 0) {
971 break;
972 }
973 }
974 }
975 }
976
977 #if defined(UNITTEST)
978
979 #include <inttypes.h>
980 #include <stdio.h>
981
982 static void
radix_tree_dump_node(const struct radix_tree * t,void * vp,uint64_t offset,unsigned int height)983 radix_tree_dump_node(const struct radix_tree *t, void *vp,
984 uint64_t offset, unsigned int height)
985 {
986 struct radix_tree_node *n;
987 unsigned int i;
988
989 for (i = 0; i < t->t_height - height; i++) {
990 printf(" ");
991 }
992 if (entry_tagmask(vp) == 0) {
993 printf("[%" PRIu64 "] %p", offset, entry_ptr(vp));
994 } else {
995 printf("[%" PRIu64 "] %p (tagmask=0x%x)", offset, entry_ptr(vp),
996 entry_tagmask(vp));
997 }
998 if (height == 0) {
999 printf(" (leaf)\n");
1000 return;
1001 }
1002 n = entry_ptr(vp);
1003 assert(any_children_tagmask(n) == entry_tagmask(vp));
1004 printf(" (%u children)\n", n->n_nptrs);
1005 for (i = 0; i < __arraycount(n->n_ptrs); i++) {
1006 void *c;
1007
1008 c = n->n_ptrs[i];
1009 if (c == NULL) {
1010 continue;
1011 }
1012 radix_tree_dump_node(t, c,
1013 offset + i * (UINT64_C(1) <<
1014 (RADIX_TREE_BITS_PER_HEIGHT * (height - 1))), height - 1);
1015 }
1016 }
1017
1018 void radix_tree_dump(const struct radix_tree *);
1019
1020 void
radix_tree_dump(const struct radix_tree * t)1021 radix_tree_dump(const struct radix_tree *t)
1022 {
1023
1024 printf("tree %p height=%u\n", t, t->t_height);
1025 radix_tree_dump_node(t, t->t_root, 0, t->t_height);
1026 }
1027
1028 static void
test1(void)1029 test1(void)
1030 {
1031 struct radix_tree s;
1032 struct radix_tree *t = &s;
1033 void *results[3];
1034
1035 radix_tree_init_tree(t);
1036 radix_tree_dump(t);
1037 assert(radix_tree_lookup_node(t, 0) == NULL);
1038 assert(radix_tree_lookup_node(t, 1000) == NULL);
1039 assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 0);
1040 assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 0);
1041 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 0);
1042 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 0);
1043 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0) == 0);
1044 assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, 0) == 0);
1045 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
1046 == 0);
1047 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3,
1048 0) == 0);
1049 assert(radix_tree_empty_tree_p(t));
1050 assert(radix_tree_empty_tagged_tree_p(t, 0));
1051 assert(radix_tree_empty_tagged_tree_p(t, 1));
1052 assert(radix_tree_insert_node(t, 0, (void *)0xdeadbea0) == 0);
1053 assert(!radix_tree_empty_tree_p(t));
1054 assert(radix_tree_empty_tagged_tree_p(t, 0));
1055 assert(radix_tree_empty_tagged_tree_p(t, 1));
1056 assert(radix_tree_lookup_node(t, 0) == (void *)0xdeadbea0);
1057 assert(radix_tree_lookup_node(t, 1000) == NULL);
1058 memset(results, 0, sizeof(results));
1059 assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 1);
1060 assert(results[0] == (void *)0xdeadbea0);
1061 assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 0);
1062 memset(results, 0, sizeof(results));
1063 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 1);
1064 assert(results[0] == (void *)0xdeadbea0);
1065 memset(results, 0, sizeof(results));
1066 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 1);
1067 assert(results[0] == (void *)0xdeadbea0);
1068 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0)
1069 == 0);
1070 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
1071 == 0);
1072 assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0);
1073 assert(radix_tree_remove_node(t, 0) == (void *)0xdeadbea0);
1074 assert(!radix_tree_empty_tree_p(t));
1075 radix_tree_dump(t);
1076 assert(radix_tree_lookup_node(t, 0) == NULL);
1077 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
1078 memset(results, 0, sizeof(results));
1079 assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 1);
1080 assert(results[0] == (void *)0xdeadbea0);
1081 memset(results, 0, sizeof(results));
1082 assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 1);
1083 assert(results[0] == (void *)0xdeadbea0);
1084 assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 0);
1085 memset(results, 0, sizeof(results));
1086 assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 1);
1087 assert(results[0] == (void *)0xdeadbea0);
1088 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0)
1089 == 0);
1090 assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
1091 == 0);
1092 assert(!radix_tree_get_tag(t, 1000, 0));
1093 assert(!radix_tree_get_tag(t, 1000, 1));
1094 assert(radix_tree_empty_tagged_tree_p(t, 0));
1095 assert(radix_tree_empty_tagged_tree_p(t, 1));
1096 radix_tree_set_tag(t, 1000, 1);
1097 assert(!radix_tree_get_tag(t, 1000, 0));
1098 assert(radix_tree_get_tag(t, 1000, 1));
1099 assert(radix_tree_empty_tagged_tree_p(t, 0));
1100 assert(!radix_tree_empty_tagged_tree_p(t, 1));
1101 radix_tree_dump(t);
1102 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
1103 assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0);
1104 radix_tree_dump(t);
1105 assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0);
1106 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
1107 assert(radix_tree_insert_node(t, UINT64_C(10000000000), (void *)0xdea0)
1108 == 0);
1109 radix_tree_dump(t);
1110 assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0);
1111 assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
1112 assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) ==
1113 (void *)0xdea0);
1114 radix_tree_dump(t);
1115 assert(!radix_tree_get_tag(t, 0, 1));
1116 assert(radix_tree_get_tag(t, 1000, 1));
1117 assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1));
1118 radix_tree_set_tag(t, 0, 1);;
1119 radix_tree_set_tag(t, UINT64_C(10000000000), 1);
1120 radix_tree_dump(t);
1121 assert(radix_tree_get_tag(t, 0, 1));
1122 assert(radix_tree_get_tag(t, 1000, 1));
1123 assert(radix_tree_get_tag(t, UINT64_C(10000000000), 1));
1124 radix_tree_clear_tag(t, 0, 1);;
1125 radix_tree_clear_tag(t, UINT64_C(10000000000), 1);
1126 radix_tree_dump(t);
1127 assert(!radix_tree_get_tag(t, 0, 1));
1128 assert(radix_tree_get_tag(t, 1000, 1));
1129 assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1));
1130 radix_tree_dump(t);
1131 assert(radix_tree_replace_node(t, 1000, (void *)0x12345678) ==
1132 (void *)0xdeadbea0);
1133 assert(!radix_tree_get_tag(t, 1000, 0));
1134 assert(radix_tree_get_tag(t, 1000, 1));
1135 assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 3);
1136 assert(results[0] == (void *)0xbea0);
1137 assert(results[1] == (void *)0x12345678);
1138 assert(results[2] == (void *)0xdea0);
1139 assert(radix_tree_gang_lookup_node(t, 1, results, 3) == 2);
1140 assert(results[0] == (void *)0x12345678);
1141 assert(results[1] == (void *)0xdea0);
1142 assert(radix_tree_gang_lookup_node(t, 1001, results, 3) == 1);
1143 assert(results[0] == (void *)0xdea0);
1144 assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3)
1145 == 0);
1146 assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results,
1147 3) == 0);
1148 assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, 1) == 1);
1149 assert(results[0] == (void *)0x12345678);
1150 assert(entry_tagmask(t->t_root) != 0);
1151 assert(radix_tree_remove_node(t, 1000) == (void *)0x12345678);
1152 assert(entry_tagmask(t->t_root) == 0);
1153 radix_tree_dump(t);
1154 assert(radix_tree_remove_node(t, UINT64_C(10000000000)) ==
1155 (void *)0xdea0);
1156 radix_tree_dump(t);
1157 assert(radix_tree_remove_node(t, 0) == (void *)0xbea0);
1158 radix_tree_dump(t);
1159 radix_tree_fini_tree(t);
1160 }
1161
1162 #include <sys/time.h>
1163
1164 struct testnode {
1165 uint64_t idx;
1166 bool tagged[RADIX_TREE_TAG_ID_MAX];
1167 };
1168
1169 static void
printops(const char * title,const char * name,int tag,unsigned int n,const struct timeval * stv,const struct timeval * etv)1170 printops(const char *title, const char *name, int tag, unsigned int n,
1171 const struct timeval *stv, const struct timeval *etv)
1172 {
1173 uint64_t s = stv->tv_sec * 1000000 + stv->tv_usec;
1174 uint64_t e = etv->tv_sec * 1000000 + etv->tv_usec;
1175
1176 printf("RESULT %s %s %d %lf op/s\n", title, name, tag,
1177 (double)n / (e - s) * 1000000);
1178 }
1179
1180 #define TEST2_GANG_LOOKUP_NODES 16
1181
1182 static bool
test2_should_tag(unsigned int i,radix_tree_tagid_t tagid)1183 test2_should_tag(unsigned int i, radix_tree_tagid_t tagid)
1184 {
1185
1186 if (tagid == 0) {
1187 return (i & 0x3) == 0; /* 25% */
1188 } else {
1189 return (i % 7) == 0; /* 14% */
1190 }
1191 }
1192
1193 static void
test2(const char * title,bool dense)1194 test2(const char *title, bool dense)
1195 {
1196 struct radix_tree s;
1197 struct radix_tree *t = &s;
1198 struct testnode *n;
1199 unsigned int i;
1200 unsigned int nnodes = 100000;
1201 unsigned int removed;
1202 radix_tree_tagid_t tag;
1203 unsigned int ntagged[RADIX_TREE_TAG_ID_MAX];
1204 struct testnode *nodes;
1205 struct timeval stv;
1206 struct timeval etv;
1207
1208 nodes = malloc(nnodes * sizeof(*nodes));
1209 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1210 ntagged[tag] = 0;
1211 }
1212 radix_tree_init_tree(t);
1213 for (i = 0; i < nnodes; i++) {
1214 n = &nodes[i];
1215 n->idx = random();
1216 if (sizeof(long) == 4) {
1217 n->idx <<= 32;
1218 n->idx |= (uint32_t)random();
1219 }
1220 if (dense) {
1221 n->idx %= nnodes * 2;
1222 }
1223 while (radix_tree_lookup_node(t, n->idx) != NULL) {
1224 n->idx++;
1225 }
1226 radix_tree_insert_node(t, n->idx, n);
1227 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1228 n->tagged[tag] = test2_should_tag(i, tag);
1229 if (n->tagged[tag]) {
1230 radix_tree_set_tag(t, n->idx, tag);
1231 ntagged[tag]++;
1232 }
1233 assert(n->tagged[tag] ==
1234 radix_tree_get_tag(t, n->idx, tag));
1235 }
1236 }
1237
1238 gettimeofday(&stv, NULL);
1239 for (i = 0; i < nnodes; i++) {
1240 n = &nodes[i];
1241 assert(radix_tree_lookup_node(t, n->idx) == n);
1242 }
1243 gettimeofday(&etv, NULL);
1244 printops(title, "lookup", 0, nnodes, &stv, &etv);
1245
1246 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1247 unsigned int count = 0;
1248
1249 gettimeofday(&stv, NULL);
1250 for (i = 0; i < nnodes; i++) {
1251 bool tagged;
1252
1253 n = &nodes[i];
1254 tagged = radix_tree_get_tag(t, n->idx, tag);
1255 assert(n->tagged[tag] == tagged);
1256 if (tagged) {
1257 count++;
1258 }
1259 }
1260 gettimeofday(&etv, NULL);
1261 assert(ntagged[tag] == count);
1262 printops(title, "get_tag", tag, nnodes, &stv, &etv);
1263 }
1264
1265 gettimeofday(&stv, NULL);
1266 for (i = 0; i < nnodes; i++) {
1267 n = &nodes[i];
1268 radix_tree_remove_node(t, n->idx);
1269 }
1270 gettimeofday(&etv, NULL);
1271 printops(title, "remove", 0, nnodes, &stv, &etv);
1272
1273 gettimeofday(&stv, NULL);
1274 for (i = 0; i < nnodes; i++) {
1275 n = &nodes[i];
1276 radix_tree_insert_node(t, n->idx, n);
1277 }
1278 gettimeofday(&etv, NULL);
1279 printops(title, "insert", 0, nnodes, &stv, &etv);
1280
1281 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1282 ntagged[tag] = 0;
1283 gettimeofday(&stv, NULL);
1284 for (i = 0; i < nnodes; i++) {
1285 n = &nodes[i];
1286 if (n->tagged[tag]) {
1287 radix_tree_set_tag(t, n->idx, tag);
1288 ntagged[tag]++;
1289 }
1290 }
1291 gettimeofday(&etv, NULL);
1292 printops(title, "set_tag", tag, ntagged[tag], &stv, &etv);
1293 }
1294
1295 gettimeofday(&stv, NULL);
1296 {
1297 struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1298 uint64_t nextidx;
1299 unsigned int nfound;
1300 unsigned int total;
1301
1302 nextidx = 0;
1303 total = 0;
1304 while ((nfound = radix_tree_gang_lookup_node(t, nextidx,
1305 (void *)results, __arraycount(results))) > 0) {
1306 nextidx = results[nfound - 1]->idx + 1;
1307 total += nfound;
1308 if (nextidx == 0) {
1309 break;
1310 }
1311 }
1312 assert(total == nnodes);
1313 }
1314 gettimeofday(&etv, NULL);
1315 printops(title, "ganglookup", 0, nnodes, &stv, &etv);
1316
1317 gettimeofday(&stv, NULL);
1318 {
1319 struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1320 uint64_t nextidx;
1321 unsigned int nfound;
1322 unsigned int total;
1323
1324 nextidx = UINT64_MAX;
1325 total = 0;
1326 while ((nfound = radix_tree_gang_lookup_node_reverse(t, nextidx,
1327 (void *)results, __arraycount(results))) > 0) {
1328 nextidx = results[nfound - 1]->idx - 1;
1329 total += nfound;
1330 if (nextidx == UINT64_MAX) {
1331 break;
1332 }
1333 }
1334 assert(total == nnodes);
1335 }
1336 gettimeofday(&etv, NULL);
1337 printops(title, "ganglookup_reverse", 0, nnodes, &stv, &etv);
1338
1339 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1340 gettimeofday(&stv, NULL);
1341 {
1342 struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1343 uint64_t nextidx;
1344 unsigned int nfound;
1345 unsigned int total;
1346
1347 nextidx = 0;
1348 total = 0;
1349 while ((nfound = radix_tree_gang_lookup_tagged_node(t,
1350 nextidx, (void *)results, __arraycount(results),
1351 tag)) > 0) {
1352 nextidx = results[nfound - 1]->idx + 1;
1353 total += nfound;
1354 }
1355 assert(total == ntagged[tag]);
1356 }
1357 gettimeofday(&etv, NULL);
1358 printops(title, "ganglookup_tag", tag, ntagged[tag], &stv,
1359 &etv);
1360 }
1361
1362 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1363 gettimeofday(&stv, NULL);
1364 {
1365 struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1366 uint64_t nextidx;
1367 unsigned int nfound;
1368 unsigned int total;
1369
1370 nextidx = UINT64_MAX;
1371 total = 0;
1372 while ((nfound =
1373 radix_tree_gang_lookup_tagged_node_reverse(t,
1374 nextidx, (void *)results, __arraycount(results),
1375 tag)) > 0) {
1376 nextidx = results[nfound - 1]->idx - 1;
1377 total += nfound;
1378 if (nextidx == UINT64_MAX) {
1379 break;
1380 }
1381 }
1382 assert(total == ntagged[tag]);
1383 }
1384 gettimeofday(&etv, NULL);
1385 printops(title, "ganglookup_tag_reverse", tag, ntagged[tag],
1386 &stv, &etv);
1387 }
1388
1389 removed = 0;
1390 for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
1391 unsigned int total;
1392
1393 total = 0;
1394 gettimeofday(&stv, NULL);
1395 {
1396 struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1397 uint64_t nextidx;
1398 unsigned int nfound;
1399
1400 nextidx = 0;
1401 while ((nfound = radix_tree_gang_lookup_tagged_node(t,
1402 nextidx, (void *)results, __arraycount(results),
1403 tag)) > 0) {
1404 for (i = 0; i < nfound; i++) {
1405 radix_tree_remove_node(t,
1406 results[i]->idx);
1407 }
1408 nextidx = results[nfound - 1]->idx + 1;
1409 total += nfound;
1410 if (nextidx == 0) {
1411 break;
1412 }
1413 }
1414 assert(tag != 0 || total == ntagged[tag]);
1415 assert(total <= ntagged[tag]);
1416 }
1417 gettimeofday(&etv, NULL);
1418 printops(title, "ganglookup_tag+remove", tag, total, &stv,
1419 &etv);
1420 removed += total;
1421 }
1422
1423 gettimeofday(&stv, NULL);
1424 {
1425 struct testnode *results[TEST2_GANG_LOOKUP_NODES];
1426 uint64_t nextidx;
1427 unsigned int nfound;
1428 unsigned int total;
1429
1430 nextidx = 0;
1431 total = 0;
1432 while ((nfound = radix_tree_gang_lookup_node(t, nextidx,
1433 (void *)results, __arraycount(results))) > 0) {
1434 for (i = 0; i < nfound; i++) {
1435 assert(results[i] == radix_tree_remove_node(t,
1436 results[i]->idx));
1437 }
1438 nextidx = results[nfound - 1]->idx + 1;
1439 total += nfound;
1440 if (nextidx == 0) {
1441 break;
1442 }
1443 }
1444 assert(total == nnodes - removed);
1445 }
1446 gettimeofday(&etv, NULL);
1447 printops(title, "ganglookup+remove", 0, nnodes - removed, &stv, &etv);
1448
1449 assert(radix_tree_empty_tree_p(t));
1450 assert(radix_tree_empty_tagged_tree_p(t, 0));
1451 assert(radix_tree_empty_tagged_tree_p(t, 1));
1452 radix_tree_fini_tree(t);
1453 free(nodes);
1454 }
1455
1456 int
main(int argc,char * argv[])1457 main(int argc, char *argv[])
1458 {
1459
1460 test1();
1461 test2("dense", true);
1462 test2("sparse", false);
1463 return 0;
1464 }
1465
1466 #endif /* defined(UNITTEST) */
1467