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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
#ifndef _EYTZINGER_H
#define _EYTZINGER_H
#include <linux/bitops.h>
#include <linux/log2.h>
#include "util.h"
/*
* Traversal for trees in eytzinger layout - a full binary tree layed out in an
* array
*
* We used one based indexing, not zero based: with one based indexing, each
* level of the tree starts at a power of two - leading to better alignment -
* and it's what you want for implementing next/prev and to/from inorder.
*
* To/from inorder also uses 1 based indexing.
*
* Size parameter is treated as if we were using 0 based indexing, however:
* valid nodes, and inorder indices, are in the range [1..size)
*/
static inline unsigned eytzinger_child(unsigned j, unsigned child)
{
EBUG_ON(child > 1);
return (j << 1) + child;
}
static inline unsigned eytzinger_left_child(unsigned j)
{
return eytzinger_child(j, 0);
}
static inline unsigned eytzinger_right_child(unsigned j)
{
return eytzinger_child(j, 1);
}
static inline unsigned eytzinger_first(unsigned size)
{
return rounddown_pow_of_two(size - 1);
}
static inline unsigned eytzinger_last(unsigned size)
{
return rounddown_pow_of_two(size) - 1;
}
/*
* eytzinger_next() and eytzinger_prev() have the nice properties that
*
* eytzinger_next(0) == eytzinger_first())
* eytzinger_prev(0) == eytzinger_last())
*
* eytzinger_prev(eytzinger_first()) == 0
* eytzinger_next(eytzinger_last()) == 0
*/
static inline unsigned eytzinger_next(unsigned j, unsigned size)
{
EBUG_ON(j >= size);
if (eytzinger_right_child(j) < size) {
j = eytzinger_right_child(j);
j <<= __fls(size) - __fls(j);
j >>= j >= size;
} else {
j >>= ffz(j) + 1;
}
return j;
}
static inline unsigned eytzinger_prev(unsigned j, unsigned size)
{
EBUG_ON(j >= size);
if (eytzinger_left_child(j) < size) {
j = eytzinger_left_child(j);
j <<= __fls(size) - __fls(j);
j -= 1;
j >>= j >= size;
} else {
j >>= __ffs(j) + 1;
}
return j;
}
static inline unsigned eytzinger_extra(unsigned size)
{
return (size - rounddown_pow_of_two(size - 1)) << 1;
}
static inline unsigned __eytzinger_to_inorder(unsigned j, unsigned size,
unsigned extra)
{
unsigned b = __fls(j);
unsigned shift = __fls(size - 1) - b;
int s;
EBUG_ON(!j || j >= size);
j ^= 1U << b;
j <<= 1;
j |= 1;
j <<= shift;
/*
* sign bit trick:
*
* if (j > extra)
* j -= (j - extra) >> 1;
*/
s = extra - j;
j += (s >> 1) & (s >> 31);
return j;
}
static inline unsigned __inorder_to_eytzinger(unsigned j, unsigned size,
unsigned extra)
{
unsigned shift;
int s;
EBUG_ON(!j || j >= size);
/*
* sign bit trick:
*
* if (j > extra)
* j += j - extra;
*/
s = extra - j;
j -= s & (s >> 31);
shift = __ffs(j);
j >>= shift + 1;
j |= 1U << (__fls(size - 1) - shift);
return j;
}
static inline unsigned eytzinger_to_inorder(unsigned j, unsigned size)
{
return __eytzinger_to_inorder(j, size, eytzinger_extra(size));
}
static inline unsigned inorder_to_eytzinger(unsigned j, unsigned size)
{
return __inorder_to_eytzinger(j, size, eytzinger_extra(size));
}
#define eytzinger_for_each(_i, _size) \
for ((_i) = eytzinger_first((_size)); \
(_i) != 0; \
(_i) = eytzinger_next((_i), (_size)))
#if 0
void eytzinger_test(void)
{
unsigned i, j, size;
for (size = 2;
size < 65536000;
size++) {
if (!(size % 4096))
printk(KERN_INFO "tree size %u\n", size);
assert(eytzinger_prev(0, size) == eytzinger_last(size));
assert(eytzinger_next(0, size) == eytzinger_first(size));
assert(eytzinger_prev(eytzinger_first(size), size) == 0);
assert(eytzinger_next(eytzinger_last(size), size) == 0);
eytzinger_for_each(j, size) {
assert(from_inorder(i, size) == j);
assert(to_inorder(j, size) == i);
if (j != eytzinger_last(size)) {
unsigned next = eytzinger_next(j, size);
assert(eytzinger_prev(next, size) == j);
}
}
}
}
#endif
#endif /* _EYTZINGER_H */
|
