No empty .Rs/.Re

[netbsd-mini2440.git] / common / lib / libc / gen / ptree.c

/* $NetBSD: ptree.c,v 1.4 2009/01/18 12:06:14 lukem Exp $ */

/*-
 * Copyright (c) 2008 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Matt Thomas <matt@3am-software.com>.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#define _PT_PRIVATE

#if defined(PTCHECK) && !defined(PTDEBUG)
#define PTDEBUG
#endif

#if defined(_KERNEL) || defined(_STANDALONE)
#include <sys/param.h>
#include <sys/types.h>
#include <sys/systm.h>
#include <lib/libkern/libkern.h>
__KERNEL_RCSID(0, "$NetBSD: ptree.c,v 1.4 2009/01/18 12:06:14 lukem Exp $");
#else
#include <stddef.h>
#include <stdint.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>
#ifdef PTDEBUG
#include <assert.h>
#define KASSERT(e)      assert(e)
#else
#define KASSERT(e)      do { } while (/*CONSTCOND*/ 0)
#endif
__RCSID("$NetBSD: ptree.c,v 1.4 2009/01/18 12:06:14 lukem Exp $");
#endif /* _KERNEL || _STANDALONE */

#ifdef _LIBC
#include "namespace.h"
#endif

#ifdef PTTEST
#include "ptree.h"
#else
#include <sys/ptree.h>
#endif

/*
 * This is an implementation of a radix / PATRICIA tree.  As in a traditional 
 * patricia tree, all the data is at the leaves of the tree.  An N-value
 * tree would have N leaves, N-1 branching nodes, and a root pointer.  Each
 * branching node would have left(0) and right(1) pointers that either point
 * to another branching node or a leaf node.  The root pointer would also
 * point to either the first branching node or a leaf node.  Leaf nodes
 * have no need for pointers.
 *
 * However, allocation for these branching nodes is problematic since the
 * allocation could fail.  This would cause insertions to fail for reasons  
 * beyond the users control.  So to prevent this, in this implementation
 * each node has two identities: its leaf identity and its branch identity.
 * Each is separate from the other.  Every branch is tagged as to whether
 * it points to a leaf or a branch.  This is not an attribute of the object
 * but of the pointer to the object.  The low bit of the pointer is used as
 * the tag to determine whether it points to a leaf or branch identity, with
 * branch identities having the low bit set.
 * 
 * A node's branch identity has one rule: when traversing the tree from the
 * root to the node's leaf identity, one of the branches traversed will be via
 * the node's branch identity.  Of course, that has an exception: since to
 * store N leaves, you need N-1 branches.  That one node whose branch identity
 * isn't used is stored as "oddman"-out in the root.
 *
 * Branching nodes also has a bit offset and a bit length which determines
 * which branch slot is used.  The bit length can be zero resulting in a
 * one-way branch.  This is happens in two special cases: the root and
 * interior mask nodes.
 *
 * To support longest match first lookups, when a mask node (one that only
 * match the first N bits) has children who first N bits match the mask nodes,
 * that mask node is converted from being a leaf node to being a one-way
 * branch-node.  The mask becomes fixed in position in the tree.  The mask
 * will always be the longest mask match for its descendants (unless they
 * traverse an even longer match).
 */

#define NODETOITEM(pt, ptn)     \
        ((void *)((uintptr_t)(ptn) - (pt)->pt_node_offset))
#define NODETOKEY(pt, ptn)      \
        ((void *)((uintptr_t)(ptn) - (pt)->pt_node_offset + pt->pt_key_offset))
#define ITEMTONODE(pt, ptn)     \
        ((pt_node_t *)((uintptr_t)(ptn) + (pt)->pt_node_offset))

bool ptree_check(const pt_tree_t *);
#if PTCHECK > 1
#define PTREE_CHECK(pt)         ptree_check(pt)
#else
#define PTREE_CHECK(pt)         do { } while (/*CONSTCOND*/ 0)
#endif

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)
{
        return (*pt->pt_ops->ptto_matchnode)(NODETOKEY(pt, target),
            (ptn != NULL ? NODETOKEY(pt, ptn) : NULL), max_bitoff,
            bitoff_p, slots_p);
}

static inline pt_slot_t
ptree_testnode(const pt_tree_t *pt, const pt_node_t *target,
        const pt_node_t *ptn)
{
        const pt_bitlen_t bitlen = PTN_BRANCH_BITLEN(ptn);
        if (bitlen == 0)
                return PT_SLOT_ROOT;
        return (*pt->pt_ops->ptto_testnode)(NODETOKEY(pt, target),
             PTN_BRANCH_BITOFF(ptn),
             bitlen);
}

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)
{
        return (*pt->pt_ops->ptto_matchkey)(key, NODETOKEY(pt, ptn),
            bitoff, bitlen);
}

static inline pt_slot_t
ptree_testkey(const pt_tree_t *pt, const void *key, const pt_node_t *ptn)
{
        return (*pt->pt_ops->ptto_testkey)(key,
            PTN_BRANCH_BITOFF(ptn),
            PTN_BRANCH_BITLEN(ptn));
}

static inline void
ptree_set_position(uintptr_t node, pt_slot_t position)
{
        if (PT_LEAF_P(node))
                PTN_SET_LEAF_POSITION(PT_NODE(node), position);
        else
                PTN_SET_BRANCH_POSITION(PT_NODE(node), position);
}

void
ptree_init(pt_tree_t *pt, const pt_tree_ops_t *ops, size_t node_offset,
        size_t key_offset)
{
        memset(pt, 0, sizeof(*pt));
        pt->pt_node_offset = node_offset;
        pt->pt_key_offset = key_offset;
        pt->pt_ops = ops;
}

