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