Logo Search packages:      
Sourcecode: vile version File versions

btree.c

/*
 * $Id: btree.c,v 1.17 2003/05/15 23:20:45 tom Exp $
 * Copyright 1997-1999 by Thomas E. Dickey
 *
 * Maintains a balanced binary tree (aka AVL tree) of unspecified nodes.  The
 * algorithm is taken from "The Art of Computer Programming -- Volume 3 --
 * Sorting and Searching", by Donald Knuth.  Knuth presents the insertion and
 * search algorithms in assembly language for MIX, and gives an overview of the
 * deletion algorithm for the "interested reader".
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#if !defined(DEBUG_BTREE) && !defined(NDEBUG)
#define NDEBUG
#endif

#if defined(DEBUG_BTREE)
#if defined(OPT_TRACE) || defined(DOALLOC)
#include "trace.h"
#endif

#ifdef USE_DBMALLOC
#include <dbmalloc.h>
#endif

#ifdef USE_DMALLOC
#include <dmalloc.h>
#endif

#define castalloc(cast,nbytes) (cast *)malloc(nbytes)
#define     for_ever for(;;)
#define beginDisplay() /* nothing */
#define endofDisplay() /* nothing */

#else
#include "estruct.h"
#include "edef.h"
#endif

#include <assert.h>

#include "btree.h"

                  /* definitions to make this simple, like Knuth */
#define     LLINK(p)    BI_LEFT(p)
#define     RLINK(p)    BI_RIGHT(p)
#define     KEY(p)            BI_KEY(p)
#define     B(p)        (p)->balance

#define COMPARE(a,b)    btree_strcmp(a,b)

#define     LINK(a,p)   (p)->links[(a)>0]

#ifdef DEBUG_BTREE
# ifndef TRACE
#  if DEBUG_BTREE > 0
#   define TRACE(p)     printf p ; fflush(stdout)
#  endif
# endif
#else
# undef TRACE
# define DEBUG_BTREE -1
#endif

#if DEBUG_BTREE > 1
#define TRACE_TREE(s,p) TRACE((s)); btree_printf(p)
#endif

#if DEBUG_BTREE > 2
#define TRACE_SUBTREE(s,h,p)  TRACE((s)); dump_nodes(h,p,0)
#endif

#ifndef TRACE
#define TRACE(p)  /*nothing*/
#endif

#ifndef TRACE_TREE
#define TRACE_TREE(s,p) /*nothing*/
#endif

#ifndef TRACE_SUBTREE
#define TRACE_SUBTREE(s,h,p)  /*nothing*/
#endif

#if DEBUG_BTREE >= 0
static int btree_verify(BI_TREE *funcs, BI_NODE *p);
static void dump_nodes(BI_TREE *funcs, BI_NODE * p, int level);
#endif

/*
 * FIXME
 */
static int
btree_strcmp(const char *a, const char *b)
{
      register int cmp = strcmp(a, b);
      if (cmp < 0)
            cmp = -1;
      else if (cmp > 0)
            cmp = 1;
      return cmp;
}

