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
23 #define HEIGHT_LIMIT 64 /* Tallest allowable tree */
26 typedef struct jsw_anode {
27 int level; /* Horizontal level for balance */
28 void *data; /* User-defined content */
29 struct jsw_anode *link[2]; /* Left (0) and right (1) links */
33 jsw_anode_t *root; /* Top of the tree */
34 jsw_anode_t *nil; /* End of tree sentinel */
35 cmp_f cmp; /* Compare two items */
36 dup_f dup; /* Clone an item (user-defined) */
37 rel_f rel; /* Destroy an item (user-defined) */
38 size_t size; /* Number of items (user-defined) */
42 jsw_atree_t *tree; /* Paired tree */
43 jsw_anode_t *it; /* Current node */
44 jsw_anode_t *path[HEIGHT_LIMIT]; /* Traversal path */
45 size_t top; /* Top of stack */
48 /* Remove left horizontal links */
49 #define skew(t) do { \
50 if ( t->link[0]->level == t->level && t->level != 0 ) { \
51 jsw_anode_t *save = t->link[0]; \
52 t->link[0] = save->link[1]; \
58 /* Remove consecutive horizontal links */
59 #define split(t) do { \
60 if ( t->link[1]->link[1]->level == t->level && t->level != 0 ) { \
61 jsw_anode_t *save = t->link[1]; \
62 t->link[1] = save->link[0]; \
69 static jsw_anode_t *new_node ( jsw_atree_t *tree, void *data )
71 jsw_anode_t *rn = malloc ( sizeof *rn );
77 rn->data = tree->dup ( data );
78 rn->link[0] = rn->link[1] = tree->nil;
83 jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel )
85 jsw_atree_t *rt = malloc ( sizeof *rt );
90 /* Initialize sentinel */
91 rt->nil = malloc ( sizeof *rt->nil );
92 if ( rt->nil == NULL ) {
97 rt->nil->data = NULL; /* Simplifies some ops */
99 rt->nil->link[0] = rt->nil->link[1] = rt->nil;
101 /* Initialize tree */
111 void jsw_adelete ( jsw_atree_t *tree )
113 jsw_anode_t *it = tree->root;
116 /* Destruction by rotation */
117 while ( it != tree->nil ) {
118 if ( it->link[0] == tree->nil ) {
121 tree->rel ( it->data );
127 it->link[0] = save->link[1];
134 /* Finalize destruction */
139 void *jsw_afind ( jsw_atree_t *tree, void *data) {
140 jsw_anode_t *it = tree->root;
143 while ( it != tree->nil ) {
144 cmp = tree->cmp(it->data, data);
149 it = it->link[cmp < 0];
152 /* nil->data == NULL */
156 int jsw_ainsert ( jsw_atree_t *tree, void *data )
158 if ( tree->root == tree->nil ) {
159 /* Empty tree case */
160 tree->root = new_node ( tree, data );
161 if ( tree->root == tree->nil )
165 jsw_anode_t *it = tree->root;
166 jsw_anode_t *path[HEIGHT_LIMIT];
169 /* Find a spot and save the path */
172 dir = tree->cmp ( it->data, data ) < 0;
174 if ( it->link[dir] == tree->nil )
180 /* Create a new item */
181 it->link[dir] = new_node ( tree, data );
182 if ( it->link[dir] == tree->nil )
185 /* Walk back and rebalance */
186 while ( --top >= 0 ) {
189 dir = path[top - 1]->link[1] == path[top];
196 path[top - 1]->link[dir] = path[top];
198 tree->root = path[top];
207 int jsw_aerase ( jsw_atree_t *tree, void *data )
209 if ( tree->root == tree->nil )
212 jsw_anode_t *it = tree->root;
213 jsw_anode_t *path[HEIGHT_LIMIT];
214 int top = 0, dir, cmp;
216 /* Find node to remove and save path */
220 if ( it == tree->nil )
223 cmp = tree->cmp ( it->data, data );
231 /* Remove the found node */
232 if ( it->link[0] == tree->nil
233 || it->link[1] == tree->nil )
235 /* Single child case */
236 int dir2 = it->link[0] == tree->nil;
238 /* Unlink the item */
240 path[top - 1]->link[dir] = it->link[dir2];
242 tree->root = it->link[1];
244 tree->rel ( it->data );
249 jsw_anode_t *heir = it->link[1];
250 jsw_anode_t *prev = it;
252 while ( heir->link[0] != tree->nil ) {
253 path[top++] = prev = heir;
254 heir = heir->link[0];
259 (free item, replace item, free heir)
261 tree->rel ( it->data );
262 it->data = heir->data;
263 prev->link[prev == it] = heir->link[1];
267 /* Walk back up and rebalance */
268 while ( --top >= 0 ) {
269 jsw_anode_t *up = path[top];
272 dir = path[top - 1]->link[1] == up;
274 /* Rebalance (aka. black magic) */
275 if ( up->link[0]->level < up->level - 1
276 || up->link[1]->level < up->level - 1 )
278 if ( up->link[1]->level > --up->level )
279 up->link[1]->level = up->level;
281 /* Order is important! */
283 skew ( up->link[1] );
284 skew ( up->link[1]->link[1] );
286 split ( up->link[1] );
291 path[top - 1]->link[dir] = up;
302 size_t jsw_asize ( jsw_atree_t *tree )
307 jsw_atrav_t *jsw_atnew ( void )
309 return malloc ( sizeof ( jsw_atrav_t ) );
312 void jsw_atdelete ( jsw_atrav_t *trav )
318 First step in traversal,
321 static void *start ( jsw_atrav_t *trav,
322 jsw_atree_t *tree, int dir )
325 trav->it = tree->root;
328 /* Build a path to work with */
329 if ( trav->it != tree->nil ) {
330 while ( trav->it->link[dir] != tree->nil ) {
331 trav->path[trav->top++] = trav->it;
332 trav->it = trav->it->link[dir];
336 /* Could be nil, but nil->data == NULL */
337 return trav->it->data;
341 Subsequent traversal steps,
342 handles ascending and descending
344 static void *move ( jsw_atrav_t *trav, int dir )
346 jsw_anode_t *nil = trav->tree->nil;
348 if ( trav->it->link[dir] != nil ) {
349 /* Continue down this branch */
350 trav->path[trav->top++] = trav->it;
351 trav->it = trav->it->link[dir];
353 while ( trav->it->link[!dir] != nil ) {
354 trav->path[trav->top++] = trav->it;
355 trav->it = trav->it->link[!dir];
359 /* Move to the next branch */
363 if ( trav->top == 0 ) {
369 trav->it = trav->path[--trav->top];
370 } while ( last == trav->it->link[dir] );
373 /* Could be nil, but nil->data == NULL */
374 return trav->it->data;
377 void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree )
379 return start ( trav, tree, 0 ); /* Min value */
382 void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree )
384 return start ( trav, tree, 1 ); /* Max value */
387 void *jsw_atnext ( jsw_atrav_t *trav )
389 return move ( trav, 1 ); /* Toward larger items */
392 void *jsw_atprev ( jsw_atrav_t *trav )
394 return move ( trav, 0 ); /* Toward smaller items */