1/* $NetBSD: ptree.c,v 1.10 2012/10/06 22:15:09 matt 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.10 2012/10/06 22:15:09 matt 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.10 2012/10/06 22:15:09 matt 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