]> pd.if.org Git - zpackage/blob - lib/jsw/jsw_rbtree.c
use posix strdup in findpkg
[zpackage] / lib / jsw / jsw_rbtree.c
1 /*
2   Red Black balanced tree library
3
4     > Created (Julienne Walker): August 23, 2003
5     > Modified (Julienne Walker): March 14, 2008
6 */
7 #include "jsw_rbtree.h"
8
9 #include <stdlib.h>
10
11 #ifndef HEIGHT_LIMIT
12 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
13 #endif
14
15 typedef struct jsw_rbnode {
16   int                red;     /* Color (1=red, 0=black) */
17   void              *data;    /* User-defined content */
18   struct jsw_rbnode *link[2]; /* Left (0) and right (1) links */
19 } jsw_rbnode_t;
20
21 struct jsw_rbtree {
22   jsw_rbnode_t *root; /* Top of the tree */
23   cmp_f         cmp;  /* Compare two items */
24   dup_f         dup;  /* Clone an item (user-defined) */
25   rel_f         rel;  /* Destroy an item (user-defined) */
26   size_t        size; /* Number of items (user-defined) */
27 };
28
29 struct jsw_rbtrav {
30   jsw_rbtree_t *tree;               /* Paired tree */
31   jsw_rbnode_t *it;                 /* Current node */
32   jsw_rbnode_t *path[HEIGHT_LIMIT]; /* Traversal path */
33   size_t        top;                /* Top of stack */
34 };
35
36 /**
37   <summary>
38   Checks the color of a red black node
39   <summary>
40   <param name="root">The node to check</param>
41   <returns>1 for a red node, 0 for a black node</returns>
42   <remarks>For jsw_rbtree.c internal use only</remarks>
43 */
44 static int is_red ( jsw_rbnode_t *root )
45 {
46   return root != NULL && root->red == 1;
47 }
48
49 /**
50   <summary>
51   Performs a single red black rotation in the specified direction
52   This function assumes that all nodes are valid for a rotation
53   <summary>
54   <param name="root">The original root to rotate around</param>
55   <param name="dir">The direction to rotate (0 = left, 1 = right)</param>
56   <returns>The new root ater rotation</returns>
57   <remarks>For jsw_rbtree.c internal use only</remarks>
58 */
59 static jsw_rbnode_t *jsw_single ( jsw_rbnode_t *root, int dir )
60 {
61   jsw_rbnode_t *save = root->link[!dir];
62
63   root->link[!dir] = save->link[dir];
64   save->link[dir] = root;
65
66   root->red = 1;
67   save->red = 0;
68
69   return save;
70 }
71
72 /**
73   <summary>
74   Performs a double red black rotation in the specified direction
75   This function assumes that all nodes are valid for a rotation
76   <summary>
77   <param name="root">The original root to rotate around</param>
78   <param name="dir">The direction to rotate (0 = left, 1 = right)</param>
79   <returns>The new root after rotation</returns>
80   <remarks>For jsw_rbtree.c internal use only</remarks>
81 */
82 static jsw_rbnode_t *jsw_double ( jsw_rbnode_t *root, int dir )
83 {
84   root->link[!dir] = jsw_single ( root->link[!dir], !dir );
85
86   return jsw_single ( root, dir );
87 }
88
89 /**
90   <summary>
91   Creates an initializes a new red black node with a copy of
92   the data. This function does not insert the new node into a tree
93   <summary>
94   <param name="tree">The red black tree this node is being created for</param>
95   <param name="data">The data value that will be stored in this node</param>
96   <returns>A pointer to the new node</returns>
97   <remarks>
98   For jsw_rbtree.c internal use only. The data for this node must
99   be freed using the same tree's rel function. The returned pointer
100   must be freed using C's free function
101   </remarks>
102 */
103 static jsw_rbnode_t *new_node ( jsw_rbtree_t *tree, void *data )
104 {
105   jsw_rbnode_t *rn = malloc ( sizeof *rn );
106
107   if ( rn == NULL )
108     return NULL;
109
110   rn->red = 1;
111   rn->data = tree->dup ( data );
112   rn->link[0] = rn->link[1] = NULL;
113
114   return rn;
115 }
116
117 /**
118   <summary>
119   Creates and initializes an empty red black tree with
120   user-defined comparison, data copy, and data release operations
121   <summary>
122   <param name="cmp">User-defined data comparison function</param>
123   <param name="dup">User-defined data copy function</param>
124   <param name="rel">User-defined data release function</param>
125   <returns>A pointer to the new tree</returns>
126   <remarks>
127   The returned pointer must be released with jsw_rbdelete
128   </remarks>
129 */
130 jsw_rbtree_t *jsw_rbnew ( cmp_f cmp, dup_f dup, rel_f rel )
131 {
132   jsw_rbtree_t *rt = malloc ( sizeof *rt );
133
134   if ( rt == NULL )
135     return NULL;
136
137   rt->root = NULL;
138   rt->cmp = cmp;
139   rt->dup = dup;
140   rt->rel = rel;
141   rt->size = 0;
142
143   return rt;
144 }
145
146 /**
147   <summary>
148   Releases a valid red black tree
149   <summary>
150   <param name="tree">The tree to release</param>
151   <remarks>
152   The tree must have been created using jsw_rbnew
153   </remarks>
154 */
155 void jsw_rbdelete ( jsw_rbtree_t *tree )
156 {
157   jsw_rbnode_t *it = tree->root;
158   jsw_rbnode_t *save;
159
160   /*
161     Rotate away the left links so that
162     we can treat this like the destruction
163     of a linked list
164   */
165   while ( it != NULL ) {
166     if ( it->link[0] == NULL ) {
167       /* No left links, just kill the node and move on */
168       save = it->link[1];
169       tree->rel ( it->data );
170       free ( it );
171     }
172     else {
173       /* Rotate away the left link and check again */
174       save = it->link[0];
175       it->link[0] = save->link[1];
176       save->link[1] = it;
177     }
178
179     it = save;
180   }
181
182   free ( tree );
183 }
184
185 /**
186   <summary>
187   Search for a copy of the specified
188   node data in a red black tree
189   <summary>
190   <param name="tree">The tree to search</param>
191   <param name="data">The data value to search for</param>
192   <returns>
193   A pointer to the data value stored in the tree,
194   or a null pointer if no data could be found
195   </returns>
196 */
197 void *jsw_rbfind ( jsw_rbtree_t *tree, void *data )
198 {
199   jsw_rbnode_t *it = tree->root;
200
201   while ( it != NULL ) {
202     int cmp = tree->cmp ( it->data, data );
203
204     if ( cmp == 0 )
205       break;
206
207     /*
208       If the tree supports duplicates, they should be
209       chained to the right subtree for this to work
210     */
211     it = it->link[cmp < 0];
212   }
213
214   return it == NULL ? NULL : it->data;
215 }
216
217 /**
218   <summary>
219   Insert a copy of the user-specified
220   data into a red black tree
221   <summary>
222   <param name="tree">The tree to insert into</param>
223   <param name="data">The data value to insert</param>
224   <returns>
225   1 if the value was inserted successfully,
226   0 if the insertion failed for any reason
227   </returns>
228 */
229 int jsw_rbinsert ( jsw_rbtree_t *tree, void *data )
230 {
231   if ( tree->root == NULL ) {
232     /*
233       We have an empty tree; attach the
234       new node directly to the root
235     */
236     tree->root = new_node ( tree, data );
237
238     if ( tree->root == NULL )
239       return 0;
240   }
241   else {
242     jsw_rbnode_t head = {0}; /* False tree root */
243     jsw_rbnode_t *g, *t;     /* Grandparent & parent */
244     jsw_rbnode_t *p, *q;     /* Iterator & parent */
245     int dir = 0, last = 0;
246
247     /* Set up our helpers */
248     t = &head;
249     g = p = NULL;
250     q = t->link[1] = tree->root;
251
252     /* Search down the tree for a place to insert */
253     for ( ; ; ) {
254       if ( q == NULL ) {
255         /* Insert a new node at the first null link */
256         p->link[dir] = q = new_node ( tree, data );
257
258         if ( q == NULL )
259           return 0;
260       }
261       else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) {
262         /* Simple red violation: color flip */
263         q->red = 1;
264         q->link[0]->red = 0;
265         q->link[1]->red = 0;
266       }
267
268       if ( is_red ( q ) && is_red ( p ) ) {
269         /* Hard red violation: rotations necessary */
270         int dir2 = t->link[1] == g;
271
272         if ( q == p->link[last] )
273           t->link[dir2] = jsw_single ( g, !last );
274         else
275           t->link[dir2] = jsw_double ( g, !last );
276       }
277
278       /*
279         Stop working if we inserted a node. This
280         check also disallows duplicates in the tree
281       */
282       if ( tree->cmp ( q->data, data ) == 0 )
283         break;
284
285       last = dir;
286       dir = tree->cmp ( q->data, data ) < 0;
287
288       /* Move the helpers down */
289       if ( g != NULL )
290         t = g;
291
292       g = p, p = q;
293       q = q->link[dir];
294     }
295
296     /* Update the root (it may be different) */
297     tree->root = head.link[1];
298   }
299
300   /* Make the root black for simplified logic */
301   tree->root->red = 0;
302   ++tree->size;
303
304   return 1;
305 }
306
307 /**
308   <summary>
309   Remove a node from a red black tree
310   that matches the user-specified data
311   <summary>
312   <param name="tree">The tree to remove from</param>
313   <param name="data">The data value to search for</param>
314   <returns>
315   1 if the value was removed successfully,
316   0 if the removal failed for any reason
317   </returns>
318   <remarks>
319   The most common failure reason should be
320   that the data was not found in the tree
321   </remarks>
322 */
323 int jsw_rberase ( jsw_rbtree_t *tree, void *data )
324 {
325   if ( tree->root != NULL ) {
326     jsw_rbnode_t head = {0}; /* False tree root */
327     jsw_rbnode_t *q, *p, *g; /* Helpers */
328     jsw_rbnode_t *f = NULL;  /* Found item */
329     int dir = 1;
330
331     /* Set up our helpers */
332     q = &head;
333     g = p = NULL;
334     q->link[1] = tree->root;
335
336     /*
337       Search and push a red node down
338       to fix red violations as we go
339     */
340     while ( q->link[dir] != NULL ) {
341       int last = dir;
342
343       /* Move the helpers down */
344       g = p, p = q;
345       q = q->link[dir];
346       dir = tree->cmp ( q->data, data ) < 0;
347
348       /*
349         Save the node with matching data and keep
350         going; we'll do removal tasks at the end
351       */
352       if ( tree->cmp ( q->data, data ) == 0 )
353         f = q;
354
355       /* Push the red node down with rotations and color flips */
356       if ( !is_red ( q ) && !is_red ( q->link[dir] ) ) {
357         if ( is_red ( q->link[!dir] ) )
358           p = p->link[last] = jsw_single ( q, dir );
359         else if ( !is_red ( q->link[!dir] ) ) {
360           jsw_rbnode_t *s = p->link[!last];
361
362           if ( s != NULL ) {
363             if ( !is_red ( s->link[!last] ) && !is_red ( s->link[last] ) ) {
364               /* Color flip */
365               p->red = 0;
366               s->red = 1;
367               q->red = 1;
368             }
369             else {
370               int dir2 = g->link[1] == p;
371
372               if ( is_red ( s->link[last] ) )
373                 g->link[dir2] = jsw_double ( p, last );
374               else if ( is_red ( s->link[!last] ) )
375                 g->link[dir2] = jsw_single ( p, last );
376
377               /* Ensure correct coloring */
378               q->red = g->link[dir2]->red = 1;
379               g->link[dir2]->link[0]->red = 0;
380               g->link[dir2]->link[1]->red = 0;
381             }
382           }
383         }
384       }
385     }
386
387     /* Replace and remove the saved node */
388     if ( f != NULL ) {
389       tree->rel ( f->data );
390       f->data = q->data;
391       p->link[p->link[1] == q] =
392         q->link[q->link[0] == NULL];
393       free ( q );
394     }
395
396     /* Update the root (it may be different) */
397     tree->root = head.link[1];
398
399     /* Make the root black for simplified logic */
400     if ( tree->root != NULL )
401       tree->root->red = 0;
402
403     --tree->size;
404   }
405
406   return 1;
407 }
408
409 /**
410   <summary>
411   Gets the number of nodes in a red black tree
412   <summary>
413   <param name="tree">The tree to calculate a size for</param>
414   <returns>The number of nodes in the tree</returns>
415 */
416 size_t jsw_rbsize ( jsw_rbtree_t *tree )
417 {
418   return tree->size;
419 }
420
421 /**
422   <summary>
423   Create a new traversal object
424   <summary>
425   <returns>A pointer to the new object</returns>
426   <remarks>
427   The traversal object is not initialized until
428   jsw_rbtfirst or jsw_rbtlast are called.
429   The pointer must be released with jsw_rbtdelete
430   </remarks>
431 */
432 jsw_rbtrav_t *jsw_rbtnew ( void )
433 {
434   return malloc ( sizeof ( jsw_rbtrav_t ) );
435 }
436
437 /**
438   <summary>
439   Release a traversal object
440   <summary>
441   <param name="trav">The object to release</param>
442   <remarks>
443   The object must have been created with jsw_rbtnew
444   </remarks>
445 */
446 void jsw_rbtdelete ( jsw_rbtrav_t *trav )
447 {
448   free ( trav );
449 }
450
451 /**
452   <summary>
453   Initialize a traversal object. The user-specified
454   direction determines whether to begin traversal at the
455   smallest or largest valued node
456   <summary>
457   <param name="trav">The traversal object to initialize</param>
458   <param name="tree">The tree that the object will be attached to</param>
459   <param name="dir">
460   The direction to traverse (0 = ascending, 1 = descending)
461   </param>
462   <returns>A pointer to the smallest or largest data value</returns>
463   <remarks>For jsw_rbtree.c internal use only</remarks>
464 */
465 static void *start ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree, int dir )
466 {
467   trav->tree = tree;
468   trav->it = tree->root;
469   trav->top = 0;
470
471   /* Save the path for later traversal */
472   if ( trav->it != NULL ) {
473     while ( trav->it->link[dir] != NULL ) {
474       trav->path[trav->top++] = trav->it;
475       trav->it = trav->it->link[dir];
476     }
477   }
478
479   return trav->it == NULL ? NULL : trav->it->data;
480 }
481
482 /**
483   <summary>
484   Traverse a red black tree in the user-specified direction
485   <summary>
486   <param name="trav">The initialized traversal object</param>
487   <param name="dir">
488   The direction to traverse (0 = ascending, 1 = descending)
489   </param>
490   <returns>
491   A pointer to the next data value in the specified direction
492   </returns>
493   <remarks>For jsw_rbtree.c internal use only</remarks>
494 */
495 static void *move ( jsw_rbtrav_t *trav, int dir )
496 {
497   if ( trav->it->link[dir] != NULL ) {
498     /* Continue down this branch */
499     trav->path[trav->top++] = trav->it;
500     trav->it = trav->it->link[dir];
501
502     while ( trav->it->link[!dir] != NULL ) {
503       trav->path[trav->top++] = trav->it;
504       trav->it = trav->it->link[!dir];
505     }
506   }
507   else {
508     /* Move to the next branch */
509     jsw_rbnode_t *last;
510
511     do {
512       if ( trav->top == 0 ) {
513         trav->it = NULL;
514         break;
515       }
516
517       last = trav->it;
518       trav->it = trav->path[--trav->top];
519     } while ( last == trav->it->link[dir] );
520   }
521
522   return trav->it == NULL ? NULL : trav->it->data;
523 }
524
525 /**
526   <summary>
527   Initialize a traversal object to the smallest valued node
528   <summary>
529   <param name="trav">The traversal object to initialize</param>
530   <param name="tree">The tree that the object will be attached to</param>
531   <returns>A pointer to the smallest data value</returns>
532 */
533 void *jsw_rbtfirst ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )
534 {
535   return start ( trav, tree, 0 ); /* Min value */
536 }
537
538 /**
539   <summary>
540   Initialize a traversal object to the largest valued node
541   <summary>
542   <param name="trav">The traversal object to initialize</param>
543   <param name="tree">The tree that the object will be attached to</param>
544   <returns>A pointer to the largest data value</returns>
545 */
546 void *jsw_rbtlast ( jsw_rbtrav_t *trav, jsw_rbtree_t *tree )
547 {
548   return start ( trav, tree, 1 ); /* Max value */
549 }
550
551 /**
552   <summary>
553   Traverse to the next value in ascending order
554   <summary>
555   <param name="trav">The initialized traversal object</param>
556   <returns>A pointer to the next value in ascending order</returns>
557 */
558 void *jsw_rbtnext ( jsw_rbtrav_t *trav )
559 {
560   return move ( trav, 1 ); /* Toward larger items */
561 }
562
563 /**
564   <summary>
565   Traverse to the next value in descending order
566   <summary>
567   <param name="trav">The initialized traversal object</param>
568   <returns>A pointer to the next value in descending order</returns>
569 */
570 void *jsw_rbtprev ( jsw_rbtrav_t *trav )
571 {
572   return move ( trav, 0 ); /* Toward smaller items */
573 }