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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 * |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 * |
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 * |
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 |
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 * |
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 |
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 |
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 |
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 |
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 | |