1 /* $OpenBSD: rb-linux.c,v 1.2 2024/09/01 06:05:11 anton Exp $ */
2 /*
3 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28 #include <sys/types.h>
29 #include <unistd.h>
30 #include <stdio.h>
31 #include <err.h>
32 #include <stdlib.h>
33 #include <stddef.h>
34 #include <stdbool.h>
35 #include <linux/rbtree.h>
36 #include <linux/container_of.h>
37
38 struct keynode {
39 struct rb_node node;
40 int key;
41 };
42
43 struct rb_root root;
44
45 static struct keynode *
rb_find(struct rb_root * head,struct keynode * elm)46 rb_find(struct rb_root *head, struct keynode *elm)
47 {
48 struct rb_node *tmp = head->rb_node;
49
50 while (tmp) {
51 struct keynode *n = container_of(tmp, struct keynode, node);
52 if (elm->key < n->key)
53 tmp = tmp->rb_left;
54 else if (elm->key > n->key)
55 tmp = tmp->rb_right;
56 else
57 return n;
58 }
59 return NULL;
60 }
61
62 static struct keynode *
rb_insert(struct rb_root * head,struct keynode * elm)63 rb_insert(struct rb_root *head, struct keynode *elm)
64 {
65 struct rb_node **tmp;
66 struct rb_node *parent = NULL;
67 tmp = &(head->rb_node);
68
69 while (*tmp) {
70 struct keynode *n = container_of(*tmp, struct keynode, node);
71 parent = *tmp;
72 if (elm->key < n->key)
73 tmp = &((*tmp)->rb_left);
74 else if (elm->key > n->key)
75 tmp = &((*tmp)->rb_right);
76 else
77 return n;
78 }
79
80 rb_link_node(&elm->node, parent, tmp);
81 rb_insert_color(&elm->node, head);
82
83 return NULL;
84 }
85
86 #define TESTS 10
87 #define ITER 150
88 #define MIN 5
89 #define MAX 5000
90
91 int
main(int argc,char ** argv)92 main(int argc, char **argv)
93 {
94 struct keynode *tmp, *ins;
95 int i, t, max, min;
96 struct rb_node *rb_node;
97
98 root = RB_ROOT;
99
100 for (t = 0; t < 10; t++) {
101 for (i = 0; i < ITER; i++) {
102 tmp = malloc(sizeof(struct keynode));
103 if (tmp == NULL)
104 err(1, "malloc");
105 do {
106 tmp->key = arc4random_uniform(MAX - MIN);
107 tmp->key += MIN;
108 } while (rb_find(&root, tmp) != NULL);
109 if (i == 0)
110 max = min = tmp->key;
111 else {
112 if (tmp->key > max)
113 max = tmp->key;
114 if (tmp->key < min)
115 min = tmp->key;
116 }
117 if (rb_insert(&root, tmp) != NULL)
118 errx(1, "rb_insert failed");
119 }
120
121 rb_node = rb_first(&root);
122 ins = container_of(rb_node, struct keynode, node);
123 if (ins->key != min)
124 errx(1, "min does not match");
125 tmp = ins;
126 rb_node = rb_last(&root);
127 ins = container_of(rb_node, struct keynode, node);
128 if (ins->key != max)
129 errx(1, "max does not match");
130
131 rb_erase(&tmp->node, &root);
132
133 for (i = 0; i < ITER - 1; i++) {
134 rb_node = rb_first(&root);
135 if (rb_node == NULL)
136 errx(1, "rb_first error");
137 tmp = container_of(rb_node, struct keynode, node);
138 rb_erase(&tmp->node, &root);
139 free(tmp);
140 }
141 }
142
143 exit(0);
144 }
145
146 #undef RB_ROOT
147 #define RB_ROOT(head) (head)->rbh_root
148
149 RB_GENERATE(linux_root, rb_node, __entry, panic_cmp);
150
151 int
panic_cmp(struct rb_node * a,struct rb_node * b)152 panic_cmp(struct rb_node *a, struct rb_node *b)
153 {
154 errx(1, "%s", __func__);
155 }
156