typedef struct {
        uintptr_t *id_insertp;
        pt_node_t *id_parent;
        uintptr_t id_node;
        pt_slot_t id_parent_slot;
        pt_bitoff_t id_bitoff;
        pt_slot_t id_slot;
} pt_insertdata_t;

typedef bool (*pt_insertfunc_t)(pt_tree_t *, pt_node_t *, pt_insertdata_t *);

/*
 * Move a branch identify from src to dst.  The leaves don't care since 
 * nothing for them has changed.
 */
/*ARGSUSED*/
static uintptr_t
ptree_move_branch(pt_tree_t * const pt, pt_node_t * const dst,
        const pt_node_t * const src)
{
        KASSERT(PTN_BRANCH_BITLEN(src) == 1);
        /* set branch bitlen and bitoff in one step.  */
        dst->ptn_branchdata = src->ptn_branchdata;
        PTN_SET_BRANCH_POSITION(dst, PTN_BRANCH_POSITION(src));
        PTN_COPY_BRANCH_SLOTS(dst, src);
        return PTN_BRANCH(dst);
}

#ifndef PTNOMASK
static inline uintptr_t *
ptree_find_branch(pt_tree_t * const pt, uintptr_t branch_node)
{
        pt_node_t * const branch = PT_NODE(branch_node);
        pt_node_t *parent;

        for (parent = &pt->pt_rootnode;;) {
                uintptr_t *nodep =
                    &PTN_BRANCH_SLOT(parent, ptree_testnode(pt, branch, parent));
                if (*nodep == branch_node)
                        return nodep;
                if (PT_LEAF_P(*nodep))
                        return NULL;
                parent = PT_NODE(*nodep);
        }
}

static bool
ptree_insert_leaf_after_mask(pt_tree_t * const pt, pt_node_t * const target,
        pt_insertdata_t * const id)
{
        const uintptr_t target_node = PTN_LEAF(target);
        const uintptr_t mask_node = id->id_node;
        pt_node_t * const mask = PT_NODE(mask_node);
        const pt_bitlen_t mask_len = PTN_MASK_BITLEN(mask);

        KASSERT(PT_LEAF_P(mask_node));
        KASSERT(PTN_LEAF_POSITION(mask) == id->id_parent_slot);
        KASSERT(mask_len <= id->id_bitoff);
        KASSERT(PTN_ISMASK_P(mask));
        KASSERT(!PTN_ISMASK_P(target) || mask_len < PTN_MASK_BITLEN(target));

        if (mask_node == PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode)) {
                KASSERT(id->id_parent != mask);
                /*
                 * Nice, mask was an oddman.  So just set the oddman to target.
                 */
                PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = target_node;
        } else {
                /*
                 * We need to find out who's pointing to mask's branch
                 * identity.  We know that between root and the leaf identity,
                 * we must traverse the node's branch identity.
                 */
                uintptr_t * const mask_nodep = ptree_find_branch(pt, PTN_BRANCH(mask));
                KASSERT(mask_nodep != NULL);
                KASSERT(*mask_nodep == PTN_BRANCH(mask));
                KASSERT(PTN_BRANCH_BITLEN(mask) == 1);

                /*
                 * Alas, mask was used as a branch.  Since the mask is becoming
                 * a one-way branch, we need make target take over mask's
                 * branching responsibilities.  Only then can we change it.
                 */
                *mask_nodep = ptree_move_branch(pt, target, mask);

                /*
                 * However, it's possible that mask's parent is itself.  If
                 * that's true, update the insert point to use target since it
                 * has taken over mask's branching duties.
                 */
                if (id->id_parent == mask)
                        id->id_insertp = &PTN_BRANCH_SLOT(target,
                            id->id_parent_slot);
        }

        PTN_SET_BRANCH_BITLEN(mask, 0);
        PTN_SET_BRANCH_BITOFF(mask, mask_len);

        PTN_BRANCH_ROOT_SLOT(mask) = target_node;
        PTN_BRANCH_ODDMAN_SLOT(mask) = PT_NULL;
        PTN_SET_LEAF_POSITION(target, PT_SLOT_ROOT);
        PTN_SET_BRANCH_POSITION(mask, id->id_parent_slot);

        /*
         * Now that everything is done, to make target visible we need to
         * change mask from a leaf to a branch.
         */
        *id->id_insertp = PTN_BRANCH(mask);
        PTREE_CHECK(pt);
        return true;
}

/*ARGSUSED*/
static bool
ptree_insert_mask_before_node(pt_tree_t * const pt, pt_node_t * const target,
        pt_insertdata_t * const id)
{
        const uintptr_t node = id->id_node;
        pt_node_t * const ptn = PT_NODE(node);
        const pt_slot_t mask_len = PTN_MASK_BITLEN(target);
        const pt_bitlen_t node_mask_len = PTN_MASK_BITLEN(ptn);

        KASSERT(PT_LEAF_P(node) || id->id_parent_slot == PTN_BRANCH_POSITION(ptn));
        KASSERT(PT_BRANCH_P(node) || id->id_parent_slot == PTN_LEAF_POSITION(ptn));
        KASSERT(PTN_ISMASK_P(target));

        /*
         * If the node we are placing ourself in front is a mask with the
         * same mask length as us, return failure.
         */
        if (PTN_ISMASK_P(ptn) && node_mask_len == mask_len)
                return false;

        PTN_SET_BRANCH_BITLEN(target, 0);
        PTN_SET_BRANCH_BITOFF(target, mask_len);

        PTN_BRANCH_SLOT(target, PT_SLOT_ROOT) = node;
        *id->id_insertp = PTN_BRANCH(target);

        PTN_SET_BRANCH_POSITION(target, id->id_parent_slot);
        ptree_set_position(node, PT_SLOT_ROOT);

        PTREE_CHECK(pt);
        return true;
}
#endif /* !PTNOMASK */