BI_DATA *
btree_insert(BI_TREE *funcs, BI_DATA *data)
{
                        /* (A1:Initialize) */
register
      BI_NODE     *t = &(funcs->head),    /* 't' => to the father of 's'      */
            *s = RLINK(t),          /* 's' => to rebalancing point      */
            *p = RLINK(t),          /* 'p' => down the tree       */
            *q,
            *r;
register
      int   a;
      BI_DATA     *value = 0;

      TRACE(("inserting '%s'\n", data->bi_key));
      if (p == 0) {
            RLINK(t) = p = (*funcs->allocat)(data);
            funcs->depth += 1;
            funcs->count += 1;
            return &(p->value);
      }
                        /* (A2:Compare) */
      while ((a = COMPARE(data->bi_key, KEY(p))) != 0) {
                        /* (A3,A4: move left/right accordingly)   */
            if ((q = LINK(a,p)) != 0) {
                  value = &(p->value);
                  if (B(q)) {
                        t = p;
                        s = q;
                  }
                  p = q;
                  /* ...continue comparing */
            } else {
                  /* (A5:Insert) */
                  LINK(a,p) = q = (*funcs->allocat)(data);
                  funcs->count += 1;
                  value = &(q->value);

                  /* (A6:Adjust balance factors) */
                  /*
                   * Now the balance factors on nodes between 's' and 'q'
                   * need to be changed from zero to +/- 1.
                   */
                  if (COMPARE(data->bi_key, KEY(s)) < 0)
                        r = p = LLINK(s);
                  else
                        r = p = RLINK(s);

                  while (p != q) {
                        if ((a = COMPARE(data->bi_key, KEY(p))) != 0) {
                              B(p) = (a < 0) ? -1 : 1;
                              p = LINK(a,p);
                        }
                  }

                        /* (A7:Balancing act) */
                  a = (COMPARE(data->bi_key, KEY(s)) < 0) ? -1 : 1;

                  if (B(s) == 0) {
                        /* ...the tree has grown higher     */
                        B(s) = a;
                        funcs->depth += 1;
                  } else if (B(s) == -a) {
                        /* ...the tree has gotten more balanced   */
                        B(s) = 0;
                  } else /* (B(s) == a) */ {
                        assert(B(s) == a);
                        /* ...the tree has gotten out of balance */
                        TRACE(("...must rebalance\n"));
                        if (B(r) == a) {
                              TRACE(("(A8:Single rotation)\n"));
                              p          = r;
                              LINK(a,s)  = LINK(-a,r);
                              LINK(-a,r) = s;

                              B(s) = B(r) = 0;
                        } else /* (B(r) == -a) */ {
                              assert(B(r) == -a);
                              TRACE(("(A9: Double rotation)\n"));
                              p          = LINK(-a,r);
                              LINK(-a,r) = LINK(a,p);
                              LINK(a,p)  = r;
                              LINK(a,s)  = LINK(-a,p);
                              LINK(-a,p) = s;

                              TRACE(("r=%s\n", KEY(r)));
                              TRACE(("s=%s\n", KEY(s)));
                              TRACE(("B(%s) = %d vs a = %d\n",
                                    KEY(p), B(p), a));

                              if (B(p) == a)
                                    { B(s) = -a; B(r) = 0;  }
                              else if (B(p) == 0)
                                    { B(s) =     B(r) = 0;  }
                              else /* if (B(p) == -a) */
                                    { B(s) = 0;  B(r) = a;  }

                              B(p) = 0;
                        }
                        /* A10:Finishing touch */
                        t->links[(s == RLINK(t))] = p;
                  }
                  break;
            }
      }
      return (value);
}

static BI_NODE *
parent_of(BI_TREE *funcs, BI_NODE *s)
{
      BI_NODE     *r = &(funcs->head),
            *p = RLINK(r);     /* 'p' => down the tree      */
      int a;

      while ((a = COMPARE(KEY(s), KEY(p))) != 0) {
            assert(LINK(a,p) != 0);
            r = p;
            p = LINK(a,p);
      }
      TRACE(("parent of '%s' is '%s'\n", KEY(s), KEY(r)));
      return r;
}

#define MAXSTK 20
#define PUSH(A,P) { \
      TRACE(("@%d:push #%d a=%2d, B=%2d, p='%s' -> '%s'\n", __LINE__, \
            k, A, B(P), P?KEY(P):"", LINK(A,P)?KEY(LINK(A,P)):"")); \
      stack[k].a = A;\
      stack[k].p = P;\
      k++; }

