-/*\r
- AVL balanced tree library\r
-\r
- > Created (Julienne Walker): June 17, 2003\r
- > Modified (Julienne Walker): September 24, 2005\r
-*/\r
-#include "jsw_avltree.h"\r
-\r
-#ifdef __cplusplus\r
-#include <cstdlib>\r
-\r
-using std::malloc;\r
-using std::free;\r
-using std::size_t;\r
-#else\r
-#include <stdlib.h>\r
-#endif\r
-\r
-#ifndef HEIGHT_LIMIT\r
-#define HEIGHT_LIMIT 64 /* Tallest allowable tree */\r
-#endif\r
-\r
-typedef struct jsw_avlnode {\r
- int balance; /* Balance factor */\r
- void *data; /* User-defined content */\r
- struct jsw_avlnode *link[2]; /* Left (0) and right (1) links */\r
-} jsw_avlnode_t;\r
-\r
-struct jsw_avltree {\r
- jsw_avlnode_t *root; /* Top of the tree */\r
- cmp_f cmp; /* Compare two items */\r
- dup_f dup; /* Clone an item (user-defined) */\r
- rel_f rel; /* Destroy an item (user-defined) */\r
- size_t size; /* Number of items (user-defined) */\r
-};\r
-\r
-struct jsw_avltrav {\r
- jsw_avltree_t *tree; /* Paired tree */\r
- jsw_avlnode_t *it; /* Current node */\r
- jsw_avlnode_t *path[HEIGHT_LIMIT]; /* Traversal path */\r
- size_t top; /* Top of stack */\r
-};\r
-\r
-/* Two way single rotation */\r
-#define jsw_single(root,dir) do { \\r
- jsw_avlnode_t *save = root->link[!dir]; \\r
- root->link[!dir] = save->link[dir]; \\r
- save->link[dir] = root; \\r
- root = save; \\r
-} while (0)\r
-\r
-/* Two way double rotation */\r
-#define jsw_double(root,dir) do { \\r
- jsw_avlnode_t *save = root->link[!dir]->link[dir]; \\r
- root->link[!dir]->link[dir] = save->link[!dir]; \\r
- save->link[!dir] = root->link[!dir]; \\r
- root->link[!dir] = save; \\r
- save = root->link[!dir]; \\r
- root->link[!dir] = save->link[dir]; \\r
- save->link[dir] = root; \\r
- root = save; \\r
-} while (0)\r
-\r
-/* Adjust balance before double rotation */\r
-#define jsw_adjust_balance(root,dir,bal) do { \\r
- jsw_avlnode_t *n = root->link[dir]; \\r
- jsw_avlnode_t *nn = n->link[!dir]; \\r
- if ( nn->balance == 0 ) \\r
- root->balance = n->balance = 0; \\r
- else if ( nn->balance == bal ) { \\r
- root->balance = -bal; \\r
- n->balance = 0; \\r
- } \\r
- else { /* nn->balance == -bal */ \\r
- root->balance = 0; \\r
- n->balance = bal; \\r
- } \\r
- nn->balance = 0; \\r
-} while (0)\r
-\r
-/* Rebalance after insertion */\r
-#define jsw_insert_balance(root,dir) do { \\r
- jsw_avlnode_t *n = root->link[dir]; \\r
- int bal = dir == 0 ? -1 : +1; \\r
- if ( n->balance == bal ) { \\r
- root->balance = n->balance = 0; \\r
- jsw_single ( root, !dir ); \\r
- } \\r
- else { /* n->balance == -bal */ \\r
- jsw_adjust_balance ( root, dir, bal ); \\r
- jsw_double ( root, !dir ); \\r
- } \\r
-} while (0)\r
-\r
-/* Rebalance after deletion */\r
-#define jsw_remove_balance(root,dir,done) do { \\r
- jsw_avlnode_t *n = root->link[!dir]; \\r
- int bal = dir == 0 ? -1 : +1; \\r
- if ( n->balance == -bal ) { \\r
- root->balance = n->balance = 0; \\r
- jsw_single ( root, dir ); \\r
- } \\r
- else if ( n->balance == bal ) { \\r
- jsw_adjust_balance ( root, !dir, -bal ); \\r
- jsw_double ( root, dir ); \\r
- } \\r
- else { /* n->balance == 0 */ \\r
- root->balance = -bal; \\r
- n->balance = bal; \\r
- jsw_single ( root, dir ); \\r
- done = 1; \\r
- } \\r
-} while (0)\r
-\r
-static jsw_avlnode_t *new_node ( jsw_avltree_t *tree, void *data )\r
-{\r
- jsw_avlnode_t *rn = (jsw_avlnode_t *)malloc ( sizeof *rn );\r
-\r
- if ( rn == NULL )\r
- return NULL;\r
-\r
- rn->balance = 0;\r
- rn->data = tree->dup ( data );\r
- rn->link[0] = rn->link[1] = NULL;\r
-\r
- return rn;\r
-}\r
-\r
-jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel )\r
-{\r
- jsw_avltree_t *rt = (jsw_avltree_t *)malloc ( sizeof *rt );\r
-\r
- if ( rt == NULL )\r
- return NULL;\r
-\r
- rt->root = NULL;\r
- rt->cmp = cmp;\r
- rt->dup = dup;\r
- rt->rel = rel;\r
- rt->size = 0;\r
-\r
- return rt;\r
-}\r
-\r
-void jsw_avldelete ( jsw_avltree_t *tree )\r
-{\r
- jsw_avlnode_t *it = tree->root;\r
- jsw_avlnode_t *save;\r
-\r
- /* Destruction by rotation */\r
- while ( it != NULL ) {\r
- if ( it->link[0] == NULL ) {\r
- /* Remove node */\r
- save = it->link[1];\r
- tree->rel ( it->data );\r
- free ( it );\r
- }\r
- else {\r
- /* Rotate right */\r
- save = it->link[0];\r
- it->link[0] = save->link[1];\r
- save->link[1] = it;\r
- }\r
-\r
- it = save;\r
- }\r
-\r
- free ( tree );\r
-}\r
-\r
-void *jsw_avlfind ( jsw_avltree_t *tree, void *data )\r
-{\r
- jsw_avlnode_t *it = tree->root;\r
-\r
- while ( it != NULL ) {\r
- int cmp = tree->cmp ( it->data, data );\r
-\r
- if ( cmp == 0 )\r
- break;\r
-\r
- it = it->link[cmp < 0];\r
- }\r
-\r
- return it == NULL ? NULL : it->data;\r
-}\r
-\r
-int jsw_avlinsert ( jsw_avltree_t *tree, void *data )\r
-{\r
- /* Empty tree case */\r
- if ( tree->root == NULL ) {\r
- tree->root = new_node ( tree, data );\r
- if ( tree->root == NULL )\r
- return 0;\r
- }\r
- else {\r
- jsw_avlnode_t head = {0}; /* Temporary tree root */\r
- jsw_avlnode_t *s, *t; /* Place to rebalance and parent */\r
- jsw_avlnode_t *p, *q; /* Iterator and save pointer */\r
- int dir;\r
-\r
- /* Set up false root to ease maintenance */\r
- t = &head;\r
- t->link[1] = tree->root;\r
-\r
- /* Search down the tree, saving rebalance points */\r
- for ( s = p = t->link[1]; ; p = q ) {\r
- dir = tree->cmp ( p->data, data ) < 0;\r
- q = p->link[dir];\r
-\r
- if ( q == NULL )\r
- break;\r
- \r
- if ( q->balance != 0 ) {\r
- t = p;\r
- s = q;\r
- }\r
- }\r
-\r
- p->link[dir] = q = new_node ( tree, data );\r
- if ( q == NULL )\r
- return 0;\r
-\r
- /* Update balance factors */\r
- for ( p = s; p != q; p = p->link[dir] ) {\r
- dir = tree->cmp ( p->data, data ) < 0;\r
- p->balance += dir == 0 ? -1 : +1;\r
- }\r
-\r
- q = s; /* Save rebalance point for parent fix */\r
-\r
- /* Rebalance if necessary */\r
- if ( abs ( s->balance ) > 1 ) {\r
- dir = tree->cmp ( s->data, data ) < 0;\r
- jsw_insert_balance ( s, dir );\r
- }\r
-\r
- /* Fix parent */\r
- if ( q == head.link[1] )\r
- tree->root = s;\r
- else\r
- t->link[q == t->link[1]] = s;\r
- }\r
-\r
- ++tree->size;\r
-\r
- return 1;\r
-}\r
-\r
-int jsw_avlerase ( jsw_avltree_t *tree, void *data )\r
-{\r
- if ( tree->root != NULL ) {\r
- jsw_avlnode_t *it, *up[HEIGHT_LIMIT];\r
- int upd[HEIGHT_LIMIT], top = 0;\r
- int done = 0;\r
-\r
- it = tree->root;\r
-\r
- /* Search down tree and save path */\r
- for ( ; ; ) {\r
- if ( it == NULL )\r
- return 0;\r
- else if ( tree->cmp ( it->data, data ) == 0 )\r
- break;\r
-\r
- /* Push direction and node onto stack */\r
- upd[top] = tree->cmp ( it->data, data ) < 0;\r
- up[top++] = it;\r
-\r
- it = it->link[upd[top - 1]];\r
- }\r
-\r
- /* Remove the node */\r
- if ( it->link[0] == NULL || it->link[1] == NULL ) {\r
- /* Which child is not null? */\r
- int dir = it->link[0] == NULL;\r
-\r
- /* Fix parent */\r
- if ( top != 0 )\r
- up[top - 1]->link[upd[top - 1]] = it->link[dir];\r
- else\r
- tree->root = it->link[dir];\r
-\r
- tree->rel ( it->data );\r
- free ( it );\r
- }\r
- else {\r
- /* Find the inorder successor */\r
- jsw_avlnode_t *heir = it->link[1];\r
- void *save;\r
- \r
- /* Save this path too */\r
- upd[top] = 1;\r
- up[top++] = it;\r
-\r
- while ( heir->link[0] != NULL ) {\r
- upd[top] = 0;\r
- up[top++] = heir;\r
- heir = heir->link[0];\r
- }\r
-\r
- /* Swap data */\r
- save = it->data;\r
- it->data = heir->data;\r
- heir->data = save;\r
-\r
- /* Unlink successor and fix parent */\r
- up[top - 1]->link[up[top - 1] == it] = heir->link[1];\r
-\r
- tree->rel ( heir->data );\r
- free ( heir );\r
- }\r
-\r
- /* Walk back up the search path */\r
- while ( --top >= 0 && !done ) {\r
- /* Update balance factors */\r
- up[top]->balance += upd[top] != 0 ? -1 : +1;\r
-\r
- /* Terminate or rebalance as necessary */\r
- if ( abs ( up[top]->balance ) == 1 )\r
- break;\r
- else if ( abs ( up[top]->balance ) > 1 ) {\r
- jsw_remove_balance ( up[top], upd[top], done );\r
-\r
- /* Fix parent */\r
- if ( top != 0 )\r
- up[top - 1]->link[upd[top - 1]] = up[top];\r
- else\r
- tree->root = up[0];\r
- }\r
- }\r
-\r
- --tree->size;\r
- }\r
-\r
- return 1;\r
-}\r
-\r
-size_t jsw_avlsize ( jsw_avltree_t *tree )\r
-{\r
- return tree->size;\r
-}\r
-\r
-jsw_avltrav_t *jsw_avltnew ( void )\r
-{\r
- return malloc ( sizeof ( jsw_avltrav_t ) );\r
-}\r
-\r
-void jsw_avltdelete ( jsw_avltrav_t *trav )\r
-{\r
- free ( trav );\r
-}\r
-\r
-/*\r
- First step in traversal,\r
- handles min and max\r
-*/\r
-static void *start ( jsw_avltrav_t *trav, jsw_avltree_t *tree, int dir )\r
-{\r
- trav->tree = tree;\r
- trav->it = tree->root;\r
- trav->top = 0;\r
-\r
- /* Build a path to work with */\r
- if ( trav->it != NULL ) {\r
- while ( trav->it->link[dir] != NULL ) {\r
- trav->path[trav->top++] = trav->it;\r
- trav->it = trav->it->link[dir];\r
- }\r
- }\r
-\r
- return trav->it == NULL ? NULL : trav->it->data;\r
-}\r
-\r
-/*\r
- Subsequent traversal steps,\r
- handles ascending and descending\r
-*/\r
-static void *move ( jsw_avltrav_t *trav, int dir )\r
-{\r
- if ( trav->it->link[dir] != NULL ) {\r
- /* Continue down this branch */\r
- trav->path[trav->top++] = trav->it;\r
- trav->it = trav->it->link[dir];\r
-\r
- while ( trav->it->link[!dir] != NULL ) {\r
- trav->path[trav->top++] = trav->it;\r
- trav->it = trav->it->link[!dir];\r
- }\r
- }\r
- else {\r
- /* Move to the next branch */\r
- jsw_avlnode_t *last;\r
-\r
- do {\r
- if ( trav->top == 0 ) {\r
- trav->it = NULL;\r
- break;\r
- }\r
-\r
- last = trav->it;\r
- trav->it = trav->path[--trav->top];\r
- } while ( last == trav->it->link[dir] );\r
- }\r
-\r
- return trav->it == NULL ? NULL : trav->it->data;\r
-}\r
-\r
-void *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree )\r
-{\r
- return start ( trav, tree, 0 ); /* Min value */\r
-}\r
-\r
-void *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree )\r
-{\r
- return start ( trav, tree, 1 ); /* Max value */\r
-}\r
-\r
-void *jsw_avltnext ( jsw_avltrav_t *trav )\r
-{\r
- return move ( trav, 1 ); /* Toward larger items */\r
-}\r
-\r
-void *jsw_avltprev ( jsw_avltrav_t *trav )\r
-{\r
- return move ( trav, 0 ); /* Toward smaller items */\r
-}\r
+/*
+ AVL balanced tree library
+
+ > Created (Julienne Walker): June 17, 2003
+ > Modified (Julienne Walker): September 24, 2005
+*/
+#include "jsw_avltree.h"
+
+#ifdef __cplusplus
+#include <cstdlib>
+
+using std::malloc;
+using std::free;
+using std::size_t;
+#else
+#include <stdlib.h>
+#endif
+
+#ifndef HEIGHT_LIMIT
+#define HEIGHT_LIMIT 64 /* Tallest allowable tree */
+#endif
+
+typedef struct jsw_avlnode {
+ int balance; /* Balance factor */
+ void *data; /* User-defined content */
+ struct jsw_avlnode *link[2]; /* Left (0) and right (1) links */
+} jsw_avlnode_t;
+
+struct jsw_avltree {
+ jsw_avlnode_t *root; /* Top of the tree */
+ cmp_f cmp; /* Compare two items */
+ dup_f dup; /* Clone an item (user-defined) */
+ rel_f rel; /* Destroy an item (user-defined) */
+ size_t size; /* Number of items (user-defined) */
+};
+
+struct jsw_avltrav {
+ jsw_avltree_t *tree; /* Paired tree */
+ jsw_avlnode_t *it; /* Current node */
+ jsw_avlnode_t *path[HEIGHT_LIMIT]; /* Traversal path */
+ size_t top; /* Top of stack */
+};
+
+/* Two way single rotation */
+#define jsw_single(root,dir) do { \
+ jsw_avlnode_t *save = root->link[!dir]; \
+ root->link[!dir] = save->link[dir]; \
+ save->link[dir] = root; \
+ root = save; \
+} while (0)
+
+/* Two way double rotation */
+#define jsw_double(root,dir) do { \
+ jsw_avlnode_t *save = root->link[!dir]->link[dir]; \
+ root->link[!dir]->link[dir] = save->link[!dir]; \
+ save->link[!dir] = root->link[!dir]; \
+ root->link[!dir] = save; \
+ save = root->link[!dir]; \
+ root->link[!dir] = save->link[dir]; \
+ save->link[dir] = root; \
+ root = save; \
+} while (0)
+
+/* Adjust balance before double rotation */
+#define jsw_adjust_balance(root,dir,bal) do { \
+ jsw_avlnode_t *n = root->link[dir]; \
+ jsw_avlnode_t *nn = n->link[!dir]; \
+ if ( nn->balance == 0 ) \
+ root->balance = n->balance = 0; \
+ else if ( nn->balance == bal ) { \
+ root->balance = -bal; \
+ n->balance = 0; \
+ } \
+ else { /* nn->balance == -bal */ \
+ root->balance = 0; \
+ n->balance = bal; \
+ } \
+ nn->balance = 0; \
+} while (0)
+
+/* Rebalance after insertion */
+#define jsw_insert_balance(root,dir) do { \
+ jsw_avlnode_t *n = root->link[dir]; \
+ int bal = dir == 0 ? -1 : +1; \
+ if ( n->balance == bal ) { \
+ root->balance = n->balance = 0; \
+ jsw_single ( root, !dir ); \
+ } \
+ else { /* n->balance == -bal */ \
+ jsw_adjust_balance ( root, dir, bal ); \
+ jsw_double ( root, !dir ); \
+ } \
+} while (0)
+
+/* Rebalance after deletion */
+#define jsw_remove_balance(root,dir,done) do { \
+ jsw_avlnode_t *n = root->link[!dir]; \
+ int bal = dir == 0 ? -1 : +1; \
+ if ( n->balance == -bal ) { \
+ root->balance = n->balance = 0; \
+ jsw_single ( root, dir ); \
+ } \
+ else if ( n->balance == bal ) { \
+ jsw_adjust_balance ( root, !dir, -bal ); \
+ jsw_double ( root, dir ); \
+ } \
+ else { /* n->balance == 0 */ \
+ root->balance = -bal; \
+ n->balance = bal; \
+ jsw_single ( root, dir ); \
+ done = 1; \
+ } \
+} while (0)
+
+static jsw_avlnode_t *new_node ( jsw_avltree_t *tree, void *data )
+{
+ jsw_avlnode_t *rn = (jsw_avlnode_t *)malloc ( sizeof *rn );
+
+ if ( rn == NULL )
+ return NULL;
+
+ rn->balance = 0;
+ rn->data = tree->dup ( data );
+ rn->link[0] = rn->link[1] = NULL;
+
+ return rn;
+}
+
+jsw_avltree_t *jsw_avlnew ( cmp_f cmp, dup_f dup, rel_f rel )
+{
+ jsw_avltree_t *rt = (jsw_avltree_t *)malloc ( sizeof *rt );
+
+ if ( rt == NULL )
+ return NULL;
+
+ rt->root = NULL;
+ rt->cmp = cmp;
+ rt->dup = dup;
+ rt->rel = rel;
+ rt->size = 0;
+
+ return rt;
+}
+
+void jsw_avldelete ( jsw_avltree_t *tree )
+{
+ jsw_avlnode_t *it = tree->root;
+ jsw_avlnode_t *save;
+
+ /* Destruction by rotation */
+ while ( it != NULL ) {
+ if ( it->link[0] == NULL ) {
+ /* Remove node */
+ save = it->link[1];
+ tree->rel ( it->data );
+ free ( it );
+ }
+ else {
+ /* Rotate right */
+ save = it->link[0];
+ it->link[0] = save->link[1];
+ save->link[1] = it;
+ }
+
+ it = save;
+ }
+
+ free ( tree );
+}
+
+void *jsw_avlfind ( jsw_avltree_t *tree, void *data )
+{
+ jsw_avlnode_t *it = tree->root;
+
+ while ( it != NULL ) {
+ int cmp = tree->cmp ( it->data, data );
+
+ if ( cmp == 0 )
+ break;
+
+ it = it->link[cmp < 0];
+ }
+
+ return it == NULL ? NULL : it->data;
+}
+
+int jsw_avlinsert ( jsw_avltree_t *tree, void *data )
+{
+ /* Empty tree case */
+ if ( tree->root == NULL ) {
+ tree->root = new_node ( tree, data );
+ if ( tree->root == NULL )
+ return 0;
+ }
+ else {
+ jsw_avlnode_t head = {0}; /* Temporary tree root */
+ jsw_avlnode_t *s, *t; /* Place to rebalance and parent */
+ jsw_avlnode_t *p, *q; /* Iterator and save pointer */
+ int dir;
+
+ /* Set up false root to ease maintenance */
+ t = &head;
+ t->link[1] = tree->root;
+
+ /* Search down the tree, saving rebalance points */
+ for ( s = p = t->link[1]; ; p = q ) {
+ dir = tree->cmp ( p->data, data ) < 0;
+ q = p->link[dir];
+
+ if ( q == NULL )
+ break;
+
+ if ( q->balance != 0 ) {
+ t = p;
+ s = q;
+ }
+ }
+
+ p->link[dir] = q = new_node ( tree, data );
+ if ( q == NULL )
+ return 0;
+
+ /* Update balance factors */
+ for ( p = s; p != q; p = p->link[dir] ) {
+ dir = tree->cmp ( p->data, data ) < 0;
+ p->balance += dir == 0 ? -1 : +1;
+ }
+
+ q = s; /* Save rebalance point for parent fix */
+
+ /* Rebalance if necessary */
+ if ( abs ( s->balance ) > 1 ) {
+ dir = tree->cmp ( s->data, data ) < 0;
+ jsw_insert_balance ( s, dir );
+ }
+
+ /* Fix parent */
+ if ( q == head.link[1] )
+ tree->root = s;
+ else
+ t->link[q == t->link[1]] = s;
+ }
+
+ ++tree->size;
+
+ return 1;
+}
+
+int jsw_avlerase ( jsw_avltree_t *tree, void *data )
+{
+ if ( tree->root != NULL ) {
+ jsw_avlnode_t *it, *up[HEIGHT_LIMIT];
+ int upd[HEIGHT_LIMIT], top = 0;
+ int done = 0;
+
+ it = tree->root;
+
+ /* Search down tree and save path */
+ for ( ; ; ) {
+ if ( it == NULL )
+ return 0;
+ else if ( tree->cmp ( it->data, data ) == 0 )
+ break;
+
+ /* Push direction and node onto stack */
+ upd[top] = tree->cmp ( it->data, data ) < 0;
+ up[top++] = it;
+
+ it = it->link[upd[top - 1]];
+ }
+
+ /* Remove the node */
+ if ( it->link[0] == NULL || it->link[1] == NULL ) {
+ /* Which child is not null? */
+ int dir = it->link[0] == NULL;
+
+ /* Fix parent */
+ if ( top != 0 )
+ up[top - 1]->link[upd[top - 1]] = it->link[dir];
+ else
+ tree->root = it->link[dir];
+
+ tree->rel ( it->data );
+ free ( it );
+ }
+ else {
+ /* Find the inorder successor */
+ jsw_avlnode_t *heir = it->link[1];
+ void *save;
+
+ /* Save this path too */
+ upd[top] = 1;
+ up[top++] = it;
+
+ while ( heir->link[0] != NULL ) {
+ upd[top] = 0;
+ up[top++] = heir;
+ heir = heir->link[0];
+ }
+
+ /* Swap data */
+ save = it->data;
+ it->data = heir->data;
+ heir->data = save;
+
+ /* Unlink successor and fix parent */
+ up[top - 1]->link[up[top - 1] == it] = heir->link[1];
+
+ tree->rel ( heir->data );
+ free ( heir );
+ }
+
+ /* Walk back up the search path */
+ while ( --top >= 0 && !done ) {
+ /* Update balance factors */
+ up[top]->balance += upd[top] != 0 ? -1 : +1;
+
+ /* Terminate or rebalance as necessary */
+ if ( abs ( up[top]->balance ) == 1 )
+ break;
+ else if ( abs ( up[top]->balance ) > 1 ) {
+ jsw_remove_balance ( up[top], upd[top], done );
+
+ /* Fix parent */
+ if ( top != 0 )
+ up[top - 1]->link[upd[top - 1]] = up[top];
+ else
+ tree->root = up[0];
+ }
+ }
+
+ --tree->size;
+ }
+
+ return 1;
+}
+
+size_t jsw_avlsize ( jsw_avltree_t *tree )
+{
+ return tree->size;
+}
+
+jsw_avltrav_t *jsw_avltnew ( void )
+{
+ return malloc ( sizeof ( jsw_avltrav_t ) );
+}
+
+void jsw_avltdelete ( jsw_avltrav_t *trav )
+{
+ free ( trav );
+}
+
+/*
+ First step in traversal,
+ handles min and max
+*/
+static void *start ( jsw_avltrav_t *trav, jsw_avltree_t *tree, int dir )
+{
+ trav->tree = tree;
+ trav->it = tree->root;
+ trav->top = 0;
+
+ /* Build a path to work with */
+ if ( trav->it != NULL ) {
+ while ( trav->it->link[dir] != NULL ) {
+ trav->path[trav->top++] = trav->it;
+ trav->it = trav->it->link[dir];
+ }
+ }
+
+ return trav->it == NULL ? NULL : trav->it->data;
+}
+
+/*
+ Subsequent traversal steps,
+ handles ascending and descending
+*/
+static void *move ( jsw_avltrav_t *trav, int dir )
+{
+ if ( trav->it->link[dir] != NULL ) {
+ /* Continue down this branch */
+ trav->path[trav->top++] = trav->it;
+ trav->it = trav->it->link[dir];
+
+ while ( trav->it->link[!dir] != NULL ) {
+ trav->path[trav->top++] = trav->it;
+ trav->it = trav->it->link[!dir];
+ }
+ }
+ else {
+ /* Move to the next branch */
+ jsw_avlnode_t *last;
+
+ do {
+ if ( trav->top == 0 ) {
+ trav->it = NULL;
+ break;
+ }
+
+ last = trav->it;
+ trav->it = trav->path[--trav->top];
+ } while ( last == trav->it->link[dir] );
+ }
+
+ return trav->it == NULL ? NULL : trav->it->data;
+}
+
+void *jsw_avltfirst ( jsw_avltrav_t *trav, jsw_avltree_t *tree )
+{
+ return start ( trav, tree, 0 ); /* Min value */
+}
+
+void *jsw_avltlast ( jsw_avltrav_t *trav, jsw_avltree_t *tree )
+{
+ return start ( trav, tree, 1 ); /* Max value */
+}
+
+void *jsw_avltnext ( jsw_avltrav_t *trav )
+{
+ return move ( trav, 1 ); /* Toward larger items */
+}
+
+void *jsw_avltprev ( jsw_avltrav_t *trav )
+{
+ return move ( trav, 0 ); /* Toward smaller items */
+}
projects / jsw / blobdiff