/*ARGSUSED*/
static bool
ptree_insert_branch_at_node(pt_tree_t * const pt, pt_node_t * const target,
        pt_insertdata_t * const id)
{
        const uintptr_t target_node = PTN_LEAF(target);
        const uintptr_t node = id->id_node;
        const pt_slot_t other_slot = id->id_slot ^ PT_SLOT_OTHER;

        KASSERT(PT_BRANCH_P(node) || id->id_parent_slot == PTN_LEAF_POSITION(PT_NODE(node)));
        KASSERT(PT_LEAF_P(node) || id->id_parent_slot == PTN_BRANCH_POSITION(PT_NODE(node)));
        KASSERT((node == pt->pt_root) == (id->id_parent == &pt->pt_rootnode));
#ifndef PTNOMASK
        KASSERT(!PTN_ISMASK_P(target) || id->id_bitoff <= PTN_MASK_BITLEN(target));
#endif
        KASSERT(node == pt->pt_root || PTN_BRANCH_BITOFF(id->id_parent) + PTN_BRANCH_BITLEN(id->id_parent) <= id->id_bitoff);

        PTN_SET_BRANCH_BITOFF(target, id->id_bitoff);
        PTN_SET_BRANCH_BITLEN(target, 1);

        PTN_BRANCH_SLOT(target, id->id_slot) = target_node;
        PTN_BRANCH_SLOT(target, other_slot) = node;
        *id->id_insertp = PTN_BRANCH(target);

        PTN_SET_LEAF_POSITION(target, id->id_slot);
        ptree_set_position(node, other_slot);

        PTN_SET_BRANCH_POSITION(target, id->id_parent_slot);
        PTREE_CHECK(pt);
        return true;
}

static bool
ptree_insert_leaf(pt_tree_t * const pt, pt_node_t * const target,
        pt_insertdata_t * const id)
{
        const uintptr_t leaf_node = id->id_node;
        pt_node_t * const leaf = PT_NODE(leaf_node);
#ifdef PTNOMASK
        const bool inserting_mask = false;
        const bool at_mask = false;
#else
        const bool inserting_mask = PTN_ISMASK_P(target);
        const bool at_mask = PTN_ISMASK_P(leaf);
        const pt_bitlen_t leaf_masklen = PTN_MASK_BITLEN(leaf);
        const pt_bitlen_t target_masklen = PTN_MASK_BITLEN(target);
#endif
        pt_insertfunc_t insertfunc = ptree_insert_branch_at_node;
        bool matched;

        /*
         * In all likelyhood we are going simply going to insert a branch
         * where this leaf is which will point to the old and new leaves.
         */
        KASSERT(PT_LEAF_P(leaf_node));
        KASSERT(PTN_LEAF_POSITION(leaf) == id->id_parent_slot);
        matched = ptree_matchnode(pt, target, leaf, UINT_MAX,
            &id->id_bitoff, &id->id_slot);
        if (__predict_false(!inserting_mask)) {
                /*
                 * We aren't inserting a mask nor is the leaf a mask, which
                 * means we are trying to insert a duplicate leaf.  Can't do
                 * that.
                 */
                if (!at_mask && matched)
                        return false;

#ifndef PTNOMASK
                /*
                 * We are at a mask and the leaf we are about to insert
                 * is at or beyond the mask, we need to convert the mask
                 * from a leaf to a one-way branch interior mask.
                 */
                if (at_mask && id->id_bitoff >= leaf_masklen)
                        insertfunc = ptree_insert_leaf_after_mask;
#endif /* PTNOMASK */
        }
#ifndef PTNOMASK
        else {
                /*
                 * We are inserting a mask.
                 */
                if (matched) {
                        /*
                         * If the leaf isn't a mask, we obviously have to
                         * insert the new mask before non-mask leaf.  If the
                         * leaf is a mask, and the new node has a LEQ mask
                         * length it too needs to inserted before leaf (*).
                         *
                         * In other cases, we place the new mask as leaf after
                         * leaf mask.  Which mask comes first will be a one-way
                         * branch interior mask node which has the other mask
                         * node as a child.
                         *
                         * (*) ptree_insert_mask_before_node can detect a
                         * duplicate mask and return failure if needed.
                         */
                        if (!at_mask || target_masklen <= leaf_masklen)
                                insertfunc = ptree_insert_mask_before_node;
                        else
                                insertfunc = ptree_insert_leaf_after_mask;
                } else if (at_mask && id->id_bitoff >= leaf_masklen) {
                        /*
                         * If the new mask has a bit offset GEQ than the leaf's
                         * mask length, convert the left to a one-way branch
                         * interior mask and make that point to the new [leaf]
                         * mask.
                         */
                        insertfunc = ptree_insert_leaf_after_mask;
                } else {
                        /*
                         * The new mask has a bit offset less than the leaf's
                         * mask length or if the leaf isn't a mask at all, the
                         * new mask deserves to be its own leaf so we use the
                         * default insertfunc to do that.
                         */
                }
        }
#endif /* PTNOMASK */

        return (*insertfunc)(pt, target, id);
}

