]> git.meshlink.io Git - meshlink/blob - lib/rbl.c
Always close all sockets in terminate_connection().
[meshlink] / lib / rbl.c
1 /*
2     rbl.c -- red-black tree + linked list convenience
3     Copyright (C) 2000 Ivo Timmermans <itimmermans@bigfoot.com>,
4                   2000 Guus Sliepen <guus@sliepen.warande.net>
5
6     This program is free software; you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published by
8     the Free Software Foundation; either version 2 of the License, or
9     (at your option) any later version.
10
11     This program is distributed in the hope that it will be useful,
12     but WITHOUT ANY WARRANTY; without even the implied warranty of
13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14     GNU General Public License for more details.
15
16     You should have received a copy of the GNU General Public License
17     along with this program; if not, write to the Free Software
18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19
20     $Id: rbl.c,v 1.1.2.12 2000/11/24 23:12:59 guus Exp $
21 */
22
23 #include "config.h"
24
25 #include <stdlib.h>
26 #include <xalloc.h>
27
28 #include "rbl.h"
29 #include <system.h>
30
31 /* Allocate a new rbl node */
32 rbl_t *new_rbl()
33 {
34   return (rbl_t *)xmalloc_and_zero(sizeof(rbl_t));
35 }
36
37 /* Free a rbl node */
38 void free_rbl(rbl_t *rbl)
39 {
40   if(rbl->data && rbl->tree->delete)
41     rbl->tree->delete(rbl->data);
42   free(rbl);
43 }
44
45 /* Allocate a new rbltree header */
46 rbltree_t *new_rbltree(rbl_compare_t compare, rbl_action_t delete)
47 {
48   rbltree_t *tree;
49
50   tree = (rbltree_t *)xmalloc_and_zero(sizeof(rbltree_t));
51   if(tree)
52     {
53       tree->compare = compare;
54       tree->delete = delete;
55     }
56   
57   return tree;
58 }
59
60 /* Free a rbltree header */
61 void free_rbltree(rbltree_t *tree)
62 {
63   free(tree);
64 }
65
66 /* Search closest match in the tree */
67 rbl_t *rbl_search_closest_rbl(rbltree_t *tree, void *data)
68 {
69   rbl_t *rbl, *next;
70   int result;
71
72   next = rbl = tree->top;
73   
74   while(next)
75     {
76       rbl = next;
77       
78       result = tree->compare(data, rbl->data);
79
80       if(result < 0)
81         next = rbl->left;
82       else if(result > 0)
83         next = rbl->right;
84       else
85         break;
86     }
87     
88   return rbl;
89 }
90
91 /* Search closest match in the tree */
92 rbl_t *rbl_search_closest_greater_rbl(rbltree_t *tree, void *data)
93 {
94   rbl_t *rbl;
95
96   rbl = rbl_search_closest_rbl(tree, data);
97
98   if(rbl)
99     {
100       if(tree->compare(data, rbl->data) > 0)
101         rbl = rbl->next;
102     }
103     
104   return rbl;
105 }
106
107 /* Search closest match in the tree */
108 rbl_t *rbl_search_closest_smaller_rbl(rbltree_t *tree, void *data)
109 {
110   rbl_t *rbl;
111
112   rbl = rbl_search_closest_rbl(tree, data);
113
114   if(rbl)
115     {
116       if(tree->compare(data, rbl->data) < 0)
117         rbl = rbl->next;
118     }
119     
120   return rbl;
121 }
122
123 void *rbl_search_closest(rbltree_t *tree, void *data)
124 {
125   rbl_t *rbl;
126   
127   rbl = rbl_search_closest_rbl(tree, data);
128
129   if(rbl)
130     return rbl->data;
131   else
132     return NULL;
133 }
134
135 void *rbl_search_closest_greater(rbltree_t *tree, void *data)
136 {
137   rbl_t *rbl;
138   
139   rbl = rbl_search_closest_greater_rbl(tree, data);
140
141   if(rbl)
142     return rbl->data;
143   else
144     return NULL;
145 }
146
147 void *rbl_search_closest_smaller(rbltree_t *tree, void *data)
148 {
149   rbl_t *rbl;
150   
151   rbl = rbl_search_closest_smaller_rbl(tree, data);
152
153   if(rbl)
154     return rbl->data;
155   else
156     return NULL;
157 }
158
159 /* Search exact match or return NULL pointer */
160 rbl_t *rbl_search_rbl(rbltree_t *tree, void *data)
161 {
162   rbl_t *rbl;
163   int result;
164
165   rbl = tree->top;
166   
167   while(rbl)
168     {
169       result = tree->compare(data, rbl->data);
170
171       if(result < 0)
172         rbl = rbl->left;
173       else if(result > 0)
174         rbl = rbl->right;
175       else
176         return rbl;
177     }
178
179   return NULL;
180 }
181
182 void *rbl_search(rbltree_t *tree, void *data)
183 {
184   rbl_t *rbl;
185
186   rbl = rbl_search_rbl(tree, data);
187
188   if(rbl)
189     return rbl->data;
190   else
191     return NULL;  
192 }
193
194 /* Red-black tree operations taken from Introduction to Algorithms,
195    Cormen, Leiserson & Rivest, chapter 14.
196 */
197
198 void rbl_left_rotate(rbl_t *x)
199 {
200   rbl_t *y;
201   
202   y = x->right;
203   x->right = y->left;
204
205   if(y->left)
206     y->left->parent = x;
207
208   y->parent = x->parent;
209   
210   if(!x->parent)
211     x->tree->top = y;
212   else
213     if(x == x->parent->left)
214       x->parent->left = y;
215     else
216       x->parent->right = y;
217
218   y->left = x;
219   x->parent = y;      
220 }
221
222 void rbl_right_rotate(rbl_t *y)
223 {
224   rbl_t *x;
225
226   x = y->left;
227   y->left = x->right;
228
229   if(x->right)
230     x->right->parent = y;
231
232   x->parent = y->parent;
233   
234   if(!y->parent)
235     y->tree->top = x;
236   else
237     if(y == y->parent->right)
238       y->parent->right = x;
239     else
240       y->parent->left = x;
241   
242   x->right = y;
243   y->parent = x;      
244 }
245
246 /* Insert a node into the rbl tree */
247 rbl_t *rbl_insert_rbl(rbltree_t *tree, rbl_t *rbl)
248 {
249   rbl_t *closest, *x, *y;
250   int result;
251   
252   rbl->tree = tree;
253
254   /* Binary tree and linked list insert */
255   
256   if(tree->top)
257     {
258       closest = rbl_search_closest_rbl(tree, rbl->data);
259       result = tree->compare(rbl->data, closest->data);
260       if(result < 0)
261         {
262           closest->left = rbl;
263
264           rbl->prev = closest->prev;
265           rbl->next = closest;
266           closest->prev = rbl;
267
268           if(rbl->prev)
269             rbl->prev->next = rbl;
270           else
271             tree->head = rbl;
272         }
273       else if(result > 0)
274         {
275           closest->right = rbl;
276
277           rbl->next = closest->next;
278           rbl->prev = closest;
279           closest->next = rbl;
280
281           if(rbl->next)
282             rbl->next->prev = rbl;
283           else
284             tree->tail = rbl;
285         }
286       else
287         return closest;         /* Ofcourse, we cannot add two identical things */
288
289       rbl->parent = closest;
290     }
291   else
292     {
293       tree->top = rbl;
294       tree->head = rbl;
295       tree->tail = rbl;
296     }
297
298   /* Red-black part of insert */
299   
300   x = rbl;
301   x->color = RBL_RED;
302   
303   while(x != tree->top && x->parent->color == RBL_RED)
304     {
305       if(x->parent == x->parent->parent->left)
306         {
307           y = x->parent->parent->right;
308           if(y && y->color == RBL_RED)
309             {
310               x->parent->color = RBL_BLACK;
311               y->color = RBL_BLACK;
312               x->parent->parent->color = RBL_RED;
313               x = x->parent->parent;
314             }
315           else          
316             {
317               if(x == x->parent->right)
318                 {
319                   x = x->parent;
320                   rbl_left_rotate(x);
321                 }
322               x->parent->color = RBL_BLACK;
323               x->parent->parent->color = RBL_RED;
324               rbl_right_rotate(x->parent->parent);
325             }
326         }
327       else
328         {
329           y = x->parent->parent->left;
330           if(y && y->color == RBL_RED)
331             {
332               x->parent->color = RBL_BLACK;
333               y->color = RBL_BLACK;
334               x->parent->parent->color = RBL_RED;
335               x = x->parent->parent;
336             }
337           else          
338             {
339               if(x == x->parent->left)
340                 {
341                   x = x->parent;
342                   rbl_right_rotate(x);
343                 }
344               x->parent->color = RBL_BLACK;
345               x->parent->parent->color = RBL_RED;
346               rbl_left_rotate(x->parent->parent);
347             }
348         }
349     }
350   
351   tree->top->color = RBL_BLACK;
352   return rbl;
353 }
354
355 /* Create a new node and insert it into the tree */
356 rbl_t *rbl_insert(rbltree_t *tree, void *data)
357 {
358   rbl_t *rbl;
359   
360   rbl = new_rbl();
361   rbl->data = data;
362
363   if(rbl_insert_rbl(tree, rbl) == rbl)
364     return rbl;
365   else
366     {
367       free_rbl(rbl);
368       return NULL;
369     }
370 }
371
372 /* Restore red-black property after violation due to a deletion */
373 void rbl_delete_fixup(rbl_t *x)
374 {
375   rbl_t *w;
376   
377   while(x != x->tree->top && x->color == RBL_BLACK)
378     {
379       if(x == x->parent->left)
380         {
381           w = x->parent->right;
382           if(w->color == RBL_RED)
383             {
384               w->color = RBL_BLACK;
385               x->parent->color = RBL_RED;
386               rbl_left_rotate(x->parent);
387               w = x->parent->right;
388             }
389           if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
390             {
391               w->color = RBL_RED;
392               x = x->parent;
393             }
394           else
395             {
396               if(w->right->color == RBL_BLACK)
397                 {
398                   w->left->color = RBL_BLACK;
399                   w->color = RBL_RED;
400                   rbl_right_rotate(w);
401                   w = x->parent->right;
402                 }
403               w->color = x->parent->color;
404               x->parent->color = RBL_BLACK;
405               w->right->color = RBL_BLACK;
406               rbl_left_rotate(x->parent);
407               x = x->tree->top;
408             }
409         }
410       else
411         {
412           w = x->parent->left;
413           if(w->color == RBL_RED)
414             {
415               w->color = RBL_BLACK;
416               x->parent->color = RBL_RED;
417               rbl_right_rotate(x->parent);
418               w = x->parent->left;
419             }
420           if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
421             {
422               w->color = RBL_RED;
423               x = x->parent;
424             }
425           else
426             {
427               if(w->left->color == RBL_BLACK)
428                 {
429                   w->right->color = RBL_BLACK;
430                   w->color = RBL_RED;
431                   rbl_left_rotate(w);
432                   w = x->parent->left;
433                 }
434               w->color = x->parent->color;
435               x->parent->color = RBL_BLACK;
436               w->left->color = RBL_BLACK;
437               rbl_right_rotate(x->parent);
438               x = x->tree->top;
439             }
440         }
441     }
442   
443   x->color = RBL_BLACK;
444 }
445
446 /* Unlink node from the tree, but keep the node intact. */
447 rbl_t *rbl_unlink_rbl(rbl_t *rbl)
448 {
449   rbl_t *x, *y;
450
451   /* Binary tree delete */
452
453   if(rbl->left && rbl->right)
454     y = rbl->next;
455   else
456     y = rbl;
457     
458   if(y->left)
459     x = y->left;
460   else
461     x = y->right;
462     
463   if(x)
464     x->parent = y->parent;
465     
466   if(!y->parent)
467     rbl->tree->top = x;
468   else
469     if(y == y->parent->left)
470       y->parent->left = x;
471     else
472       y->parent->right = x;
473   
474   if(y != rbl)
475     {
476       y->left = rbl->left;
477       y->right = rbl->right;
478       y->parent = rbl->parent;
479       if(rbl == rbl->parent->left)
480         rbl->parent->left = y;
481       else
482         rbl->parent->right = y;
483     }
484
485   /* Linked list delete */
486   
487   if(rbl->prev)
488     rbl->prev->next = rbl->next;
489   else
490     rbl->tree->head = rbl->next;
491   
492   if(rbl->next)
493     rbl->next->prev = rbl->prev;
494   else
495     rbl->tree->tail = rbl->prev;
496
497   /* Red-black part of delete */
498   
499   if(y->color == RBL_BLACK && x)
500     rbl_delete_fixup(x);
501
502   return rbl;
503 }
504
505 /* Search node in tree and unlink it */
506 rbl_t *rbl_unlink(rbltree_t *tree, void *data)
507 {
508   rbl_t *rbl;
509   
510   rbl = rbl_search_rbl(tree, data);
511   
512   if(rbl)
513     rbl_unlink_rbl(rbl);
514
515   return rbl;
516 }
517
518 /* Unlink node and free it */
519 void rbl_delete_rbl(rbl_t *rbl)
520 {
521   rbl_unlink_rbl(rbl);
522   free_rbl(rbl);
523 }
524
525 /* Search node in tree, unlink and free it */
526 void rbl_delete(rbltree_t *tree, void *data)
527 {
528   rbl_t *rbl;
529
530   rbl = rbl_unlink(tree, data);
531
532   if(rbl)
533     free_rbl(rbl);
534 }
535
536 /* Optimized unlinking for a complete tree */
537 void rbl_unlink_rbltree(rbltree_t *tree)
538 {
539   rbl_t *rbl, *next;
540   
541   for(rbl = tree->head; rbl; rbl = next)
542     {
543       next = rbl->next;
544       rbl->tree = NULL;
545       rbl->parent = NULL;
546       rbl->left = NULL;
547       rbl->right = NULL;
548       rbl->prev = NULL;
549       rbl->next = NULL;
550     }
551     
552   tree->top = NULL;
553   tree->head = NULL;
554   tree->tail = NULL;
555 }
556
557 /* Optimized deletion for a complete tree */
558 void rbl_delete_rbltree(rbltree_t *tree)
559 {
560   rbl_t *rbl, *next;
561   
562   for(rbl = tree->head; rbl; rbl = next)
563     {
564       next = rbl->next;
565       free_rbl(rbl);
566     }
567
568   tree->top = NULL;
569   tree->head = NULL;
570   tree->tail = NULL;
571 }
572
573 /* Do action for each list entry (in order)
574    Deletion of entry for which action is called is allowed.
575  */
576 void rbl_foreach(rbltree_t *tree, rbl_action_t action)
577 {
578   rbl_t *rbl, *next;
579   
580   for(rbl = tree->head; rbl; rbl = next)
581     {
582       next = rbl->next;
583       action(rbl->data);
584     }
585 }
586
587 void rbl_foreach_rbl(rbltree_t *tree, rbl_action_rbl_t action)
588 {
589   rbl_t *rbl, *next;
590   
591   for(rbl = tree->head; rbl; rbl = next)
592     {
593       next = rbl->next;
594       action(rbl);
595     }
596 }