/* (C) Copyright International Business Machines Corporation 23 January */
/* 1990.  All Rights Reserved. */
/*  */
/* See the file USERAGREEMENT distributed with this software for full */
/* terms and conditions of use. */
/* File: t_avl.c */
/* Author: David F. Bacon */
#ifndef lint
static char sccsinfo[] = "@(#)t_avl.c	1.15 3/13/90";
#endif

#include <varargs.h>

#include "li.h"
#include "storage.h"
#include "accessors.h"

#include "tablefuncs.h"

#define MAXDEPTH 30
				/* no more than 2^MAXDEPTH elements */

#define avlt(t, tblnum) ((t)->tbls[tblnum].rep.keyavl)

#define is_whole_key(key) (get_elem(key, 0).table->size is 0)

#define TOP(pos) (pos->stk[pos->top].node)
#define PUSH(pos, n, dir) ((pos)->stk[++((pos)->top)].direction = dir, \
			      (pos)->stk[(pos)->top].node = n)
#define POP(pos) (pos->stk[pos->top--].direction)
#define NONEMPTY(pos) (pos->top >= 0)



/*ARGSUSED*/
status				/* doubles as avl_precopy */
avl_alloc(t, tblnum, newval)
dfd_table *t;
trepnum tblnum;
valcell newval;
{
    avlt(t, tblnum) = nil;
    return(SUCCESS);
}



predef_exception
avl_insert(t, tblnum, val)
dfd_table *t;
trepnum tblnum;
valcell val;
{
    valcell get_key();
    predef_exception avltree_insert();

    return(avltree_insert(t, get_key(t, tblnum), & avlt(t, tblnum), val));
}


void
avl_uninsert(t, tblnum, val)
dfd_table *t;
trepnum tblnum;
valcell val;
{
    void avltree_delete();

    avltree_delete(t, get_key(t, tblnum), (avl_position *) nil,
		   & avlt(t, tblnum), val);
}



int
avl_foreach(va_alist)
va_dcl
{
    int foreach_trav();

    va_tableargs(argv, t, tblnum, func, elemcounter, expectedval)

    return(foreach_trav(& avlt(t, tblnum), t, tblnum, func, elemcounter, 
			expectedval, argv)); 
}


static int
foreach_trav(avltree, t, tblnum, func, elemcounter, expectedval, argv)
avlnode_t **avltree;
dfd_table *t;
trepnum tblnum;
int (*func)();
counter *elemcounter;
int expectedval;
va_list argv;
{
    int rc;


    if (*avltree is nil)
      return(expectedval);

    rc = foreach_trav(& (*avltree)->left, t, tblnum, func, elemcounter, 
		      expectedval, argv);
    if (rc isnt expectedval)
      return(rc);

    rc = (*func)(t, tblnum, (*avltree)->value, *elemcounter, argv);
    if (rc isnt expectedval)
      return(rc);

    return(foreach_trav(& (*avltree)->right, t, tblnum, func, elemcounter, 
			expectedval, argv));
}


/*ARGSUSED*/
status
avl_initget(t, tblnum, pos, initpos)
dfd_table *t;
trepnum tblnum;
position *pos;
int initpos;			/* ignored: we are unordered */
{
    void pushleft();

    counter size;

    /* following expression is guaranteed greater than the maximum */
    /* depth of an AVL tree with n nodes, as given in Horowitz&Sahni, */
    /* p. 454, as log_phi(sqrt(5)*(n+1)) - 2, where phi is the golden */
    /* ratio, (1+sqrt(5))/2 */
    size = 2*intlog(t->size+1)+2;

    pos->avl = (avl_position *) 
      getmain(sizeof(avl_position) +
	      sizeof(nodepos) * (size - ARBSIZE));
    if (pos->avl is nil)
      return(FAILURE);

    pos->avl->size = size;
    pos->avl->top = 0;
    pos->avl->stk[0].node = avlt(t, tblnum);
    pos->avl->stk[0].direction = AVL_LEFT;

    if (pos->avl->stk[0].node is nil)
      pos->avl->top = -1;	/* make it an empty stack */
    else
      pushleft(pos->avl);

    return(SUCCESS);
}


/*ARGSUSED*/
predef_exception
avl_get(t, tblnum, pos, val)
dfd_table *t;
trepnum tblnum;
position *pos;
valcell *val;
{
    void popright();


    if (not NONEMPTY(pos->avl))
      return(NotFound);

    *val = TOP(pos->avl)->value;
    popright(pos->avl);
    return(Normal);
}


/*ARGSUSED*/
void
avl_remove(t, tblnum, val, keytblnum, seltblnum, pos)
dfd_table *t;
trepnum tblnum;
valcell val;
trepnum keytblnum;
trepnum seltblnum;
position *pos;
{
    void avltree_delete();

    avltree_delete(t, get_key(t, tblnum), 
		   (tblnum is seltblnum ? pos->avl : (avl_position *) nil),
		   & avlt(t, tblnum), val);
}



/* Routines to fix an avl_position during deletion. */
/* If the 'pos' parameter is nil in either routine, nothing is done. */

