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