home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 5 Edit
/
05-Edit.zip
/
vile-src.zip
/
vile-8.1
/
btree.c
< prev
next >
Wrap
C/C++ Source or Header
|
1998-04-28
|
20KB
|
913 lines
/*
* $Id: btree.c,v 1.4 1998/04/28 10:15:52 tom Exp $
* Copyright 1997 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
#include <assert.h>
#include "btree.h"
#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)
/* 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
#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
#ifdef DEBUG_BTREE
static int btree_verify(BI_TREE *funcs, BI_NODE *p);
#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 = RLINK(t),
*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 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 (;;) {
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"))
r = q;
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);
nptr = castalloc(const char *, sizeof(const char *) * (cnt + 1));
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;
}
#ifdef DEBUG_BTREE
TRACE_TREE("AFTER-DELETE, ", funcs);
if (!btree_verify(funcs, RLINK(&(funcs->head)))) {
TRACE(("Try-verify failed\n"))
return 0;
}
#endif
}
return 1;
}
/******************************************************************************/
#ifdef DEBUG_BTREE
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)
{
free(node);
}
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
};
/******************************************************************************/
#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 */