]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | |
2 | #include <zebra.h> | |
3 | #include "ospf6_bintree.h" | |
4 | ||
5 | static struct bintree_node * | |
6 | bintree_lookup_node_min (struct bintree_node *subroot) | |
7 | { | |
8 | struct bintree_node *node; | |
9 | ||
10 | if (subroot == NULL) | |
11 | return NULL; | |
12 | ||
13 | node = subroot; | |
14 | while (node->bl_left) | |
15 | node = node->bl_left; | |
16 | return node; | |
17 | } | |
18 | ||
19 | static struct bintree_node * | |
20 | bintree_lookup_node_max (struct bintree_node *subroot) | |
21 | { | |
22 | struct bintree_node *node; | |
23 | ||
24 | assert (subroot != NULL); | |
25 | node = subroot; | |
26 | while (node->bl_right) | |
27 | node = node->bl_right; | |
28 | return node; | |
29 | } | |
30 | ||
31 | void * | |
32 | bintree_lookup (void *data, struct bintree *tree) | |
33 | { | |
34 | int cmp; | |
35 | struct bintree_node *node; | |
36 | ||
37 | node = tree->root; | |
38 | ||
39 | while (node) | |
40 | { | |
41 | if (tree->cmp) | |
42 | cmp = (*tree->cmp) (node->data, data); | |
43 | else | |
44 | cmp = (node->data - data); | |
45 | ||
46 | if (cmp == 0) | |
47 | break; | |
48 | ||
49 | if (cmp > 0) | |
50 | node = node->bl_left; | |
51 | else /* if (cmp < 0) */ | |
52 | node = node->bl_right; | |
53 | } | |
54 | ||
55 | if (node) | |
56 | return node->data; | |
57 | ||
58 | return NULL; | |
59 | } | |
60 | ||
61 | void * | |
62 | bintree_lookup_min (struct bintree *tree) | |
63 | { | |
64 | struct bintree_node *node; | |
65 | node = bintree_lookup_node_min (tree->root); | |
66 | if (node == NULL) | |
67 | return NULL; | |
68 | return node->data; | |
69 | } | |
70 | ||
71 | void * | |
72 | bintree_lookup_max (struct bintree *tree) | |
73 | { | |
74 | struct bintree_node *node; | |
75 | node = bintree_lookup_node_max (tree->root); | |
76 | if (node == NULL) | |
77 | return NULL; | |
78 | return node->data; | |
79 | } | |
80 | ||
81 | int | |
82 | bintree_add (void *data, struct bintree *tree) | |
83 | { | |
84 | int cmp = 0; | |
85 | struct bintree_node *node, *parent; | |
86 | ||
87 | node = tree->root; | |
88 | parent = NULL; | |
89 | ||
90 | while (node) | |
91 | { | |
92 | if (tree->cmp) | |
93 | cmp = (*tree->cmp) (node->data, data); | |
94 | else | |
95 | cmp = (node->data - data); | |
96 | ||
97 | if (cmp == 0) | |
98 | break; | |
99 | ||
100 | parent = node; | |
101 | if (cmp > 0) | |
102 | node = node->bl_left; | |
103 | else /* if (cmp < 0) */ | |
104 | node = node->bl_right; | |
105 | } | |
106 | ||
107 | if (node) | |
108 | return -1; | |
109 | ||
110 | node = malloc (sizeof (struct bintree_node)); | |
111 | memset (node, 0, sizeof (struct bintree_node)); | |
112 | node->tree = tree; | |
113 | node->data = data; | |
114 | ||
115 | if (parent) | |
116 | { | |
117 | node->parent = parent; | |
118 | ||
119 | assert (cmp != 0); | |
120 | if (cmp > 0) | |
121 | { | |
122 | node->parent_link = BL_LEFT; | |
123 | parent->bl_left = node; | |
124 | } | |
125 | else /* if (cmp < 0) */ | |
126 | { | |
127 | node->parent_link = BL_RIGHT; | |
128 | parent->bl_right = node; | |
129 | } | |
130 | } | |
131 | else | |
132 | tree->root = node; | |
133 | ||
134 | tree->count++; | |
135 | return 0; | |
136 | } | |
137 | ||
138 | static void | |
139 | bintree_remove_nochild (struct bintree_node *node) | |
140 | { | |
141 | assert (node->bl_left == NULL && node->bl_right == NULL); | |
142 | ||
143 | if (node->parent == NULL) | |
144 | node->tree->root = NULL; | |
145 | else | |
146 | node->parent->link[node->parent_link] = NULL; | |
147 | } | |
148 | ||
149 | static void | |
150 | bintree_remove_onechild (struct bintree_node *node) | |
151 | { | |
152 | assert ((node->bl_left == NULL && node->bl_right != NULL) || | |
153 | (node->bl_left != NULL && node->bl_right == NULL)); | |
154 | ||
155 | if (node->bl_left) | |
156 | { | |
157 | if (node->parent == NULL) | |
158 | { | |
159 | node->tree->root = node->bl_left; | |
160 | node->bl_left->parent = NULL; | |
161 | } | |
162 | else | |
163 | { | |
164 | node->parent->link[node->parent_link] = node->bl_left; | |
165 | node->bl_left->parent = node->parent; | |
166 | node->bl_left->parent_link = node->parent_link; | |
167 | } | |
168 | } | |
169 | else if (node->bl_right) | |
170 | { | |
171 | if (node->parent == NULL) | |
172 | { | |
173 | node->tree->root = node->bl_right; | |
174 | node->bl_right->parent = NULL; | |
175 | } | |
176 | else | |
177 | { | |
178 | node->parent->link[node->parent_link] = node->bl_right; | |
179 | node->bl_right->parent = node->parent; | |
180 | node->bl_right->parent_link = node->parent_link; | |
181 | } | |
182 | } | |
183 | else | |
184 | assert (0); | |
185 | } | |
186 | ||
187 | int | |
188 | bintree_remove (void *data, struct bintree *tree) | |
189 | { | |
190 | int cmp; | |
191 | struct bintree_node *node; | |
192 | ||
193 | node = tree->root; | |
194 | ||
195 | while (node) | |
196 | { | |
197 | if (tree->cmp) | |
198 | cmp = (*tree->cmp) (node->data, data); | |
199 | else | |
200 | cmp = (node->data - data); | |
201 | ||
202 | if (cmp == 0) | |
203 | break; | |
204 | ||
205 | if (cmp > 0) | |
206 | node = node->bl_left; | |
207 | else /* if (cmp < 0) */ | |
208 | node = node->bl_right; | |
209 | } | |
210 | ||
211 | if (node == NULL) | |
212 | return -1; | |
213 | ||
214 | if (node->bl_left == NULL && node->bl_right == NULL) | |
215 | { | |
216 | bintree_remove_nochild (node); | |
217 | free (node); | |
218 | tree->count--; | |
219 | return 0; | |
220 | } | |
221 | ||
222 | if ((node->bl_left == NULL && node->bl_right != NULL) || | |
223 | (node->bl_left != NULL && node->bl_right == NULL)) | |
224 | { | |
225 | bintree_remove_onechild (node); | |
226 | free (node); | |
227 | tree->count--; | |
228 | return 0; | |
229 | } | |
230 | ||
231 | if (node->bl_left != NULL && node->bl_right != NULL) | |
232 | { | |
233 | struct bintree_node *successor; | |
234 | ||
235 | /* find successor of the removing node */ | |
236 | successor = bintree_lookup_node_min (node->bl_right); | |
237 | ||
238 | /* remove successor from tree */ | |
239 | if (successor->bl_right) | |
240 | bintree_remove_onechild (successor); | |
241 | else | |
242 | bintree_remove_nochild (successor); | |
243 | ||
244 | /* swap removing node with successor */ | |
245 | successor->parent = node->parent; | |
246 | successor->parent_link = node->parent_link; | |
247 | successor->bl_left = node->bl_left; | |
248 | successor->bl_right = node->bl_right; | |
249 | ||
250 | /* if the successor was the node->bl_right itself, | |
251 | bintree_remove_**child may touch node->bl_right, | |
252 | so only the successor->bl_right may be NULL | |
253 | by above assignment */ | |
254 | successor->bl_left->parent = successor; | |
255 | if (successor->bl_right) | |
256 | successor->bl_right->parent = successor; | |
257 | ||
258 | if (successor->parent == NULL) | |
259 | tree->root = successor; | |
260 | else | |
261 | successor->parent->link[successor->parent_link] = successor; | |
262 | ||
263 | free (node); | |
264 | tree->count--; | |
265 | return 0; | |
266 | } | |
267 | ||
268 | /* not reached */ | |
269 | return -1; | |
270 | } | |
271 | ||
272 | /* in-order traversal */ | |
273 | ||
274 | void | |
275 | bintree_head (struct bintree *tree, struct bintree_node *node) | |
276 | { | |
277 | struct bintree_node *head; | |
278 | ||
279 | head = bintree_lookup_node_min (tree->root); | |
280 | if (head == NULL) | |
281 | { | |
282 | node->parent = NULL; | |
283 | node->bl_left = NULL; | |
284 | node->bl_right = NULL; | |
285 | node->data = NULL; | |
286 | return; | |
287 | } | |
288 | ||
289 | node->tree = head->tree; | |
290 | node->parent = head->parent; | |
291 | node->parent_link = head->parent_link; | |
292 | node->bl_left = head->bl_left; | |
293 | node->bl_right = head->bl_right; | |
294 | node->data = head->data; | |
295 | } | |
296 | ||
297 | int | |
298 | bintree_end (struct bintree_node *node) | |
299 | { | |
300 | if (node->parent || node->bl_left || node->bl_right || node->data) | |
301 | return 0; | |
302 | return 1; | |
303 | } | |
304 | ||
305 | #define GOTO_PROCED_SUBTREE_TOP(node) \ | |
306 | while (node->parent && node->parent->bl_right && \ | |
307 | node->parent->bl_right->data == node->data) \ | |
308 | { \ | |
309 | node->data = node->parent->data; \ | |
310 | node->bl_left = node->parent->bl_left; \ | |
311 | node->bl_right = node->parent->bl_right; \ | |
312 | node->parent_link = node->parent->parent_link; \ | |
313 | node->parent = node->parent->parent; \ | |
314 | } | |
315 | ||
316 | void | |
317 | bintree_next (struct bintree_node *node) | |
318 | { | |
319 | struct bintree_node *next = NULL; | |
320 | ||
321 | /* if node have just been removed, current point should have just been | |
322 | replaced with its successor. that certainly will not be processed | |
323 | yet, so process it */ | |
324 | if (node->parent == NULL) | |
325 | { | |
326 | if (node->tree->root == NULL) | |
327 | { | |
328 | assert (node->tree->count == 0); | |
329 | node->parent = NULL; | |
330 | node->bl_left = NULL; | |
331 | node->bl_right = NULL; | |
332 | node->data = NULL; | |
333 | return; | |
334 | } | |
335 | else if (node->tree->root->data != node->data) | |
336 | next = node->tree->root; | |
337 | } | |
338 | else if (node->parent->link[node->parent_link] == NULL) | |
339 | { | |
340 | if (node->parent_link == BL_LEFT) | |
341 | next = node->parent; | |
342 | else | |
343 | { | |
344 | GOTO_PROCED_SUBTREE_TOP (node); | |
345 | next = node->parent; | |
346 | } | |
347 | } | |
348 | else if (node->parent->link[node->parent_link]->data != node->data) | |
349 | next = node->parent->link[node->parent_link]; | |
350 | ||
351 | if (next == NULL) | |
352 | { | |
353 | if (node->bl_right) | |
354 | next = bintree_lookup_node_min (node->bl_right); | |
355 | else | |
356 | { | |
357 | GOTO_PROCED_SUBTREE_TOP (node); | |
358 | next = node->parent; | |
359 | } | |
360 | } | |
361 | ||
362 | if (next) | |
363 | { | |
364 | node->tree = next->tree; | |
365 | node->parent = next->parent; | |
366 | node->parent_link = next->parent_link; | |
367 | node->bl_left = next->bl_left; | |
368 | node->bl_right = next->bl_right; | |
369 | node->data = next->data; | |
370 | } | |
371 | else | |
372 | { | |
373 | node->parent = NULL; | |
374 | node->bl_left = NULL; | |
375 | node->bl_right = NULL; | |
376 | node->data = NULL; | |
377 | } | |
378 | } | |
379 | ||
380 | struct bintree * | |
381 | bintree_create () | |
382 | { | |
383 | struct bintree *tree; | |
384 | ||
385 | tree = malloc (sizeof (struct bintree)); | |
386 | memset (tree, 0, sizeof (struct bintree)); | |
387 | ||
388 | return tree; | |
389 | } | |
390 | ||
391 | void | |
392 | bintree_delete (struct bintree *tree) | |
393 | { | |
394 | struct bintree_node node; | |
395 | ||
396 | for (bintree_head (tree, &node); ! bintree_end (&node); | |
397 | bintree_next (&node)) | |
398 | bintree_remove (node.data, tree); | |
399 | ||
400 | assert (tree->count == 0); | |
401 | free (tree); | |
402 | } | |
403 | ||
404 | int indent_num = 0; | |
405 | ||
406 | void | |
407 | bintree_print_sub (void (*print) (int, void *), struct bintree_node *subroot) | |
408 | { | |
409 | if (subroot == NULL) | |
410 | return; | |
411 | ||
412 | if (subroot->bl_right) | |
413 | { | |
414 | indent_num++; | |
415 | bintree_print_sub (print, subroot->bl_right); | |
416 | indent_num--; | |
417 | } | |
418 | ||
419 | (*print) (indent_num, subroot->data); | |
420 | ||
421 | if (subroot->bl_left) | |
422 | { | |
423 | indent_num++; | |
424 | bintree_print_sub (print, subroot->bl_left); | |
425 | indent_num--; | |
426 | } | |
427 | } | |
428 | ||
429 | void | |
430 | bintree_print (void (*print) (int, void *), struct bintree *tree) | |
431 | { | |
432 | indent_num = 0; | |
433 | bintree_print_sub (print, tree->root); | |
434 | } | |
435 | ||
436 |