Download code

Jump to: navigation, search

Back to Red-black_tree_(C)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

rbtree.c

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
 14 */
 15 
 16 #include "rbtree.h"
 17 #include <assert.h>
 18 #include <stdlib.h>
 19 
 20 typedef rbtree_node node;
 21 typedef enum rbtree_node_color color;
 22 
 23 static node grandparent(node n);
 24 static node sibling(node n);
 25 static node uncle(node n);
 26 static void verify_properties(rbtree t);
 27 static void verify_property_1(node root);
 28 static void verify_property_2(node root);
 29 static color node_color(node n);
 30 static void verify_property_4(node root);
 31 static void verify_property_5(node root);
 32 static void verify_property_5_helper(node n, int black_count, int* black_count_path);
 33 
 34 static node new_node(void* key, void* value, color node_color, node left, node right);
 35 static node lookup_node(rbtree t, void* key, compare_func compare);
 36 static void rotate_left(rbtree t, node n);
 37 static void rotate_right(rbtree t, node n);
 38 
 39 static void replace_node(rbtree t, node oldn, node newn);
 40 static void insert_case1(rbtree t, node n);
 41 static void insert_case2(rbtree t, node n);
 42 static void insert_case3(rbtree t, node n);
 43 static void insert_case4(rbtree t, node n);
 44 static void insert_case5(rbtree t, node n);
 45 static node maximum_node(node root);
 46 static void delete_case1(rbtree t, node n);
 47 static void delete_case2(rbtree t, node n);
 48 static void delete_case3(rbtree t, node n);
 49 static void delete_case4(rbtree t, node n);
 50 static void delete_case5(rbtree t, node n);
 51 static void delete_case6(rbtree t, node n);
 52 
 53 node grandparent(node n) {
 54     assert (n != NULL);
 55     assert (n->parent != NULL); /* Not the root node */
 56     assert (n->parent->parent != NULL); /* Not child of root */
 57     return n->parent->parent;
 58 }
 59 node sibling(node n) {
 60     assert (n != NULL);
 61     assert (n->parent != NULL); /* Root node has no sibling */
 62     if (n == n->parent->left)
 63         return n->parent->right;
 64     else
 65         return n->parent->left;
 66 }
 67 node uncle(node n) {
 68     assert (n != NULL);
 69     assert (n->parent != NULL); /* Root node has no uncle */
 70     assert (n->parent->parent != NULL); /* Children of root have no uncle */
 71     return sibling(n->parent);
 72 }
 73 void verify_properties(rbtree t) {
 74 #ifdef VERIFY_RBTREE
 75     verify_property_1(t->root);
 76     verify_property_2(t->root);
 77     /* Property 3 is implicit */
 78     verify_property_4(t->root);
 79     verify_property_5(t->root);
 80 #endif
 81 }
 82 void verify_property_1(node n) {
 83     assert(node_color(n) == RED || node_color(n) == BLACK);
 84     if (n == NULL) return;
 85     verify_property_1(n->left);
 86     verify_property_1(n->right);
 87 }
 88 void verify_property_2(node root) {
 89     assert(node_color(root) == BLACK);
 90 }
 91 color node_color(node n) {
 92     return n == NULL ? BLACK : n->color;
 93 }
 94 void verify_property_4(node n) {
 95     if (node_color(n) == RED) {
 96         assert (node_color(n->left)   == BLACK);
 97         assert (node_color(n->right)  == BLACK);
 98         assert (node_color(n->parent) == BLACK);
 99     }
100     if (n == NULL) return;
101     verify_property_4(n->left);
102     verify_property_4(n->right);
103 }
104 void verify_property_5(node root) {
105     int black_count_path = -1;
106     verify_property_5_helper(root, 0, &black_count_path);
107 }
108 
109 void verify_property_5_helper(node n, int black_count, int* path_black_count) {
110     if (node_color(n) == BLACK) {
111         black_count++;
112     }
113     if (n == NULL) {
114         if (*path_black_count == -1) {
115             *path_black_count = black_count;
116         } else {
117             assert (black_count == *path_black_count);
118         }
119         return;
120     }
121     verify_property_5_helper(n->left,  black_count, path_black_count);
122     verify_property_5_helper(n->right, black_count, path_black_count);
123 }
124 rbtree rbtree_create() {
125     rbtree t = malloc(sizeof(struct rbtree_t));
126     t->root = NULL;
127     verify_properties(t);
128     return t;
129 }
130 node new_node(void* key, void* value, color node_color, node left, node right) {
131     node result = malloc(sizeof(struct rbtree_node_t));
132     result->key = key;
133     result->value = value;
134     result->color = node_color;
135     result->left = left;
136     result->right = right;
137     if (left  != NULL)  left->parent = result;
138     if (right != NULL) right->parent = result;
139     result->parent = NULL;
140     return result;
141 }
142 node lookup_node(rbtree t, void* key, compare_func compare) {
143     node n = t->root;
144     while (n != NULL) {
145         int comp_result = compare(key, n->key);
146         if (comp_result == 0) {
147             return n;
148         } else if (comp_result < 0) {
149             n = n->left;
150         } else {
151             assert(comp_result > 0);
152             n = n->right;
153         }
154     }
155     return n;
156 }
157 void* rbtree_lookup(rbtree t, void* key, compare_func compare) {
158     node n = lookup_node(t, key, compare);
159     return n == NULL ? NULL : n->value;
160 }
161 void rotate_left(rbtree t, node n) {
162     node r = n->right;
163     replace_node(t, n, r);
164     n->right = r->left;
165     if (r->left != NULL) {
166         r->left->parent = n;
167     }
168     r->left = n;
169     n->parent = r;
170 }
171 
172 void rotate_right(rbtree t, node n) {
173     node L = n->left;
174     replace_node(t, n, L);
175     n->left = L->right;
176     if (L->right != NULL) {
177         L->right->parent = n;
178     }
179     L->right = n;
180     n->parent = L;
181 }
182 void replace_node(rbtree t, node oldn, node newn) {
183     if (oldn->parent == NULL) {
184         t->root = newn;
185     } else {
186         if (oldn == oldn->parent->left)
187             oldn->parent->left = newn;
188         else
189             oldn->parent->right = newn;
190     }
191     if (newn != NULL) {
192         newn->parent = oldn->parent;
193     }
194 }
195 void rbtree_insert(rbtree t, void* key, void* value, compare_func compare) {
196     node inserted_node = new_node(key, value, RED, NULL, NULL);
197     if (t->root == NULL) {
198         t->root = inserted_node;
199     } else {
200         node n = t->root;
201         while (1) {
202             int comp_result = compare(key, n->key);
203             if (comp_result == 0) {
204                 n->value = value;
205                 return;
206             } else if (comp_result < 0) {
207                 if (n->left == NULL) {
208                     n->left = inserted_node;
209                     break;
210                 } else {
211                     n = n->left;
212                 }
213             } else {
214                 assert (comp_result > 0);
215                 if (n->right == NULL) {
216                     n->right = inserted_node;
217                     break;
218                 } else {
219                     n = n->right;
220                 }
221             }
222         }
223         inserted_node->parent = n;
224     }
225     insert_case1(t, inserted_node);
226     verify_properties(t);
227 }
228 void insert_case1(rbtree t, node n) {
229     if (n->parent == NULL)
230         n->color = BLACK;
231     else
232         insert_case2(t, n);
233 }
234 void insert_case2(rbtree t, node n) {
235     if (node_color(n->parent) == BLACK)
236         return; /* Tree is still valid */
237     else
238         insert_case3(t, n);
239 }
240 void insert_case3(rbtree t, node n) {
241     if (node_color(uncle(n)) == RED) {
242         n->parent->color = BLACK;
243         uncle(n)->color = BLACK;
244         grandparent(n)->color = RED;
245         insert_case1(t, grandparent(n));
246     } else {
247         insert_case4(t, n);
248     }
249 }
250 void insert_case4(rbtree t, node n) {
251     if (n == n->parent->right && n->parent == grandparent(n)->left) {
252         rotate_left(t, n->parent);
253         n = n->left;
254     } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
255         rotate_right(t, n->parent);
256         n = n->right;
257     }
258     insert_case5(t, n);
259 }
260 void insert_case5(rbtree t, node n) {
261     n->parent->color = BLACK;
262     grandparent(n)->color = RED;
263     if (n == n->parent->left && n->parent == grandparent(n)->left) {
264         rotate_right(t, grandparent(n));
265     } else {
266         assert (n == n->parent->right && n->parent == grandparent(n)->right);
267         rotate_left(t, grandparent(n));
268     }
269 }
270 void rbtree_delete(rbtree t, void* key, compare_func compare) {
271     node child;
272     node n = lookup_node(t, key, compare);
273     if (n == NULL) return;  /* Key not found, do nothing */
274     if (n->left != NULL && n->right != NULL) {
275         /* Copy key/value from predecessor and then delete it instead */
276         node pred = maximum_node(n->left);
277         n->key   = pred->key;
278         n->value = pred->value;
279         n = pred;
280     }
281 
282     assert(n->left == NULL || n->right == NULL);
283     child = n->right == NULL ? n->left  : n->right;
284     if (node_color(n) == BLACK) {
285         n->color = node_color(child);
286         delete_case1(t, n);
287     }
288     replace_node(t, n, child);
289     if (n->parent == NULL && child != NULL) // root should be black
290         child->color = BLACK;
291     free(n);
292 
293     verify_properties(t);
294 }
295 static node maximum_node(node n) {
296     assert (n != NULL);
297     while (n->right != NULL) {
298         n = n->right;
299     }
300     return n;
301 }
302 void delete_case1(rbtree t, node n) {
303     if (n->parent == NULL)
304         return;
305     else
306         delete_case2(t, n);
307 }
308 void delete_case2(rbtree t, node n) {
309     if (node_color(sibling(n)) == RED) {
310         n->parent->color = RED;
311         sibling(n)->color = BLACK;
312         if (n == n->parent->left)
313             rotate_left(t, n->parent);
314         else
315             rotate_right(t, n->parent);
316     }
317     delete_case3(t, n);
318 }
319 void delete_case3(rbtree t, node n) {
320     if (node_color(n->parent) == BLACK &&
321         node_color(sibling(n)) == BLACK &&
322         node_color(sibling(n)->left) == BLACK &&
323         node_color(sibling(n)->right) == BLACK)
324     {
325         sibling(n)->color = RED;
326         delete_case1(t, n->parent);
327     }
328     else
329         delete_case4(t, n);
330 }
331 void delete_case4(rbtree t, node n) {
332     if (node_color(n->parent) == RED &&
333         node_color(sibling(n)) == BLACK &&
334         node_color(sibling(n)->left) == BLACK &&
335         node_color(sibling(n)->right) == BLACK)
336     {
337         sibling(n)->color = RED;
338         n->parent->color = BLACK;
339     }
340     else
341         delete_case5(t, n);
342 }
343 void delete_case5(rbtree t, node n) {
344     if (n == n->parent->left &&
345         node_color(sibling(n)) == BLACK &&
346         node_color(sibling(n)->left) == RED &&
347         node_color(sibling(n)->right) == BLACK)
348     {
349         sibling(n)->color = RED;
350         sibling(n)->left->color = BLACK;
351         rotate_right(t, sibling(n));
352     }
353     else if (n == n->parent->right &&
354              node_color(sibling(n)) == BLACK &&
355              node_color(sibling(n)->right) == RED &&
356              node_color(sibling(n)->left) == BLACK)
357     {
358         sibling(n)->color = RED;
359         sibling(n)->right->color = BLACK;
360         rotate_left(t, sibling(n));
361     }
362     delete_case6(t, n);
363 }
364 void delete_case6(rbtree t, node n) {
365     sibling(n)->color = node_color(n->parent);
366     n->parent->color = BLACK;
367     if (n == n->parent->left) {
368         assert (node_color(sibling(n)->right) == RED);
369         sibling(n)->right->color = BLACK;
370         rotate_left(t, n->parent);
371     }
372     else
373     {
374         assert (node_color(sibling(n)->left) == RED);
375         sibling(n)->left->color = BLACK;
376         rotate_right(t, n->parent);
377     }
378 }