int
btree_delete(BI_TREE *funcs, const char *data)
{
      struct {
      BI_NODE     *p;
      int   a;
      } stack[MAXSTK];
      int   k = 0;
                        /* (A1:Initialize) */
register
      BI_NODE     *t = &(funcs->head),
            *p, *q, *r, *s;
register
      int   a, b;
      char  *value;

      if ((p = t) == 0
       || (p = LINK(a=1,p)) == 0) {
            return 0;
      }
                        /* (A2:Compare) */
      while ((a = COMPARE(data, value = KEY(p))) != 0) {
            if ((q = LINK(a,p)) == 0) {
                  value = 0;
                  break;
            }
                        /* (A3,A4: move left/right accordingly)   */
            t = p;
            p = LINK(a,p);
            /* ...continue comparing */
      }

      if (value != 0) { /* we found the node to delete, in p */
            TRACE(("deleting node '%s'\n", value));
            q = p;
            p = t;
            a = (q == RLINK(p)) ? 1 : -1;

            TRACE(("@%d, p='%s'\n", __LINE__, p?KEY(p):""));
            TRACE(("@%d, q='%s'\n", __LINE__, q?KEY(q):""));
            TRACE(("@%d, a=%d\n",   __LINE__, a));

                        /* D1: Is RLINK null? */
            if (RLINK(q) == 0) {
                  TRACE(("D1\n"));

                  LINK(a,p) = LLINK(q);
                  s = p;
#if 0 /* LATER? */
            } else if (LLINK(q) == 0) { /* D1.5 */
                  TRACE(("D1.5\n"));
                  LINK(a,p) = RLINK(q);
                  s = RLINK(q);
#endif
            } else {    /* D2: Find successor */
                  TRACE_SUBTREE("SUBTREE(p)-before\n", funcs, p);
                  r = RLINK(q);
                  if (LLINK(r) == 0) {
                        TRACE(("D2, r='%s', q='%s'\n", KEY(r), KEY(q)));
                        TRACE(("DIFF: %d\n", B(r) - B(q)));

                        LLINK(r) = LLINK(q);
                        LINK(a,p) = r;
                        s = r;
                        TRACE(("(D2) replace balance %2d with %2d, a=%2d\n", B(s), B(q), a));
                        B(s) = B(q);
                        a = 1;      /* for RLINK(q) */

                        TRACE_SUBTREE("SUBTREE(p)-after\n", funcs, p);
                        TRACE(("@%d, p='%s'\n", __LINE__, KEY(p)));
                        TRACE(("@%d, r='%s'\n", __LINE__, KEY(r)));
                  } else { /* D3: Find null LLINK */
                        TRACE(("D3: find null LLINK\n"));

                        TRACE(("@%d, r='%s'\n", __LINE__, r?KEY(r):""));
                        s = r;
                        do {
                              r = s;
                              s = LLINK(r);
                        } while (LLINK(s) != 0);

                        LLINK(s) = LLINK(q);
                        LLINK(r) = RLINK(s);
                        RLINK(s) = RLINK(q);
                        TRACE(("@%d, p='%s', a=%d\n", __LINE__, KEY(p), a));
                        TRACE(("@%d, r='%s'\n", __LINE__, KEY(r)));
                        TRACE(("@%d, s='%s'\n", __LINE__, KEY(s)));
                        LINK(a,p) = s;
                        TRACE(("(D3) replace balance %2d with %2d, a=%2d\n", B(s), B(q), a));
                        B(s) = B(q);
                        s = r;
                        a = -1;     /* ...since we followed left */
                  }
            }
            b = a;
                        /* D4: Free the node */
            assert(q != 0);
            (*funcs->dealloc)(q);
            funcs->count -= 1;
            TRACE_TREE("after delinking:",funcs);

                        /* Construct the auxiliary stack */
            a = 1;
            q = &(funcs->head);
            if (s != 0
             && s != q
             && q != 0) {
                  TRACE(("Construct stack from '%s' down to '%s', final a=%d\n",
                        q?KEY(q):"",
                        s?KEY(s):"",
                        b));
                  while (s != q) {
                        PUSH(a,q);
                        q = LINK(a,q);
                        a = COMPARE(KEY(s), KEY(q));
                  }
                  PUSH(b,q);
                  TRACE(("...done building stack\n"));
            }

                        /* Rebalance the tree */
            for_ever {
                  if (--k <= 0) {
                        TRACE(("shorten the whole tree\n"));
                        funcs->depth -= 1;
                        break;
                  }
                  p = stack[k].p;
                  a = stack[k].a;
                  TRACE(("processing #%d '%s' B = %d, a = %d (%p)\n",
                        k, KEY(p), B(p), a, LINK(a,p)));
                  if (B(p) == a) {
                        TRACE(("Case (i)\n"));
                        B(p) = 0;
                  } else if (B(p) == 0) {
                        TRACE(("Case (ii)\n"));
                        B(p) = -a;
                        break;
                  } else {
                        TRACE(("Case (iii): Rebalancing needed!\n"));

                        q = LINK(-a,p);
                        assert(q != 0);
                        assert(k >  0);
                        assert(B(p) == -a);

                        t = stack[k-1].p;
                        TRACE(("t:%s, balance:%d\n", KEY(t), B(t)));
                        TRACE(("A:p:%s, balance:%d\n", KEY(p), B(p)));
                        TRACE(("B:q:%s, balance:%d\n", KEY(q), B(q)));
                        TRACE_TREE("before rebalancing:", funcs);

                        if (B(q) == -a) {
                              TRACE(("CASE 1: single rotation\n"));

                              r          = q;

                              TRACE(("link LINK(-a,p) -> LINK( a,q) = '%s'\n", LINK(a,q)?KEY(LINK(a,q)):""));
                              TRACE(("link LINK( a,q) -> p          = '%s'\n", p?KEY(p):""));

                              LINK(-a,p) = LINK(a,q);
                              LINK(a,q)  = p;

                              B(p) = B(q) = 0;

                              t = parent_of(funcs, p);

                              TRACE(("Finish by linking '%s' to %sLINK(%s)\n",
                                    KEY(r),
                                    (p == RLINK(t))
                                          ? "R"
                                          : (p == LLINK(t))
                                                ? "L" : "?",
                                    KEY(t)));

                              t->links[(p == RLINK(t))] = r;

                        } else if (B(q) == a) {
                              TRACE(("CASE 2: double rotation\n"));

                              r          = LINK(a,q);
#if DEBUG_BTREE > 1
                              TRACE(("a = '%d'\n", a));
                              TRACE(("p = '%s'\n", p?KEY(p):""));
                              TRACE(("q = '%s'\n", q?KEY(q):""));
                              TRACE(("r = '%s'\n", r?KEY(r):""));
                              TRACE(("link LINK( a,q) -> LINK(-a,r) = '%s'\n", LINK(-a,r)?KEY(LINK(-a,r)):""));
                              TRACE(("link LINK(-a,r) -> q          = '%s'\n", KEY(q)));
                              TRACE(("link LINK(-a,p) -> LINK(a,r)  = '%s'\n", LINK(a,r)?KEY(LINK(a,r)):""));
                              TRACE(("link LINK( a,r) -> p          = '%s'\n", KEY(p)));
#endif
                              LINK(a,q)  = LINK(-a,r);
                              LINK(-a,r) = q;
                              LINK(-a,p) = LINK(a,r);
                              LINK(a,r)  = p;

                              TRACE(("compute balance for '%s', %d vs a=%d\n",
                                    KEY(r), B(r), a));

                              if (B(r) == -a)
                                    { B(p) = a;  B(q) = 0;  }
                              else if (B(r) == 0)
                                    { B(p) =     B(q) = 0;  }
                              else /* (B(r) == a) */
                                    { B(p) = 0;  B(q) = -a;  }

                              B(r) = 0;

                              a = stack[k-1].a;
                              t = stack[k-1].p;

                              TRACE(("Finish by linking '%s' to %sLINK(%s)\n",
                                    KEY(r),
                                    (a>0) ? "R" : "L",
                                    KEY(t)));

                              LINK(a,t) = r;

                        } else {
                              TRACE(("CASE 3: single rotation, end\n"));

                              LINK(-a,p) = LINK(a,q);
                              LINK(a,q)  = p;

                              B(q) = -B(p);

                              LINK(stack[k-1].a,stack[k-1].p) = q;
                              break;
                        }

                        TRACE_TREE("after rebalancing:", funcs);

                  }
            }
      }
      return (value != 0);
}

