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
30 #define rb_sentinel &pTree->sentinel
\r
32 static void debug_verify_properties(struct clib_rb*);
\r
33 static void debug_verify_property_1(struct clib_rb*,struct clib_rb_node*);
\r
34 static void debug_verify_property_2(struct clib_rb*,struct clib_rb_node*);
\r
35 static int debug_node_color(struct clib_rb*,struct clib_rb_node* n);
\r
36 static void debug_verify_property_4(struct clib_rb*,struct clib_rb_node*);
\r
37 static void debug_verify_property_5(struct clib_rb*,struct clib_rb_node*);
\r
38 static void debug_verify_property_5_helper(struct clib_rb*,struct clib_rb_node*,int,int*);
\r
42 pvt_left_rotate(struct clib_rb *pTree, struct clib_rb_node *x){
\r
43 struct clib_rb_node *y;
\r
46 if (y->left != rb_sentinel)
\r
47 y->left->parent = x;
\r
48 if (y != rb_sentinel)
\r
49 y->parent = x->parent;
\r
51 if (x == x->parent->left)
\r
52 x->parent->left = y;
\r
54 x->parent->right = y;
\r
59 if (x != rb_sentinel)
\r
63 pvt_right_rotate(struct clib_rb *pTree, struct clib_rb_node *x) {
\r
64 struct clib_rb_node *y = x->left;
\r
66 if (y->right != rb_sentinel)
\r
67 y->right->parent = x;
\r
68 if (y != rb_sentinel)
\r
69 y->parent = x->parent;
\r
71 if (x == x->parent->right)
\r
72 x->parent->right = y;
\r
74 x->parent->left = y;
\r
79 if (x != rb_sentinel)
\r
84 new_clib_rb(clib_compare fn_c,clib_destroy fn_ed, clib_destroy fn_vd ){
\r
86 struct clib_rb *pTree = (struct clib_rb*)malloc(sizeof(struct clib_rb));
\r
87 if ( pTree == (struct clib_rb*)0 )
\r
88 return (struct clib_rb*)0;
\r
90 pTree->compare_fn = fn_c;
\r
91 pTree->destruct_k_fn = fn_ed;
\r
92 pTree->destruct_v_fn = fn_vd;
\r
93 pTree->root = rb_sentinel;
\r
94 pTree->sentinel.left = rb_sentinel;
\r
95 pTree->sentinel.right = rb_sentinel;
\r
96 pTree->sentinel.parent = (struct clib_rb_node*)0 ;
\r
97 pTree->sentinel.color = clib_black;
\r
102 pvt_rb_insert_fixup( struct clib_rb *pTree, struct clib_rb_node *x ) {
\r
103 while (x != pTree->root && x->parent->color == clib_red) {
\r
104 if (x->parent == x->parent->parent->left) {
\r
105 struct clib_rb_node *y = x->parent->parent->right;
\r
106 if (y->color == clib_red) {
\r
107 x->parent->color = clib_black;
\r
108 y->color = clib_black;
\r
109 x->parent->parent->color = clib_red;
\r
110 x = x->parent->parent;
\r
112 if (x == x->parent->right){
\r
114 pvt_left_rotate (pTree, x);
\r
116 x->parent->color = clib_black;
\r
117 x->parent->parent->color = clib_red;
\r
118 pvt_right_rotate (pTree, x->parent->parent);
\r
121 struct clib_rb_node *y = x->parent->parent->left;
\r
122 if (y->color == clib_red) {
\r
123 x->parent->color = clib_black;
\r
124 y->color = clib_black;
\r
125 x->parent->parent->color = clib_red;
\r
126 x = x->parent->parent;
\r
128 if (x == x->parent->left) {
\r
130 pvt_right_rotate (pTree, x);
\r
132 x->parent->color = clib_black;
\r
133 x->parent->parent->color = clib_red;
\r
134 pvt_left_rotate (pTree, x->parent->parent);
\r
138 pTree->root->color = clib_black;
\r
140 struct clib_rb_node*
\r
141 find_clib_rb (struct clib_rb *pTree, void *key) {
\r
142 struct clib_rb_node *x = pTree->root;
\r
144 while (x != rb_sentinel) {
\r
147 get_raw_clib_object ( x->key, &cur_key );
\r
148 c = pTree->compare_fn (key, cur_key);
\r
153 x = c < 0 ? x->left : x->right;
\r
156 if ( x == rb_sentinel )
\r
157 return (struct clib_rb_node*)0 ;
\r
163 insert_clib_rb(struct clib_rb *pTree, void *k, size_t key_size, void *v, size_t value_size) {
\r
165 clib_error rc = CLIB_ERROR_SUCCESS;
\r
166 struct clib_rb_node *x;
\r
167 struct clib_rb_node *y;
\r
168 struct clib_rb_node *z;
\r
170 x = (struct clib_rb_node*)malloc (sizeof(struct clib_rb_node));
\r
171 if ( x == (struct clib_rb_node*)0 )
\r
172 return CLIB_ERROR_MEMORY;
\r
174 x->left = rb_sentinel;
\r
175 x->right = rb_sentinel;
\r
176 x->color = clib_red;
\r
178 x->key = new_clib_object ( k, key_size );
\r
180 x->value = new_clib_object ( v, value_size );
\r
182 x->value = (struct clib_object*)0;
\r
186 z = (struct clib_rb_node*)0 ;
\r
188 while (y != rb_sentinel) {
\r
193 get_raw_clib_object ( y->key, &cur_key );
\r
194 get_raw_clib_object ( x->key, &new_key );
\r
196 c = (pTree->compare_fn) ( new_key , cur_key);
\r
200 /* TODO : Delete node here */
\r
201 return CLIB_RBTREE_KEY_DUPLICATE;
\r
214 get_raw_clib_object ( z->key, &cur_key );
\r
215 get_raw_clib_object ( x->key, &new_key );
\r
217 c = pTree->compare_fn( new_key, cur_key);
\r
229 pvt_rb_insert_fixup (pTree, x);
\r
231 debug_verify_properties ( pTree);
\r
235 pvt_rb_remove_fixup( struct clib_rb *pTree, struct clib_rb_node *x ) {
\r
236 while (x != pTree->root && x->color == clib_black) {
\r
237 if (x == x->parent->left) {
\r
238 struct clib_rb_node *w = x->parent->right;
\r
239 if (w->color == clib_red) {
\r
240 w->color = clib_black;
\r
241 x->parent->color = clib_red;
\r
242 pvt_left_rotate (pTree, x->parent);
\r
243 w = x->parent->right;
\r
245 if (w->left->color == clib_black && w->right->color == clib_black) {
\r
246 w->color = clib_red;
\r
249 if (w->right->color == clib_black) {
\r
250 w->left->color = clib_black;
\r
251 w->color = clib_red;
\r
252 pvt_right_rotate (pTree, w);
\r
253 w = x->parent->right;
\r
255 w->color = x->parent->color;
\r
256 x->parent->color = clib_black;
\r
257 w->right->color = clib_black;
\r
258 pvt_left_rotate (pTree, x->parent);
\r
262 struct clib_rb_node *w = x->parent->left;
\r
263 if (w->color == clib_red) {
\r
264 w->color = clib_black;
\r
265 x->parent->color = clib_red;
\r
266 pvt_right_rotate (pTree, x->parent);
\r
267 w = x->parent->left;
\r
269 if (w->right->color == clib_black && w->left->color == clib_black) {
\r
270 w->color = clib_red;
\r
273 if (w->left->color == clib_black) {
\r
274 w->right->color = clib_black;
\r
275 w->color = clib_red;
\r
276 pvt_left_rotate (pTree, w);
\r
277 w = x->parent->left;
\r
279 w->color = x->parent->color;
\r
280 x->parent->color = clib_black;
\r
281 w->left->color = clib_black;
\r
282 pvt_right_rotate (pTree, x->parent);
\r
287 x->color = clib_black;
\r
290 static struct clib_rb_node*
\r
291 pvt_remove_clib_rb(struct clib_rb *pTree, struct clib_rb_node *z ) {
\r
292 struct clib_rb_node *x = (struct clib_rb_node*)0 ;
\r
293 struct clib_rb_node *y = (struct clib_rb_node*)0 ;
\r
295 if (z->left == rb_sentinel || z->right == rb_sentinel)
\r
299 while (y->left != rb_sentinel)
\r
302 if (y->left != rb_sentinel)
\r
307 x->parent = y->parent;
\r
310 if (y == y->parent->left)
\r
311 y->parent->left = x;
\r
313 y->parent->right = x;
\r
318 struct clib_object* tmp;
\r
324 z->value = y->value;
\r
327 if (y->color == clib_black)
\r
328 pvt_rb_remove_fixup (pTree, x);
\r
330 debug_verify_properties ( pTree);
\r
334 struct clib_rb_node*
\r
335 remove_clib_rb (struct clib_rb *pTree, void *key) {
\r
336 struct clib_rb_node *z = (struct clib_rb_node*)0 ;
\r
339 while (z != rb_sentinel) {
\r
342 get_raw_clib_object ( z->key, &cur_key );
\r
343 c = pTree->compare_fn (key, cur_key);
\r
349 z = ( c < 0) ? z->left : z->right;
\r
352 if (z == rb_sentinel)
\r
353 return (struct clib_rb_node*)0 ;
\r
354 return pvt_remove_clib_rb(pTree, z );
\r
357 pvt_delete_clib_rb_node (struct clib_rb *pTree, struct clib_rb_node *x ) {
\r
362 if ( pTree->destruct_k_fn ) {
\r
363 get_raw_clib_object ( x->key, &key );
\r
364 pTree->destruct_k_fn ( key );
\r
366 delete_clib_object( x->key );
\r
369 if ( pTree->destruct_v_fn ) {
\r
370 get_raw_clib_object ( x->value, &value);
\r
371 pTree->destruct_v_fn ( value );
\r
373 delete_clib_object( x->value );
\r
378 delete_clib_rb(struct clib_rb *pTree) {
\r
380 clib_error rc = CLIB_ERROR_SUCCESS;
\r
381 struct clib_rb_node *z = pTree->root;
\r
383 while (z != rb_sentinel) {
\r
384 if (z->left != rb_sentinel)
\r
386 else if (z->right != rb_sentinel)
\r
389 pvt_delete_clib_rb_node ( pTree, z );
\r
392 if (z->left != rb_sentinel){
\r
394 z->left = rb_sentinel;
\r
395 }else if (z->right != rb_sentinel){
\r
397 z->right = rb_sentinel;
\r
408 struct clib_rb_node *
\r
409 minimum_clib_rb( struct clib_rb *pTree, struct clib_rb_node *x ) {
\r
410 while ( x->left != rb_sentinel)
\r
415 struct clib_rb_node *
\r
416 maximum_clib_rb( struct clib_rb *pTree, struct clib_rb_node *x ) {
\r
417 while ( x->right != rb_sentinel)
\r
424 empty_clib_rb(struct clib_rb *pTree) {
\r
425 if ( pTree->root != rb_sentinel )
\r
429 struct clib_rb_node*
\r
430 tree_successor(struct clib_rb *pTree, struct clib_rb_node *x) {
\r
431 struct clib_rb_node *y = (struct clib_rb_node*)0;
\r
432 if ( x->right != rb_sentinel)
\r
433 return minimum_clib_rb( pTree, x->right);
\r
435 if ( x == maximum_clib_rb(pTree,pTree->root))
\r
436 return (struct clib_rb_node*)0;
\r
439 while ( y != rb_sentinel && x == y->right ){
\r
447 void debug_verify_properties(struct clib_rb* t) {
\r
448 debug_verify_property_1(t,t->root);
\r
449 debug_verify_property_2(t,t->root);
\r
450 debug_verify_property_4(t,t->root);
\r
451 debug_verify_property_5(t,t->root);
\r
454 void debug_verify_property_1(struct clib_rb *pTree,struct clib_rb_node* n) {
\r
455 assert(debug_node_color(pTree,n) == clib_red || debug_node_color(pTree,n) == clib_black);
\r
456 if (n == rb_sentinel) return;
\r
457 debug_verify_property_1(pTree,n->left);
\r
458 debug_verify_property_1(pTree,n->right);
\r
461 void debug_verify_property_2(struct clib_rb *pTree,struct clib_rb_node* root) {
\r
462 assert(debug_node_color(pTree,root) == clib_black);
\r
465 int debug_node_color(struct clib_rb *pTree,struct clib_rb_node* n) {
\r
466 return n == rb_sentinel ? clib_black : n->color;
\r
469 void debug_verify_property_4(struct clib_rb *pTree,struct clib_rb_node* n) {
\r
470 if (debug_node_color(pTree,n) == clib_red) {
\r
471 assert (debug_node_color(pTree,n->left) == clib_black);
\r
472 assert (debug_node_color(pTree,n->right) == clib_black);
\r
473 assert (debug_node_color(pTree,n->parent) == clib_black);
\r
475 if (n == rb_sentinel) return;
\r
476 debug_verify_property_4(pTree,n->left);
\r
477 debug_verify_property_4(pTree,n->right);
\r
480 void debug_verify_property_5(struct clib_rb *pTree,struct clib_rb_node* root) {
\r
481 int black_count_path = -1;
\r
482 debug_verify_property_5_helper(pTree,root, 0, &black_count_path);
\r
485 void debug_verify_property_5_helper(struct clib_rb *pTree,struct clib_rb_node* n, int black_count, int* path_black_count) {
\r
486 if (debug_node_color(pTree,n) == clib_black) {
\r
489 if (n == rb_sentinel) {
\r
490 if (*path_black_count == -1) {
\r
491 *path_black_count = black_count;
\r
493 assert (black_count == *path_black_count);
\r
497 debug_verify_property_5_helper(pTree,n->left, black_count, path_black_count);
\r
498 debug_verify_property_5_helper(pTree,n->right, black_count, path_black_count);
\r