/* Remove the node being deleted from the current position stack.  This */
 /* can only happen when that node has an empty left subtree and a right */
 /* subtree with exactly one node (that node being the one currently */
 /* pointed at by the finger) */
void
avl_rm_from_path(node, pos)
avlnode_t *node;
avl_position *pos;
{
    int oldtop;

    if (pos isnt nil)		/* is there a finger to update? */
      if (NONEMPTY(pos)) {	/* and is it not yet exhausted? */
	  oldtop = pos->top--;	/* yes, path shrinks by one */
				/* and splice out doomed node */
	  pos->stk[oldtop-1].node = pos->stk[oldtop].node;
      }
}

/* Splice a new node into the path.  If the old node is not currently on */
 /* the path, this is a no-op, otherwise the new node is spliced in */
 /* before the old node.  The direction from new to old is set as */
 /* specified in the 'dir' argument; direction to new is same as former */
 /* direction to old from its former parent */
void
avl_add_to_path(oldnode, newnode, dir, pos)
avlnode_t *newnode, *oldnode;
flag dir;
avl_position *pos;
{
    int i, j;

    if (pos isnt nil)		/* is there a finger to adjust? */
      if (NONEMPTY(pos)) {	/* and is it not yet exhausted? */
	  for (i = 0; i <= pos->top; i++) /* locate the old node */
	    if (pos->stk[i].node is oldnode)
	      break;
	  if (i <= pos->top) {	/* it was in the path */
	      for (j = ++(pos->top); j > i; j--) /* make room for new node */
		pos->stk[j] = pos->stk[j-1];
	      pos->stk[i].node = newnode; /* insert the new node */
	      pos->stk[i+1].node = oldnode; /* and move the old one done */
	      pos->stk[i+1].direction = dir;
	  }
      }
}

/* Back up a path to the given node */
void
avl_truncate_path(node, pos)
avlnode_t *node;
avl_position *pos;
{
    if (pos isnt nil)
      if (NONEMPTY(pos))
          while (pos->stk[pos->top].node isnt node)
	      pos->top--;
}

/*ARGSUSED*/
void
avl_endget(t, tblnum, pos)
dfd_table *t;
trepnum tblnum;
position *pos;
{
    freemain(pos->avl, sizeof(avl_position) + 
	     (pos->avl->size - ARBSIZE) * sizeof(nodepos));
}


/******************************************************************************
 *                        Generic Functions                                   *
 *****************************************************************************/

void
avl_finalize(t, tblnum, depth, f_op, sched)
dfd_table *t;
trepnum tblnum;
flag depth;
finalize_op f_op;
schedblock *sched;
{
    void trav_finalize();

    trav_finalize(& avlt(t, tblnum), depth, f_op, t->tsdr->finalize, sched);
}


void
trav_finalize(avltree, depth, f_op, finalizer, sched)
avlnode_t **avltree;
flag depth;
finalize_op f_op;
void (*finalizer)();
schedblock *sched;
{
    if (not *avltree)
      return;

    trav_finalize(&(*avltree)->left, depth, f_op, finalizer, sched);

    if (depth is DEEP) 
      (*finalizer)((*avltree)->value, f_op, sched);

    trav_finalize(&(*avltree)->right, depth, f_op, finalizer, sched);

    { dispose(*avltree, avlnode_t); }
    *avltree = nil;
}


#define S1 (& s1.p)
#define S2 (& s2.p)

status
avl_equal(t1, tblnum, t2)
dfd_table *t1;
trepnum tblnum;
dfd_table *t2;
{
    void popright();
    void pushleft();

    struct {
	avl_position p;
	nodepos s[MAXDEPTH];	/* placeholder for stack */
    } s1, s2;

    
    s1.p.top = 0;
    s1.p.stk[0].node = avlt(t1, tblnum);
    s1.p.stk[0].direction = AVL_LEFT;
    s2.p.top = 0;
    s2.p.stk[0].node = avlt(t2, tblnum);
    s2.p.stk[0].direction = AVL_LEFT;

    pushleft(S1); pushleft(S2);
    
    while (NONEMPTY(S1)) {
	if ((*t1->tsdr->equal)(TOP(S1)->value, TOP(S2)->value)
	    is FAILURE)
	  return(FAILURE);

	popright(S1); popright(S2);
    }

    return(SUCCESS);
}    

status
avl_comparekeys(t1, tblnum, t2)
dfd_table *t1;
trepnum tblnum;
dfd_table *t2;
{
    void popright();
    void pushleft();

    struct {
	avl_position p;
	nodepos s[MAXDEPTH];	/* placeholder for stack */
    } s1, s2;
    comparison cmp;
    
    s1.p.top = 0;
    s1.p.stk[0].node = avlt(t1, tblnum);
    s1.p.stk[0].direction = AVL_LEFT;
    s2.p.top = 0;
    s2.p.stk[0].node = avlt(t2, tblnum);
    s2.p.stk[0].direction = AVL_LEFT;

    pushleft(S1); pushleft(S2);
    
    while (NONEMPTY(S1)) {
	if ((cmp = (*t1->tsdr->comparekeys)(TOP(S1)->value, TOP(S2)->value))
	    isnt CMP_EQUAL)
	  return(cmp);

	popright(S1); popright(S2);
    }

    return(cmp);
}    

