FreeBSD/Linux Kernel Cross Reference
sys/sys/ptree.h
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 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
194 #endif /* _SYS_PTREE_H_ */
Cache object: c70edfa0895567142d48292adff7e262
|