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