junkcode: upload via website.
[ccan] / junkcode / dongre.avinash@gmail.com-clibutils / test / t_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 <stdlib.h>\r
28 #include <string.h>\r
29 #include <assert.h>\r
30 \r
31 #define BLACK 0\r
32 #define RED   1\r
33 \r
34 #define rb_sentinel &tree->sentinel \r
35 \r
36 static void*\r
37     get_key ( struct clib_rb* tree, struct clib_rb_node* node) {\r
38         if ( node ) \r
39             return node->raw_data.key;\r
40         return (void*)0;\r
41     }\r
42 \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
46             return node->left;\r
47         return (struct clib_rb_node*)0 ;\r
48     }\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
52             return node->right;\r
53         return (struct clib_rb_node*)0 ;\r
54     }\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
60     }\r
61 \r
62 int \r
63 compare_rb_e ( void*  l, void* r ) {\r
64 \r
65     int left =  0;\r
66     int right = 0;\r
67 \r
68     if ( l ) left  = *(int*)l;\r
69     if ( r ) right = *(int*)r;\r
70 \r
71     if ( left < right ) return -1;\r
72     if ( left == right ) return 0;\r
73 \r
74     return 1;\r
75 }\r
76 \r
77 void \r
78 free_rb_e ( void* p ) {\r
79     if ( p ) {\r
80         free ( p );\r
81     }\r
82 }\r
83 \r
84 typedef struct test_data_tree {\r
85     int element;\r
86     int left;\r
87     int right;\r
88     int parent;\r
89     int color;\r
90 } TS;\r
91 \r
92 \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
98 \r
99     current_key = (void*)malloc ( tree->size_of_key);\r
100     memcpy ( current_key, key, tree->size_of_key);\r
101 \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
105             node = node->left;\r
106         } else {\r
107             node = node->right;\r
108         }\r
109     } \r
110     free ( current_key );\r
111     return node;\r
112 }\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
116 }\r
117 \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
123     if ( x )\r
124         *l = *(int*)get_key(tree,x);\r
125     x = get_right(tree,v);\r
126     if (x) \r
127         *r = *(int*)get_key(tree,x);\r
128     x = get_parent ( tree, v );\r
129     if (x)              \r
130         *p = *(int*)get_key(tree,x);\r
131 }\r
132 \r
133 static void \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
139     else\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
143     else\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
147     else\r
148         assert ((void* )0 == (void* )get_key(tree,get_parent(tree,v)));\r
149 }\r
150 \r
151 static void\r
152 test_all_elements(struct clib_rb* tree, TS ts[], int size) {\r
153     int i = 0;\r
154     for ( i = 0; i < size; i++) {\r
155         void* v = (void*)0;\r
156         int l,r,p,e;\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
160     }\r
161 }\r
162 \r
163 static struct clib_rb* \r
164 create_tree(TS ts[], int size) {\r
165     int i = 0;\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
169     }\r
170     return tree;\r
171 }\r
172 \r
173 \r
174 void \r
175 test_clib_rb() {\r
176     int size;\r
177     int size_after_delete;\r
178     int i = 0;\r
179     struct clib_rb* tree;\r
180     struct clib_rb_node* node;\r
181 \r
182     TS ts[] = {\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
186         {9,7,13,6,BLACK}\r
187     };\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
192         {9,7,0,6,BLACK}\r
193     };  \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
198     };  \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
203     };                  \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
208         {1,0,0,2,RED}\r
209     };                  \r
210 \r
211 \r
212     size = (sizeof(ts)/sizeof(TS));\r
213     tree = create_tree(ts,size);\r
214     test_all_elements(tree, ts, size); \r
215     {   \r
216         i = 13; \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
222             free ( node);\r
223         }\r
224         test_all_elements(tree, ts_delete_leaf_13, size_after_delete);\r
225     }\r
226     {\r
227         i = 9;  \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
232             free ( node);\r
233         }\r
234         test_all_elements(tree, ts_delete_9, size_after_delete);\r
235     }\r
236     {\r
237         i = 15; \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
242             free ( node);\r
243         }\r
244         test_all_elements(tree, ts_delete_15, size_after_delete);\r
245     }\r
246     {\r
247         int i = 1;\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
251     }\r
252     {\r
253       delete_clib_rb(tree);\r
254     }\r
255 }*/\r