1/* $NetBSD: ptree.c,v 1.5.8.2 2012/07/16 22:10:46 riz Exp $ */ 2 3/*- 4 * Copyright (c) 2008 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Matt Thomas <matt@3am-software.com>. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32#define _PT_PRIVATE 33 34#if defined(PTCHECK) && !defined(PTDEBUG) 35#define PTDEBUG 36#endif 37 38#if defined(_KERNEL) || defined(_STANDALONE) 39#include <sys/param.h> 40#include <sys/types.h> 41#include <sys/systm.h> 42#include <lib/libkern/libkern.h> 43__KERNEL_RCSID(0, "$NetBSD: ptree.c,v 1.5.8.2 2012/07/16 22:10:46 riz Exp $"); 44#else 45#include <stddef.h> 46#include <stdint.h> 47#include <limits.h> 48#include <stdbool.h> 49#include <string.h> 50#ifdef PTDEBUG 51#include <assert.h> 52#define KASSERT(e) assert(e) 53#else 54#define KASSERT(e) do { } while (/*CONSTCOND*/ 0) 55#endif 56__RCSID("$NetBSD: ptree.c,v 1.5.8.2 2012/07/16 22:10:46 riz Exp $"); 57#endif /* _KERNEL || _STANDALONE */ 58 59#ifdef _LIBC 60#include "namespace.h" 61#endif 62 63#ifdef PTTEST 64#include "ptree.h" 65#else 66#include <sys/ptree.h> 67#endif 68 69/* 70 * This is an implementation of a radix / PATRICIA tree. As in a traditional 71 * patricia tree, all the data is at the leaves of the tree. An N-value 72 * tree would have N leaves, N-1 branching nodes, and a root pointer. Each 73 * branching node would have left(0) and right(1) pointers that either point 74 * to another branching node or a leaf node. The root pointer would also 75 * point to either the first branching node or a leaf node. Leaf nodes 76 * have no need for pointers. 77 * 78 * However, allocation for these branching nodes is problematic since the 79 * allocation could fail. This would cause insertions to fail for reasons 80 * beyond the user's control. So to prevent this, in this implementation 81 * each node has two identities: its leaf identity and its branch identity. 82 * Each is separate from the other. Every branch is tagged as to whether 83 * it points to a leaf or a branch. This is not an attribute of the object 84 * but of the pointer to the object. The low bit of the pointer is used as 85 * the tag to determine whether it points to a leaf or branch identity, with 86 * branch identities having the low bit set. 87 * 88 * A node's branch identity has one rule: when traversing the tree from the 89 * root to the node's leaf identity, one of the branches traversed will be via 90 * the node's branch identity. Of course, that has an exception: since to 91 * store N leaves, you need N-1 branches. That one node whose branch identity 92 * isn't used is stored as "oddman"-out in the root. 93 * 94 * Branching nodes also has a bit offset and a bit length which determines 95 * which branch slot is used. The bit length can be zero resulting in a 96 * one-way branch. This happens in two special cases: the root and 97 * interior mask nodes. 98 * 99 * To support longest match first lookups, when a mask node (one that only 100 * match the first N bits) has children who first N bits match the mask nodes, 101 * that mask node is converted from being a leaf node to being a one-way 102 * branch-node. The mask becomes fixed in position in the tree. The mask 103 * will always be the longest mask match for its descendants (unless they 104 * traverse an even longer match). 105 */ 106 107#define NODETOITEM(pt, ptn) \ 108 ((void *)((uintptr_t)(ptn) - (pt)->pt_node_offset)) 109#define NODETOKEY(pt, ptn) \ 110 ((void *)((uintptr_t)(ptn) - (pt)->pt_node_offset + pt->pt_key_offset)) 111#define ITEMTONODE(pt, ptn) \ 112 ((pt_node_t *)((uintptr_t)(ptn) + (pt)->pt_node_offset)) 113 114bool ptree_check(const pt_tree_t *); 115#if PTCHECK > 1 116#define PTREE_CHECK(pt) ptree_check(pt) 117#else 118#define PTREE_CHECK(pt) do { } while (/*CONSTCOND*/ 0) 119#endif 120 121static inline bool 122ptree_matchnode(const pt_tree_t *pt, const pt_node_t *target, 123 const pt_node_t *ptn, pt_bitoff_t max_bitoff, 124 pt_bitoff_t *bitoff_p, pt_slot_t *slots_p) 125{ 126 return (*pt->pt_ops->ptto_matchnode)(NODETOKEY(pt, target), 127 (ptn != NULL ? NODETOKEY(pt, ptn) : NULL), 128 max_bitoff, bitoff_p, slots_p, pt->pt_context); 129} 130 131static inline pt_slot_t 132ptree_testnode(const pt_tree_t *pt, const pt_node_t *target, 133 const pt_node_t *ptn) 134{ 135 const pt_bitlen_t bitlen = PTN_BRANCH_BITLEN(ptn); 136 if (bitlen == 0) 137 return PT_SLOT_ROOT; /* mask or root, doesn't matter */ 138 return (*pt->pt_ops->ptto_testnode)(NODETOKEY(pt, target), 139 PTN_BRANCH_BITOFF(ptn), bitlen, pt->pt_context); 140} 141 142static inline bool 143ptree_matchkey(const pt_tree_t *pt, const void *key, 144 const pt_node_t *ptn, pt_bitoff_t bitoff, pt_bitlen_t bitlen) 145{ 146 return (*pt->pt_ops->ptto_matchkey)(key, NODETOKEY(pt, ptn), 147 bitoff, bitlen, pt->pt_context); 148} 149 150static inline pt_slot_t 151ptree_testkey(const pt_tree_t *pt, const void *key, const pt_node_t *ptn) 152{ 153 const pt_bitlen_t bitlen = PTN_BRANCH_BITLEN(ptn); 154 if (bitlen == 0) 155 return PT_SLOT_ROOT; /* mask or root, doesn't matter */ 156 return (*pt->pt_ops->ptto_testkey)(key, PTN_BRANCH_BITOFF(ptn), 157 PTN_BRANCH_BITLEN(ptn), pt->pt_context); 158} 159 160static inline void 161ptree_set_position(uintptr_t node, pt_slot_t position) 162{ 163 if (PT_LEAF_P(node)) 164 PTN_SET_LEAF_POSITION(PT_NODE(node), position); 165 else 166 PTN_SET_BRANCH_POSITION(PT_NODE(node), position); 167} 168 169void 170ptree_init(pt_tree_t *pt, const pt_tree_ops_t *ops, void *context, 171 size_t node_offset, size_t key_offset) 172{ 173 memset(pt, 0, sizeof(*pt)); 174 pt->pt_node_offset = node_offset; 175 pt->pt_key_offset = key_offset; 176 pt->pt_context = context; 177 pt->pt_ops = ops; 178} 179 180typedef struct { 181 uintptr_t *id_insertp; 182 pt_node_t *id_parent; 183 uintptr_t id_node; 184 pt_slot_t id_parent_slot; 185 pt_bitoff_t id_bitoff; 186 pt_slot_t id_slot; 187} pt_insertdata_t; 188 189typedef bool (*pt_insertfunc_t)(pt_tree_t *, pt_node_t *, pt_insertdata_t *); 190 191/* 192 * Move a branch identify from src to dst. The leaves don't care since 193 * nothing for them has changed. 194 */ 195/*ARGSUSED*/ 196static uintptr_t 197ptree_move_branch(pt_tree_t * const pt, pt_node_t * const dst, 198 const pt_node_t * const src) 199{ 200 KASSERT(PTN_BRANCH_BITLEN(src) == 1); 201 /* set branch bitlen and bitoff in one step. */ 202 dst->ptn_branchdata = src->ptn_branchdata; 203 PTN_SET_BRANCH_POSITION(dst, PTN_BRANCH_POSITION(src)); 204 PTN_COPY_BRANCH_SLOTS(dst, src); 205 return PTN_BRANCH(dst); 206} 207 208#ifndef PTNOMASK 209static inline uintptr_t * 210ptree_find_branch(pt_tree_t * const pt, uintptr_t branch_node) 211{ 212 pt_node_t * const branch = PT_NODE(branch_node); 213 pt_node_t *parent; 214 215 for (parent = &pt->pt_rootnode;;) { 216 uintptr_t *nodep = 217 &PTN_BRANCH_SLOT(parent, ptree_testnode(pt, branch, parent)); 218 if (*nodep == branch_node) 219 return nodep; 220 if (PT_LEAF_P(*nodep)) 221 return NULL; 222 parent = PT_NODE(*nodep); 223 } 224} 225 226static bool 227ptree_insert_leaf_after_mask(pt_tree_t * const pt, pt_node_t * const target, 228 pt_insertdata_t * const id) 229{ 230 const uintptr_t target_node = PTN_LEAF(target); 231 const uintptr_t mask_node = id->id_node; 232 pt_node_t * const mask = PT_NODE(mask_node); 233 const pt_bitlen_t mask_len = PTN_MASK_BITLEN(mask); 234 235 KASSERT(PT_LEAF_P(mask_node)); 236 KASSERT(PTN_LEAF_POSITION(mask) == id->id_parent_slot); 237 KASSERT(mask_len <= id->id_bitoff); 238 KASSERT(PTN_ISMASK_P(mask)); 239 KASSERT(!PTN_ISMASK_P(target) || mask_len < PTN_MASK_BITLEN(target)); 240 241 if (mask_node == PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode)) { 242 KASSERT(id->id_parent != mask); 243 /* 244 * Nice, mask was an oddman. So just set the oddman to target. 245 */ 246 PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = target_node; 247 } else { 248 /* 249 * We need to find out who's pointing to mask's branch 250 * identity. We know that between root and the leaf identity, 251 * we must traverse the node's branch identity. 252 */ 253 uintptr_t * const mask_nodep = ptree_find_branch(pt, PTN_BRANCH(mask)); 254 KASSERT(mask_nodep != NULL); 255 KASSERT(*mask_nodep == PTN_BRANCH(mask)); 256 KASSERT(PTN_BRANCH_BITLEN(mask) == 1); 257 258 /* 259 * Alas, mask was used as a branch. Since the mask is becoming 260 * a one-way branch, we need make target take over mask's 261 * branching responsibilities. Only then can we change it. 262 */ 263 *mask_nodep = ptree_move_branch(pt, target, mask); 264 265 /* 266 * However, it's possible that mask's parent is itself. If 267 * that's true, update the insert point to use target since it 268 * has taken over mask's branching duties. 269 */ 270 if (id->id_parent == mask) 271 id->id_insertp = &PTN_BRANCH_SLOT(target, 272 id->id_parent_slot); 273 } 274 275 PTN_SET_BRANCH_BITLEN(mask, 0); 276 PTN_SET_BRANCH_BITOFF(mask, mask_len); 277 278 PTN_BRANCH_ROOT_SLOT(mask) = target_node; 279 PTN_BRANCH_ODDMAN_SLOT(mask) = PT_NULL; 280 PTN_SET_LEAF_POSITION(target, PT_SLOT_ROOT); 281 PTN_SET_BRANCH_POSITION(mask, id->id_parent_slot); 282 283 /* 284 * Now that everything is done, to make target visible we need to 285 * change mask from a leaf to a branch. 286 */ 287 *id->id_insertp = PTN_BRANCH(mask); 288 PTREE_CHECK(pt); 289 return true; 290} 291 292/*ARGSUSED*/ 293static bool 294ptree_insert_mask_before_node(pt_tree_t * const pt, pt_node_t * const target, 295 pt_insertdata_t * const id) 296{ 297 const uintptr_t node = id->id_node; 298 pt_node_t * const ptn = PT_NODE(node); 299 const pt_slot_t mask_len = PTN_MASK_BITLEN(target); 300 const pt_bitlen_t node_mask_len = PTN_MASK_BITLEN(ptn); 301 302 KASSERT(PT_LEAF_P(node) || id->id_parent_slot == PTN_BRANCH_POSITION(ptn)); 303 KASSERT(PT_BRANCH_P(node) || id->id_parent_slot == PTN_LEAF_POSITION(ptn)); 304 KASSERT(PTN_ISMASK_P(target)); 305 306 /* 307 * If the node we are placing ourself in front is a mask with the 308 * same mask length as us, return failure. 309 */ 310 if (PTN_ISMASK_P(ptn) && node_mask_len == mask_len) 311 return false; 312 313 PTN_SET_BRANCH_BITLEN(target, 0); 314 PTN_SET_BRANCH_BITOFF(target, mask_len); 315 316 PTN_BRANCH_SLOT(target, PT_SLOT_ROOT) = node; 317 *id->id_insertp = PTN_BRANCH(target); 318 319 PTN_SET_BRANCH_POSITION(target, id->id_parent_slot); 320 ptree_set_position(node, PT_SLOT_ROOT); 321 322 PTREE_CHECK(pt); 323 return true; 324} 325#endif /* !PTNOMASK */ 326 327/*ARGSUSED*/ 328static bool 329ptree_insert_branch_at_node(pt_tree_t * const pt, pt_node_t * const target, 330 pt_insertdata_t * const id) 331{ 332 const uintptr_t target_node = PTN_LEAF(target); 333 const uintptr_t node = id->id_node; 334 const pt_slot_t other_slot = id->id_slot ^ PT_SLOT_OTHER; 335 336 KASSERT(PT_BRANCH_P(node) || id->id_parent_slot == PTN_LEAF_POSITION(PT_NODE(node))); 337 KASSERT(PT_LEAF_P(node) || id->id_parent_slot == PTN_BRANCH_POSITION(PT_NODE(node))); 338 KASSERT((node == pt->pt_root) == (id->id_parent == &pt->pt_rootnode)); 339#ifndef PTNOMASK 340 KASSERT(!PTN_ISMASK_P(target) || id->id_bitoff <= PTN_MASK_BITLEN(target)); 341#endif 342 KASSERT(node == pt->pt_root || PTN_BRANCH_BITOFF(id->id_parent) + PTN_BRANCH_BITLEN(id->id_parent) <= id->id_bitoff); 343 344 PTN_SET_BRANCH_BITOFF(target, id->id_bitoff); 345 PTN_SET_BRANCH_BITLEN(target, 1); 346 347 PTN_BRANCH_SLOT(target, id->id_slot) = target_node; 348 PTN_BRANCH_SLOT(target, other_slot) = node; 349 *id->id_insertp = PTN_BRANCH(target); 350 351 PTN_SET_LEAF_POSITION(target, id->id_slot); 352 ptree_set_position(node, other_slot); 353 354 PTN_SET_BRANCH_POSITION(target, id->id_parent_slot); 355 PTREE_CHECK(pt); 356 return true; 357} 358 359static bool 360ptree_insert_leaf(pt_tree_t * const pt, pt_node_t * const target, 361 pt_insertdata_t * const id) 362{ 363 const uintptr_t leaf_node = id->id_node; 364 pt_node_t * const leaf = PT_NODE(leaf_node); 365#ifdef PTNOMASK 366 const bool inserting_mask = false; 367 const bool at_mask = false; 368#else 369 const bool inserting_mask = PTN_ISMASK_P(target); 370 const bool at_mask = PTN_ISMASK_P(leaf); 371 const pt_bitlen_t leaf_masklen = PTN_MASK_BITLEN(leaf); 372 const pt_bitlen_t target_masklen = PTN_MASK_BITLEN(target); 373#endif 374 pt_insertfunc_t insertfunc = ptree_insert_branch_at_node; 375 bool matched; 376 377 /* 378 * In all likelyhood we are going simply going to insert a branch 379 * where this leaf is which will point to the old and new leaves. 380 */ 381 KASSERT(PT_LEAF_P(leaf_node)); 382 KASSERT(PTN_LEAF_POSITION(leaf) == id->id_parent_slot); 383 matched = ptree_matchnode(pt, target, leaf, UINT_MAX, 384 &id->id_bitoff, &id->id_slot); 385 if (__predict_false(!inserting_mask)) { 386 /* 387 * We aren't inserting a mask nor is the leaf a mask, which 388 * means we are trying to insert a duplicate leaf. Can't do 389 * that. 390 */ 391 if (!at_mask && matched) 392 return false; 393 394#ifndef PTNOMASK 395 /* 396 * We are at a mask and the leaf we are about to insert 397 * is at or beyond the mask, we need to convert the mask 398 * from a leaf to a one-way branch interior mask. 399 */ 400 if (at_mask && id->id_bitoff >= leaf_masklen) 401 insertfunc = ptree_insert_leaf_after_mask; 402#endif /* PTNOMASK */ 403 } 404#ifndef PTNOMASK 405 else { 406 /* 407 * We are inserting a mask. 408 */ 409 if (matched) { 410 /* 411 * If the leaf isn't a mask, we obviously have to 412 * insert the new mask before non-mask leaf. If the 413 * leaf is a mask, and the new node has a LEQ mask 414 * length it too needs to inserted before leaf (*). 415 * 416 * In other cases, we place the new mask as leaf after 417 * leaf mask. Which mask comes first will be a one-way 418 * branch interior mask node which has the other mask 419 * node as a child. 420 * 421 * (*) ptree_insert_mask_before_node can detect a 422 * duplicate mask and return failure if needed. 423 */ 424 if (!at_mask || target_masklen <= leaf_masklen) 425 insertfunc = ptree_insert_mask_before_node; 426 else 427 insertfunc = ptree_insert_leaf_after_mask; 428 } else if (at_mask && id->id_bitoff >= leaf_masklen) { 429 /* 430 * If the new mask has a bit offset GEQ than the leaf's 431 * mask length, convert the left to a one-way branch 432 * interior mask and make that point to the new [leaf] 433 * mask. 434 */ 435 insertfunc = ptree_insert_leaf_after_mask; 436 } else { 437 /* 438 * The new mask has a bit offset less than the leaf's 439 * mask length or if the leaf isn't a mask at all, the 440 * new mask deserves to be its own leaf so we use the 441 * default insertfunc to do that. 442 */ 443 } 444 } 445#endif /* PTNOMASK */ 446 447 return (*insertfunc)(pt, target, id); 448} 449 450static bool 451ptree_insert_node_common(pt_tree_t *pt, void *item) 452{ 453 pt_node_t * const target = ITEMTONODE(pt, item); 454#ifndef PTNOMASK 455 const bool inserting_mask = PTN_ISMASK_P(target); 456 const pt_bitlen_t target_masklen = PTN_MASK_BITLEN(target); 457#endif 458 pt_insertfunc_t insertfunc; 459 pt_insertdata_t id; 460 461 /* 462 * If this node already exists in the tree, return failure. 463 */ 464 if (target == PT_NODE(pt->pt_root)) 465 return false; 466 467 /* 468 * We need a leaf so we can match against. Until we get a leaf 469 * we having nothing to test against. 470 */ 471 if (__predict_false(PT_NULL_P(pt->pt_root))) { 472 PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode) = PTN_LEAF(target); 473 PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PTN_LEAF(target); 474 PTN_SET_LEAF_POSITION(target, PT_SLOT_ROOT); 475 PTREE_CHECK(pt); 476 return true; 477 } 478 479 id.id_bitoff = 0; 480 id.id_parent = &pt->pt_rootnode; 481 id.id_parent_slot = PT_SLOT_ROOT; 482 id.id_insertp = &PTN_BRANCH_ROOT_SLOT(id.id_parent); 483 for (;;) { 484 pt_bitoff_t branch_bitoff; 485 pt_node_t * const ptn = PT_NODE(*id.id_insertp); 486 id.id_node = *id.id_insertp; 487 488 /* 489 * If this node already exists in the tree, return failure. 490 */ 491 if (target == ptn) 492 return false; 493 494 /* 495 * If we hit a leaf, try to insert target at leaf. We could 496 * have inlined ptree_insert_leaf here but that would have 497 * made this routine much harder to understand. Trust the 498 * compiler to optimize this properly. 499 */ 500 if (PT_LEAF_P(id.id_node)) { 501 KASSERT(PTN_LEAF_POSITION(ptn) == id.id_parent_slot); 502 insertfunc = ptree_insert_leaf; 503 break; 504 } 505 506 /* 507 * If we aren't a leaf, we must be a branch. Make sure we are 508 * in the slot we think we are. 509 */ 510 KASSERT(PT_BRANCH_P(id.id_node)); 511 KASSERT(PTN_BRANCH_POSITION(ptn) == id.id_parent_slot); 512 513 /* 514 * Where is this branch? 515 */ 516 branch_bitoff = PTN_BRANCH_BITOFF(ptn); 517 518#ifndef PTNOMASK 519 /* 520 * If this is a one-way mask node, its offset must equal 521 * its mask's bitlen. 522 */ 523 KASSERT(!(PTN_ISMASK_P(ptn) && PTN_BRANCH_BITLEN(ptn) == 0) || PTN_MASK_BITLEN(ptn) == branch_bitoff); 524 525 /* 526 * If we are inserting a mask, and we know that at this point 527 * all bits before the current bit offset match both the target 528 * and the branch. If the target's mask length is LEQ than 529 * this branch's bit offset, then this is where the mask needs 530 * to added to the tree. 531 */ 532 if (__predict_false(inserting_mask) 533 && (PTN_ISROOT_P(pt, id.id_parent) 534 || id.id_bitoff < target_masklen) 535 && target_masklen <= branch_bitoff) { 536 /* 537 * We don't know about the bits (if any) between 538 * id.id_bitoff and the target's mask length match 539 * both the target and the branch. If the target's 540 * mask length is greater than the current bit offset 541 * make sure the untested bits match both the target 542 * and the branch. 543 */ 544 if (target_masklen == id.id_bitoff 545 || ptree_matchnode(pt, target, ptn, target_masklen, 546 &id.id_bitoff, &id.id_slot)) { 547 /* 548 * The bits matched, so insert the mask as a 549 * one-way branch. 550 */ 551 insertfunc = ptree_insert_mask_before_node; 552 break; 553 } else if (id.id_bitoff < branch_bitoff) { 554 /* 555 * They didn't match, so create a normal branch 556 * because this mask needs to a be a new leaf. 557 */ 558 insertfunc = ptree_insert_branch_at_node; 559 break; 560 } 561 } 562#endif /* PTNOMASK */ 563 564 /* 565 * If we are skipping some bits, verify they match the node. 566 * If they don't match, it means we have a leaf to insert. 567 * Note that if we are advancing bit by bit, we'll skip 568 * doing matchnode and walk the tree bit by bit via testnode. 569 */ 570 if (id.id_bitoff < branch_bitoff 571 && !ptree_matchnode(pt, target, ptn, branch_bitoff, 572 &id.id_bitoff, &id.id_slot)) { 573 KASSERT(id.id_bitoff < branch_bitoff); 574 insertfunc = ptree_insert_branch_at_node; 575 break; 576 } 577 578 /* 579 * At this point, all bits before branch_bitoff are known 580 * to match the target. 581 */ 582 KASSERT(id.id_bitoff >= branch_bitoff); 583 584 /* 585 * Decend the tree one level. 586 */ 587 id.id_parent = ptn; 588 id.id_parent_slot = ptree_testnode(pt, target, id.id_parent); 589 id.id_bitoff += PTN_BRANCH_BITLEN(id.id_parent); 590 id.id_insertp = &PTN_BRANCH_SLOT(id.id_parent, id.id_parent_slot); 591 } 592 593 /* 594 * Do the actual insertion. 595 */ 596 return (*insertfunc)(pt, target, &id); 597} 598 599bool 600ptree_insert_node(pt_tree_t *pt, void *item) 601{ 602 pt_node_t * const target = ITEMTONODE(pt, item); 603 604 memset(target, 0, sizeof(*target)); 605 return ptree_insert_node_common(pt, target); 606} 607 608#ifndef PTNOMASK 609bool 610ptree_insert_mask_node(pt_tree_t *pt, void *item, pt_bitlen_t mask_len) 611{ 612 pt_node_t * const target = ITEMTONODE(pt, item); 613 pt_bitoff_t bitoff = mask_len; 614 pt_slot_t slot; 615 616 memset(target, 0, sizeof(*target)); 617 KASSERT(mask_len == 0 || (~PT__MASK(PTN_MASK_BITLEN) & mask_len) == 0); 618 /* 619 * Only the first <mask_len> bits can be non-zero. 620 * All other bits must be 0. 621 */ 622 if (!ptree_matchnode(pt, target, NULL, UINT_MAX, &bitoff, &slot)) 623 return false; 624 PTN_SET_MASK_BITLEN(target, mask_len); 625 PTN_MARK_MASK(target); 626 return ptree_insert_node_common(pt, target); 627} 628#endif /* !PTNOMASH */ 629 630void * 631ptree_find_filtered_node(pt_tree_t *pt, const void *key, pt_filter_t filter, 632 void *filter_arg) 633{ 634#ifndef PTNOMASK 635 pt_node_t *mask = NULL; 636#endif 637 bool at_mask = false; 638 pt_node_t *ptn, *parent; 639 pt_bitoff_t bitoff; 640 pt_slot_t parent_slot; 641 642 if (PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode))) 643 return NULL; 644 645 bitoff = 0; 646 parent = &pt->pt_rootnode; 647 parent_slot = PT_SLOT_ROOT; 648 for (;;) { 649 const uintptr_t node = PTN_BRANCH_SLOT(parent, parent_slot); 650 const pt_slot_t branch_bitoff = PTN_BRANCH_BITOFF(PT_NODE(node)); 651 ptn = PT_NODE(node); 652 653 if (PT_LEAF_P(node)) { 654#ifndef PTNOMASK 655 at_mask = PTN_ISMASK_P(ptn); 656#endif 657 break; 658 } 659 660 if (bitoff < branch_bitoff) { 661 if (!ptree_matchkey(pt, key, ptn, bitoff, branch_bitoff - bitoff)) { 662#ifndef PTNOMASK 663 if (mask != NULL) 664 return NODETOITEM(pt, mask); 665#endif 666 return NULL; 667 } 668 bitoff = branch_bitoff; 669 } 670 671#ifndef PTNOMASK 672 if (PTN_ISMASK_P(ptn) && PTN_BRANCH_BITLEN(ptn) == 0 673 && (!filter 674 || (*filter)(filter_arg, NODETOITEM(pt, ptn), 675 PT_FILTER_MASK))) 676 mask = ptn; 677#endif 678 679 parent = ptn; 680 parent_slot = ptree_testkey(pt, key, parent); 681 bitoff += PTN_BRANCH_BITLEN(parent); 682 } 683 684 KASSERT(PTN_ISROOT_P(pt, parent) || PTN_BRANCH_BITOFF(parent) + PTN_BRANCH_BITLEN(parent) == bitoff); 685 if (!filter || (*filter)(filter_arg, NODETOITEM(pt, ptn), at_mask ? PT_FILTER_MASK : 0)) { 686#ifndef PTNOMASK 687 if (PTN_ISMASK_P(ptn)) { 688 const pt_bitlen_t mask_len = PTN_MASK_BITLEN(ptn); 689 if (bitoff == PTN_MASK_BITLEN(ptn)) 690 return NODETOITEM(pt, ptn); 691 if (ptree_matchkey(pt, key, ptn, bitoff, mask_len - bitoff)) 692 return NODETOITEM(pt, ptn); 693 } else 694#endif /* !PTNOMASK */ 695 if (ptree_matchkey(pt, key, ptn, bitoff, UINT_MAX)) 696 return NODETOITEM(pt, ptn); 697 } 698 699#ifndef PTNOMASK 700 /* 701 * By virtue of how the mask was placed in the tree, 702 * all nodes descended from it will match it. But the bits 703 * before the mask still need to be checked and since the 704 * mask was a branch, that was done implicitly. 705 */ 706 if (mask != NULL) { 707 KASSERT(ptree_matchkey(pt, key, mask, 0, PTN_MASK_BITLEN(mask))); 708 return NODETOITEM(pt, mask); 709 } 710#endif /* !PTNOMASK */ 711 712 /* 713 * Nothing matched. 714 */ 715 return NULL; 716} 717 718void * 719ptree_iterate(pt_tree_t *pt, const void *item, pt_direction_t direction) 720{ 721 const pt_node_t * const target = ITEMTONODE(pt, item); 722 uintptr_t node, next_node; 723 724 if (direction != PT_ASCENDING && direction != PT_DESCENDING) 725 return NULL; 726 727 node = PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode); 728 if (PT_NULL_P(node)) 729 return NULL; 730 731 if (item == NULL) { 732 pt_node_t * const ptn = PT_NODE(node); 733 if (direction == PT_ASCENDING 734 && PTN_ISMASK_P(ptn) && PTN_BRANCH_BITLEN(ptn) == 0) 735 return NODETOITEM(pt, ptn); 736 next_node = node; 737 } else { 738#ifndef PTNOMASK 739 uintptr_t mask_node = PT_NULL; 740#endif /* !PTNOMASK */ 741 next_node = PT_NULL; 742 while (!PT_LEAF_P(node)) { 743 pt_node_t * const ptn = PT_NODE(node); 744 pt_slot_t slot; 745#ifndef PTNOMASK 746 if (PTN_ISMASK_P(ptn) && PTN_BRANCH_BITLEN(ptn) == 0) { 747 if (ptn == target) 748 break; 749 if (direction == PT_DESCENDING) { 750 mask_node = node; 751 next_node = PT_NULL; 752 } 753 } 754#endif /* !PTNOMASK */ 755 slot = ptree_testnode(pt, target, ptn); 756 node = PTN_BRANCH_SLOT(ptn, slot); 757 if (direction == PT_ASCENDING) { 758 if (slot != (pt_slot_t)((1 << PTN_BRANCH_BITLEN(ptn)) - 1)) 759 next_node = PTN_BRANCH_SLOT(ptn, slot + 1); 760 } else { 761 if (slot > 0) { 762#ifndef PTNOMASK 763 mask_node = PT_NULL; 764#endif /* !PTNOMASK */ 765 next_node = PTN_BRANCH_SLOT(ptn, slot - 1); 766 } 767 } 768 } 769 if (PT_NODE(node) != target) 770 return NULL; 771#ifndef PTNOMASK 772 if (PT_BRANCH_P(node)) { 773 pt_node_t *ptn = PT_NODE(node); 774 KASSERT(PTN_ISMASK_P(PT_NODE(node)) && PTN_BRANCH_BITLEN(PT_NODE(node)) == 0); 775 if (direction == PT_ASCENDING) { 776 next_node = PTN_BRANCH_ROOT_SLOT(ptn); 777 ptn = PT_NODE(next_node); 778 } 779 } 780 /* 781 * When descending, if we countered a mask node then that's 782 * we want to return. 783 */ 784 if (direction == PT_DESCENDING && !PT_NULL_P(mask_node)) { 785 KASSERT(PT_NULL_P(next_node)); 786 return NODETOITEM(pt, PT_NODE(mask_node)); 787 } 788#endif /* !PTNOMASK */ 789 } 790 791 node = next_node; 792 if (PT_NULL_P(node)) 793 return NULL; 794 795 while (!PT_LEAF_P(node)) { 796 pt_node_t * const ptn = PT_NODE(node); 797 pt_slot_t slot; 798 if (direction == PT_ASCENDING) { 799#ifndef PTNOMASK 800 if (PT_BRANCH_P(node) 801 && PTN_ISMASK_P(ptn) 802 && PTN_BRANCH_BITLEN(ptn) == 0) 803 return NODETOITEM(pt, ptn); 804#endif /* !PTNOMASK */ 805 slot = PT_SLOT_LEFT; 806 } else { 807 slot = (1 << PTN_BRANCH_BITLEN(ptn)) - 1; 808 } 809 node = PTN_BRANCH_SLOT(ptn, slot); 810 } 811 return NODETOITEM(pt, PT_NODE(node)); 812} 813 814void 815ptree_remove_node(pt_tree_t *pt, void *item) 816{ 817 pt_node_t * const target = ITEMTONODE(pt, item); 818 const pt_slot_t leaf_slot = PTN_LEAF_POSITION(target); 819 const pt_slot_t branch_slot = PTN_BRANCH_POSITION(target); 820 pt_node_t *ptn, *parent; 821 uintptr_t node; 822 uintptr_t *removep; 823 uintptr_t *nodep; 824 pt_bitoff_t bitoff; 825 pt_slot_t parent_slot; 826#ifndef PTNOMASK 827 bool at_mask; 828#endif 829 830 if (PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode))) { 831 KASSERT(!PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode))); 832 return; 833 } 834 835 bitoff = 0; 836 removep = NULL; 837 nodep = NULL; 838 parent = &pt->pt_rootnode; 839 parent_slot = PT_SLOT_ROOT; 840 for (;;) { 841 node = PTN_BRANCH_SLOT(parent, parent_slot); 842 ptn = PT_NODE(node); 843#ifndef PTNOMASK 844 at_mask = PTN_ISMASK_P(ptn); 845#endif 846 847 if (PT_LEAF_P(node)) 848 break; 849 850 /* 851 * If we are at the target, then we are looking at its branch 852 * identity. We need to remember who's pointing at it so we 853 * stop them from doing that. 854 */ 855 if (__predict_false(ptn == target)) { 856 KASSERT(nodep == NULL); 857#ifndef PTNOMASK 858 /* 859 * Interior mask nodes are trivial to get rid of. 860 */ 861 if (at_mask && PTN_BRANCH_BITLEN(ptn) == 0) { 862 PTN_BRANCH_SLOT(parent, parent_slot) = 863 PTN_BRANCH_ROOT_SLOT(ptn); 864 KASSERT(PT_NULL_P(PTN_BRANCH_ODDMAN_SLOT(ptn))); 865 PTREE_CHECK(pt); 866 return; 867 } 868#endif /* !PTNOMASK */ 869 nodep = &PTN_BRANCH_SLOT(parent, parent_slot); 870 KASSERT(*nodep == PTN_BRANCH(target)); 871 } 872 /* 873 * We need also need to know who's pointing at our parent. 874 * After we remove ourselves from our parent, he'll only 875 * have one child and that's unacceptable. So we replace 876 * the pointer to the parent with our abadoned sibling. 877 */ 878 removep = &PTN_BRANCH_SLOT(parent, parent_slot); 879 880 /* 881 * Descend into the tree. 882 */ 883 parent = ptn; 884 parent_slot = ptree_testnode(pt, target, parent); 885 bitoff += PTN_BRANCH_BITLEN(parent); 886 } 887 888 /* 889 * We better have found that the leaf we are looking for is target. 890 */ 891 if (target != ptn) { 892 KASSERT(target == ptn); 893 return; 894 } 895 896 /* 897 * If we didn't encounter target as branch, then target must be the 898 * oddman-out. 899 */ 900 if (nodep == NULL) { 901 KASSERT(PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) == PTN_LEAF(target)); 902 KASSERT(nodep == NULL); 903 nodep = &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode); 904 } 905 906 KASSERT((removep == NULL) == (parent == &pt->pt_rootnode)); 907 908 /* 909 * We have to special remove the last leaf from the root since 910 * the only time the tree can a PT_NULL node is when it's empty. 911 */ 912 if (__predict_false(PTN_ISROOT_P(pt, parent))) { 913 KASSERT(removep == NULL); 914 KASSERT(parent == &pt->pt_rootnode); 915 KASSERT(nodep == &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode)); 916 KASSERT(*nodep == PTN_LEAF(target)); 917 PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode) = PT_NULL; 918 PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PT_NULL; 919 return; 920 } 921 922 KASSERT((parent == target) == (removep == nodep)); 923 if (PTN_BRANCH(parent) == PTN_BRANCH_SLOT(target, PTN_BRANCH_POSITION(parent))) { 924 /* 925 * The pointer to the parent actually lives in the target's 926 * branch identity. We can't just move the target's branch 927 * identity since that would result in the parent pointing 928 * to its own branch identity and that's fobidden. 929 */ 930 const pt_slot_t slot = PTN_BRANCH_POSITION(parent); 931 const pt_slot_t other_slot = slot ^ PT_SLOT_OTHER; 932 const pt_bitlen_t parent_bitlen = PTN_BRANCH_BITLEN(parent); 933 934 KASSERT(PTN_BRANCH_BITOFF(target) < PTN_BRANCH_BITOFF(parent)); 935 936 /* 937 * This gets so confusing. The target's branch identity 938 * points to the branch identity of the parent of the target's 939 * leaf identity: 940 * 941 * TB = { X, PB = { TL, Y } } 942 * or TB = { X, PB = { TL } } 943 * 944 * So we can't move the target's branch identity to the parent 945 * because that would corrupt the tree. 946 */ 947 if (__predict_true(parent_bitlen > 0)) { 948 /* 949 * The parent is a two-way branch. We have to have 950 * do to this chang in two steps to keep internally 951 * consistent. First step is to copy our sibling from 952 * our parent to where we are pointing to parent's 953 * branch identiy. This remove all references to his 954 * branch identity from the tree. We then simply make 955 * the parent assume the target's branching duties. 956 * 957 * TB = { X, PB = { Y, TL } } --> PB = { X, Y }. 958 * TB = { X, PB = { TL, Y } } --> PB = { X, Y }. 959 * TB = { PB = { Y, TL }, X } --> PB = { Y, X }. 960 * TB = { PB = { TL, Y }, X } --> PB = { Y, X }. 961 */ 962 PTN_BRANCH_SLOT(target, slot) = 963 PTN_BRANCH_SLOT(parent, parent_slot ^ PT_SLOT_OTHER); 964 *nodep = ptree_move_branch(pt, parent, target); 965 PTREE_CHECK(pt); 966 return; 967 } else { 968 /* 969 * If parent was a one-way branch, it must have been 970 * mask which pointed to a single leaf which we are 971 * removing. This means we have to convert the 972 * parent back to a leaf node. So in the same 973 * position that target pointed to parent, we place 974 * leaf pointer to parent. In the other position, 975 * we just put the other node from target. 976 * 977 * TB = { X, PB = { TL } } --> PB = { X, PL } 978 */ 979 KASSERT(PTN_ISMASK_P(parent)); 980 KASSERT(slot == ptree_testnode(pt, parent, target)); 981 PTN_BRANCH_SLOT(parent, slot) = PTN_LEAF(parent); 982 PTN_BRANCH_SLOT(parent, other_slot) = 983 PTN_BRANCH_SLOT(target, other_slot); 984 PTN_SET_LEAF_POSITION(parent,slot); 985 PTN_SET_BRANCH_BITLEN(parent, 1); 986 } 987 PTN_SET_BRANCH_BITOFF(parent, PTN_BRANCH_BITOFF(target)); 988 PTN_SET_BRANCH_POSITION(parent, PTN_BRANCH_POSITION(target)); 989 990 *nodep = PTN_BRANCH(parent); 991 PTREE_CHECK(pt); 992 return; 993 } 994 995#ifndef PTNOMASK 996 if (__predict_false(PTN_BRANCH_BITLEN(parent) == 0)) { 997 /* 998 * Parent was a one-way branch which is changing back to a leaf. 999 * Since parent is no longer a one-way branch, it can take over 1000 * target's branching duties. 1001 * 1002 * GB = { PB = { TL } } --> GB = { PL } 1003 * TB = { X, Y } --> PB = { X, Y } 1004 */ 1005 KASSERT(PTN_ISMASK_P(parent)); 1006 KASSERT(parent != target); 1007 *removep = PTN_LEAF(parent); 1008 } else 1009#endif /* !PTNOMASK */ 1010 { 1011 /* 1012 * Now we are the normal removal case. Since after the 1013 * target's leaf identity is removed from the its parent, 1014 * that parent will only have one decendent. So we can 1015 * just as easily replace the node that has the parent's 1016 * branch identity with the surviving node. This freeing 1017 * parent from its branching duties which means it can 1018 * take over target's branching duties. 1019 * 1020 * GB = { PB = { X, TL } } --> GB = { X } 1021 * TB = { V, W } --> PB = { V, W } 1022 */ 1023 const pt_slot_t other_slot = parent_slot ^ PT_SLOT_OTHER; 1024 uintptr_t other_node = PTN_BRANCH_SLOT(parent, other_slot); 1025 const pt_slot_t target_slot = (parent == target ? branch_slot : leaf_slot); 1026 1027 *removep = other_node; 1028 1029 ptree_set_position(other_node, target_slot); 1030 1031 /* 1032 * If target's branch identity contained its leaf identity, we 1033 * have nothing left to do. We've already moved 'X' so there 1034 * is no longer anything in the target's branch identiy that 1035 * has to be preserved. 1036 */ 1037 if (parent == target) { 1038 /* 1039 * GB = { TB = { X, TL } } --> GB = { X } 1040 * TB = { X, TL } --> don't care 1041 */ 1042 PTREE_CHECK(pt); 1043 return; 1044 } 1045 } 1046 1047 /* 1048 * If target wasn't used as a branch, then it must have been the 1049 * oddman-out of the tree (the one node that doesn't have a branch 1050 * identity). This makes parent the new oddman-out. 1051 */ 1052 if (*nodep == PTN_LEAF(target)) { 1053 KASSERT(nodep == &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode)); 1054 PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PTN_LEAF(parent); 1055 PTREE_CHECK(pt); 1056 return; 1057 } 1058 1059 /* 1060 * Finally move the target's branching duties to the parent. 1061 */ 1062 KASSERT(PTN_BRANCH_BITOFF(parent) > PTN_BRANCH_BITOFF(target)); 1063 *nodep = ptree_move_branch(pt, parent, target); 1064 PTREE_CHECK(pt); 1065} 1066 1067#ifdef PTCHECK 1068static const pt_node_t * 1069ptree_check_find_node2(const pt_tree_t *pt, const pt_node_t *parent, 1070 uintptr_t target) 1071{ 1072 const pt_bitlen_t slots = 1 << PTN_BRANCH_BITLEN(parent); 1073 pt_slot_t slot; 1074 1075 for (slot = 0; slot < slots; slot++) { 1076 const uintptr_t node = PTN_BRANCH_SLOT(parent, slot); 1077 if (PTN_BRANCH_SLOT(parent, slot) == node) 1078 return parent; 1079 } 1080 for (slot = 0; slot < slots; slot++) { 1081 const uintptr_t node = PTN_BRANCH_SLOT(parent, slot); 1082 const pt_node_t *branch; 1083 if (!PT_BRANCH_P(node)) 1084 continue; 1085 branch = ptree_check_find_node2(pt, PT_NODE(node), target); 1086 if (branch != NULL) 1087 return branch; 1088 } 1089 1090 return NULL; 1091} 1092 1093static bool 1094ptree_check_leaf(const pt_tree_t *pt, const pt_node_t *parent, 1095 const pt_node_t *ptn) 1096{ 1097 const pt_bitoff_t leaf_position = PTN_LEAF_POSITION(ptn); 1098 const pt_bitlen_t bitlen = PTN_BRANCH_BITLEN(ptn); 1099 const pt_bitlen_t mask_len = PTN_MASK_BITLEN(ptn); 1100 const uintptr_t leaf_node = PTN_LEAF(ptn); 1101 const bool is_parent_root = (parent == &pt->pt_rootnode); 1102 const bool is_mask = PTN_ISMASK_P(ptn); 1103 bool ok = true; 1104 1105 if (is_parent_root) { 1106 ok = ok && PTN_BRANCH_ODDMAN_SLOT(parent) == leaf_node; 1107 KASSERT(ok); 1108 return ok; 1109 } 1110 1111 if (is_mask && PTN_ISMASK_P(parent) && PTN_BRANCH_BITLEN(parent) == 0) { 1112 ok = ok && PTN_MASK_BITLEN(parent) < mask_len; 1113 KASSERT(ok); 1114 ok = ok && PTN_BRANCH_BITOFF(parent) < mask_len; 1115 KASSERT(ok); 1116 } 1117 ok = ok && PTN_BRANCH_SLOT(parent, leaf_position) == leaf_node; 1118 KASSERT(ok); 1119 ok = ok && leaf_position == ptree_testnode(pt, ptn, parent); 1120 KASSERT(ok); 1121 if (PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) != leaf_node) { 1122 ok = ok && bitlen > 0; 1123 KASSERT(ok); 1124 ok = ok && ptn == ptree_check_find_node2(pt, ptn, PTN_LEAF(ptn)); 1125 KASSERT(ok); 1126 } 1127 return ok; 1128} 1129 1130static bool 1131ptree_check_branch(const pt_tree_t *pt, const pt_node_t *parent, 1132 const pt_node_t *ptn) 1133{ 1134 const bool is_parent_root = (parent == &pt->pt_rootnode); 1135 const pt_slot_t branch_slot = PTN_BRANCH_POSITION(ptn); 1136 const pt_bitoff_t bitoff = PTN_BRANCH_BITOFF(ptn); 1137 const pt_bitoff_t bitlen = PTN_BRANCH_BITLEN(ptn); 1138 const pt_bitoff_t parent_bitoff = PTN_BRANCH_BITOFF(parent); 1139 const pt_bitoff_t parent_bitlen = PTN_BRANCH_BITLEN(parent); 1140 const bool is_parent_mask = PTN_ISMASK_P(parent) && parent_bitlen == 0; 1141 const bool is_mask = PTN_ISMASK_P(ptn) && bitlen == 0; 1142 const pt_bitoff_t parent_mask_len = PTN_MASK_BITLEN(parent); 1143 const pt_bitoff_t mask_len = PTN_MASK_BITLEN(ptn); 1144 const pt_bitlen_t slots = 1 << bitlen; 1145 pt_slot_t slot; 1146 bool ok = true; 1147 1148 ok = ok && PTN_BRANCH_SLOT(parent, branch_slot) == PTN_BRANCH(ptn); 1149 KASSERT(ok); 1150 ok = ok && branch_slot == ptree_testnode(pt, ptn, parent); 1151 KASSERT(ok); 1152 1153 if (is_mask) { 1154 ok = ok && bitoff == mask_len; 1155 KASSERT(ok); 1156 if (is_parent_mask) { 1157 ok = ok && parent_mask_len < mask_len; 1158 KASSERT(ok); 1159 ok = ok && parent_bitoff < bitoff; 1160 KASSERT(ok); 1161 } 1162 } else { 1163 if (is_parent_mask) { 1164 ok = ok && parent_bitoff <= bitoff; 1165 } else if (!is_parent_root) { 1166 ok = ok && parent_bitoff < bitoff; 1167 } 1168 KASSERT(ok); 1169 } 1170 1171 for (slot = 0; slot < slots; slot++) { 1172 const uintptr_t node = PTN_BRANCH_SLOT(ptn, slot); 1173 pt_bitoff_t tmp_bitoff = 0; 1174 pt_slot_t tmp_slot; 1175 ok = ok && node != PTN_BRANCH(ptn); 1176 KASSERT(ok); 1177 if (bitlen > 0) { 1178 ok = ok && ptree_matchnode(pt, PT_NODE(node), ptn, bitoff, &tmp_bitoff, &tmp_slot); 1179 KASSERT(ok); 1180 tmp_slot = ptree_testnode(pt, PT_NODE(node), ptn); 1181 ok = ok && slot == tmp_slot; 1182 KASSERT(ok); 1183 } 1184 if (PT_LEAF_P(node)) 1185 ok = ok && ptree_check_leaf(pt, ptn, PT_NODE(node)); 1186 else 1187 ok = ok && ptree_check_branch(pt, ptn, PT_NODE(node)); 1188 } 1189 1190 return ok; 1191} 1192#endif /* PTCHECK */ 1193 1194/*ARGSUSED*/ 1195bool 1196ptree_check(const pt_tree_t *pt) 1197{ 1198 bool ok = true; 1199#ifdef PTCHECK 1200 const pt_node_t * const parent = &pt->pt_rootnode; 1201 const uintptr_t node = pt->pt_root; 1202 const pt_node_t * const ptn = PT_NODE(node); 1203 1204 ok = ok && PTN_BRANCH_BITOFF(parent) == 0; 1205 ok = ok && !PTN_ISMASK_P(parent); 1206 1207 if (PT_NULL_P(node)) 1208 return ok; 1209 1210 if (PT_LEAF_P(node)) 1211 ok = ok && ptree_check_leaf(pt, parent, ptn); 1212 else 1213 ok = ok && ptree_check_branch(pt, parent, ptn); 1214#endif 1215 return ok; 1216} 1217 1218bool 1219ptree_mask_node_p(pt_tree_t *pt, const void *item, pt_bitlen_t *lenp) 1220{ 1221 const pt_node_t * const mask = ITEMTONODE(pt, item); 1222 1223 if (!PTN_ISMASK_P(mask)) 1224 return false; 1225 1226 if (lenp != NULL) 1227 *lenp = PTN_MASK_BITLEN(mask); 1228 1229 return true; 1230} 1231