hijacker
hijacker
hijacker
hijacker

rbtree.h

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
14 */
15 
16 #ifndef _RBTREE_H_
17 
18 enum rbtree_node_color { RED, BLACK };
19 
20 typedef struct rbtree_node_t {
21     void* key;
22     void* value;
23     struct rbtree_node_t* left;
24     struct rbtree_node_t* right;
25     struct rbtree_node_t* parent;
26     enum rbtree_node_color color;
27 } *rbtree_node;
28 
29 typedef struct rbtree_t {
30     rbtree_node root;
31 } *rbtree;
32 
33 typedef int (*compare_func)(void* left, void* right);
34 
35 rbtree rbtree_create();
36 void* rbtree_lookup(rbtree t, void* key, compare_func compare);
37 void rbtree_insert(rbtree t, void* key, void* value, compare_func compare);
38 void rbtree_delete(rbtree t, void* key, compare_func compare);
39 
40 #endif


hijacker
hijacker
hijacker
hijacker

build.log

1 /tmp/litprog5626665/rbtree.c: In function 'rbtree_delete':
2 /tmp/litprog5626665/rbtree.c:289:45: error: expected expression before '/' token
3 /tmp/litprog5626665/rbtree.c: At top level:
4 /tmp/litprog5626665/rbtree.c:82:6: warning: 'verify_property_1' defined but not used [-Wunused-function]
5 /tmp/litprog5626665/rbtree.c:88:6: warning: 'verify_property_2' defined but not used [-Wunused-function]
6 /tmp/litprog5626665/rbtree.c:94:6: warning: 'verify_property_4' defined but not used [-Wunused-function]
7 /tmp/litprog5626665/rbtree.c:104:6: warning: 'verify_property_5' defined but not used [-Wunused-function]