static bool
ptree_insert_node_common(pt_tree_t *pt, void *item)
{
        pt_node_t * const target = ITEMTONODE(pt, item);
#ifndef PTNOMASK
        const bool inserting_mask = PTN_ISMASK_P(target);
        const pt_bitlen_t target_masklen = PTN_MASK_BITLEN(target);
#endif
        pt_insertfunc_t insertfunc;
        pt_insertdata_t id;

        /*
         * We need a leaf so we can match against.  Until we get a leaf
         * we having nothing to test against.
         */
        if (__predict_false(PT_NULL_P(pt->pt_root))) {
                PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode) = PTN_LEAF(target);
                PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PTN_LEAF(target);
                PTN_SET_LEAF_POSITION(target, PT_SLOT_ROOT);
                PTREE_CHECK(pt);
                return true;
        }

        id.id_bitoff = 0;
        id.id_parent = &pt->pt_rootnode;
        id.id_parent_slot = PT_SLOT_ROOT;
        id.id_insertp = &PTN_BRANCH_ROOT_SLOT(id.id_parent);
        for (;;) {
                pt_bitoff_t branch_bitoff;
                pt_node_t * const ptn = PT_NODE(*id.id_insertp);
                id.id_node = *id.id_insertp;

                /*
                 * If we hit a leaf, try to insert target at leaf.  We could
                 * have inlined ptree_insert_leaf here but that would have
                 * made this routine much harder to understand.  Trust the
                 * compiler to optimize this properly.
                 */
                if (PT_LEAF_P(id.id_node)) {
                        KASSERT(PTN_LEAF_POSITION(ptn) == id.id_parent_slot);
                        insertfunc = ptree_insert_leaf;
                        break;
                }

                /*
                 * If we aren't a leaf, we must be a branch.  Make sure we are
                 * in the slot we think we are.
                 */
                KASSERT(PT_BRANCH_P(id.id_node));
                KASSERT(PTN_BRANCH_POSITION(ptn) == id.id_parent_slot);

                /*
                 * Where is this branch?
                 */
                branch_bitoff = PTN_BRANCH_BITOFF(ptn);

#ifndef PTNOMASK
                /*
                 * If this is a one-way mask node, its offset must equal
                 * its mask's bitlen.
                 */
                KASSERT(!(PTN_ISMASK_P(ptn) && PTN_BRANCH_BITLEN(ptn) == 0) || PTN_MASK_BITLEN(ptn) == branch_bitoff);

                /*
                 * If we are inserting a mask, and we know that at this point
                 * all bits before the current bit offset match both the target
                 * and the branch.  If the target's mask length is LEQ than
                 * this branch's bit offset, then this is where the mask needs
                 * to added to the tree.
                 */
                if (__predict_false(inserting_mask)
                    && (PTN_ISROOT_P(pt, id.id_parent)
                        || id.id_bitoff < target_masklen)
                    && target_masklen <= branch_bitoff) {
                        /*
                         * We don't know about the bits (if any) between
                         * id.id_bitoff and the target's mask length match
                         * both the target and the branch.  If the target's
                         * mask length is greater than the current bit offset
                         * make sure the untested bits match both the target
                         * and the branch.
                         */
                        if (target_masklen == id.id_bitoff
                            || ptree_matchnode(pt, target, ptn, target_masklen,
                                    &id.id_bitoff, &id.id_slot)) {
                                /*
                                 * The bits matched, so insert the mask as a
                                 * one-way branch.
                                 */
                                insertfunc = ptree_insert_mask_before_node;
                                break;
                        } else if (id.id_bitoff < branch_bitoff) {
                                /*
                                 * They didn't match, so create a normal branch
                                 * because this mask needs to a be a new leaf.
                                 */
                                insertfunc = ptree_insert_branch_at_node;
                                break;
                        }
                }
#endif /* PTNOMASK */

                /*
                 * If we are skipping some bits, verify they match the node.
                 * If they don't match, it means we have a leaf to insert.
                 * Note that if we are advancing bit by bit, we'll skip
                 * doing matchnode and walk the tree bit by bit via testnode.
                 */
                if (id.id_bitoff < branch_bitoff
                    && !ptree_matchnode(pt, target, ptn, branch_bitoff,
                                        &id.id_bitoff, &id.id_slot)) {
                        KASSERT(id.id_bitoff < branch_bitoff);
                        insertfunc = ptree_insert_branch_at_node;
                        break;
                }

                /*
                 * At this point, all bits before branch_bitoff are known
                 * to match the target.
                 */
                KASSERT(id.id_bitoff >= branch_bitoff);

                /*
                 * Decend the tree one level.
                 */
                id.id_parent = ptn;
                id.id_parent_slot = ptree_testnode(pt, target, id.id_parent);
                id.id_bitoff += PTN_BRANCH_BITLEN(id.id_parent);
                id.id_insertp = &PTN_BRANCH_SLOT(id.id_parent, id.id_parent_slot);
        }

        /*
         * Do the actual insertion.
         */
        return (*insertfunc)(pt, target, &id);
}

bool
ptree_insert_node(pt_tree_t *pt, void *item)
{
        pt_node_t * const target = ITEMTONODE(pt, item);

        memset(target, 0, sizeof(*target));
        return ptree_insert_node_common(pt, target);
}

#ifndef PTNOMASK
bool
ptree_insert_mask_node(pt_tree_t *pt, void *item, pt_bitlen_t mask_len)
{
        pt_node_t * const target = ITEMTONODE(pt, item);
        pt_bitoff_t bitoff = mask_len;
        pt_slot_t slot;

        memset(target, 0, sizeof(*target));
        KASSERT(mask_len == 0 || (~PT__MASK(PTN_MASK_BITLEN) & mask_len) == 0);
        /*
         * Only the first <mask_len> bits can be non-zero.
         * All other bits must be 0.
         */
        if (!ptree_matchnode(pt, target, NULL, UINT_MAX, &bitoff, &slot))
                return false;
        PTN_SET_MASK_BITLEN(target, mask_len);
        PTN_MARK_MASK(target);
        return ptree_insert_node_common(pt, target);
}
#endif /* !PTNOMASH */