BI_DATA *
btree_search(BI_TREE *funcs, const char *data)
{
                        /* (A1:Initialize) */
register
      BI_NODE     *t = &(funcs->head),    /* 't' => to the father of 's'      */
            *p = RLINK(t),          /* 'p' => down the tree       */
            *q;
register
      int   a;

      if (p == 0) {
            return 0;
      }
                        /* (A2:Compare) */
      while ((a = COMPARE(data, KEY(p))) != 0) {
                        /* (A3,A4: move left/right accordingly)   */
            if ((q = LINK(a,p)) != 0) {
                  p = q;
                  /* ...continue comparing */
            } else {
                  break;
            }
      }
      return a ? 0 : &(p->value);
}

/******************************************************************************/

#ifndef BTREE_VERIFY
#define BTREE_VERIFY 1
#endif

#ifndef BTREE_DRIVER
#define BTREE_DRIVER 1
#endif

#if DEBUG_BTREE >= BTREE_VERIFY
static int
btree_count(BI_NODE *p)
{
      int count = 0;
      if (p != 0) {
            count = 1;
            count += btree_count(LLINK(p));
            count += btree_count(RLINK(p));
      }
      return count;
}
#endif

#if DEBUG_BTREE >= BTREE_VERIFY
static int
btree_depth(BI_NODE *p)
{
      int depth = 0;
      if (p != 0) {
            int l, r;
            assert(LLINK(p) != p);
            assert(RLINK(p) != p);
            l = btree_depth(LLINK(p));
            r = btree_depth(RLINK(p));
            depth = 1;
            if (l > r)
                  depth += l;
            else
                  depth += r;
      }
      return depth;
}
#endif

