X-Git-Url: https://pd.if.org/git/?p=jsw;a=blobdiff_plain;f=jsw_atree.c;fp=jsw_atree.c;h=ba66bd0ccb6eb984c285a178c2b6f93383de0122;hp=0029dde4ceda39ca302f50b0401811b18f897f66;hb=9fa959d28f32ae94111296c238b1e76caf152078;hpb=b8dc7e923f9cf71c3c722b872494fe639ba4621f

diff --git a/jsw_atree.c b/jsw_atree.c
index 0029dde..ba66bd0 100644
--- a/jsw_atree.c
+++ b/jsw_atree.c
@@ -1,401 +1,401 @@
-/*
-  Andersson tree library
-
-    > Created (Julienne Walker): September 10, 2005
-    > Corrections (James Bucanek): April 10, 2006
-      1) Typo in jsw_aerase:
-           up != 0 should be top != 0
-      2) Bug in jsw_aerase:
-           skew ( path[top] ) should be skew ( up )
-           split ( path[top] ) should be split ( up )
-      3) Bug in skew and split macros:
-           Condition should test for nil
-      4) Bug in jsw_aerase:
-           Search for successor should save the path
-*/
-#include "jsw_atree.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_anode {
-  int               level;   /* Horizontal level for balance */
-  void             *data;    /* User-defined content */
-  struct jsw_anode *link[2]; /* Left (0) and right (1) links */
-} jsw_anode_t;
-
-struct jsw_atree {
-  jsw_anode_t *root; /* Top of the tree */
-  jsw_anode_t *nil;  /* End of tree sentinel */
-  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_atrav {
-  jsw_atree_t *tree;               /* Paired tree */
-  jsw_anode_t *it;                 /* Current node */
-  jsw_anode_t *path[HEIGHT_LIMIT]; /* Traversal path */
-  size_t       top;                /* Top of stack */
-};
-
-/* Remove left horizontal links */
-#define skew(t) do {                                      \
-  if ( t->link[0]->level == t->level && t->level != 0 ) { \
-    jsw_anode_t *save = t->link[0];                       \
-    t->link[0] = save->link[1];                           \
-    save->link[1] = t;                                    \
-    t = save;                                             \
-  }                                                       \
-} while(0)
-
-/* Remove consecutive horizontal links */
-#define split(t) do {                                              \
-  if ( t->link[1]->link[1]->level == t->level && t->level != 0 ) { \
-    jsw_anode_t *save = t->link[1];                                \
-    t->link[1] = save->link[0];                                    \
-    save->link[0] = t;                                             \
-    t = save;                                                      \
-    ++t->level;                                                    \
-  }                                                                \
-} while(0)
-
-static jsw_anode_t *new_node ( jsw_atree_t *tree, void *data )
-{
-  jsw_anode_t *rn = (jsw_anode_t *)malloc ( sizeof *rn );
-
-  if ( rn == NULL )
-    return tree->nil;
-
-  rn->level = 1;
-  rn->data = tree->dup ( data );
-  rn->link[0] = rn->link[1] = tree->nil;
-
-  return rn;
-}
-
-jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel )
-{
-  jsw_atree_t *rt = (jsw_atree_t *)malloc ( sizeof *rt );
-
-  if ( rt == NULL )
-    return NULL;
-
-  /* Initialize sentinel */
-  rt->nil = (jsw_anode_t *)malloc ( sizeof *rt->nil );
-  if ( rt->nil == NULL ) {
-    free ( rt );
-    return NULL;
-  }
-
-  rt->nil->data = NULL; /* Simplifies some ops */
-  rt->nil->level = 0;
-  rt->nil->link[0] = rt->nil->link[1] = rt->nil;
-
-  /* Initialize tree */
-  rt->root = rt->nil;
-  rt->cmp = cmp;
-  rt->dup = dup;
-  rt->rel = rel;
-  rt->size = 0;
-
-  return rt;
-}
-
-void jsw_adelete ( jsw_atree_t *tree )
-{
-  jsw_anode_t *it = tree->root;
-  jsw_anode_t *save;
-
-  /* Destruction by rotation */
-  while ( it != tree->nil ) {
-    if ( it->link[0] == tree->nil ) {
-      /* 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;
-  }
-
-  /* Finalize destruction */
-  free ( tree->nil );
-  free ( tree );
-}
-
-void *jsw_afind ( jsw_atree_t *tree, void *data )
-{
-  jsw_anode_t *it = tree->root;
-
-  while ( it != tree->nil ) {
-    int cmp = tree->cmp ( it->data, data );
-
-    if ( cmp == 0 )
-      break;
-
-    it = it->link[cmp < 0];
-  }
-
-  /* nil->data == NULL */
-  return it->data;
-}
-
-int jsw_ainsert ( jsw_atree_t *tree, void *data )
-{
-  if ( tree->root == tree->nil ) {
-    /* Empty tree case */
-    tree->root = new_node ( tree, data );
-    if ( tree->root == tree->nil )
-      return 0;
-  }
-  else {
-    jsw_anode_t *it = tree->root;
-    jsw_anode_t *path[HEIGHT_LIMIT];
-    int top = 0, dir;
-
-    /* Find a spot and save the path */
-    for ( ; ; ) {
-      path[top++] = it;
-      dir = tree->cmp ( it->data, data ) < 0;
-
-      if ( it->link[dir] == tree->nil )
-        break;
-
-      it = it->link[dir];
-    }
-
-    /* Create a new item */
-    it->link[dir] = new_node ( tree, data );
-    if ( it->link[dir] == tree->nil )
-      return 0;
-
-    /* Walk back and rebalance */
-    while ( --top >= 0 ) {
-      /* Which child? */
-      if ( top != 0 )
-        dir = path[top - 1]->link[1] == path[top];
-
-      skew ( path[top] );
-      split ( path[top] );
-
-      /* Fix the parent */
-      if ( top != 0 )
-        path[top - 1]->link[dir] = path[top];
-      else
-        tree->root = path[top];
-    }
-  }
-
-  ++tree->size;
-
-  return 1;
-}
-
-int jsw_aerase ( jsw_atree_t *tree, void *data )
-{
-  if ( tree->root == tree->nil )
-    return 0;
-  else {
-    jsw_anode_t *it = tree->root;
-    jsw_anode_t *path[HEIGHT_LIMIT];
-    int top = 0, dir, cmp;
-
-    /* Find node to remove and save path */
-    for ( ; ; ) {
-      path[top++] = it;
-
-      if ( it == tree->nil )
-        return 0;
-
-      cmp = tree->cmp ( it->data, data );
-      if ( cmp == 0 )
-        break;
-
-      dir = cmp < 0;
-      it = it->link[dir];
-    }
-
-    /* Remove the found node */
-    if ( it->link[0] == tree->nil
-      || it->link[1] == tree->nil )
-    {
-      /* Single child case */
-      int dir2 = it->link[0] == tree->nil;
-
-      /* Unlink the item */
-      if ( --top != 0 )
-        path[top - 1]->link[dir] = it->link[dir2];
-      else
-        tree->root = it->link[1];
-
-      tree->rel ( it->data );
-      free ( it );
-    }
-    else {
-      /* Two child case */
-      jsw_anode_t *heir = it->link[1];
-      jsw_anode_t *prev = it;
-
-      while ( heir->link[0] != tree->nil ) {
-        path[top++] = prev = heir;
-        heir = heir->link[0];
-      }
-
-      /*
-        Order is important!
-        (free item, replace item, free heir)
-      */
-      tree->rel ( it->data );
-      it->data = heir->data;
-      prev->link[prev == it] = heir->link[1];
-      free ( heir );
-    }
-
-    /* Walk back up and rebalance */
-    while ( --top >= 0 ) {
-      jsw_anode_t *up = path[top];
-
-      if ( top != 0 )
-        dir = path[top - 1]->link[1] == up;
-
-      /* Rebalance (aka. black magic) */
-      if ( up->link[0]->level < up->level - 1
-        || up->link[1]->level < up->level - 1 )
-      {
-        if ( up->link[1]->level > --up->level )
-          up->link[1]->level = up->level;
-
-        /* Order is important! */
-        skew ( up );
-        skew ( up->link[1] );
-        skew ( up->link[1]->link[1] );
-        split ( up );
-        split ( up->link[1] );
-      }
-
-      /* Fix the parent */
-      if ( top != 0 )
-        path[top - 1]->link[dir] = up;
-      else
-        tree->root = up;
-    }
-  }
-
-  --tree->size;
-
-  return 1;
-}
-
-size_t jsw_asize ( jsw_atree_t *tree )
-{
-  return tree->size;
-}
-
-jsw_atrav_t *jsw_atnew ( void )
-{
-  return malloc ( sizeof ( jsw_atrav_t ) );
-}
-
-void jsw_atdelete ( jsw_atrav_t *trav )
-{
-  free ( trav );
-}
-
-/*
-  First step in traversal,
-  handles min and max
-*/
-static void *start ( jsw_atrav_t *trav,
-  jsw_atree_t *tree, int dir )
-{
-  trav->tree = tree;
-  trav->it = tree->root;
-  trav->top = 0;
-
-  /* Build a path to work with */
-  if ( trav->it != tree->nil ) {
-    while ( trav->it->link[dir] != tree->nil ) {
-      trav->path[trav->top++] = trav->it;
-      trav->it = trav->it->link[dir];
-    }
-  }
-
-  /* Could be nil, but nil->data == NULL */
-  return trav->it->data;
-}
-
-/*
-  Subsequent traversal steps,
-  handles ascending and descending
-*/
-static void *move ( jsw_atrav_t *trav, int dir )
-{
-  jsw_anode_t *nil = trav->tree->nil;
-
-  if ( trav->it->link[dir] != nil ) {
-    /* Continue down this branch */
-    trav->path[trav->top++] = trav->it;
-    trav->it = trav->it->link[dir];
-
-    while ( trav->it->link[!dir] != nil ) {
-      trav->path[trav->top++] = trav->it;
-      trav->it = trav->it->link[!dir];
-    }
-  }
-  else {
-    /* Move to the next branch */
-    jsw_anode_t *last;
-
-    do {
-      if ( trav->top == 0 ) {
-        trav->it = nil;
-        break;
-      }
-
-      last = trav->it;
-      trav->it = trav->path[--trav->top];
-    } while ( last == trav->it->link[dir] );
-  }
-
-  /* Could be nil, but nil->data == NULL */
-  return trav->it->data;
-}
-
-void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree )
-{
-  return start ( trav, tree, 0 ); /* Min value */
-}
-
-void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree )
-{
-  return start ( trav, tree, 1 ); /* Max value */
-}
-
-void *jsw_atnext ( jsw_atrav_t *trav )
-{
-  return move ( trav, 1 ); /* Toward larger items */
-}
-
-void *jsw_atprev ( jsw_atrav_t *trav )
-{
-  return move ( trav, 0 ); /* Toward smaller items */
-}
+/*
+  Andersson tree library
+
+    > Created (Julienne Walker): September 10, 2005
+    > Corrections (James Bucanek): April 10, 2006
+      1) Typo in jsw_aerase:
+           up != 0 should be top != 0
+      2) Bug in jsw_aerase:
+           skew ( path[top] ) should be skew ( up )
+           split ( path[top] ) should be split ( up )
+      3) Bug in skew and split macros:
+           Condition should test for nil
+      4) Bug in jsw_aerase:
+           Search for successor should save the path
+*/
+#include "jsw_atree.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_anode {
+  int               level;   /* Horizontal level for balance */
+  void             *data;    /* User-defined content */
+  struct jsw_anode *link[2]; /* Left (0) and right (1) links */
+} jsw_anode_t;
+
+struct jsw_atree {
+  jsw_anode_t *root; /* Top of the tree */
+  jsw_anode_t *nil;  /* End of tree sentinel */
+  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_atrav {
+  jsw_atree_t *tree;               /* Paired tree */
+  jsw_anode_t *it;                 /* Current node */
+  jsw_anode_t *path[HEIGHT_LIMIT]; /* Traversal path */
+  size_t       top;                /* Top of stack */
+};
+
+/* Remove left horizontal links */
+#define skew(t) do {                                      \
+  if ( t->link[0]->level == t->level && t->level != 0 ) { \
+    jsw_anode_t *save = t->link[0];                       \
+    t->link[0] = save->link[1];                           \
+    save->link[1] = t;                                    \
+    t = save;                                             \
+  }                                                       \
+} while(0)
+
+/* Remove consecutive horizontal links */
+#define split(t) do {                                              \
+  if ( t->link[1]->link[1]->level == t->level && t->level != 0 ) { \
+    jsw_anode_t *save = t->link[1];                                \
+    t->link[1] = save->link[0];                                    \
+    save->link[0] = t;                                             \
+    t = save;                                                      \
+    ++t->level;                                                    \
+  }                                                                \
+} while(0)
+
+static jsw_anode_t *new_node ( jsw_atree_t *tree, void *data )
+{
+  jsw_anode_t *rn = (jsw_anode_t *)malloc ( sizeof *rn );
+
+  if ( rn == NULL )
+    return tree->nil;
+
+  rn->level = 1;
+  rn->data = tree->dup ( data );
+  rn->link[0] = rn->link[1] = tree->nil;
+
+  return rn;
+}
+
+jsw_atree_t *jsw_anew ( cmp_f cmp, dup_f dup, rel_f rel )
+{
+  jsw_atree_t *rt = (jsw_atree_t *)malloc ( sizeof *rt );
+
+  if ( rt == NULL )
+    return NULL;
+
+  /* Initialize sentinel */
+  rt->nil = (jsw_anode_t *)malloc ( sizeof *rt->nil );
+  if ( rt->nil == NULL ) {
+    free ( rt );
+    return NULL;
+  }
+
+  rt->nil->data = NULL; /* Simplifies some ops */
+  rt->nil->level = 0;
+  rt->nil->link[0] = rt->nil->link[1] = rt->nil;
+
+  /* Initialize tree */
+  rt->root = rt->nil;
+  rt->cmp = cmp;
+  rt->dup = dup;
+  rt->rel = rel;
+  rt->size = 0;
+
+  return rt;
+}
+
+void jsw_adelete ( jsw_atree_t *tree )
+{
+  jsw_anode_t *it = tree->root;
+  jsw_anode_t *save;
+
+  /* Destruction by rotation */
+  while ( it != tree->nil ) {
+    if ( it->link[0] == tree->nil ) {
+      /* 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;
+  }
+
+  /* Finalize destruction */
+  free ( tree->nil );
+  free ( tree );
+}
+
+void *jsw_afind ( jsw_atree_t *tree, void *data )
+{
+  jsw_anode_t *it = tree->root;
+
+  while ( it != tree->nil ) {
+    int cmp = tree->cmp ( it->data, data );
+
+    if ( cmp == 0 )
+      break;
+
+    it = it->link[cmp < 0];
+  }
+
+  /* nil->data == NULL */
+  return it->data;
+}
+
+int jsw_ainsert ( jsw_atree_t *tree, void *data )
+{
+  if ( tree->root == tree->nil ) {
+    /* Empty tree case */
+    tree->root = new_node ( tree, data );
+    if ( tree->root == tree->nil )
+      return 0;
+  }
+  else {
+    jsw_anode_t *it = tree->root;
+    jsw_anode_t *path[HEIGHT_LIMIT];
+    int top = 0, dir;
+
+    /* Find a spot and save the path */
+    for ( ; ; ) {
+      path[top++] = it;
+      dir = tree->cmp ( it->data, data ) < 0;
+
+      if ( it->link[dir] == tree->nil )
+        break;
+
+      it = it->link[dir];
+    }
+
+    /* Create a new item */
+    it->link[dir] = new_node ( tree, data );
+    if ( it->link[dir] == tree->nil )
+      return 0;
+
+    /* Walk back and rebalance */
+    while ( --top >= 0 ) {
+      /* Which child? */
+      if ( top != 0 )
+        dir = path[top - 1]->link[1] == path[top];
+
+      skew ( path[top] );
+      split ( path[top] );
+
+      /* Fix the parent */
+      if ( top != 0 )
+        path[top - 1]->link[dir] = path[top];
+      else
+        tree->root = path[top];
+    }
+  }
+
+  ++tree->size;
+
+  return 1;
+}
+
+int jsw_aerase ( jsw_atree_t *tree, void *data )
+{
+  if ( tree->root == tree->nil )
+    return 0;
+  else {
+    jsw_anode_t *it = tree->root;
+    jsw_anode_t *path[HEIGHT_LIMIT];
+    int top = 0, dir, cmp;
+
+    /* Find node to remove and save path */
+    for ( ; ; ) {
+      path[top++] = it;
+
+      if ( it == tree->nil )
+        return 0;
+
+      cmp = tree->cmp ( it->data, data );
+      if ( cmp == 0 )
+        break;
+
+      dir = cmp < 0;
+      it = it->link[dir];
+    }
+
+    /* Remove the found node */
+    if ( it->link[0] == tree->nil
+      || it->link[1] == tree->nil )
+    {
+      /* Single child case */
+      int dir2 = it->link[0] == tree->nil;
+
+      /* Unlink the item */
+      if ( --top != 0 )
+        path[top - 1]->link[dir] = it->link[dir2];
+      else
+        tree->root = it->link[1];
+
+      tree->rel ( it->data );
+      free ( it );
+    }
+    else {
+      /* Two child case */
+      jsw_anode_t *heir = it->link[1];
+      jsw_anode_t *prev = it;
+
+      while ( heir->link[0] != tree->nil ) {
+        path[top++] = prev = heir;
+        heir = heir->link[0];
+      }
+
+      /*
+        Order is important!
+        (free item, replace item, free heir)
+      */
+      tree->rel ( it->data );
+      it->data = heir->data;
+      prev->link[prev == it] = heir->link[1];
+      free ( heir );
+    }
+
+    /* Walk back up and rebalance */
+    while ( --top >= 0 ) {
+      jsw_anode_t *up = path[top];
+
+      if ( top != 0 )
+        dir = path[top - 1]->link[1] == up;
+
+      /* Rebalance (aka. black magic) */
+      if ( up->link[0]->level < up->level - 1
+        || up->link[1]->level < up->level - 1 )
+      {
+        if ( up->link[1]->level > --up->level )
+          up->link[1]->level = up->level;
+
+        /* Order is important! */
+        skew ( up );
+        skew ( up->link[1] );
+        skew ( up->link[1]->link[1] );
+        split ( up );
+        split ( up->link[1] );
+      }
+
+      /* Fix the parent */
+      if ( top != 0 )
+        path[top - 1]->link[dir] = up;
+      else
+        tree->root = up;
+    }
+  }
+
+  --tree->size;
+
+  return 1;
+}
+
+size_t jsw_asize ( jsw_atree_t *tree )
+{
+  return tree->size;
+}
+
+jsw_atrav_t *jsw_atnew ( void )
+{
+  return malloc ( sizeof ( jsw_atrav_t ) );
+}
+
+void jsw_atdelete ( jsw_atrav_t *trav )
+{
+  free ( trav );
+}
+
+/*
+  First step in traversal,
+  handles min and max
+*/
+static void *start ( jsw_atrav_t *trav,
+  jsw_atree_t *tree, int dir )
+{
+  trav->tree = tree;
+  trav->it = tree->root;
+  trav->top = 0;
+
+  /* Build a path to work with */
+  if ( trav->it != tree->nil ) {
+    while ( trav->it->link[dir] != tree->nil ) {
+      trav->path[trav->top++] = trav->it;
+      trav->it = trav->it->link[dir];
+    }
+  }
+
+  /* Could be nil, but nil->data == NULL */
+  return trav->it->data;
+}
+
+/*
+  Subsequent traversal steps,
+  handles ascending and descending
+*/
+static void *move ( jsw_atrav_t *trav, int dir )
+{
+  jsw_anode_t *nil = trav->tree->nil;
+
+  if ( trav->it->link[dir] != nil ) {
+    /* Continue down this branch */
+    trav->path[trav->top++] = trav->it;
+    trav->it = trav->it->link[dir];
+
+    while ( trav->it->link[!dir] != nil ) {
+      trav->path[trav->top++] = trav->it;
+      trav->it = trav->it->link[!dir];
+    }
+  }
+  else {
+    /* Move to the next branch */
+    jsw_anode_t *last;
+
+    do {
+      if ( trav->top == 0 ) {
+        trav->it = nil;
+        break;
+      }
+
+      last = trav->it;
+      trav->it = trav->path[--trav->top];
+    } while ( last == trav->it->link[dir] );
+  }
+
+  /* Could be nil, but nil->data == NULL */
+  return trav->it->data;
+}
+
+void *jsw_atfirst ( jsw_atrav_t *trav, jsw_atree_t *tree )
+{
+  return start ( trav, tree, 0 ); /* Min value */
+}
+
+void *jsw_atlast ( jsw_atrav_t *trav, jsw_atree_t *tree )
+{
+  return start ( trav, tree, 1 ); /* Max value */
+}
+
+void *jsw_atnext ( jsw_atrav_t *trav )
+{
+  return move ( trav, 1 ); /* Toward larger items */
+}
+
+void *jsw_atprev ( jsw_atrav_t *trav )
+{
+  return move ( trav, 0 ); /* Toward smaller items */
+}