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