1/* $NetBSD: radixtree.c,v 1.16 2011/10/25 14:11:27 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.16 2011/10/25 14:11:27 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.16 2011/10/25 14:11:27 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 105static inline void * 106entry_ptr(void *p) 107{ 108 109 return (void *)((uintptr_t)p & ~RADIX_TREE_TAG_MASK); 110} 111 112static inline unsigned int 113entry_tagmask(void *p) 114{ 115 116 return (uintptr_t)p & RADIX_TREE_TAG_MASK; 117} 118 119static inline void * 120entry_compose(void *p, unsigned int tagmask) 121{ 122 123 return (void *)((uintptr_t)p | tagmask); 124} 125 126static inline bool 127entry_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 140static inline unsigned int 141tagid_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 155struct 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 166static unsigned int 167any_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 188struct 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 201static inline void ** 202path_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 210static inline struct radix_tree_node * 211path_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 225void 226radix_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 239void 240radix_tree_fini_tree(struct radix_tree *t) 241{ 242 243 KASSERT(t->t_root == NULL); 244 KASSERT(t->t_height == 0); 245} 246 247bool 248radix_tree_empty_tree_p(struct radix_tree *t) 249{ 250 251 return t->t_root == NULL; 252} 253 254bool 255radix_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 262static void 263radix_tree_node_init(struct radix_tree_node *n) 264{ 265 266 memset(n, 0, sizeof(*n)); 267} 268 269#if defined(_KERNEL) 270pool_cache_t radix_tree_node_cache __read_mostly; 271 272static int 273radix_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 288void 289radix_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 299static bool __unused 300radix_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 315static struct radix_tree_node * 316radix_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 336static void 337radix_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 350static int 351radix_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 401static inline void ** 402radix_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 508int 509radix_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 534void * 535radix_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 557void * 558radix_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 632void * 633radix_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 644static inline void 645gang_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 665static inline unsigned int 666__attribute__((__always_inline__)) 667gang_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 } 722scan_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) { 751no_siblings: 752 /* 753 * not found. go to parent. 754 */ 755 lastidx--; 756 vpp = path_pptr(t, path, lastidx); 757 goto scan_siblings; 758 } 759descend: 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 797unsigned int 798radix_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 814unsigned int 815radix_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 831unsigned int 832radix_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 849unsigned int 850radix_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 867bool 868radix_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 898void 899radix_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 932void 933radix_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 982static void 983radix_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 1018void radix_tree_dump(const struct radix_tree *); 1019 1020void 1021radix_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 1028static void 1029test1(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 1164struct testnode { 1165 uint64_t idx; 1166 bool tagged[RADIX_TREE_TAG_ID_MAX]; 1167}; 1168 1169static void 1170printops(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 1182static bool 1183test2_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 1193static void 1194test2(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 1456int 1457main(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