1 | /* $NetBSD: ptree.h,v 1.8 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 | #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 (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 | |
194 | #endif /* _SYS_PTREE_H_ */ |
195 | |