void *
ptree_find_filtered_node(pt_tree_t *pt, void *key, pt_filter_t filter,
        void *filter_arg)
{
#ifndef PTNOMASK
        pt_node_t *mask = NULL;
#endif
        bool at_mask = false;
        pt_node_t *ptn, *parent;
        pt_bitoff_t bitoff;
        pt_slot_t parent_slot;

        if (PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode)))
                return NULL;

        bitoff = 0;
        parent = &pt->pt_rootnode;
        parent_slot = PT_SLOT_ROOT;
        for (;;) {
                const uintptr_t node = PTN_BRANCH_SLOT(parent, parent_slot);
                const pt_slot_t branch_bitoff = PTN_BRANCH_BITOFF(PT_NODE(node));
                ptn = PT_NODE(node);

                if (PT_LEAF_P(node)) {
#ifndef PTNOMASK
                        at_mask = PTN_ISMASK_P(ptn);
#endif
                        break;
                }

                if (bitoff < branch_bitoff) {
                        if (!ptree_matchkey(pt, key, ptn, bitoff, branch_bitoff - bitoff)) {
#ifndef PTNOMASK
                                if (mask != NULL)
                                        return NODETOITEM(pt, mask);
#endif
                                return NULL;
                        }
                        bitoff = branch_bitoff;
                }

#ifndef PTNOMASK
                if (PTN_ISMASK_P(ptn) && PTN_BRANCH_BITLEN(ptn) == 0
                    && (!filter
                        || (*filter)(filter_arg, NODETOITEM(pt, ptn),
                                     PT_FILTER_MASK)))
                        mask = ptn;
#endif

                parent = ptn;
                parent_slot = ptree_testkey(pt, key, parent);
                bitoff += PTN_BRANCH_BITLEN(parent);
        }

        KASSERT(PTN_ISROOT_P(pt, parent) || PTN_BRANCH_BITOFF(parent) + PTN_BRANCH_BITLEN(parent) == bitoff);
        if (!filter || (*filter)(filter_arg, NODETOITEM(pt, ptn), at_mask ? PT_FILTER_MASK : 0)) {
#ifndef PTNOMASK
                if (PTN_ISMASK_P(ptn)) {
                        const pt_bitlen_t mask_len = PTN_MASK_BITLEN(ptn);
                        if (bitoff == PTN_MASK_BITLEN(ptn))
                                return NODETOITEM(pt, ptn);
                        if (ptree_matchkey(pt, key, ptn, bitoff, mask_len - bitoff))
                                return NODETOITEM(pt, ptn);
                } else
#endif /* !PTNOMASK */
                if (ptree_matchkey(pt, key, ptn, bitoff, UINT_MAX))
                        return NODETOITEM(pt, ptn);
        }

#ifndef PTNOMASK
        /*
         * By virtue of how the mask was placed in the tree,
         * all nodes descended from it will match it.  But the bits
         * before the mask still need to be checked and since the
         * mask was a branch, that was done implicitly.
         */
        if (mask != NULL) {
                KASSERT(ptree_matchkey(pt, key, mask, 0, PTN_MASK_BITLEN(mask)));
                return NODETOITEM(pt, mask);
        }
#endif /* !PTNOMASK */

        /*
         * Nothing matched.
         */
        return NULL;
}

void *
ptree_iterate(pt_tree_t *pt, const void *item, pt_direction_t direction)
{
        const pt_node_t * const target = ITEMTONODE(pt, item);
        uintptr_t node, next_node;

        if (direction != PT_ASCENDING && direction != PT_DESCENDING)
                return NULL;

        node = PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode);
        if (PT_NULL_P(node))
                return NULL;

        if (item == NULL) {
                pt_node_t * const ptn = PT_NODE(node);
                if (direction == PT_ASCENDING
                    && PTN_ISMASK_P(ptn) && PTN_BRANCH_BITLEN(ptn) == 0)
                        return NODETOITEM(pt, ptn);
                next_node = node;
        } else {
#ifndef PTNOMASK
                uintptr_t mask_node = PT_NULL;
#endif /* !PTNOMASK */
                next_node = PT_NULL;
                while (!PT_LEAF_P(node)) { 
                        pt_node_t * const ptn = PT_NODE(node);
                        pt_slot_t slot;
#ifndef PTNOMASK
                        if (PTN_ISMASK_P(ptn) && PTN_BRANCH_BITLEN(ptn) == 0) {
                                if (ptn == target)
                                        break;
                                if (direction == PT_DESCENDING) {
                                        mask_node = node;
                                        next_node = PT_NULL;
                                }
                        }
#endif /* !PTNOMASK */
                        slot = ptree_testnode(pt, target, ptn);
                        node = PTN_BRANCH_SLOT(ptn, slot);
                        if (direction == PT_ASCENDING) {
                                if (slot != (pt_slot_t)((1 << PTN_BRANCH_BITLEN(ptn)) - 1))
                                        next_node = PTN_BRANCH_SLOT(ptn, slot + 1);
                        } else {
                                if (slot > 0) {
#ifndef PTNOMASK
                                        mask_node = PT_NULL;
#endif /* !PTNOMASK */
                                        next_node = PTN_BRANCH_SLOT(ptn, slot - 1);
                                }
                        }
                }
                if (PT_NODE(node) != target)
                        return NULL;
#ifndef PTNOMASK
                if (PT_BRANCH_P(node)) {
                        pt_node_t *ptn = PT_NODE(node);
                        KASSERT(PTN_ISMASK_P(PT_NODE(node)) && PTN_BRANCH_BITLEN(PT_NODE(node)) == 0);
                        if (direction == PT_ASCENDING) {
                                next_node = PTN_BRANCH_ROOT_SLOT(ptn);
                                ptn = PT_NODE(next_node);
                        }
                }
                /*
                 * When descending, if we countered a mask node then that's
                 * we want to return.
                 */
                if (direction == PT_DESCENDING && !PT_NULL_P(mask_node)) {
                        KASSERT(PT_NULL_P(next_node));
                        return NODETOITEM(pt, PT_NODE(mask_node));
                }
#endif /* !PTNOMASK */
        }

        node = next_node;
        if (PT_NULL_P(node))
                return NULL;

        while (!PT_LEAF_P(node)) {
                pt_node_t * const ptn = PT_NODE(node);
                pt_slot_t slot;
                if (direction == PT_ASCENDING) {
#ifndef PTNOMASK
                        if (PT_BRANCH_P(node)
                            && PTN_ISMASK_P(ptn)
                            && PTN_BRANCH_BITLEN(ptn) == 0)
                                return NODETOITEM(pt, ptn);
#endif /* !PTNOMASK */
                        slot = PT_SLOT_LEFT;
                } else {
                        slot = (1 << PTN_BRANCH_BITLEN(ptn)) - 1;
                }
                node = PTN_BRANCH_SLOT(ptn, slot);
        }
        return NODETOITEM(pt, PT_NODE(node));
}