static void
dump_nodes(BI_TREE *funcs, BI_NODE * p, int level)
{
      if (p) {
            dump_nodes(funcs, LLINK(p),  level+1);
            (*funcs->display)(p, level);
#if DEBUG_BTREE > 0
            if (LLINK(p) != 0
             && COMPARE(KEY(LLINK(p)), KEY(p)) > 0)
                  TRACE((" OOPS:L"));
            if (RLINK(p) != 0
             && COMPARE(KEY(RLINK(p)), KEY(p)) < 0)
                  TRACE((" OOPS:R"));
            TRACE((" %d", btree_depth(p)));
#endif
#if DEBUG_BTREE >= BTREE_DRIVER
            printf("\n");
#endif
            dump_nodes(funcs, RLINK(p), level+1);
      }
}

/*
 * Invoke display function for each node
 */
void
btree_printf(BI_TREE * funcs)
{
      TRACE(("TREE, depth %d, count %d\n", funcs->depth, funcs->count));
      dump_nodes(funcs, RLINK(&(funcs->head)), 0);
}

/******************************************************************************/

/*
 * Find the the matching entry given a name in the tree.  Match according to
 * the 'mode' parameter:
 *
 *    If it's FALSE then only the first len characters must match and this
 *    will return the parent of the subtree that contains these entries (so
 *    that an inorder walk can find the other matches).
 *
 *    Use TRUE to force this to return the first of the ordered list of
 *    partial matches; we need this behavior for interactive name completion.
 */
BI_NODE *
btree_pmatch(BI_NODE *n, const int mode, const char *name)
{
      BI_NODE *m;
      size_t len = strlen(name);

      while (n != 0) {
            int cmp;

            cmp = strncmp(name, BI_KEY(n), len);

            if (cmp == 0) {
                  if (mode
                   && (m = btree_pmatch(BI_LEFT(n), mode, name)) != 0)
                        n = m;
                  return n;
            } else if (cmp < 0) {
                  n = BI_LEFT(n);
            } else {
                  n = BI_RIGHT(n);
            }
      }
      return 0;
}

/*
 * Find the size of the binary-subtree with the matching name.
 */
static int
btree_pcount(BI_NODE *node, char *matchname, size_t len)
{
      int left = 0, right = 0, me = 0;

      if (BI_LEFT(node) != 0) {
            left = btree_pcount(BI_LEFT(node), matchname, len);
      }

      if ((len == 0)
       || (strncmp(BI_KEY(node), matchname, len) == 0))
            me = 1;

      if (BI_RIGHT(node) != 0) {
            right = btree_pcount(BI_RIGHT(node), matchname, len);
      }

      return me + left + right;
}

