1 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
\r
2 * This file is part of clib library
\r
3 * Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )
\r
5 * Permission is hereby granted, free of charge, to any person obtaining a copy
\r
6 * of this software and associated documentation files (the "Software"), to deal
\r
7 * in the Software without restriction, including without limitation the rights
\r
8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
\r
9 * copies of the Software, and to permit persons to whom the Software is
\r
10 * furnished to do so, subject to the following conditions:
\r
12 * The above copyright notice and this permission notice shall be included in
\r
13 * all copies or substantial portions of the Software.
\r
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
\r
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
\r
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
\r
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
\r
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
\r
22 ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/
\r
26 /*#include <stdio.h>
\r
34 #define rb_sentinel &tree->sentinel
\r
37 get_key ( struct clib_rb* tree, struct clib_rb_node* node) {
\r
39 return node->raw_data.key;
\r
43 static struct clib_rb_node*
\r
44 get_left (struct clib_rb* tree, struct clib_rb_node* node ) {
\r
45 if ( node->left != rb_sentinel && node->left != (struct clib_rb_node*)0 )
\r
47 return (struct clib_rb_node*)0 ;
\r
49 static struct clib_rb_node*
\r
50 get_right (struct clib_rb* tree, struct clib_rb_node* node ){
\r
51 if ( node->right != rb_sentinel && node->right != (struct clib_rb_node*)0 )
\r
53 return (struct clib_rb_node*)0 ;
\r
55 static struct clib_rb_node*
\r
56 get_parent ( struct clib_rb* tree,struct clib_rb_node* node ) {
\r
57 if ( node->parent != rb_sentinel && node->parent != (struct clib_rb_node*)0 )
\r
58 return node->parent;
\r
59 return (struct clib_rb_node*)0 ;
\r
63 compare_rb_e ( void* l, void* r ) {
\r
68 if ( l ) left = *(int*)l;
\r
69 if ( r ) right = *(int*)r;
\r
71 if ( left < right ) return -1;
\r
72 if ( left == right ) return 0;
\r
78 free_rb_e ( void* p ) {
\r
84 typedef struct test_data_tree {
\r
93 static struct clib_rb_node*
\r
94 pvt_find_clib_rb ( struct clib_rb* tree, clib_compare fn_c, void *key ) {
\r
95 struct clib_rb_node* node = tree->root;
\r
96 void* current_key = (void*)0;
\r
97 int compare_result = 0;
\r
99 current_key = (void*)malloc ( tree->size_of_key);
\r
100 memcpy ( current_key, key, tree->size_of_key);
\r
102 compare_result = (fn_c)(current_key, node->raw_data.key);
\r
103 while ((node != rb_sentinel) && (compare_result = (fn_c)(current_key, node->raw_data.key)) != 0 ){
\r
104 if ( compare_result < 0 ) {
\r
107 node = node->right;
\r
110 free ( current_key );
\r
113 struct clib_rb_node*
\r
114 find(struct clib_rb* tree, void *key ) {
\r
115 return pvt_find_clib_rb ( tree, tree->compare_fn, key );
\r
118 static void update_values ( void* v, int *l, int *r, int *p , int *e, struct clib_rb* tree ) {
\r
119 struct clib_rb_node *x;
\r
120 if ( get_key(tree,v))
\r
121 *e = *(int*)get_key (tree,v);
\r
122 x = get_left(tree,v);
\r
124 *l = *(int*)get_key(tree,x);
\r
125 x = get_right(tree,v);
\r
127 *r = *(int*)get_key(tree,x);
\r
128 x = get_parent ( tree, v );
\r
130 *p = *(int*)get_key(tree,x);
\r
134 test_each_elements(int l,int r, int p, int e,void* v, TS ts[], int i,
\r
135 struct clib_rb* tree) {
\r
136 assert ( ts[i].element == e);
\r
137 if (ts[i].left != 0 )
\r
138 assert ( ts[i].left == l);
\r
140 assert ((void* )0 == (void* )get_key(tree,get_left(tree,v)));
\r
141 if ( ts[i].right != 0 )
\r
142 assert (ts[i].right == r);
\r
144 assert ((void* )0 == (void* )get_key(tree,get_right(tree,v)));
\r
145 if (ts[i].parent != 0 )
\r
146 assert (ts[i].parent == p);
\r
148 assert ((void* )0 == (void* )get_key(tree,get_parent(tree,v)));
\r
152 test_all_elements(struct clib_rb* tree, TS ts[], int size) {
\r
154 for ( i = 0; i < size; i++) {
\r
155 void* v = (void*)0;
\r
157 v = find ( tree, &ts[i].element);
\r
158 update_values( v, &l,&r,&p,&e, tree);
\r
159 test_each_elements(l,r,p,e,v, ts, i, tree);
\r
163 static struct clib_rb*
\r
164 create_tree(TS ts[], int size) {
\r
166 struct clib_rb* tree = new_clib_rb( compare_rb_e,free_rb_e, (void*)0, sizeof(int),0);
\r
167 for ( i = 0; i < size; i++) {
\r
168 insert_clib_rb( tree, &(ts[i].element) ,(void*)0);
\r
177 int size_after_delete;
\r
179 struct clib_rb* tree;
\r
180 struct clib_rb_node* node;
\r
183 {15,6,18,0,BLACK},{6,3,9,15,RED},{18,17,20,15,BLACK},
\r
184 {3,2,4,6,BLACK},{7,0,0,9,RED},{17,0,0,18,RED},
\r
185 {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED},{13,0,0,9,RED},
\r
188 TS ts_delete_leaf_13[] = {
\r
189 {15,6,18,0,BLACK},{6,3,9,15,RED},{18,17,20,15,BLACK},
\r
190 {3,2,4,6,BLACK},{7,0,0,9,RED},{17,0,0,18,RED},
\r
191 {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED},
\r
194 TS ts_delete_9[] = {
\r
195 {15,6,18,0,BLACK},{6,3,7,15,RED},{18,17,20,15,BLACK},
\r
196 {3,2,4,6,RED},{7,0,0,6,RED},{17,0,0,18,RED},
\r
197 {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED}
\r
199 TS ts_delete_15[] = {
\r
200 {6,3,7,17,RED},{18,0,20,17,BLACK},
\r
201 {3,2,4,6,RED},{7,0,0,6,RED},{17,6,18,0,RED},
\r
202 {20,0,0,18,RED},{2,0,0,3,RED},{4,0,0,3,RED}
\r
204 TS ts_insert_1[] = {
\r
205 {6,3,17,0,BLACK},{18,0,20,17,BLACK},
\r
206 {3,2,4,6,RED},{7,0,0,17,RED},{17,7,18,6,RED},
\r
207 {20,0,0,18,RED},{2,1,0,3,BLACK},{4,0,0,3,BLACK},
\r
212 size = (sizeof(ts)/sizeof(TS));
\r
213 tree = create_tree(ts,size);
\r
214 test_all_elements(tree, ts, size);
\r
217 size = (sizeof(ts)/sizeof(TS));
\r
218 size_after_delete = (sizeof(ts_delete_leaf_13)/sizeof(TS));
\r
219 node = remove_clib_rb( tree, &i);
\r
220 if ( node != (struct clib_rb_node*)0 ) {
\r
221 free ( node->raw_data.key);
\r
224 test_all_elements(tree, ts_delete_leaf_13, size_after_delete);
\r
228 size_after_delete = (sizeof(ts_delete_9)/sizeof(TS));
\r
229 node = remove_clib_rb( tree, &i);
\r
230 if ( node != (struct clib_rb_node*)0 ) {
\r
231 free ( node->raw_data.key);
\r
234 test_all_elements(tree, ts_delete_9, size_after_delete);
\r
238 size_after_delete = (sizeof(ts_delete_15)/sizeof(TS));
\r
239 node = remove_clib_rb( tree, &i);
\r
240 if ( node != (struct clib_rb_node*)0 ) {
\r
241 free ( node->raw_data.key);
\r
244 test_all_elements(tree, ts_delete_15, size_after_delete);
\r
248 insert_clib_rb( tree, &i, (void*)0);
\r
249 size_after_delete = (sizeof(ts_insert_1)/sizeof(TS));
\r
250 test_all_elements(tree, ts_insert_1, size_after_delete);
\r
253 delete_clib_rb(tree);
\r