xref: /minix3/common/lib/libc/gen/ptree.c (revision f14fb602092e015ff630df58e17c2a9cd57d29b3)
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 
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
ptree_matchnode(const pt_tree_t * pt,const pt_node_t * target,const pt_node_t * ptn,pt_bitoff_t max_bitoff,pt_bitoff_t * bitoff_p,pt_slot_t * slots_p)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),
128 	    max_bitoff, bitoff_p, slots_p, pt->pt_context);
129 }
130 
131 static inline pt_slot_t
ptree_testnode(const pt_tree_t * pt,const pt_node_t * target,const pt_node_t * ptn)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;	/* 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 
142 static inline bool
ptree_matchkey(const pt_tree_t * pt,const void * key,const pt_node_t * ptn,pt_bitoff_t bitoff,pt_bitlen_t bitlen)143 ptree_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 
150 static inline pt_slot_t
ptree_testkey(const pt_tree_t * pt,const void * key,const pt_node_t * ptn)151 ptree_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 
160 static inline void
ptree_set_position(uintptr_t node,pt_slot_t position)161 ptree_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 
169 void
ptree_init(pt_tree_t * pt,const pt_tree_ops_t * ops,void * context,size_t node_offset,size_t key_offset)170 ptree_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 
180 typedef 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 
189 typedef 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*/
196 static uintptr_t
ptree_move_branch(pt_tree_t * const pt,pt_node_t * const dst,const pt_node_t * const src)197 ptree_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
209 static inline uintptr_t *
ptree_find_branch(pt_tree_t * const pt,uintptr_t branch_node)210 ptree_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 
226 static bool
ptree_insert_leaf_after_mask(pt_tree_t * const pt,pt_node_t * const target,pt_insertdata_t * const id)227 ptree_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*/
293 static bool
ptree_insert_mask_before_node(pt_tree_t * const pt,pt_node_t * const target,pt_insertdata_t * const id)294 ptree_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*/
328 static bool
ptree_insert_branch_at_node(pt_tree_t * const pt,pt_node_t * const target,pt_insertdata_t * const id)329 ptree_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 
359 static bool
ptree_insert_leaf(pt_tree_t * const pt,pt_node_t * const target,pt_insertdata_t * const id)360 ptree_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 
450 static bool
ptree_insert_node_common(pt_tree_t * pt,void * item)451 ptree_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 
599 bool
ptree_insert_node(pt_tree_t * pt,void * item)600 ptree_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
609 bool
ptree_insert_mask_node(pt_tree_t * pt,void * item,pt_bitlen_t mask_len)610 ptree_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 
630 void *
ptree_find_filtered_node(pt_tree_t * pt,const void * key,pt_filter_t filter,void * filter_arg)631 ptree_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 
718 void *
ptree_iterate(pt_tree_t * pt,const void * item,pt_direction_t direction)719 ptree_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 
814 void
ptree_remove_node(pt_tree_t * pt,void * item)815 ptree_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
1068 static const pt_node_t *
ptree_check_find_node2(const pt_tree_t * pt,const pt_node_t * parent,uintptr_t target)1069 ptree_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 
1093 static bool
ptree_check_leaf(const pt_tree_t * pt,const pt_node_t * parent,const pt_node_t * ptn)1094 ptree_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 
1130 static bool
ptree_check_branch(const pt_tree_t * pt,const pt_node_t * parent,const pt_node_t * ptn)1131 ptree_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*/
1195 bool
ptree_check(const pt_tree_t * pt)1196 ptree_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 
1218 bool
ptree_mask_node_p(pt_tree_t * pt,const void * item,pt_bitlen_t * lenp)1219 ptree_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