include/sys/ptree.h

   1 /* $NetBSD: ptree.h,v 1.3 2008/11/25 15:13:47 ad Exp $ */
   2 /*-
   3  * Copyright (c) 2008 The NetBSD Foundation, Inc.
   4  * All rights reserved.
   5  *
   6  * This code is derived from software contributed to The NetBSD Foundation
   7  * by Matt Thomas <matt@3am-software.com>
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  19  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  20  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  22  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGE.
  29  */
  30 #ifndef _SYS_PTREE_H_
  31 #define _SYS_PTREE_H_
  32
  33 #if !defined(_KERNEL) && !defined(_STANDALONE)
  34 #include <stdbool.h>
  35 #include <stdint.h>
  36 #endif
  37
  38 typedef enum {
  39         PT_DESCENDING=-1,
  40         PT_ASCENDING=1
  41 } pt_direction_t;
  42
  43 typedef unsigned int pt_slot_t;
  44 typedef unsigned int pt_bitoff_t;
  45 typedef unsigned int pt_bitlen_t;
  46
  47 typedef struct pt_node {
  48         uintptr_t ptn_slots[2];         /* must be first */
  49 #define PT_SLOT_LEFT                    0
  50 #define PT_SLOT_RIGHT                   1
  51 #ifdef _PT_PRIVATE
  52 #define PT_SLOT_ROOT                    0
  53 #define PT_SLOT_OTHER                   1
  54 #define PT_SLOT_ODDMAN                  1
  55 #define PT_TYPE_LEAF                    0x00000000
  56 #define PT_TYPE_BRANCH                  0x00000001
  57 #define PT_TYPE_MASK                    0x00000001
  58 #endif /* _PT_PRIVATE */
  59
  60         uint32_t ptn_nodedata;
  61 #ifdef _PT_PRIVATE
  62 #define PTN_LEAF_POSITION_BITS          8
  63 #define PTN_LEAF_POSITION_SHIFT         0
  64 #define PTN_BRANCH_POSITION_BITS        8
  65 #define PTN_BRANCH_POSITION_SHIFT       8
  66 #ifndef PTNOMASK
  67 #define PTN_MASK_BITLEN_BITS            15
  68 #define PTN_MASK_BITLEN_SHIFT           16
  69 #define PTN_MASK_FLAG                   0x80000000
  70 #endif
  71 #endif /* _PT_PRIVATE */
  72
  73         uint32_t ptn_branchdata;
  74 #ifdef _PT_PRIVATE
  75 #define PTN_BRANCH_BITOFF_BITS          15
  76 #define PTN_BRANCH_BITOFF_SHIFT         0
  77 #define PTN_BRANCH_BITLEN_BITS          8
  78 #define PTN_BRANCH_BITLEN_SHIFT         16
  79 #if 0
  80 #define PTN_ORIENTATION_BITS            1
  81 #define PTN_ORIENTATION_SHIFT           30
  82 #endif
  83 #define PTN_BRANCH_UNUSED               0x3f000000
  84 #define PTN_XBRANCH_FLAG                0x80000000
  85 #endif /* _PT_PRIVATE */
  86 } pt_node_t;
  87
  88 #ifdef _PT_PRIVATE
  89 #define PT_NODE(node)           ((pt_node_t *)(node & ~PT_TYPE_MASK))
  90 #define PT_TYPE(node)           ((node) & PT_TYPE_MASK)
  91 #define PT_NULL                 0
  92 #define PT_NULL_P(node)         ((node) == PT_NULL)
  93 #define PT_LEAF_P(node)         (PT_TYPE(node) == PT_TYPE_LEAF)
  94 #define PT_BRANCH_P(node)       (PT_TYPE(node) == PT_TYPE_BRANCH)
  95 #define PTN__TYPELESS(ptn)      (((uintptr_t)ptn) & ~PT_TYPE_MASK)
  96 #define PTN_LEAF(ptn)           (PTN__TYPELESS(ptn) | PT_TYPE_LEAF)
  97 #define PTN_BRANCH(ptn)         (PTN__TYPELESS(ptn) | PT_TYPE_BRANCH)
  98
  99 #ifndef PTNOMASK
 100 #define PTN_MARK_MASK(ptn)      ((ptn)->ptn_nodedata |= PTN_MASK_FLAG)
 101 #define PTN_ISMASK_P(ptn)       (((ptn)->ptn_nodedata & PTN_MASK_FLAG) != 0)
 102 #endif
 103 #define PTN_MARK_XBRANCH(ptn)   ((ptn)->ptn_branchdata |= PTN_XBRANCH_FLAG)
 104 #define PTN_ISXBRANCH_P(ptn)    (((ptn)->ptn_branchdata & PTN_XBRANCH_FLAG) != 0)
 105 #define PTN_ISROOT_P(pt, ptn)   ((ptn) == &(pt)->pt_rootnode)
 106
 107 #define PTN_BRANCH_SLOT(ptn,slot)       ((ptn)->ptn_slots[slot])
 108 #define PTN_BRANCH_ROOT_SLOT(ptn)       ((ptn)->ptn_slots[PT_SLOT_ROOT])
 109 #define PTN_BRANCH_ODDMAN_SLOT(ptn)     ((ptn)->ptn_slots[PT_SLOT_ODDMAN])
 110 #define PTN_COPY_BRANCH_SLOTS(dst,src)  \
 111         ((dst)->ptn_slots[PT_SLOT_LEFT ] = (src)->ptn_slots[PT_SLOT_LEFT ], \
 112          (dst)->ptn_slots[PT_SLOT_RIGHT] = (src)->ptn_slots[PT_SLOT_RIGHT])
 113 #define PTN_ISSLOTVALID_P(ptn,slot)     ((slot) < (1 << PTN_BRANCH_BITLEN(pt)))
 114
 115 #define PT__MASK(n)             ((1 << n ## _BITS) - 1)
 116 #define PT__SHIFT(n)            (n ## _SHIFT)
 117 #define PTN__EXTRACT(field, b) \
 118         (((field) >> PT__SHIFT(b)) & PT__MASK(b))
 119 #define PTN__INSERT2(field, v, shift, mask) \
 120         ((field) = ((field) & ~((mask) << (shift))) | ((v) << (shift)))
 121 #define PTN__INSERT(field, b, v) \
 122         PTN__INSERT2(field, v, PT__SHIFT(b), PT__MASK(b))
 123
 124 #define PTN_BRANCH_BITOFF(ptn)          \
 125         PTN__EXTRACT((ptn)->ptn_branchdata, PTN_BRANCH_BITOFF)
 126 #define PTN_BRANCH_BITLEN(ptn)          \
 127         PTN__EXTRACT((ptn)->ptn_branchdata, PTN_BRANCH_BITLEN)
 128 #define PTN_SET_BRANCH_BITOFF(ptn,bitoff) \
 129         PTN__INSERT((ptn)->ptn_branchdata, PTN_BRANCH_BITOFF, bitoff)
 130 #define PTN_SET_BRANCH_BITLEN(ptn,bitlen) \
 131         PTN__INSERT((ptn)->ptn_branchdata, PTN_BRANCH_BITLEN, bitlen)
 132
 133 #define PTN_LEAF_POSITION(ptn)          \
 134         PTN__EXTRACT((ptn)->ptn_nodedata, PTN_LEAF_POSITION)
 135 #define PTN_BRANCH_POSITION(ptn)        \
 136         PTN__EXTRACT((ptn)->ptn_nodedata, PTN_BRANCH_POSITION)
 137 #define PTN_SET_LEAF_POSITION(ptn,slot) \
 138         PTN__INSERT((ptn)->ptn_nodedata, PTN_LEAF_POSITION, slot)
 139 #define PTN_SET_BRANCH_POSITION(ptn,slot) \
 140         PTN__INSERT((ptn)->ptn_nodedata, PTN_BRANCH_POSITION, slot)
 141
 142 #ifndef PTNOMASK
 143 #define PTN_MASK_BITLEN(ptn)            \
 144         PTN__EXTRACT((ptn)->ptn_nodedata, PTN_MASK_BITLEN)
 145 #define PTN_SET_MASK_BITLEN(ptn,masklen) \
 146         PTN__INSERT((ptn)->ptn_nodedata, PTN_MASK_BITLEN, masklen)
 147 #endif
 148
 149 #if 0
 150 #define PTN_ORIENTATION(ptn)    \
 151         PTN__EXTRACT((ptn)->ptn_branchdata, PTN_ORIENTATION)
 152 #define PTN_SET_ORIENTATION(ptn,slot) \
 153         PTN__INSERT((ptn)->ptn_branchdata, PTN_ORIENTATION, slot)
 154 #endif
 155 #endif /* _PT_PRIVATE */
 156
 157 typedef struct pt_tree_ops {
 158         bool (*ptto_matchnode)(const void *, const void *, pt_bitoff_t,
 159                 pt_bitoff_t *, pt_slot_t *);
 160         bool (*ptto_matchkey)(const void *, const void *, pt_bitoff_t,
 161                 pt_bitlen_t);
 162         pt_slot_t (*ptto_testnode)(const void *, pt_bitoff_t, pt_bitlen_t);
 163         pt_slot_t (*ptto_testkey)(const void *, pt_bitoff_t, pt_bitlen_t);
 164 } pt_tree_ops_t;
 165
 166 typedef struct pt_tree {
 167         pt_node_t pt_rootnode;
 168 #define pt_root                 pt_rootnode.ptn_slots[PT_SLOT_ROOT]
 169 #define pt_oddman               pt_rootnode.ptn_slots[PT_SLOT_ODDMAN]
 170         const pt_tree_ops_t *pt_ops;
 171         size_t pt_node_offset;
 172         size_t pt_key_offset;
 173         uintptr_t pt_spare[4];
 174 } pt_tree_t;
 175
 176 #define PT_FILTER_MASK          0x00000001      /* node is a mask */
 177 typedef bool (*pt_filter_t)(void *, const void *, int);
 178
 179 void    ptree_init(pt_tree_t *, const pt_tree_ops_t *, size_t, size_t);
 180 bool    ptree_insert_node(pt_tree_t *, void *);
 181 bool    ptree_insert_mask_node(pt_tree_t *, void *, pt_bitlen_t);
 182 void *  ptree_find_filtered_node(pt_tree_t *, void *, pt_filter_t, void *);
 183 #define ptree_find_node(pt,key) \
 184         ptree_find_filtered_node((pt), (key), NULL, NULL)
 185 void    ptree_remove_node(pt_tree_t *, void *);
 186 void *  ptree_iterate(pt_tree_t *, const void *, pt_direction_t);
 187
 188 #endif /* _SYS_PTREE_H_ */