static void
build_parray(BI_NODE *head, char *matchname, size_t len, const char **nptr, int *i)
{
      if (BI_LEFT(head) != 0) {
            build_parray(BI_LEFT(head), matchname, len, nptr, i);
      }

      if ((len == 0)
       || (strncmp(BI_KEY(head), matchname, len) == 0)) {
            nptr[*i] = BI_KEY(head);
            (*i)++;
      }

      if (BI_RIGHT(head) != 0) {
            build_parray(BI_RIGHT(head), matchname, len, nptr, i);
      }
}

/*
 * Build an array of the keys that partially-match the given name to at least
 * the given length 'len'.
 */
const char **
btree_parray(BI_TREE *tree, char *name, unsigned len)
{
      BI_NODE *top;
      const char **nptr = 0;
      top = btree_pmatch(BI_RIGHT(&(tree->head)), 0, name);

      if (top != 0) {
            int i = 0;
            size_t cnt = btree_pcount(top, name, len);
            beginDisplay();
            nptr = castalloc(const char *, sizeof(const char *) * (cnt + 1));
            endofDisplay();
            if (nptr != 0) {
                  build_parray(top, name, len, nptr, &i);
                  nptr[i] = 0;
            }
      }
      return nptr;
}

int btree_freeup(BI_TREE *funcs)
{
      TRACE(("Deleting all nodes...\n"));
      TRACE_TREE("INITIAL-", funcs);
      while (RLINK(&(funcs->head))) {
            TRACE(("Try to delete '%s'\n", KEY(RLINK(&(funcs->head)))));
            if (!btree_delete(funcs, KEY(RLINK(&(funcs->head))))) {
                  TRACE(("Try-delete failed\n"));
                  return 0;
            }
#if DEBUG_BTREE >= 0
            TRACE_TREE("AFTER-DELETE, ", funcs);
            if (!btree_verify(funcs, RLINK(&(funcs->head)))) {
                  TRACE(("Try-verify failed\n"));
                  return 0;
            }
#endif
      }
      return 1;
}

/******************************************************************************/

#if DEBUG_BTREE >= 0

static int
btree_verify(BI_TREE *funcs, BI_NODE *p)
{
#if DEBUG_BTREE >= BTREE_VERIFY
      int ok = 1;

      if (p != 0) {
            int root = (p == &(funcs->head));
            BI_NODE *l = root ? 0 : LLINK(p);
            BI_NODE *r = RLINK(p);
            int balance = 0;
            int compare = 0;

            if (p == RLINK(&(funcs->head))) {
                  int count = btree_count(p);
                  if (count != funcs->count) {
                        ok = 0;
                        TRACE(("OOPS: Counted %d vs %d in header\n",
                              count, funcs->count));
                  }
            }
            /* verify the balance factor */
            if ((balance = btree_depth(r) - btree_depth(l)) != 0) {
                  if (balance > 0) {
                        if (balance > 1) {
                              ok = 0;
                              TRACE(("OOPS: '%s' is unbalanced\n", KEY(p)));
                        }
                        balance = 1;
                  } else {
                        if (balance < -1) {
                              ok = 0;
                              TRACE(("OOPS: '%s' is unbalanced\n", KEY(p)));
                        }
                        balance = -1;
                  }
            }
            if (B(p) != balance) {
                  ok = 0;
                  TRACE(("OOPS: Balance '%s' have %d vs %d\n",
                        KEY(p), B(p), balance));
            }

            /* verify that the nodes are in correct order */
            compare = COMPARE(
                        (l != 0) ? KEY(l) : "",
                        (r != 0) ? KEY(r) : "\377");
            if (compare >= 0) {
                  ok = 0;
                  TRACE(("OOPS: Compare %s, have %d vs -1\n",
                        KEY(p), compare));
            }

            /* recur as needed */
            ok &= btree_verify(funcs, l);
            ok &= btree_verify(funcs, r);
      }
      return ok;
#else
      return 1;
#endif
}

#if DEBUG_BTREE >= BTREE_DRIVER

/******************************************************************************/
#undef typecalloc
#define typecalloc(cast) (cast *)calloc(sizeof(cast),1)

static BI_NODE *
new_node (BI_DATA * data)
{
      BI_NODE *result = typecalloc(BI_NODE);
      result->value = *data;
      result->value.bi_key = strdup(data->bi_key); /* DEBUG-only */
      return result;
}