hijacker
hijacker
hijacker
hijacker

testmain.c

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567
14 */
15 
16 #include "rbtree.h"
17 #include <stdio.h>
18 #include <assert.h>
19 #include <stdlib.h> /* rand() */
20 
21 static int compare_int(void* left, void* right);
22 static void print_tree(rbtree t);
23 static void print_tree_helper(rbtree_node n, int indent);
24 
25 int compare_int(void* leftp, void* rightp) {
26     int left = (int)leftp;
27     int right = (int)rightp;
28     if (left < right) 
29         return -1;
30     else if (left > right)
31         return 1;
32     else {
33         assert (left == right);
34         return 0;
35     }
36 }
37 
38 #define INDENT_STEP  4
39 
40 void print_tree_helper(rbtree_node n, int indent);
41 
42 void print_tree(rbtree t) {
43     print_tree_helper(t->root, 0);
44     puts("");
45 }
46 
47 void print_tree_helper(rbtree_node n, int indent) {
48     int i;
49     if (n == NULL) {
50         fputs("<empty tree>", stdout);
51         return;
52     }
53     if (n->right != NULL) {
54         print_tree_helper(n->right, indent + INDENT_STEP);
55     }
56     for(i=0; i<indent; i++)
57         fputs(" ", stdout);
58     if (n->color == BLACK)
59         printf("%d\n", (int)n->key);
60     else
61         printf("<%d>\n", (int)n->key);
62     if (n->left != NULL) {
63         print_tree_helper(n->left, indent + INDENT_STEP);
64     }
65 }
66 
67 int main() {
68     int i;
69     rbtree t = rbtree_create();
70     print_tree(t);
71 
72     for(i=0; i<5000; i++) {
73         int x = rand() % 10000;
74         int y = rand() % 10000;
75 #ifdef TRACE
76         print_tree(t);
77         printf("Inserting %d -> %d\n\n", x, y);
78 #endif
79         rbtree_insert(t, (void*)x, (void*)y, compare_int);
80         assert(rbtree_lookup(t, (void*)x, compare_int) == (void*)y);
81     }
82     for(i=0; i<60000; i++) {
83         int x = rand() % 10000;
84 #ifdef TRACE
85         print_tree(t);
86         printf("Deleting key %d\n\n", x);
87 #endif
88         rbtree_delete(t, (void*)x, compare_int);
89     }
90     return 0;
91 }


hijacker
hijacker
hijacker
hijacker