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