static void
old_node (BI_NODE *node)
{
      beginDisplay();
      free(node);
      endofDisplay();
}

static void
dpy_node (BI_NODE *a, int level)
{
      while (level-- > 0)
            printf(". ");
      printf("%s (%d)", KEY(a), B(a));
      fflush(stdout);
}

static      BI_TREE     text_tree = {
      new_node,
      old_node,
      dpy_node,
      0,
      0,
      {{0,0},0,{0,0}}
      };

/******************************************************************************/

#define MAX_VEC 10000

int main(int argc, char *argv[])
{
      BI_DATA temp;
      BI_NODE *top;
      int n, m;
      int done = 0;
      char buffer[BUFSIZ];
      int vector[MAX_VEC];
      const char **list;

      memset(&temp, 0, sizeof(temp));
      for (n = 1; n < argc; n++) {
            temp.bi_key = argv[n];
            btree_insert(&text_tree, &temp);
      }

      btree_printf(&text_tree);
      btree_verify(&text_tree, RLINK(&(text_tree.head)));

      while (!done && fgets(buffer, sizeof(buffer), stdin) != 0) {
            char *t = buffer;
            char *s = t + strlen(t);

            if (s != buffer && *--s == '\n')
                  *s = 0;

            switch (*t++) {
            default:
                  printf("Commands are f(ind) i(nsert), d(elete), l(ist), p(rint), r(andom)\n");
                  break;
            case 'f':
                  n = (btree_search(&text_tree, t) != 0);
                  printf("** found(%s) %d\n", t, n);
                  break;
            case 'i':
                  temp.bi_key = t;
                  n = (btree_insert(&text_tree, &temp) != 0);
                  printf("** insert(%s) %d\n", t, n);
                  break;
            case 'd':
                  n = btree_delete(&text_tree, t);
                  printf("** delete(%s) %d\n", t, n);
                  break;
            case 'l':
                  if ((list = btree_parray(&text_tree, t, strlen(t))) != 0) {
                        printf("** list(%s)\n", t);
                        for (n = 0; list[n] != 0; n++)
                              printf("[%d] '%s'\n", n, list[n]);
                        free(list);
                  }
                  else
                        printf("** list(%s) fail\n", t);
                  break;
            case 'L':
                  if ((top = btree_pmatch(RLINK(&text_tree.head), 1, t)) != 0)
                        printf("** List(%s) -> '%s'\n", t, KEY(top));
                  else
                        printf("** List(%s) fail\n", t);
                  break;
            case 'p':
                  btree_printf(&text_tree);
                  break;
            case 'r':
                  for (n = 0; n < MAX_VEC; n++) {
                        vector[n] = random();
                        sprintf(buffer, "%d", vector[n]);
                        temp.bi_key = buffer;
                        (void) btree_insert(&text_tree, &temp);
                        printf("** inserted(%s)\n", buffer);
                  }
                  for (m = 0; m < 2; m++)
                  for (n = 0; n < MAX_VEC; n++) {
                        unsigned delete = random() & 1;
                        char *name = delete ? "delete" : "insert";
                        int ok;

                        sprintf(buffer, "%d", vector[n]);
                        printf("** random %s (%s)\n", name, buffer);
                        temp.bi_key = buffer;
                        if (delete)
                              ok = btree_delete(&text_tree, buffer);
                        else
                              ok = btree_insert(&text_tree, &temp) != 0;
                        if (!btree_verify(&text_tree, RLINK(&(text_tree.head)))) {
                              printf("OOPS: Random %s-verify '%s' failed\n", name, buffer);
                              btree_printf(&text_tree);
                              return (1);
                        }
                        printf("** result: %d\n", ok);
                  }
                  break;
            case 'q':
                  done = 1;
                  break;
            case '#':
                  break;
            }
            btree_verify(&text_tree, RLINK(&(text_tree.head)));
      }
      btree_freeup(&text_tree);

      printf("done!\n\n");
      return 0;
}
#endif /* DEBUG_BTREE >= BTREE_DRIVER */

#endif /* DEBUG_BTREE */

Generated by  Doxygen 1.6.0   Back to index