4 > Created (Julienne Walker): September 10, 2005
5 > Corrections (James Bucanek): April 10, 2006
7 up != 0 should be top != 0
9 skew ( path[top] ) should be skew ( up )
10 split ( path[top] ) should be split ( up )
11 3) Bug in skew and split macros:
12 Condition should test for nil
14 Search for successor should save the path
16 #include "jsw_atree.h"
29 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
32 typedef struct jsw_anode {
33 int level; /* Horizontal level for balance */
34 void *data; /* User-defined content */
35 struct jsw_anode *link[2]; /* Left (0) and right (1) links */
39 jsw_anode_t *root; /* Top of the tree */
40 jsw_anode_t *nil; /* End of tree sentinel */
41 cmp_f cmp; /* Compare two items */
42 dup_f dup; /* Clone an item (user-defined) */
43 rel_f rel; /* Destroy an item (user-defined) */
44 size_t size; /* Number of items (user-defined) */
48 jsw_atree_t *tree; /* Paired tree */
49 jsw_anode_t *it; /* Current node */
50 jsw_anode_t *path[HEIGHT_LIMIT]; /* Traversal path */
51 size_t top; /* Top of stack */
54 /* Remove left horizontal links */
55 #define skew(t) do { \
56 if ( t->link[0]->level == t->level && t->level != 0 ) { \
57 jsw_anode_t *save = t->link[0]; \
58 t->link[0] = save->link[1]; \
64 /* Remove consecutive horizontal links */
65 #define split(t) do { \
66 if ( t->link[1]->link[1]->level == t->level && t->level != 0 ) { \
67 jsw_anode_t *save = t->link[1]; \
68 t->link[1] = save->link[0]; \
75 static jsw_anode_t *new_node ( jsw_atree_t *tree, void *data )
77 jsw_anode_t *rn = (jsw_anode_t *)malloc ( sizeof *rn );
83 rn->data = tree->dup ( data );
84 rn->link[0] = rn->link[1] = tree->nil;
89 jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel )
91 jsw_atree_t *rt = (jsw_atree_t *)malloc ( sizeof *rt );
96 /* Initialize sentinel */
97 rt->nil = (jsw_anode_t *)malloc ( sizeof *rt->nil );
98 if ( rt->nil == NULL ) {
103 rt->nil->data = NULL; /* Simplifies some ops */
105 rt->nil->link[0] = rt->nil->link[1] = rt->nil;
107 /* Initialize tree */
117 void jsw_adelete ( jsw_atree_t *tree )
119 jsw_anode_t *it = tree->root;
122 /* Destruction by rotation */
123 while ( it != tree->nil ) {
124 if ( it->link[0] == tree->nil ) {
127 tree->rel ( it->data );
133 it->link[0] = save->link[1];
140 /* Finalize destruction */
145 void *jsw_afind ( jsw_atree_t *tree, void *data )
147 jsw_anode_t *it = tree->root;
149 while ( it != tree->nil ) {
150 int cmp = tree->cmp ( it->data, data );
155 it = it->link[cmp < 0];
158 /* nil->data == NULL */
162 int jsw_ainsert ( jsw_atree_t *tree, void *data )
164 if ( tree->root == tree->nil ) {
165 /* Empty tree case */
166 tree->root = new_node ( tree, data );
167 if ( tree->root == tree->nil )
171 jsw_anode_t *it = tree->root;
172 jsw_anode_t *path[HEIGHT_LIMIT];
175 /* Find a spot and save the path */
178 dir = tree->cmp ( it->data, data ) < 0;
180 if ( it->link[dir] == tree->nil )
186 /* Create a new item */
187 it->link[dir] = new_node ( tree, data );
188 if ( it->link[dir] == tree->nil )
191 /* Walk back and rebalance */
192 while ( --top >= 0 ) {
195 dir = path[top - 1]->link[1] == path[top];
202 path[top - 1]->link[dir] = path[top];
204 tree->root = path[top];
213 int jsw_aerase ( jsw_atree_t *tree, void *data )
215 if ( tree->root == tree->nil )
218 jsw_anode_t *it = tree->root;
219 jsw_anode_t *path[HEIGHT_LIMIT];
220 int top = 0, dir, cmp;
222 /* Find node to remove and save path */
226 if ( it == tree->nil )
229 cmp = tree->cmp ( it->data, data );
237 /* Remove the found node */
238 if ( it->link[0] == tree->nil
239 || it->link[1] == tree->nil )
241 /* Single child case */
242 int dir2 = it->link[0] == tree->nil;
244 /* Unlink the item */
246 path[top - 1]->link[dir] = it->link[dir2];
248 tree->root = it->link[1];
250 tree->rel ( it->data );
255 jsw_anode_t *heir = it->link[1];
256 jsw_anode_t *prev = it;
258 while ( heir->link[0] != tree->nil ) {
259 path[top++] = prev = heir;
260 heir = heir->link[0];
265 (free item, replace item, free heir)
267 tree->rel ( it->data );
268 it->data = heir->data;
269 prev->link[prev == it] = heir->link[1];
273 /* Walk back up and rebalance */
274 while ( --top >= 0 ) {
275 jsw_anode_t *up = path[top];
278 dir = path[top - 1]->link[1] == up;
280 /* Rebalance (aka. black magic) */
281 if ( up->link[0]->level < up->level - 1
282 || up->link[1]->level < up->level - 1 )
284 if ( up->link[1]->level > --up->level )
285 up->link[1]->level = up->level;
287 /* Order is important! */
289 skew ( up->link[1] );
290 skew ( up->link[1]->link[1] );
292 split ( up->link[1] );
297 path[top - 1]->link[dir] = up;
308 size_t jsw_asize ( jsw_atree_t *tree )
313 jsw_atrav_t *jsw_atnew ( void )
315 return malloc ( sizeof ( jsw_atrav_t ) );
318 void jsw_atdelete ( jsw_atrav_t *trav )
324 First step in traversal,
327 static void *start ( jsw_atrav_t *trav,
328 jsw_atree_t *tree, int dir )
331 trav->it = tree->root;
334 /* Build a path to work with */
335 if ( trav->it != tree->nil ) {
336 while ( trav->it->link[dir] != tree->nil ) {
337 trav->path[trav->top++] = trav->it;
338 trav->it = trav->it->link[dir];
342 /* Could be nil, but nil->data == NULL */
343 return trav->it->data;
347 Subsequent traversal steps,
348 handles ascending and descending
350 static void *move ( jsw_atrav_t *trav, int dir )
352 jsw_anode_t *nil = trav->tree->nil;
354 if ( trav->it->link[dir] != nil ) {
355 /* Continue down this branch */
356 trav->path[trav->top++] = trav->it;
357 trav->it = trav->it->link[dir];
359 while ( trav->it->link[!dir] != nil ) {
360 trav->path[trav->top++] = trav->it;
361 trav->it = trav->it->link[!dir];
365 /* Move to the next branch */
369 if ( trav->top == 0 ) {
375 trav->it = trav->path[--trav->top];
376 } while ( last == trav->it->link[dir] );
379 /* Could be nil, but nil->data == NULL */
380 return trav->it->data;
383 void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree )
385 return start ( trav, tree, 0 ); /* Min value */
388 void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree )
390 return start ( trav, tree, 1 ); /* Max value */
393 void *jsw_atnext ( jsw_atrav_t *trav )
395 return move ( trav, 1 ); /* Toward larger items */
398 void *jsw_atprev ( jsw_atrav_t *trav )
400 return move ( trav, 0 ); /* Toward smaller items */