aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 03:23:15 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 03:23:15 -0400
commit9e2d8656f5e8aa214e66b462680cf86b210b74a8 (patch)
treef67d62e896cedf75599ea45f9ecf9999c6ad24cd /lib
parent1ea4f4f8405cc1ceec23f2d261bc3775785e6712 (diff)
parent9e695d2ecc8451cc2c1603d60b5c8e7f5581923a (diff)
Merge branch 'akpm' (Andrew's patch-bomb)
Merge patches from Andrew Morton: "A few misc things and very nearly all of the MM tree. A tremendous amount of stuff (again), including a significant rbtree library rework." * emailed patches from Andrew Morton <akpm@linux-foundation.org>: (160 commits) sparc64: Support transparent huge pages. mm: thp: Use more portable PMD clearing sequenece in zap_huge_pmd(). mm: Add and use update_mmu_cache_pmd() in transparent huge page code. sparc64: Document PGD and PMD layout. sparc64: Eliminate PTE table memory wastage. sparc64: Halve the size of PTE tables sparc64: Only support 4MB huge pages and 8KB base pages. memory-hotplug: suppress "Trying to free nonexistent resource <XXXXXXXXXXXXXXXX-YYYYYYYYYYYYYYYY>" warning mm: memcg: clean up mm_match_cgroup() signature mm: document PageHuge somewhat mm: use %pK for /proc/vmallocinfo mm, thp: fix mlock statistics mm, thp: fix mapped pages avoiding unevictable list on mlock memory-hotplug: update memory block's state and notify userspace memory-hotplug: preparation to notify memory block's state at memory hot remove mm: avoid section mismatch warning for memblock_type_name make GFP_NOTRACK definition unconditional cma: decrease cc.nr_migratepages after reclaiming pagelist CMA: migrate mlocked pages kpageflags: fix wrong KPF_THP on non-huge compound pages ...
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig.debug38
-rw-r--r--lib/Makefile7
-rw-r--r--lib/interval_tree.c10
-rw-r--r--lib/interval_tree_test_main.c105
-rw-r--r--lib/prio_tree.c466
-rw-r--r--lib/rbtree.c656
-rw-r--r--lib/rbtree_test.c234
7 files changed, 735 insertions, 781 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 7fba3a98967f..28e9d6c98941 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -450,12 +450,12 @@ config SLUB_STATS
450 out which slabs are relevant to a particular load. 450 out which slabs are relevant to a particular load.
451 Try running: slabinfo -DA 451 Try running: slabinfo -DA
452 452
453config HAVE_DEBUG_KMEMLEAK
454 bool
455
453config DEBUG_KMEMLEAK 456config DEBUG_KMEMLEAK
454 bool "Kernel memory leak detector" 457 bool "Kernel memory leak detector"
455 depends on DEBUG_KERNEL && EXPERIMENTAL && \ 458 depends on DEBUG_KERNEL && EXPERIMENTAL && HAVE_DEBUG_KMEMLEAK
456 (X86 || ARM || PPC || MIPS || S390 || SPARC64 || SUPERH || \
457 MICROBLAZE || TILE || ARM64)
458
459 select DEBUG_FS 459 select DEBUG_FS
460 select STACKTRACE if STACKTRACE_SUPPORT 460 select STACKTRACE if STACKTRACE_SUPPORT
461 select KALLSYMS 461 select KALLSYMS
@@ -751,12 +751,12 @@ config DEBUG_HIGHMEM
751 This options enables addition error checking for high memory systems. 751 This options enables addition error checking for high memory systems.
752 Disable for production systems. 752 Disable for production systems.
753 753
754config HAVE_DEBUG_BUGVERBOSE
755 bool
756
754config DEBUG_BUGVERBOSE 757config DEBUG_BUGVERBOSE
755 bool "Verbose BUG() reporting (adds 70K)" if DEBUG_KERNEL && EXPERT 758 bool "Verbose BUG() reporting (adds 70K)" if DEBUG_KERNEL && EXPERT
756 depends on BUG 759 depends on BUG && (GENERIC_BUG || HAVE_DEBUG_BUGVERBOSE)
757 depends on ARM || AVR32 || M32R || M68K || SPARC32 || SPARC64 || \
758 FRV || SUPERH || GENERIC_BUG || BLACKFIN || MN10300 || \
759 TILE || ARM64
760 default y 760 default y
761 help 761 help
762 Say Y here to make BUG() panics output the file name and line number 762 Say Y here to make BUG() panics output the file name and line number
@@ -798,6 +798,15 @@ config DEBUG_VM
798 798
799 If unsure, say N. 799 If unsure, say N.
800 800
801config DEBUG_VM_RB
802 bool "Debug VM red-black trees"
803 depends on DEBUG_VM
804 help
805 Enable this to turn on more extended checks in the virtual-memory
806 system that may impact performance.
807
808 If unsure, say N.
809
801config DEBUG_VIRTUAL 810config DEBUG_VIRTUAL
802 bool "Debug VM translations" 811 bool "Debug VM translations"
803 depends on DEBUG_KERNEL && X86 812 depends on DEBUG_KERNEL && X86
@@ -1282,6 +1291,19 @@ config LATENCYTOP
1282source mm/Kconfig.debug 1291source mm/Kconfig.debug
1283source kernel/trace/Kconfig 1292source kernel/trace/Kconfig
1284 1293
1294config RBTREE_TEST
1295 tristate "Red-Black tree test"
1296 depends on m && DEBUG_KERNEL
1297 help
1298 A benchmark measuring the performance of the rbtree library.
1299 Also includes rbtree invariant checks.
1300
1301config INTERVAL_TREE_TEST
1302 tristate "Interval tree test"
1303 depends on m && DEBUG_KERNEL
1304 help
1305 A benchmark measuring the performance of the interval tree library
1306
1285config PROVIDE_OHCI1394_DMA_INIT 1307config PROVIDE_OHCI1394_DMA_INIT
1286 bool "Remote debugging over FireWire early on boot" 1308 bool "Remote debugging over FireWire early on boot"
1287 depends on PCI && X86 1309 depends on PCI && X86
diff --git a/lib/Makefile b/lib/Makefile
index 42d283edc4d3..3128e357e286 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -9,7 +9,7 @@ endif
9 9
10lib-y := ctype.o string.o vsprintf.o cmdline.o \ 10lib-y := ctype.o string.o vsprintf.o cmdline.o \
11 rbtree.o radix-tree.o dump_stack.o timerqueue.o\ 11 rbtree.o radix-tree.o dump_stack.o timerqueue.o\
12 idr.o int_sqrt.o extable.o prio_tree.o \ 12 idr.o int_sqrt.o extable.o \
13 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ 13 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
14 proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \ 14 proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \
15 is_single_threaded.o plist.o decompress.o 15 is_single_threaded.o plist.o decompress.o
@@ -140,6 +140,11 @@ $(foreach file, $(libfdt_files), \
140 $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt)) 140 $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt))
141lib-$(CONFIG_LIBFDT) += $(libfdt_files) 141lib-$(CONFIG_LIBFDT) += $(libfdt_files)
142 142
143obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o
144obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o
145
146interval_tree_test-objs := interval_tree_test_main.o interval_tree.o
147
143hostprogs-y := gen_crc32table 148hostprogs-y := gen_crc32table
144clean-files := crc32table.h 149clean-files := crc32table.h
145 150
diff --git a/lib/interval_tree.c b/lib/interval_tree.c
new file mode 100644
index 000000000000..e6eb406f2d65
--- /dev/null
+++ b/lib/interval_tree.c
@@ -0,0 +1,10 @@
1#include <linux/init.h>
2#include <linux/interval_tree.h>
3#include <linux/interval_tree_generic.h>
4
5#define START(node) ((node)->start)
6#define LAST(node) ((node)->last)
7
8INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
9 unsigned long, __subtree_last,
10 START, LAST,, interval_tree)
diff --git a/lib/interval_tree_test_main.c b/lib/interval_tree_test_main.c
new file mode 100644
index 000000000000..b25903987f7a
--- /dev/null
+++ b/lib/interval_tree_test_main.c
@@ -0,0 +1,105 @@
1#include <linux/module.h>
2#include <linux/interval_tree.h>
3#include <linux/random.h>
4#include <asm/timex.h>
5
6#define NODES 100
7#define PERF_LOOPS 100000
8#define SEARCHES 100
9#define SEARCH_LOOPS 10000
10
11static struct rb_root root = RB_ROOT;
12static struct interval_tree_node nodes[NODES];
13static u32 queries[SEARCHES];
14
15static struct rnd_state rnd;
16
17static inline unsigned long
18search(unsigned long query, struct rb_root *root)
19{
20 struct interval_tree_node *node;
21 unsigned long results = 0;
22
23 for (node = interval_tree_iter_first(root, query, query); node;
24 node = interval_tree_iter_next(node, query, query))
25 results++;
26 return results;
27}
28
29static void init(void)
30{
31 int i;
32 for (i = 0; i < NODES; i++) {
33 u32 a = prandom32(&rnd), b = prandom32(&rnd);
34 if (a <= b) {
35 nodes[i].start = a;
36 nodes[i].last = b;
37 } else {
38 nodes[i].start = b;
39 nodes[i].last = a;
40 }
41 }
42 for (i = 0; i < SEARCHES; i++)
43 queries[i] = prandom32(&rnd);
44}
45
46static int interval_tree_test_init(void)
47{
48 int i, j;
49 unsigned long results;
50 cycles_t time1, time2, time;
51
52 printk(KERN_ALERT "interval tree insert/remove");
53
54 prandom32_seed(&rnd, 3141592653589793238ULL);
55 init();
56
57 time1 = get_cycles();
58
59 for (i = 0; i < PERF_LOOPS; i++) {
60 for (j = 0; j < NODES; j++)
61 interval_tree_insert(nodes + j, &root);
62 for (j = 0; j < NODES; j++)
63 interval_tree_remove(nodes + j, &root);
64 }
65
66 time2 = get_cycles();
67 time = time2 - time1;
68
69 time = div_u64(time, PERF_LOOPS);
70 printk(" -> %llu cycles\n", (unsigned long long)time);
71
72 printk(KERN_ALERT "interval tree search");
73
74 for (j = 0; j < NODES; j++)
75 interval_tree_insert(nodes + j, &root);
76
77 time1 = get_cycles();
78
79 results = 0;
80 for (i = 0; i < SEARCH_LOOPS; i++)
81 for (j = 0; j < SEARCHES; j++)
82 results += search(queries[j], &root);
83
84 time2 = get_cycles();
85 time = time2 - time1;
86
87 time = div_u64(time, SEARCH_LOOPS);
88 results = div_u64(results, SEARCH_LOOPS);
89 printk(" -> %llu cycles (%lu results)\n",
90 (unsigned long long)time, results);
91
92 return -EAGAIN; /* Fail will directly unload the module */
93}
94
95static void interval_tree_test_exit(void)
96{
97 printk(KERN_ALERT "test exit\n");
98}
99
100module_init(interval_tree_test_init)
101module_exit(interval_tree_test_exit)
102
103MODULE_LICENSE("GPL");
104MODULE_AUTHOR("Michel Lespinasse");
105MODULE_DESCRIPTION("Interval Tree test");
diff --git a/lib/prio_tree.c b/lib/prio_tree.c
deleted file mode 100644
index 8d443af03b4c..000000000000
--- a/lib/prio_tree.c
+++ /dev/null
@@ -1,466 +0,0 @@
1/*
2 * lib/prio_tree.c - priority search tree
3 *
4 * Copyright (C) 2004, Rajesh Venkatasubramanian <vrajesh@umich.edu>
5 *
6 * This file is released under the GPL v2.
7 *
8 * Based on the radix priority search tree proposed by Edward M. McCreight
9 * SIAM Journal of Computing, vol. 14, no.2, pages 257-276, May 1985
10 *
11 * 02Feb2004 Initial version
12 */
13
14#include <linux/init.h>
15#include <linux/mm.h>
16#include <linux/prio_tree.h>
17
18/*
19 * A clever mix of heap and radix trees forms a radix priority search tree (PST)
20 * which is useful for storing intervals, e.g, we can consider a vma as a closed
21 * interval of file pages [offset_begin, offset_end], and store all vmas that
22 * map a file in a PST. Then, using the PST, we can answer a stabbing query,
23 * i.e., selecting a set of stored intervals (vmas) that overlap with (map) a
24 * given input interval X (a set of consecutive file pages), in "O(log n + m)"
25 * time where 'log n' is the height of the PST, and 'm' is the number of stored
26 * intervals (vmas) that overlap (map) with the input interval X (the set of
27 * consecutive file pages).
28 *
29 * In our implementation, we store closed intervals of the form [radix_index,
30 * heap_index]. We assume that always radix_index <= heap_index. McCreight's PST
31 * is designed for storing intervals with unique radix indices, i.e., each
32 * interval have different radix_index. However, this limitation can be easily
33 * overcome by using the size, i.e., heap_index - radix_index, as part of the
34 * index, so we index the tree using [(radix_index,size), heap_index].
35 *
36 * When the above-mentioned indexing scheme is used, theoretically, in a 32 bit
37 * machine, the maximum height of a PST can be 64. We can use a balanced version
38 * of the priority search tree to optimize the tree height, but the balanced
39 * tree proposed by McCreight is too complex and memory-hungry for our purpose.
40 */
41
42/*
43 * The following macros are used for implementing prio_tree for i_mmap
44 */
45
46#define RADIX_INDEX(vma) ((vma)->vm_pgoff)
47#define VMA_SIZE(vma) (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)
48/* avoid overflow */
49#define HEAP_INDEX(vma) ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))
50
51
52static void get_index(const struct prio_tree_root *root,
53 const struct prio_tree_node *node,
54 unsigned long *radix, unsigned long *heap)
55{
56 if (root->raw) {
57 struct vm_area_struct *vma = prio_tree_entry(
58 node, struct vm_area_struct, shared.prio_tree_node);
59
60 *radix = RADIX_INDEX(vma);
61 *heap = HEAP_INDEX(vma);
62 }
63 else {
64 *radix = node->start;
65 *heap = node->last;
66 }
67}
68
69static unsigned long index_bits_to_maxindex[BITS_PER_LONG];
70
71void __init prio_tree_init(void)
72{
73 unsigned int i;
74
75 for (i = 0; i < ARRAY_SIZE(index_bits_to_maxindex) - 1; i++)
76 index_bits_to_maxindex[i] = (1UL << (i + 1)) - 1;
77 index_bits_to_maxindex[ARRAY_SIZE(index_bits_to_maxindex) - 1] = ~0UL;
78}
79
80/*
81 * Maximum heap_index that can be stored in a PST with index_bits bits
82 */
83static inline unsigned long prio_tree_maxindex(unsigned int bits)
84{
85 return index_bits_to_maxindex[bits - 1];
86}
87
88static void prio_set_parent(struct prio_tree_node *parent,
89 struct prio_tree_node *child, bool left)
90{
91 if (left)
92 parent->left = child;
93 else
94 parent->right = child;
95
96 child->parent = parent;
97}
98
99/*
100 * Extend a priority search tree so that it can store a node with heap_index
101 * max_heap_index. In the worst case, this algorithm takes O((log n)^2).
102 * However, this function is used rarely and the common case performance is
103 * not bad.
104 */
105static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root,
106 struct prio_tree_node *node, unsigned long max_heap_index)
107{
108 struct prio_tree_node *prev;
109
110 if (max_heap_index > prio_tree_maxindex(root->index_bits))
111 root->index_bits++;
112
113 prev = node;
114 INIT_PRIO_TREE_NODE(node);
115
116 while (max_heap_index > prio_tree_maxindex(root->index_bits)) {
117 struct prio_tree_node *tmp = root->prio_tree_node;
118
119 root->index_bits++;
120
121 if (prio_tree_empty(root))
122 continue;
123
124 prio_tree_remove(root, root->prio_tree_node);
125 INIT_PRIO_TREE_NODE(tmp);
126
127 prio_set_parent(prev, tmp, true);
128 prev = tmp;
129 }
130
131 if (!prio_tree_empty(root))
132 prio_set_parent(prev, root->prio_tree_node, true);
133
134 root->prio_tree_node = node;
135 return node;
136}
137
138/*
139 * Replace a prio_tree_node with a new node and return the old node
140 */
141struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
142 struct prio_tree_node *old, struct prio_tree_node *node)
143{
144 INIT_PRIO_TREE_NODE(node);
145
146 if (prio_tree_root(old)) {
147 BUG_ON(root->prio_tree_node != old);
148 /*
149 * We can reduce root->index_bits here. However, it is complex
150 * and does not help much to improve performance (IMO).
151 */
152 root->prio_tree_node = node;
153 } else
154 prio_set_parent(old->parent, node, old->parent->left == old);
155
156 if (!prio_tree_left_empty(old))
157 prio_set_parent(node, old->left, true);
158
159 if (!prio_tree_right_empty(old))
160 prio_set_parent(node, old->right, false);
161
162 return old;
163}
164
165/*
166 * Insert a prio_tree_node @node into a radix priority search tree @root. The
167 * algorithm typically takes O(log n) time where 'log n' is the number of bits
168 * required to represent the maximum heap_index. In the worst case, the algo
169 * can take O((log n)^2) - check prio_tree_expand.
170 *
171 * If a prior node with same radix_index and heap_index is already found in
172 * the tree, then returns the address of the prior node. Otherwise, inserts
173 * @node into the tree and returns @node.
174 */
175struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
176 struct prio_tree_node *node)
177{
178 struct prio_tree_node *cur, *res = node;
179 unsigned long radix_index, heap_index;
180 unsigned long r_index, h_index, index, mask;
181 int size_flag = 0;
182
183 get_index(root, node, &radix_index, &heap_index);
184
185 if (prio_tree_empty(root) ||
186 heap_index > prio_tree_maxindex(root->index_bits))
187 return prio_tree_expand(root, node, heap_index);
188
189 cur = root->prio_tree_node;
190 mask = 1UL << (root->index_bits - 1);
191
192 while (mask) {
193 get_index(root, cur, &r_index, &h_index);
194
195 if (r_index == radix_index && h_index == heap_index)
196 return cur;
197
198 if (h_index < heap_index ||
199 (h_index == heap_index && r_index > radix_index)) {
200 struct prio_tree_node *tmp = node;
201 node = prio_tree_replace(root, cur, node);
202 cur = tmp;
203 /* swap indices */
204 index = r_index;
205 r_index = radix_index;
206 radix_index = index;
207 index = h_index;
208 h_index = heap_index;
209 heap_index = index;
210 }
211
212 if (size_flag)
213 index = heap_index - radix_index;
214 else
215 index = radix_index;
216
217 if (index & mask) {
218 if (prio_tree_right_empty(cur)) {
219 INIT_PRIO_TREE_NODE(node);
220 prio_set_parent(cur, node, false);
221 return res;
222 } else
223 cur = cur->right;
224 } else {
225 if (prio_tree_left_empty(cur)) {
226 INIT_PRIO_TREE_NODE(node);
227 prio_set_parent(cur, node, true);
228 return res;
229 } else
230 cur = cur->left;
231 }
232
233 mask >>= 1;
234
235 if (!mask) {
236 mask = 1UL << (BITS_PER_LONG - 1);
237 size_flag = 1;
238 }
239 }
240 /* Should not reach here */
241 BUG();
242 return NULL;
243}
244
245/*
246 * Remove a prio_tree_node @node from a radix priority search tree @root. The
247 * algorithm takes O(log n) time where 'log n' is the number of bits required
248 * to represent the maximum heap_index.
249 */
250void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
251{
252 struct prio_tree_node *cur;
253 unsigned long r_index, h_index_right, h_index_left;
254
255 cur = node;
256
257 while (!prio_tree_left_empty(cur) || !prio_tree_right_empty(cur)) {
258 if (!prio_tree_left_empty(cur))
259 get_index(root, cur->left, &r_index, &h_index_left);
260 else {
261 cur = cur->right;
262 continue;
263 }
264
265 if (!prio_tree_right_empty(cur))
266 get_index(root, cur->right, &r_index, &h_index_right);
267 else {
268 cur = cur->left;
269 continue;
270 }
271
272 /* both h_index_left and h_index_right cannot be 0 */
273 if (h_index_left >= h_index_right)
274 cur = cur->left;
275 else
276 cur = cur->right;
277 }
278
279 if (prio_tree_root(cur)) {
280 BUG_ON(root->prio_tree_node != cur);
281 __INIT_PRIO_TREE_ROOT(root, root->raw);
282 return;
283 }
284
285 if (cur->parent->right == cur)
286 cur->parent->right = cur->parent;
287 else
288 cur->parent->left = cur->parent;
289
290 while (cur != node)
291 cur = prio_tree_replace(root, cur->parent, cur);
292}
293
294static void iter_walk_down(struct prio_tree_iter *iter)
295{
296 iter->mask >>= 1;
297 if (iter->mask) {
298 if (iter->size_level)
299 iter->size_level++;
300 return;
301 }
302
303 if (iter->size_level) {
304 BUG_ON(!prio_tree_left_empty(iter->cur));
305 BUG_ON(!prio_tree_right_empty(iter->cur));
306 iter->size_level++;
307 iter->mask = ULONG_MAX;
308 } else {
309 iter->size_level = 1;
310 iter->mask = 1UL << (BITS_PER_LONG - 1);
311 }
312}
313
314static void iter_walk_up(struct prio_tree_iter *iter)
315{
316 if (iter->mask == ULONG_MAX)
317 iter->mask = 1UL;
318 else if (iter->size_level == 1)
319 iter->mask = 1UL;
320 else
321 iter->mask <<= 1;
322 if (iter->size_level)
323 iter->size_level--;
324 if (!iter->size_level && (iter->value & iter->mask))
325 iter->value ^= iter->mask;
326}
327
328/*
329 * Following functions help to enumerate all prio_tree_nodes in the tree that
330 * overlap with the input interval X [radix_index, heap_index]. The enumeration
331 * takes O(log n + m) time where 'log n' is the height of the tree (which is
332 * proportional to # of bits required to represent the maximum heap_index) and
333 * 'm' is the number of prio_tree_nodes that overlap the interval X.
334 */
335
336static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter,
337 unsigned long *r_index, unsigned long *h_index)
338{
339 if (prio_tree_left_empty(iter->cur))
340 return NULL;
341
342 get_index(iter->root, iter->cur->left, r_index, h_index);
343
344 if (iter->r_index <= *h_index) {
345 iter->cur = iter->cur->left;
346 iter_walk_down(iter);
347 return iter->cur;
348 }
349
350 return NULL;
351}
352
353static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,
354 unsigned long *r_index, unsigned long *h_index)
355{
356 unsigned long value;
357
358 if (prio_tree_right_empty(iter->cur))
359 return NULL;
360
361 if (iter->size_level)
362 value = iter->value;
363 else
364 value = iter->value | iter->mask;
365
366 if (iter->h_index < value)
367 return NULL;
368
369 get_index(iter->root, iter->cur->right, r_index, h_index);
370
371 if (iter->r_index <= *h_index) {
372 iter->cur = iter->cur->right;
373 iter_walk_down(iter);
374 return iter->cur;
375 }
376
377 return NULL;
378}
379
380static struct prio_tree_node *prio_tree_parent(struct prio_tree_iter *iter)
381{
382 iter->cur = iter->cur->parent;
383 iter_walk_up(iter);
384 return iter->cur;
385}
386
387static inline int overlap(struct prio_tree_iter *iter,
388 unsigned long r_index, unsigned long h_index)
389{
390 return iter->h_index >= r_index && iter->r_index <= h_index;
391}
392
393/*
394 * prio_tree_first:
395 *
396 * Get the first prio_tree_node that overlaps with the interval [radix_index,
397 * heap_index]. Note that always radix_index <= heap_index. We do a pre-order
398 * traversal of the tree.
399 */
400static struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter)
401{
402 struct prio_tree_root *root;
403 unsigned long r_index, h_index;
404
405 INIT_PRIO_TREE_ITER(iter);
406
407 root = iter->root;
408 if (prio_tree_empty(root))
409 return NULL;
410
411 get_index(root, root->prio_tree_node, &r_index, &h_index);
412
413 if (iter->r_index > h_index)
414 return NULL;
415
416 iter->mask = 1UL << (root->index_bits - 1);
417 iter->cur = root->prio_tree_node;
418
419 while (1) {
420 if (overlap(iter, r_index, h_index))
421 return iter->cur;
422
423 if (prio_tree_left(iter, &r_index, &h_index))
424 continue;
425
426 if (prio_tree_right(iter, &r_index, &h_index))
427 continue;
428
429 break;
430 }
431 return NULL;
432}
433
434/*
435 * prio_tree_next:
436 *
437 * Get the next prio_tree_node that overlaps with the input interval in iter
438 */
439struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter)
440{
441 unsigned long r_index, h_index;
442
443 if (iter->cur == NULL)
444 return prio_tree_first(iter);
445
446repeat:
447 while (prio_tree_left(iter, &r_index, &h_index))
448 if (overlap(iter, r_index, h_index))
449 return iter->cur;
450
451 while (!prio_tree_right(iter, &r_index, &h_index)) {
452 while (!prio_tree_root(iter->cur) &&
453 iter->cur->parent->right == iter->cur)
454 prio_tree_parent(iter);
455
456 if (prio_tree_root(iter->cur))
457 return NULL;
458
459 prio_tree_parent(iter);
460 }
461
462 if (overlap(iter, r_index, h_index))
463 return iter->cur;
464
465 goto repeat;
466}
diff --git a/lib/rbtree.c b/lib/rbtree.c
index d4175565dc2c..4f56a11d67fa 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -2,7 +2,8 @@
2 Red Black Trees 2 Red Black Trees
3 (C) 1999 Andrea Arcangeli <andrea@suse.de> 3 (C) 1999 Andrea Arcangeli <andrea@suse.de>
4 (C) 2002 David Woodhouse <dwmw2@infradead.org> 4 (C) 2002 David Woodhouse <dwmw2@infradead.org>
5 5 (C) 2012 Michel Lespinasse <walken@google.com>
6
6 This program is free software; you can redistribute it and/or modify 7 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by 8 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or 9 the Free Software Foundation; either version 2 of the License, or
@@ -20,339 +21,382 @@
20 linux/lib/rbtree.c 21 linux/lib/rbtree.c
21*/ 22*/
22 23
23#include <linux/rbtree.h> 24#include <linux/rbtree_augmented.h>
24#include <linux/export.h> 25#include <linux/export.h>
25 26
26static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) 27/*
27{ 28 * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
28 struct rb_node *right = node->rb_right; 29 *
29 struct rb_node *parent = rb_parent(node); 30 * 1) A node is either red or black
30 31 * 2) The root is black
31 if ((node->rb_right = right->rb_left)) 32 * 3) All leaves (NULL) are black
32 rb_set_parent(right->rb_left, node); 33 * 4) Both children of every red node are black
33 right->rb_left = node; 34 * 5) Every simple path from root to leaves contains the same number
34 35 * of black nodes.
35 rb_set_parent(right, parent); 36 *
37 * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
38 * consecutive red nodes in a path and every red node is therefore followed by
39 * a black. So if B is the number of black nodes on every simple path (as per
40 * 5), then the longest possible path due to 4 is 2B.
41 *
42 * We shall indicate color with case, where black nodes are uppercase and red
43 * nodes will be lowercase. Unknown color nodes shall be drawn as red within
44 * parentheses and have some accompanying text comment.
45 */
36 46
37 if (parent) 47static inline void rb_set_black(struct rb_node *rb)
38 { 48{
39 if (node == parent->rb_left) 49 rb->__rb_parent_color |= RB_BLACK;
40 parent->rb_left = right;
41 else
42 parent->rb_right = right;
43 }
44 else
45 root->rb_node = right;
46 rb_set_parent(node, right);
47} 50}
48 51
49static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 52static inline struct rb_node *rb_red_parent(struct rb_node *red)
50{ 53{
51 struct rb_node *left = node->rb_left; 54 return (struct rb_node *)red->__rb_parent_color;
52 struct rb_node *parent = rb_parent(node); 55}
53
54 if ((node->rb_left = left->rb_right))
55 rb_set_parent(left->rb_right, node);
56 left->rb_right = node;
57
58 rb_set_parent(left, parent);
59 56
60 if (parent) 57/*
61 { 58 * Helper function for rotations:
62 if (node == parent->rb_right) 59 * - old's parent and color get assigned to new
63 parent->rb_right = left; 60 * - old gets assigned new as a parent and 'color' as a color.
64 else 61 */
65 parent->rb_left = left; 62static inline void
66 } 63__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
67 else 64 struct rb_root *root, int color)
68 root->rb_node = left; 65{
69 rb_set_parent(node, left); 66 struct rb_node *parent = rb_parent(old);
67 new->__rb_parent_color = old->__rb_parent_color;
68 rb_set_parent_color(old, new, color);
69 __rb_change_child(old, new, parent, root);
70} 70}
71 71
72void rb_insert_color(struct rb_node *node, struct rb_root *root) 72static __always_inline void
73__rb_insert(struct rb_node *node, struct rb_root *root,
74 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
73{ 75{
74 struct rb_node *parent, *gparent; 76 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
75 77
76 while ((parent = rb_parent(node)) && rb_is_red(parent)) 78 while (true) {
77 { 79 /*
78 gparent = rb_parent(parent); 80 * Loop invariant: node is red
79 81 *
80 if (parent == gparent->rb_left) 82 * If there is a black parent, we are done.
81 { 83 * Otherwise, take some corrective action as we don't
82 { 84 * want a red root or two consecutive red nodes.
83 register struct rb_node *uncle = gparent->rb_right; 85 */
84 if (uncle && rb_is_red(uncle)) 86 if (!parent) {
85 { 87 rb_set_parent_color(node, NULL, RB_BLACK);
86 rb_set_black(uncle); 88 break;
87 rb_set_black(parent); 89 } else if (rb_is_black(parent))
88 rb_set_red(gparent); 90 break;
89 node = gparent; 91
90 continue; 92 gparent = rb_red_parent(parent);
91 } 93
94 tmp = gparent->rb_right;
95 if (parent != tmp) { /* parent == gparent->rb_left */
96 if (tmp && rb_is_red(tmp)) {
97 /*
98 * Case 1 - color flips
99 *
100 * G g
101 * / \ / \
102 * p u --> P U
103 * / /
104 * n N
105 *
106 * However, since g's parent might be red, and
107 * 4) does not allow this, we need to recurse
108 * at g.
109 */
110 rb_set_parent_color(tmp, gparent, RB_BLACK);
111 rb_set_parent_color(parent, gparent, RB_BLACK);
112 node = gparent;
113 parent = rb_parent(node);
114 rb_set_parent_color(node, parent, RB_RED);
115 continue;
92 } 116 }
93 117
94 if (parent->rb_right == node) 118 tmp = parent->rb_right;
95 { 119 if (node == tmp) {
96 register struct rb_node *tmp; 120 /*
97 __rb_rotate_left(parent, root); 121 * Case 2 - left rotate at parent
98 tmp = parent; 122 *
123 * G G
124 * / \ / \
125 * p U --> n U
126 * \ /
127 * n p
128 *
129 * This still leaves us in violation of 4), the
130 * continuation into Case 3 will fix that.
131 */
132 parent->rb_right = tmp = node->rb_left;
133 node->rb_left = parent;
134 if (tmp)
135 rb_set_parent_color(tmp, parent,
136 RB_BLACK);
137 rb_set_parent_color(parent, node, RB_RED);
138 augment_rotate(parent, node);
99 parent = node; 139 parent = node;
100 node = tmp; 140 tmp = node->rb_right;
101 } 141 }
102 142
103 rb_set_black(parent); 143 /*
104 rb_set_red(gparent); 144 * Case 3 - right rotate at gparent
105 __rb_rotate_right(gparent, root); 145 *
146 * G P
147 * / \ / \
148 * p U --> n g
149 * / \
150 * n U
151 */
152 gparent->rb_left = tmp; /* == parent->rb_right */
153 parent->rb_right = gparent;
154 if (tmp)
155 rb_set_parent_color(tmp, gparent, RB_BLACK);
156 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
157 augment_rotate(gparent, parent);
158 break;
106 } else { 159 } else {
107 { 160 tmp = gparent->rb_left;
108 register struct rb_node *uncle = gparent->rb_left; 161 if (tmp && rb_is_red(tmp)) {
109 if (uncle && rb_is_red(uncle)) 162 /* Case 1 - color flips */
110 { 163 rb_set_parent_color(tmp, gparent, RB_BLACK);
111 rb_set_black(uncle); 164 rb_set_parent_color(parent, gparent, RB_BLACK);
112 rb_set_black(parent); 165 node = gparent;
113 rb_set_red(gparent); 166 parent = rb_parent(node);
114 node = gparent; 167 rb_set_parent_color(node, parent, RB_RED);
115 continue; 168 continue;
116 }
117 } 169 }
118 170
119 if (parent->rb_left == node) 171 tmp = parent->rb_left;
120 { 172 if (node == tmp) {
121 register struct rb_node *tmp; 173 /* Case 2 - right rotate at parent */
122 __rb_rotate_right(parent, root); 174 parent->rb_left = tmp = node->rb_right;
123 tmp = parent; 175 node->rb_right = parent;
176 if (tmp)
177 rb_set_parent_color(tmp, parent,
178 RB_BLACK);
179 rb_set_parent_color(parent, node, RB_RED);
180 augment_rotate(parent, node);
124 parent = node; 181 parent = node;
125 node = tmp; 182 tmp = node->rb_left;
126 } 183 }
127 184
128 rb_set_black(parent); 185 /* Case 3 - left rotate at gparent */
129 rb_set_red(gparent); 186 gparent->rb_right = tmp; /* == parent->rb_left */
130 __rb_rotate_left(gparent, root); 187 parent->rb_left = gparent;
188 if (tmp)
189 rb_set_parent_color(tmp, gparent, RB_BLACK);
190 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
191 augment_rotate(gparent, parent);
192 break;
131 } 193 }
132 } 194 }
133
134 rb_set_black(root->rb_node);
135} 195}
136EXPORT_SYMBOL(rb_insert_color);
137 196
138static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 197__always_inline void
139 struct rb_root *root) 198__rb_erase_color(struct rb_node *parent, struct rb_root *root,
199 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
140{ 200{
141 struct rb_node *other; 201 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
142 202
143 while ((!node || rb_is_black(node)) && node != root->rb_node) 203 while (true) {
144 { 204 /*
145 if (parent->rb_left == node) 205 * Loop invariants:
146 { 206 * - node is black (or NULL on first iteration)
147 other = parent->rb_right; 207 * - node is not the root (parent is not NULL)
148 if (rb_is_red(other)) 208 * - All leaf paths going through parent and node have a
149 { 209 * black node count that is 1 lower than other leaf paths.
150 rb_set_black(other); 210 */
151 rb_set_red(parent); 211 sibling = parent->rb_right;
152 __rb_rotate_left(parent, root); 212 if (node != sibling) { /* node == parent->rb_left */
153 other = parent->rb_right; 213 if (rb_is_red(sibling)) {
214 /*
215 * Case 1 - left rotate at parent
216 *
217 * P S
218 * / \ / \
219 * N s --> p Sr
220 * / \ / \
221 * Sl Sr N Sl
222 */
223 parent->rb_right = tmp1 = sibling->rb_left;
224 sibling->rb_left = parent;
225 rb_set_parent_color(tmp1, parent, RB_BLACK);
226 __rb_rotate_set_parents(parent, sibling, root,
227 RB_RED);
228 augment_rotate(parent, sibling);
229 sibling = tmp1;
154 } 230 }
155 if ((!other->rb_left || rb_is_black(other->rb_left)) && 231 tmp1 = sibling->rb_right;
156 (!other->rb_right || rb_is_black(other->rb_right))) 232 if (!tmp1 || rb_is_black(tmp1)) {
157 { 233 tmp2 = sibling->rb_left;
158 rb_set_red(other); 234 if (!tmp2 || rb_is_black(tmp2)) {
159 node = parent; 235 /*
160 parent = rb_parent(node); 236 * Case 2 - sibling color flip
161 } 237 * (p could be either color here)
162 else 238 *
163 { 239 * (p) (p)
164 if (!other->rb_right || rb_is_black(other->rb_right)) 240 * / \ / \
165 { 241 * N S --> N s
166 rb_set_black(other->rb_left); 242 * / \ / \
167 rb_set_red(other); 243 * Sl Sr Sl Sr
168 __rb_rotate_right(other, root); 244 *
169 other = parent->rb_right; 245 * This leaves us violating 5) which
246 * can be fixed by flipping p to black
247 * if it was red, or by recursing at p.
248 * p is red when coming from Case 1.
249 */
250 rb_set_parent_color(sibling, parent,
251 RB_RED);
252 if (rb_is_red(parent))
253 rb_set_black(parent);
254 else {
255 node = parent;
256 parent = rb_parent(node);
257 if (parent)
258 continue;
259 }
260 break;
170 } 261 }
171 rb_set_color(other, rb_color(parent)); 262 /*
172 rb_set_black(parent); 263 * Case 3 - right rotate at sibling
173 rb_set_black(other->rb_right); 264 * (p could be either color here)
174 __rb_rotate_left(parent, root); 265 *
175 node = root->rb_node; 266 * (p) (p)
176 break; 267 * / \ / \
177 } 268 * N S --> N Sl
178 } 269 * / \ \
179 else 270 * sl Sr s
180 { 271 * \
181 other = parent->rb_left; 272 * Sr
182 if (rb_is_red(other)) 273 */
183 { 274 sibling->rb_left = tmp1 = tmp2->rb_right;
184 rb_set_black(other); 275 tmp2->rb_right = sibling;
185 rb_set_red(parent); 276 parent->rb_right = tmp2;
186 __rb_rotate_right(parent, root); 277 if (tmp1)
187 other = parent->rb_left; 278 rb_set_parent_color(tmp1, sibling,
279 RB_BLACK);
280 augment_rotate(sibling, tmp2);
281 tmp1 = sibling;
282 sibling = tmp2;
188 } 283 }
189 if ((!other->rb_left || rb_is_black(other->rb_left)) && 284 /*
190 (!other->rb_right || rb_is_black(other->rb_right))) 285 * Case 4 - left rotate at parent + color flips
191 { 286 * (p and sl could be either color here.
192 rb_set_red(other); 287 * After rotation, p becomes black, s acquires
193 node = parent; 288 * p's color, and sl keeps its color)
194 parent = rb_parent(node); 289 *
290 * (p) (s)
291 * / \ / \
292 * N S --> P Sr
293 * / \ / \
294 * (sl) sr N (sl)
295 */
296 parent->rb_right = tmp2 = sibling->rb_left;
297 sibling->rb_left = parent;
298 rb_set_parent_color(tmp1, sibling, RB_BLACK);
299 if (tmp2)
300 rb_set_parent(tmp2, parent);
301 __rb_rotate_set_parents(parent, sibling, root,
302 RB_BLACK);
303 augment_rotate(parent, sibling);
304 break;
305 } else {
306 sibling = parent->rb_left;
307 if (rb_is_red(sibling)) {
308 /* Case 1 - right rotate at parent */
309 parent->rb_left = tmp1 = sibling->rb_right;
310 sibling->rb_right = parent;
311 rb_set_parent_color(tmp1, parent, RB_BLACK);
312 __rb_rotate_set_parents(parent, sibling, root,
313 RB_RED);
314 augment_rotate(parent, sibling);
315 sibling = tmp1;
195 } 316 }
196 else 317 tmp1 = sibling->rb_left;
197 { 318 if (!tmp1 || rb_is_black(tmp1)) {
198 if (!other->rb_left || rb_is_black(other->rb_left)) 319 tmp2 = sibling->rb_right;
199 { 320 if (!tmp2 || rb_is_black(tmp2)) {
200 rb_set_black(other->rb_right); 321 /* Case 2 - sibling color flip */
201 rb_set_red(other); 322 rb_set_parent_color(sibling, parent,
202 __rb_rotate_left(other, root); 323 RB_RED);
203 other = parent->rb_left; 324 if (rb_is_red(parent))
325 rb_set_black(parent);
326 else {
327 node = parent;
328 parent = rb_parent(node);
329 if (parent)
330 continue;
331 }
332 break;
204 } 333 }
205 rb_set_color(other, rb_color(parent)); 334 /* Case 3 - right rotate at sibling */
206 rb_set_black(parent); 335 sibling->rb_right = tmp1 = tmp2->rb_left;
207 rb_set_black(other->rb_left); 336 tmp2->rb_left = sibling;
208 __rb_rotate_right(parent, root); 337 parent->rb_left = tmp2;
209 node = root->rb_node; 338 if (tmp1)
210 break; 339 rb_set_parent_color(tmp1, sibling,
340 RB_BLACK);
341 augment_rotate(sibling, tmp2);
342 tmp1 = sibling;
343 sibling = tmp2;
211 } 344 }
345 /* Case 4 - left rotate at parent + color flips */
346 parent->rb_left = tmp2 = sibling->rb_right;
347 sibling->rb_right = parent;
348 rb_set_parent_color(tmp1, sibling, RB_BLACK);
349 if (tmp2)
350 rb_set_parent(tmp2, parent);
351 __rb_rotate_set_parents(parent, sibling, root,
352 RB_BLACK);
353 augment_rotate(parent, sibling);
354 break;
212 } 355 }
213 } 356 }
214 if (node)
215 rb_set_black(node);
216} 357}
358EXPORT_SYMBOL(__rb_erase_color);
217 359
218void rb_erase(struct rb_node *node, struct rb_root *root) 360/*
219{ 361 * Non-augmented rbtree manipulation functions.
220 struct rb_node *child, *parent; 362 *
221 int color; 363 * We use dummy augmented callbacks here, and have the compiler optimize them
222 364 * out of the rb_insert_color() and rb_erase() function definitions.
223 if (!node->rb_left) 365 */
224 child = node->rb_right;
225 else if (!node->rb_right)
226 child = node->rb_left;
227 else
228 {
229 struct rb_node *old = node, *left;
230
231 node = node->rb_right;
232 while ((left = node->rb_left) != NULL)
233 node = left;
234
235 if (rb_parent(old)) {
236 if (rb_parent(old)->rb_left == old)
237 rb_parent(old)->rb_left = node;
238 else
239 rb_parent(old)->rb_right = node;
240 } else
241 root->rb_node = node;
242
243 child = node->rb_right;
244 parent = rb_parent(node);
245 color = rb_color(node);
246
247 if (parent == old) {
248 parent = node;
249 } else {
250 if (child)
251 rb_set_parent(child, parent);
252 parent->rb_left = child;
253
254 node->rb_right = old->rb_right;
255 rb_set_parent(old->rb_right, node);
256 }
257
258 node->rb_parent_color = old->rb_parent_color;
259 node->rb_left = old->rb_left;
260 rb_set_parent(old->rb_left, node);
261 366
262 goto color; 367static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
263 } 368static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
369static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
264 370
265 parent = rb_parent(node); 371static const struct rb_augment_callbacks dummy_callbacks = {
266 color = rb_color(node); 372 dummy_propagate, dummy_copy, dummy_rotate
267 373};
268 if (child)
269 rb_set_parent(child, parent);
270 if (parent)
271 {
272 if (parent->rb_left == node)
273 parent->rb_left = child;
274 else
275 parent->rb_right = child;
276 }
277 else
278 root->rb_node = child;
279 374
280 color: 375void rb_insert_color(struct rb_node *node, struct rb_root *root)
281 if (color == RB_BLACK)
282 __rb_erase_color(child, parent, root);
283}
284EXPORT_SYMBOL(rb_erase);
285
286static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
287{ 376{
288 struct rb_node *parent; 377 __rb_insert(node, root, dummy_rotate);
289
290up:
291 func(node, data);
292 parent = rb_parent(node);
293 if (!parent)
294 return;
295
296 if (node == parent->rb_left && parent->rb_right)
297 func(parent->rb_right, data);
298 else if (parent->rb_left)
299 func(parent->rb_left, data);
300
301 node = parent;
302 goto up;
303} 378}
379EXPORT_SYMBOL(rb_insert_color);
304 380
305/* 381void rb_erase(struct rb_node *node, struct rb_root *root)
306 * after inserting @node into the tree, update the tree to account for
307 * both the new entry and any damage done by rebalance
308 */
309void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
310{ 382{
311 if (node->rb_left) 383 rb_erase_augmented(node, root, &dummy_callbacks);
312 node = node->rb_left;
313 else if (node->rb_right)
314 node = node->rb_right;
315
316 rb_augment_path(node, func, data);
317} 384}
318EXPORT_SYMBOL(rb_augment_insert); 385EXPORT_SYMBOL(rb_erase);
319 386
320/* 387/*
321 * before removing the node, find the deepest node on the rebalance path 388 * Augmented rbtree manipulation functions.
322 * that will still be there after @node gets removed 389 *
390 * This instantiates the same __always_inline functions as in the non-augmented
391 * case, but this time with user-defined callbacks.
323 */ 392 */
324struct rb_node *rb_augment_erase_begin(struct rb_node *node)
325{
326 struct rb_node *deepest;
327
328 if (!node->rb_right && !node->rb_left)
329 deepest = rb_parent(node);
330 else if (!node->rb_right)
331 deepest = node->rb_left;
332 else if (!node->rb_left)
333 deepest = node->rb_right;
334 else {
335 deepest = rb_next(node);
336 if (deepest->rb_right)
337 deepest = deepest->rb_right;
338 else if (rb_parent(deepest) != node)
339 deepest = rb_parent(deepest);
340 }
341
342 return deepest;
343}
344EXPORT_SYMBOL(rb_augment_erase_begin);
345 393
346/* 394void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
347 * after removal, update the tree to account for the removed entry 395 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
348 * and any rebalance damage.
349 */
350void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
351{ 396{
352 if (node) 397 __rb_insert(node, root, augment_rotate);
353 rb_augment_path(node, func, data);
354} 398}
355EXPORT_SYMBOL(rb_augment_erase_end); 399EXPORT_SYMBOL(__rb_insert_augmented);
356 400
357/* 401/*
358 * This function returns the first node (in sort order) of the tree. 402 * This function returns the first node (in sort order) of the tree.
@@ -387,11 +431,13 @@ struct rb_node *rb_next(const struct rb_node *node)
387{ 431{
388 struct rb_node *parent; 432 struct rb_node *parent;
389 433
390 if (rb_parent(node) == node) 434 if (RB_EMPTY_NODE(node))
391 return NULL; 435 return NULL;
392 436
393 /* If we have a right-hand child, go down and then left as far 437 /*
394 as we can. */ 438 * If we have a right-hand child, go down and then left as far
439 * as we can.
440 */
395 if (node->rb_right) { 441 if (node->rb_right) {
396 node = node->rb_right; 442 node = node->rb_right;
397 while (node->rb_left) 443 while (node->rb_left)
@@ -399,12 +445,13 @@ struct rb_node *rb_next(const struct rb_node *node)
399 return (struct rb_node *)node; 445 return (struct rb_node *)node;
400 } 446 }
401 447
402 /* No right-hand children. Everything down and left is 448 /*
403 smaller than us, so any 'next' node must be in the general 449 * No right-hand children. Everything down and left is smaller than us,
404 direction of our parent. Go up the tree; any time the 450 * so any 'next' node must be in the general direction of our parent.
405 ancestor is a right-hand child of its parent, keep going 451 * Go up the tree; any time the ancestor is a right-hand child of its
406 up. First time it's a left-hand child of its parent, said 452 * parent, keep going up. First time it's a left-hand child of its
407 parent is our 'next' node. */ 453 * parent, said parent is our 'next' node.
454 */
408 while ((parent = rb_parent(node)) && node == parent->rb_right) 455 while ((parent = rb_parent(node)) && node == parent->rb_right)
409 node = parent; 456 node = parent;
410 457
@@ -416,11 +463,13 @@ struct rb_node *rb_prev(const struct rb_node *node)
416{ 463{
417 struct rb_node *parent; 464 struct rb_node *parent;
418 465
419 if (rb_parent(node) == node) 466 if (RB_EMPTY_NODE(node))
420 return NULL; 467 return NULL;
421 468
422 /* If we have a left-hand child, go down and then right as far 469 /*
423 as we can. */ 470 * If we have a left-hand child, go down and then right as far
471 * as we can.
472 */
424 if (node->rb_left) { 473 if (node->rb_left) {
425 node = node->rb_left; 474 node = node->rb_left;
426 while (node->rb_right) 475 while (node->rb_right)
@@ -428,8 +477,10 @@ struct rb_node *rb_prev(const struct rb_node *node)
428 return (struct rb_node *)node; 477 return (struct rb_node *)node;
429 } 478 }
430 479
431 /* No left-hand children. Go up till we find an ancestor which 480 /*
432 is a right-hand child of its parent */ 481 * No left-hand children. Go up till we find an ancestor which
482 * is a right-hand child of its parent.
483 */
433 while ((parent = rb_parent(node)) && node == parent->rb_left) 484 while ((parent = rb_parent(node)) && node == parent->rb_left)
434 node = parent; 485 node = parent;
435 486
@@ -443,14 +494,7 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
443 struct rb_node *parent = rb_parent(victim); 494 struct rb_node *parent = rb_parent(victim);
444 495
445 /* Set the surrounding nodes to point to the replacement */ 496 /* Set the surrounding nodes to point to the replacement */
446 if (parent) { 497 __rb_change_child(victim, new, parent, root);
447 if (victim == parent->rb_left)
448 parent->rb_left = new;
449 else
450 parent->rb_right = new;
451 } else {
452 root->rb_node = new;
453 }
454 if (victim->rb_left) 498 if (victim->rb_left)
455 rb_set_parent(victim->rb_left, new); 499 rb_set_parent(victim->rb_left, new);
456 if (victim->rb_right) 500 if (victim->rb_right)
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
new file mode 100644
index 000000000000..268b23951fec
--- /dev/null
+++ b/lib/rbtree_test.c
@@ -0,0 +1,234 @@
1#include <linux/module.h>
2#include <linux/rbtree_augmented.h>
3#include <linux/random.h>
4#include <asm/timex.h>
5
6#define NODES 100
7#define PERF_LOOPS 100000
8#define CHECK_LOOPS 100
9
10struct test_node {
11 struct rb_node rb;
12 u32 key;
13
14 /* following fields used for testing augmented rbtree functionality */
15 u32 val;
16 u32 augmented;
17};
18
19static struct rb_root root = RB_ROOT;
20static struct test_node nodes[NODES];
21
22static struct rnd_state rnd;
23
24static void insert(struct test_node *node, struct rb_root *root)
25{
26 struct rb_node **new = &root->rb_node, *parent = NULL;
27 u32 key = node->key;
28
29 while (*new) {
30 parent = *new;
31 if (key < rb_entry(parent, struct test_node, rb)->key)
32 new = &parent->rb_left;
33 else
34 new = &parent->rb_right;
35 }
36
37 rb_link_node(&node->rb, parent, new);
38 rb_insert_color(&node->rb, root);
39}
40
41static inline void erase(struct test_node *node, struct rb_root *root)
42{
43 rb_erase(&node->rb, root);
44}
45
46static inline u32 augment_recompute(struct test_node *node)
47{
48 u32 max = node->val, child_augmented;
49 if (node->rb.rb_left) {
50 child_augmented = rb_entry(node->rb.rb_left, struct test_node,
51 rb)->augmented;
52 if (max < child_augmented)
53 max = child_augmented;
54 }
55 if (node->rb.rb_right) {
56 child_augmented = rb_entry(node->rb.rb_right, struct test_node,
57 rb)->augmented;
58 if (max < child_augmented)
59 max = child_augmented;
60 }
61 return max;
62}
63
64RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb,
65 u32, augmented, augment_recompute)
66
67static void insert_augmented(struct test_node *node, struct rb_root *root)
68{
69 struct rb_node **new = &root->rb_node, *rb_parent = NULL;
70 u32 key = node->key;
71 u32 val = node->val;
72 struct test_node *parent;
73
74 while (*new) {
75 rb_parent = *new;
76 parent = rb_entry(rb_parent, struct test_node, rb);
77 if (parent->augmented < val)
78 parent->augmented = val;
79 if (key < parent->key)
80 new = &parent->rb.rb_left;
81 else
82 new = &parent->rb.rb_right;
83 }
84
85 node->augmented = val;
86 rb_link_node(&node->rb, rb_parent, new);
87 rb_insert_augmented(&node->rb, root, &augment_callbacks);
88}
89
90static void erase_augmented(struct test_node *node, struct rb_root *root)
91{
92 rb_erase_augmented(&node->rb, root, &augment_callbacks);
93}
94
95static void init(void)
96{
97 int i;
98 for (i = 0; i < NODES; i++) {
99 nodes[i].key = prandom32(&rnd);
100 nodes[i].val = prandom32(&rnd);
101 }
102}
103
104static bool is_red(struct rb_node *rb)
105{
106 return !(rb->__rb_parent_color & 1);
107}
108
109static int black_path_count(struct rb_node *rb)
110{
111 int count;
112 for (count = 0; rb; rb = rb_parent(rb))
113 count += !is_red(rb);
114 return count;
115}
116
117static void check(int nr_nodes)
118{
119 struct rb_node *rb;
120 int count = 0;
121 int blacks;
122 u32 prev_key = 0;
123
124 for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
125 struct test_node *node = rb_entry(rb, struct test_node, rb);
126 WARN_ON_ONCE(node->key < prev_key);
127 WARN_ON_ONCE(is_red(rb) &&
128 (!rb_parent(rb) || is_red(rb_parent(rb))));
129 if (!count)
130 blacks = black_path_count(rb);
131 else
132 WARN_ON_ONCE((!rb->rb_left || !rb->rb_right) &&
133 blacks != black_path_count(rb));
134 prev_key = node->key;
135 count++;
136 }
137 WARN_ON_ONCE(count != nr_nodes);
138}
139
140static void check_augmented(int nr_nodes)
141{
142 struct rb_node *rb;
143
144 check(nr_nodes);
145 for (rb = rb_first(&root); rb; rb = rb_next(rb)) {
146 struct test_node *node = rb_entry(rb, struct test_node, rb);
147 WARN_ON_ONCE(node->augmented != augment_recompute(node));
148 }
149}
150
151static int rbtree_test_init(void)
152{
153 int i, j;
154 cycles_t time1, time2, time;
155
156 printk(KERN_ALERT "rbtree testing");
157
158 prandom32_seed(&rnd, 3141592653589793238ULL);
159 init();
160
161 time1 = get_cycles();
162
163 for (i = 0; i < PERF_LOOPS; i++) {
164 for (j = 0; j < NODES; j++)
165 insert(nodes + j, &root);
166 for (j = 0; j < NODES; j++)
167 erase(nodes + j, &root);
168 }
169
170 time2 = get_cycles();
171 time = time2 - time1;
172
173 time = div_u64(time, PERF_LOOPS);
174 printk(" -> %llu cycles\n", (unsigned long long)time);
175
176 for (i = 0; i < CHECK_LOOPS; i++) {
177 init();
178 for (j = 0; j < NODES; j++) {
179 check(j);
180 insert(nodes + j, &root);
181 }
182 for (j = 0; j < NODES; j++) {
183 check(NODES - j);
184 erase(nodes + j, &root);
185 }
186 check(0);
187 }
188
189 printk(KERN_ALERT "augmented rbtree testing");
190
191 init();
192
193 time1 = get_cycles();
194
195 for (i = 0; i < PERF_LOOPS; i++) {
196 for (j = 0; j < NODES; j++)
197 insert_augmented(nodes + j, &root);
198 for (j = 0; j < NODES; j++)
199 erase_augmented(nodes + j, &root);
200 }
201
202 time2 = get_cycles();
203 time = time2 - time1;
204
205 time = div_u64(time, PERF_LOOPS);
206 printk(" -> %llu cycles\n", (unsigned long long)time);
207
208 for (i = 0; i < CHECK_LOOPS; i++) {
209 init();
210 for (j = 0; j < NODES; j++) {
211 check_augmented(j);
212 insert_augmented(nodes + j, &root);
213 }
214 for (j = 0; j < NODES; j++) {
215 check_augmented(NODES - j);
216 erase_augmented(nodes + j, &root);
217 }
218 check_augmented(0);
219 }
220
221 return -EAGAIN; /* Fail will directly unload the module */
222}
223
224static void rbtree_test_exit(void)
225{
226 printk(KERN_ALERT "test exit\n");
227}
228
229module_init(rbtree_test_init)
230module_exit(rbtree_test_exit)
231
232MODULE_LICENSE("GPL");
233MODULE_AUTHOR("Michel Lespinasse");
234MODULE_DESCRIPTION("Red Black Tree test");
generated by cgit v1.2.2 (git 2.25.0) at 2025-03-28 13:57:42 -0400