/******************************************************************************
 *                        Keyed Operations                                    *
 *****************************************************************************/

status 
avl_find(t, tblnum, lookupvals, valp)
dfd_table *t;
trepnum tblnum;
object **lookupvals;
valcell *valp;
{
    comparison keyed_lookup();

    valcell v;
    avlnode_t *top;
    valcell key;


    key = get_key(t, tblnum);
    top = avlt(t,tblnum);

    while (top) {

	v = top->value;
				/* stuff the pointer in */

	switch (keyed_lookup(t, v, key, lookupvals)) {
	  case CMP_EQUAL: {
	      *valp = v;
	      return(SUCCESS);
	  }

	  case CMP_LESS: {
	      top = top->left;
	      break;
	  }

	  case CMP_GREATER: {
	      top = top->right;
	      break;
	  }
	}
    }

    return(FAILURE);
}

/******************************************************************************
 *                        Support Functions                                   *
 *****************************************************************************/

void
pushleft(pos)
avl_position *pos;
{
    avlnode_t *topnode;

    while (topnode = TOP(pos)->left)
      PUSH(pos, topnode, AVL_LEFT);
}

void 
popright(pos)
avl_position *pos;
{
    avlnode_t *topnode;
    flag direction;


    if (topnode = TOP(pos)->right) {
	PUSH(pos, topnode, AVL_RIGHT);
	pushleft(pos);
    }
    else {
	direction = AVL_RIGHT;

	while (direction is AVL_RIGHT and NONEMPTY(pos))
	  direction = POP(pos);
    }
}



/* topcomp: this is the function used to compare two elements of the table
   and decide which one comes first in the total order imposed on key values.
   used by insert.
 */

comparison
topcomp(v1,v2,table,key)
valcell v1;
valcell v2;
dfd_table *table;
valcell key;			/* interpform!operand_list */
{
    comparison cmp;
    valcell op;			/* interpform!operand */
    int theoffset;
    int field, offset;
    dotcontainer *ep1, *ep2;
    object *o1, *o2;


    if (is_whole_key(key))	/* if the keyset consists of a single key */
				/*  which is empty, then the whole object */
				/*  is the key.  just invoke the comparekeys */
				/*  routine for that object. */
      return(table->tsdr->comparekeys(v1,v2));

    /* only certain fields are part of the key. compare each in succession */

    for (field = 0; field < size_of(key); field++) {
				/* cycle through all key fields... */
	op = get_elem(key, field);

	ep1 = v1.record;	/* start up the grody address arithmetic */
	ep2 = v2.record;

	for (offset = 0; offset < size_of(op); offset++) {
				/* find the corresponding components */
	    theoffset = get_elem(op, offset).integer;

	    o1 = ((object *) ep1->data) + theoffset;
	    ep1 = o1->value.record;

	    o2 = ((object *) ep2->data) + theoffset;
	    ep2 = o2->value.record;
	}

	cmp = (*o1->tsdr->comparekeys)(o1->value, o2->value);
				/* compare the two key components. */
	if (cmp isnt CMP_EQUAL)
	  return(cmp);		/* if not equal, return the status. */
    }				/* otherwise, go back for more. */

    return(CMP_EQUAL);		/* each key component made it through, so  */
				/*  they're all equal. */
}




static comparison
keyed_lookup(t, v1, key, lookupvals)
dfd_table *t;
valcell v1;
valcell key;
object **lookupvals;
{
    comparison cmp;
    valcell op;
    dotcontainer *ep1;
    object *o1;
    counter field, offset;


    if (is_whole_key(key))	/* if keys (*), then the whole object */
				/*  is the key.  just invoke the comparekeys */
				/*  routine for that object. */
      return((*t->tsdr->comparekeys)((*lookupvals)->value, v1));

    /* only certain fields are part of the key. */
    /* compare each one in succession */

    for (field = 0; field < size_of(key); field++) {
				/* cycle through all key fields... */
	op = get_elem(key, field);

	ep1 = v1.record;	/* do up the grody address arithmetic */

	for (offset = 0; offset < size_of(op); offset++) {
				/* find the corresponding components */
	    o1 = ((object *) ep1->data) + get_elem(op, offset).integer;
	    ep1 = o1->value.record;
	}

	cmp = (*o1->tsdr->comparekeys)(lookupvals[field]->value, o1->value);
				/* compare the two key components. */
	if (cmp isnt CMP_EQUAL)
	  return(cmp);		/* if not equal, return the status. */
    }

    return(CMP_EQUAL);		/* each key component made it through, so  */
				/*  they're all equal. */
}

static int			/* returns ceiling(log2(u)) */
intlog(u)
unsigned u;
{
    unsigned b;
    int p;

    for (b = 1<<31, p = 31; b > 0; b = b>>1, p--)
      if (u & b)
	return(p+1);

    return(0);
}