void
ptree_remove_node(pt_tree_t *pt, void *item)
{
        pt_node_t * const target = ITEMTONODE(pt, item);
        const pt_slot_t leaf_slot = PTN_LEAF_POSITION(target);
        const pt_slot_t branch_slot = PTN_BRANCH_POSITION(target);
        pt_node_t *ptn, *parent;
        uintptr_t node;
        uintptr_t *removep;
        uintptr_t *nodep;
        pt_bitoff_t bitoff;
        pt_slot_t parent_slot;
#ifndef PTNOMASK
        bool at_mask;
#endif

        if (PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode))) {
                KASSERT(!PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode)));
                return;
        }

        bitoff = 0;
        removep = NULL;
        nodep = NULL;
        parent = &pt->pt_rootnode;
        parent_slot = PT_SLOT_ROOT;
        for (;;) {
                node = PTN_BRANCH_SLOT(parent, parent_slot);
                ptn = PT_NODE(node);
#ifndef PTNOMASK
                at_mask = PTN_ISMASK_P(ptn);
#endif

                if (PT_LEAF_P(node))
                        break;

                /*
                 * If we are at the target, then we are looking at its branch
                 * identity.  We need to remember who's pointing at it so we
                 * stop them from doing that.
                 */
                if (__predict_false(ptn == target)) {
                        KASSERT(nodep == NULL);
#ifndef PTNOMASK
                        /*
                         * Interior mask nodes are trivial to get rid of.
                         */
                        if (at_mask && PTN_BRANCH_BITLEN(ptn) == 0) {
                                PTN_BRANCH_SLOT(parent, parent_slot) =
                                    PTN_BRANCH_ROOT_SLOT(ptn);
                                KASSERT(PT_NULL_P(PTN_BRANCH_ODDMAN_SLOT(ptn)));
                                PTREE_CHECK(pt);
                                return;
                        }
#endif /* !PTNOMASK */
                        nodep = &PTN_BRANCH_SLOT(parent, parent_slot);
                        KASSERT(*nodep == PTN_BRANCH(target));
                }
                /*
                 * We need also need to know who's pointing at our parent.
                 * After we remove ourselves from our parent, he'll only
                 * have one child and that's unacceptable.  So we replace
                 * the pointer to the parent with our abadoned sibling.
                 */
                removep = &PTN_BRANCH_SLOT(parent, parent_slot);

                /*
                 * Descend into the tree.
                 */
                parent = ptn;
                parent_slot = ptree_testnode(pt, target, parent);
                bitoff += PTN_BRANCH_BITLEN(parent);
        }

        /*
         * We better have found that the leaf we are looking for is target.
         */
        if (target != ptn) {
                KASSERT(target == ptn);
                return;
        }

        /*
         * If we didn't encounter target as branch, then target must be the
         * oddman-out.
         */
        if (nodep == NULL) {
                KASSERT(PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) == PTN_LEAF(target));
                KASSERT(nodep == NULL);
                nodep = &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode);
        }

        KASSERT((removep == NULL) == (parent == &pt->pt_rootnode));

        /*
         * We have to special remove the last leaf from the root since
         * the only time the tree can a PT_NULL node is when it's empty.
         */
        if (__predict_false(PTN_ISROOT_P(pt, parent))) {
                KASSERT(removep == NULL);
                KASSERT(parent == &pt->pt_rootnode);
                KASSERT(nodep == &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode));
                KASSERT(*nodep == PTN_LEAF(target));
                PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode) = PT_NULL;
                PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PT_NULL;
                return;
        }

        KASSERT((parent == target) == (removep == nodep));
        if (PTN_BRANCH(parent) == PTN_BRANCH_SLOT(target, PTN_BRANCH_POSITION(parent))) {
                /*
                 * The pointer to the parent actually lives in the target's
                 * branch identity.  We can't just move the target's branch
                 * identity since that would result in the parent pointing
                 * to its own branch identity and that's fobidden.
                 */
                const pt_slot_t slot = PTN_BRANCH_POSITION(parent);
                const pt_slot_t other_slot = slot ^ PT_SLOT_OTHER;
                const pt_bitlen_t parent_bitlen = PTN_BRANCH_BITLEN(parent);

                KASSERT(PTN_BRANCH_BITOFF(target) < PTN_BRANCH_BITOFF(parent));

                /*
                 * This gets so confusing.  The target's branch identity
                 * points to the branch identity of the parent of the target's
                 * leaf identity:
                 *
                 *      TB = { X, PB = { TL, Y } }
                 *   or TB = { X, PB = { TL } }
                 *
                 * So we can't move the target's branch identity to the parent
                 * because that would corrupt the tree.
                 */
                if (__predict_true(parent_bitlen > 0)) {
                        /*
                         * The parent is a two-way branch.  We have to have
                         * do to this chang in two steps to keep internally
                         * consistent.  First step is to copy our sibling from
                         * our parent to where we are pointing to parent's
                         * branch identiy.  This remove all references to his
                         * branch identity from the tree.  We then simply make
                         * the parent assume the target's branching duties.
                         *
                         *   TB = { X, PB = { Y, TL } } --> PB = { X, Y }.
                         *   TB = { X, PB = { TL, Y } } --> PB = { X, Y }.
                         *   TB = { PB = { Y, TL }, X } --> PB = { Y, X }.
                         *   TB = { PB = { TL, Y }, X } --> PB = { Y, X }.
                         */
                        PTN_BRANCH_SLOT(target, slot) =
                            PTN_BRANCH_SLOT(parent, parent_slot ^ PT_SLOT_OTHER);
                        *nodep = ptree_move_branch(pt, parent, target);
                        PTREE_CHECK(pt);
                        return;
                } else {
                        /*
                         * If parent was a one-way branch, it must have been
                         * mask which pointed to a single leaf which we are
                         * removing.  This means we have to convert the
                         * parent back to a leaf node.  So in the same
                         * position that target pointed to parent, we place
                         * leaf pointer to parent.  In the other position,
                         * we just put the other node from target.
                         *
                         *   TB = { X, PB = { TL } } --> PB = { X, PL }
                         */
                        KASSERT(PTN_ISMASK_P(parent));
                        KASSERT(slot == ptree_testnode(pt, parent, target));
                        PTN_BRANCH_SLOT(parent, slot) = PTN_LEAF(parent);
                        PTN_BRANCH_SLOT(parent, other_slot) =
                           PTN_BRANCH_SLOT(target, other_slot);
                        PTN_SET_LEAF_POSITION(parent,slot);
                        PTN_SET_BRANCH_BITLEN(parent, 1);
                }
                PTN_SET_BRANCH_BITOFF(parent, PTN_BRANCH_BITOFF(target));
                PTN_SET_BRANCH_POSITION(parent, PTN_BRANCH_POSITION(target));

                *nodep = PTN_BRANCH(parent);
                PTREE_CHECK(pt);
                return;
        }

