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