1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#ifndef _AVL_IMPL_H
#define _AVL_IMPL_H extern __attribute__((visibility("default")))
/*
* This is a private header file. Applications should not directly include
* this file.
*/
#include <sys/types.h>
#ifdef __cplusplus
extern "C" {
#endif
/*
* generic AVL tree implementation for kernel use
*
* There are 5 pieces of information stored for each node in an AVL tree
*
* pointer to less than child
* pointer to greater than child
* a pointer to the parent of this node
* an indication [0/1] of which child I am of my parent
* a "balance" (-1, 0, +1) indicating which child tree is taller
*
* Since they only need 3 bits, the last two fields are packed into the
* bottom bits of the parent pointer on 64 bit machines to save on space.
*/
#ifndef _LP64
struct avl_node {
struct avl_node *avl_child[2]; /* left/right children */
struct avl_node *avl_parent; /* this node's parent */
unsigned short avl_child_index; /* my index in parent's avl_child[] */
short avl_balance; /* balance value: -1, 0, +1 */
};
#define AVL_XPARENT(n) ((n)->avl_parent)
#define AVL_SETPARENT(n, p) ((n)->avl_parent = (p))
#define AVL_XCHILD(n) ((n)->avl_child_index)
#define AVL_SETCHILD(n, c) ((n)->avl_child_index = (unsigned short)(c))
#define AVL_XBALANCE(n) ((n)->avl_balance)
#define AVL_SETBALANCE(n, b) ((n)->avl_balance = (short)(b))
#else /* _LP64 */
/*
* for 64 bit machines, avl_pcb contains parent pointer, balance and child_index
* values packed in the following manner:
*
* |63 3| 2 |1 0 |
* |-------------------------------------|-----------------|-------------|
* | avl_parent hi order bits | avl_child_index | avl_balance |
* | | | + 1 |
* |-------------------------------------|-----------------|-------------|
*
*/
struct avl_node {
struct avl_node *avl_child[2]; /* left/right children nodes */
uintptr_t avl_pcb; /* parent, child_index, balance */
};
/*
* macros to extract/set fields in avl_pcb
*
* pointer to the parent of the current node is the high order bits
*/
#define AVL_XPARENT(n) ((struct avl_node *)((n)->avl_pcb & ~7))
#define AVL_SETPARENT(n, p) \
((n)->avl_pcb = (((n)->avl_pcb & 7) | (uintptr_t)(p)))
/*
* index of this node in its parent's avl_child[]: bit #2
*/
#define AVL_XCHILD(n) (((n)->avl_pcb >> 2) & 1)
#define AVL_SETCHILD(n, c) \
((n)->avl_pcb = (uintptr_t)(((n)->avl_pcb & ~4) | ((c) << 2)))
/*
* balance indication for a node, lowest 2 bits. A valid balance is
* -1, 0, or +1, and is encoded by adding 1 to the value to get the
* unsigned values of 0, 1, 2.
*/
#define AVL_XBALANCE(n) ((int)(((n)->avl_pcb & 3) - 1))
#define AVL_SETBALANCE(n, b) \
((n)->avl_pcb = (uintptr_t)((((n)->avl_pcb & ~3) | ((b) + 1))))
#endif /* _LP64 */
/*
* switch between a node and data pointer for a given tree
* the value of "o" is tree->avl_offset
*/
#define AVL_NODE2DATA(n, o) ((void *)((uintptr_t)(n) - (o)))
#define AVL_DATA2NODE(d, o) ((struct avl_node *)((uintptr_t)(d) + (o)))
/*
* macros used to create/access an avl_index_t
*/
#define AVL_INDEX2NODE(x) ((avl_node_t *)((x) & ~1))
#define AVL_INDEX2CHILD(x) ((x) & 1)
#define AVL_MKINDEX(n, c) ((avl_index_t)(n) | (c))
/*
* The tree structure. The fields avl_root, avl_compar, and avl_offset come
* first since they are needed for avl_find(). We want them to fit into
* a single 64 byte cache line to make avl_find() as fast as possible.
*/
struct avl_tree {
struct avl_node *avl_root; /* root node in tree */
int (*avl_compar)(const void *, const void *);
size_t avl_offset; /* offsetof(type, avl_link_t field) */
ulong_t avl_numnodes; /* number of nodes in the tree */
#ifndef _KERNEL
size_t avl_pad; /* For backwards ABI compatibility. */
#endif
};
/*
* This will only by used via AVL_NEXT() or AVL_PREV()
*/
_AVL_IMPL_H void *avl_walk(struct avl_tree *, void *, int);
#ifdef __cplusplus
}
#endif
#endif /* _AVL_IMPL_H */
|