#ifndef PTNOMASK
        if (__predict_false(PTN_BRANCH_BITLEN(parent) == 0)) {
                /*
                 * Parent was a one-way branch which is changing back to a leaf.
                 * Since parent is no longer a one-way branch, it can take over
                 * target's branching duties.
                 *
                 *  GB = { PB = { TL } }        --> GB = { PL }
                 *  TB = { X, Y }               --> PB = { X, Y }
                 */
                KASSERT(PTN_ISMASK_P(parent));
                KASSERT(parent != target);
                *removep = PTN_LEAF(parent);
        } else
#endif /* !PTNOMASK */
        {
                /*
                 * Now we are the normal removal case.  Since after the
                 * target's leaf identity is removed from the its parent,
                 * that parent will only have one decendent.  So we can
                 * just as easily replace the node that has the parent's
                 * branch identity with the surviving node.  This freeing
                 * parent from its branching duties which means it can
                 * take over target's branching duties.
                 *
                 *  GB = { PB = { X, TL } }     --> GB = { X }
                 *  TB = { V, W }               --> PB = { V, W }
                 */
                const pt_slot_t other_slot = parent_slot ^ PT_SLOT_OTHER;
                uintptr_t other_node = PTN_BRANCH_SLOT(parent, other_slot);
                const pt_slot_t target_slot = (parent == target ? branch_slot : leaf_slot);

                *removep = other_node;
                
                ptree_set_position(other_node, target_slot);

                /*
                 * If target's branch identity contained its leaf identity, we
                 * have nothing left to do.  We've already moved 'X' so there
                 * is no longer anything in the target's branch identiy that 
                 * has to be preserved.
                 */
                if (parent == target) {
                        /*
                         *  GB = { TB = { X, TL } }     --> GB = { X }
                         *  TB = { X, TL }              --> don't care
                         */
                        PTREE_CHECK(pt);
                        return;
                }
        }

        /*
         * If target wasn't used as a branch, then it must have been the
         * oddman-out of the tree (the one node that doesn't have a branch
         * identity).  This makes parent the new oddman-out.
         */
        if (*nodep == PTN_LEAF(target)) {
                KASSERT(nodep == &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode));
                PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PTN_LEAF(parent);
                PTREE_CHECK(pt);
                return;
        }

        /*
         * Finally move the target's branching duties to the parent.
         */
        KASSERT(PTN_BRANCH_BITOFF(parent) > PTN_BRANCH_BITOFF(target));
        *nodep = ptree_move_branch(pt, parent, target);
        PTREE_CHECK(pt);
}

#ifdef PTCHECK
static const pt_node_t *
ptree_check_find_node2(const pt_tree_t *pt, const pt_node_t *parent,
        uintptr_t target)
{
        const pt_bitlen_t slots = 1 << PTN_BRANCH_BITLEN(parent);
        pt_slot_t slot;

        for (slot = 0; slot < slots; slot++) {
                const uintptr_t node = PTN_BRANCH_SLOT(parent, slot);
                if (PTN_BRANCH_SLOT(parent, slot) == node)
                        return parent;
        }
        for (slot = 0; slot < slots; slot++) {
                const uintptr_t node = PTN_BRANCH_SLOT(parent, slot);
                const pt_node_t *branch;
                if (!PT_BRANCH_P(node))
                        continue;
                branch = ptree_check_find_node2(pt, PT_NODE(node), target);
                if (branch != NULL)
                        return branch;
        }

        return NULL;
}

