mem: add memends_str() helper for symmetry
[ccan] / junkcode / dongre.avinash@gmail.com-clibutils / src / c_rb.c
1 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **\r
2  *  This file is part of clib library\r
3  *  Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )\r
4  *\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
11  * \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
14  * \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
21  *  THE SOFTWARE.\r
22  ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/\r
23 \r
24 #include "c_lib.h"\r
25 \r
26 #include <stdio.h>\r
27 #include <string.h>\r
28 #include <assert.h>\r
29 \r
30 #define rb_sentinel &pTree->sentinel\r
31 \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
39 \r
40 \r
41 static void\r
42 pvt_left_rotate(struct clib_rb *pTree, struct clib_rb_node *x){\r
43     struct clib_rb_node *y;\r
44     y = x->right;\r
45     x->right = y->left;\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
50     if (x->parent){\r
51         if (x == x->parent->left)\r
52             x->parent->left = y;\r
53         else\r
54             x->parent->right = y;\r
55     }\r
56     else\r
57         pTree->root = y;\r
58     y->left = x;\r
59     if (x != rb_sentinel)\r
60         x->parent = y;\r
61 }\r
62 static void\r
63 pvt_right_rotate(struct clib_rb *pTree, struct clib_rb_node *x) {\r
64     struct clib_rb_node *y = x->left;\r
65     x->left = y->right;\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
70     if (x->parent) {\r
71         if (x == x->parent->right)\r
72             x->parent->right = y;\r
73         else\r
74             x->parent->left = y;\r
75     }\r
76     else\r
77         pTree->root = y;\r
78     y->right = x;\r
79     if (x != rb_sentinel)\r
80         x->parent = y;\r
81 }\r
82 \r
83 struct clib_rb*\r
84 new_clib_rb(clib_compare fn_c,clib_destroy fn_ed, clib_destroy fn_vd ){\r
85 \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
89 \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
98 \r
99     return pTree;\r
100 }\r
101 static void\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
111             } else {\r
112                 if (x == x->parent->right){\r
113                     x = x->parent;\r
114                     pvt_left_rotate (pTree, x);\r
115                 }\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
119             }\r
120         } else {\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
127             } else {\r
128                 if (x == x->parent->left) {\r
129                     x = x->parent;\r
130                     pvt_right_rotate (pTree, x);\r
131                 }\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
135             }\r
136         }\r
137     }\r
138     pTree->root->color = clib_black;\r
139 }\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
143 \r
144     while (x != rb_sentinel) {\r
145         int c = 0;\r
146         void *cur_key ;\r
147         get_raw_clib_object ( x->key, &cur_key );\r
148         c = pTree->compare_fn (key, cur_key);\r
149         free ( cur_key );\r
150         if (c == 0) {\r
151             break;\r
152         } else {\r
153             x = c < 0 ? x->left : x->right;\r
154         }\r
155     }\r
156     if ( x == rb_sentinel )\r
157         return (struct clib_rb_node*)0 ;\r
158 \r
159     return x;\r
160 }\r
161 \r
162 clib_error  \r
163 insert_clib_rb(struct clib_rb *pTree, void *k, size_t key_size, void *v, size_t value_size) {\r
164 \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
169 \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
173 \r
174     x->left    = rb_sentinel;\r
175     x->right   = rb_sentinel;\r
176     x->color   = clib_red;\r
177 \r
178     x->key     = new_clib_object ( k, key_size );\r
179     if ( v ) {\r
180         x->value   = new_clib_object ( v, value_size );\r
181     } else {\r
182         x->value =  (struct clib_object*)0;\r
183     }\r
184 \r
185     y = pTree->root;\r
186     z = (struct clib_rb_node*)0 ;\r
187 \r
188     while (y != rb_sentinel) {\r
189         int c = 0;\r
190         void *cur_key;\r
191                 void* new_key;\r
192 \r
193         get_raw_clib_object ( y->key, &cur_key );\r
194         get_raw_clib_object ( x->key, &new_key );\r
195 \r
196         c = (pTree->compare_fn) ( new_key , cur_key);\r
197         free ( cur_key );\r
198         free ( new_key );\r
199         if (c == 0) {\r
200             /* TODO : Delete node here */\r
201             return CLIB_RBTREE_KEY_DUPLICATE;\r
202         }\r
203         z = y;\r
204         if ( c < 0 )\r
205             y = y->left;\r
206         else\r
207             y = y->right;\r
208     }    \r
209     x->parent = z;\r
210     if (z) {\r
211         int c = 0;\r
212         void *cur_key;\r
213                 void* new_key;\r
214         get_raw_clib_object ( z->key, &cur_key );\r
215         get_raw_clib_object ( x->key, &new_key );\r
216 \r
217         c = pTree->compare_fn( new_key, cur_key);\r
218         free ( cur_key );\r
219         free ( new_key );\r
220         if (c < 0) {\r
221             z->left = x;\r
222         } else {\r
223             z->right = x;\r
224         }\r
225     }\r
226     else\r
227         pTree->root = x;\r
228 \r
229     pvt_rb_insert_fixup (pTree, x);\r
230 \r
231     debug_verify_properties ( pTree);\r
232     return rc;\r
233 }\r
234 static void\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
244             }\r
245             if (w->left->color == clib_black && w->right->color == clib_black) {\r
246                 w->color = clib_red;\r
247                 x = x->parent;\r
248             } else {\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
254                 }\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
259                 x = pTree->root;\r
260             }\r
261         } else {\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
268             }\r
269             if (w->right->color == clib_black && w->left->color == clib_black) {\r
270                 w->color = clib_red;\r
271                 x = x->parent;\r
272             } else {\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
278                 }\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
283                 x = pTree->root;\r
284             }\r
285         }\r
286     }\r
287     x->color = clib_black;\r
288 }\r
289 \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
294 \r
295     if (z->left == rb_sentinel || z->right == rb_sentinel)\r
296         y = z;\r
297     else {\r
298         y = z->right;\r
299         while (y->left != rb_sentinel)\r
300             y = y->left;\r
301     }\r
302     if (y->left != rb_sentinel)\r
303         x = y->left;\r
304     else\r
305         x = y->right;\r
306 \r
307     x->parent = y->parent;\r
308     if (y->parent)\r
309     {\r
310         if (y == y->parent->left)\r
311             y->parent->left = x;\r
312         else\r
313             y->parent->right = x;\r
314     }\r
315     else\r
316         pTree->root = x;\r
317     if (y != z) {\r
318         struct clib_object* tmp;\r
319         tmp    = z->key;\r
320         z->key = y->key;\r
321         y->key = tmp;\r
322 \r
323         tmp      = z->value;\r
324         z->value = y->value;\r
325         y->value = tmp;\r
326     }\r
327     if (y->color == clib_black)\r
328         pvt_rb_remove_fixup (pTree, x);\r
329 \r
330     debug_verify_properties ( pTree);\r
331     return y;\r
332 }\r
333 \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
337 \r
338     z = pTree->root;\r
339     while (z != rb_sentinel) {\r
340         int c = 0;\r
341         void *cur_key;\r
342         get_raw_clib_object ( z->key, &cur_key );\r
343         c = pTree->compare_fn (key, cur_key);\r
344         free ( cur_key );\r
345         if ( c == 0) {\r
346             break;\r
347         }\r
348         else {\r
349             z = ( c < 0) ? z->left : z->right;\r
350         }\r
351     }\r
352     if (z == rb_sentinel)\r
353         return (struct clib_rb_node*)0 ;\r
354     return pvt_remove_clib_rb(pTree, z );\r
355 }\r
356 static void\r
357 pvt_delete_clib_rb_node (struct clib_rb *pTree, struct clib_rb_node *x ) {\r
358 \r
359     void *key;\r
360         void *value;\r
361 \r
362     if ( pTree->destruct_k_fn ) {\r
363         get_raw_clib_object ( x->key, &key );\r
364         pTree->destruct_k_fn ( key );\r
365     }\r
366     delete_clib_object( x->key );\r
367 \r
368     if ( x->value ) {\r
369         if ( pTree->destruct_v_fn ) {\r
370             get_raw_clib_object ( x->value, &value);\r
371             pTree->destruct_v_fn ( value );\r
372         }\r
373         delete_clib_object( x->value );\r
374     }\r
375 }\r
376 \r
377 clib_error  \r
378 delete_clib_rb(struct clib_rb *pTree) {\r
379 \r
380     clib_error rc = CLIB_ERROR_SUCCESS;\r
381     struct clib_rb_node *z = pTree->root;\r
382 \r
383     while (z != rb_sentinel) {\r
384         if (z->left != rb_sentinel)\r
385             z = z->left;\r
386         else if (z->right != rb_sentinel)\r
387             z = z->right;\r
388         else {\r
389             pvt_delete_clib_rb_node ( pTree, z );\r
390             if (z->parent) {\r
391                 z = z->parent;\r
392                 if (z->left != rb_sentinel){\r
393                     free ( z->left );\r
394                     z->left = rb_sentinel;\r
395                 }else if (z->right != rb_sentinel){\r
396                     free ( z->right );\r
397                     z->right = rb_sentinel;\r
398                 }\r
399             } else {\r
400                 free ( z );\r
401                 z = rb_sentinel;\r
402             }\r
403         }\r
404     }\r
405     free ( pTree );\r
406     return rc;\r
407 }\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
411                 x = x->left;\r
412         return x;\r
413 }\r
414 \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
418                 x = x->right;\r
419         return x;\r
420 }\r
421 \r
422 \r
423 clib_bool \r
424 empty_clib_rb(struct clib_rb *pTree) {\r
425     if ( pTree->root != rb_sentinel )\r
426         return clib_true;\r
427     return clib_false;\r
428 }\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
434         \r
435         if ( x  == maximum_clib_rb(pTree,pTree->root)) \r
436                 return (struct clib_rb_node*)0;\r
437 \r
438         y = x->parent;\r
439         while ( y != rb_sentinel && x == y->right ){\r
440                 x = y;\r
441                 y = y->parent;\r
442         }\r
443         return y;\r
444 }\r
445 \r
446 \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
452 }\r
453 \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
459 }\r
460 \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
463 }\r
464 \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
467 }\r
468 \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
474     }\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
478 }\r
479 \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
483 }\r
484 \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
487         black_count++;\r
488     }\r
489     if (n == rb_sentinel) {\r
490         if (*path_black_count == -1) {\r
491             *path_black_count = black_count;\r
492         } else {\r
493             assert (black_count == *path_black_count);\r
494         }\r
495         return;\r
496     }\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
499 }\r
500 \r