static bool
ptree_check_leaf(const pt_tree_t *pt, const pt_node_t *parent,
        const pt_node_t *ptn)
{
        const pt_bitoff_t leaf_position = PTN_LEAF_POSITION(ptn);
        const pt_bitlen_t bitlen = PTN_BRANCH_BITLEN(ptn);
        const pt_bitlen_t mask_len = PTN_MASK_BITLEN(ptn);
        const uintptr_t leaf_node = PTN_LEAF(ptn);
        const bool is_parent_root = (parent == &pt->pt_rootnode);
        const bool is_mask = PTN_ISMASK_P(ptn);
        bool ok = true;

        if (is_parent_root) {
                ok = ok && PTN_BRANCH_ODDMAN_SLOT(parent) == leaf_node;
                KASSERT(ok);
                return ok;
        }

        if (is_mask && PTN_ISMASK_P(parent) && PTN_BRANCH_BITLEN(parent) == 0) {
                ok = ok && PTN_MASK_BITLEN(parent) < mask_len;
                KASSERT(ok);
                ok = ok && PTN_BRANCH_BITOFF(parent) < mask_len;
                KASSERT(ok);
        }
        ok = ok && PTN_BRANCH_SLOT(parent, leaf_position) == leaf_node;
        KASSERT(ok);
        ok = ok && leaf_position == ptree_testnode(pt, ptn, parent);
        KASSERT(ok);
        if (PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) != leaf_node) {
                ok = ok && bitlen > 0;
                KASSERT(ok);
                ok = ok && ptn == ptree_check_find_node2(pt, ptn, PTN_LEAF(ptn));
                KASSERT(ok);
        }
        return ok;
}

static bool
ptree_check_branch(const pt_tree_t *pt, const pt_node_t *parent,
        const pt_node_t *ptn)
{
        const bool is_parent_root = (parent == &pt->pt_rootnode);
        const pt_slot_t branch_slot = PTN_BRANCH_POSITION(ptn);
        const pt_bitoff_t bitoff = PTN_BRANCH_BITOFF(ptn);
        const pt_bitoff_t bitlen = PTN_BRANCH_BITLEN(ptn);
        const pt_bitoff_t parent_bitoff = PTN_BRANCH_BITOFF(parent);
        const pt_bitoff_t parent_bitlen = PTN_BRANCH_BITLEN(parent);
        const bool is_parent_mask = PTN_ISMASK_P(parent) && parent_bitlen == 0;
        const bool is_mask = PTN_ISMASK_P(ptn) && bitlen == 0;
        const pt_bitoff_t parent_mask_len = PTN_MASK_BITLEN(parent);
        const pt_bitoff_t mask_len = PTN_MASK_BITLEN(ptn);
        const pt_bitlen_t slots = 1 << bitlen;
        pt_slot_t slot;
        bool ok = true;

        ok = ok && PTN_BRANCH_SLOT(parent, branch_slot) == PTN_BRANCH(ptn);
        KASSERT(ok);
        ok = ok && branch_slot == ptree_testnode(pt, ptn, parent);
        KASSERT(ok);

        if (is_mask) {
                ok = ok && bitoff == mask_len;
                KASSERT(ok);
                if (is_parent_mask) {
                        ok = ok && parent_mask_len < mask_len;
                        KASSERT(ok);
                        ok = ok && parent_bitoff < bitoff;
                        KASSERT(ok);
                }
        } else {
                if (is_parent_mask) {
                        ok = ok && parent_bitoff <= bitoff;
                } else if (!is_parent_root) {
                        ok = ok && parent_bitoff < bitoff;
                }
                KASSERT(ok);
        }

        for (slot = 0; slot < slots; slot++) {
                const uintptr_t node = PTN_BRANCH_SLOT(ptn, slot);
                pt_bitoff_t tmp_bitoff = 0;
                pt_slot_t tmp_slot;
                ok = ok && node != PTN_BRANCH(ptn);
                KASSERT(ok);
                if (bitlen > 0) {
                        ok = ok && ptree_matchnode(pt, PT_NODE(node), ptn, bitoff, &tmp_bitoff, &tmp_slot);
                        KASSERT(ok);
                        tmp_slot = ptree_testnode(pt, PT_NODE(node), ptn);
                        ok = ok && slot == tmp_slot;
                        KASSERT(ok);
                }
                if (PT_LEAF_P(node))
                        ok = ok && ptree_check_leaf(pt, ptn, PT_NODE(node));
                else
                        ok = ok && ptree_check_branch(pt, ptn, PT_NODE(node));
        }

        return ok;
}
#endif /* PTCHECK */

/*ARGSUSED*/
bool
ptree_check(const pt_tree_t *pt)
{
        bool ok = true;
#ifdef PTCHECK
        const pt_node_t * const parent = &pt->pt_rootnode;
        const uintptr_t node = pt->pt_root;
        const pt_node_t * const ptn = PT_NODE(node);

        ok = ok && PTN_BRANCH_BITOFF(parent) == 0;
        ok = ok && !PTN_ISMASK_P(parent);

        if (PT_NULL_P(node))
                return ok;

        if (PT_LEAF_P(node))
                ok = ok && ptree_check_leaf(pt, parent, ptn);
        else
                ok = ok && ptree_check_branch(pt, parent, ptn);
#endif
        return ok;
}