DataMuseum.dk

top - metrics - download

    Length: 3548 (0xddc)
    Types: TextFile
    Names: »advavl.c«

└─⟦b20c6495f⟧ Bits:30007238 EUUGD18: Wien-båndet, efterår 1987
    └─⟦this⟧ »EUUGD18/General/Advsys/advavl.c« 

TextFile

/* advavl.c - avl tree manipulation routines */
/*
	Copyright (c) 1986, by David Michael Betz
	All rights reserved
*/

#include "advavl.h"
#include "advdbs.h"

#define TRUE	1
#define FALSE	0
#define NULL	0

/* external routines */
extern char *save();
extern char *malloc();

/* external variables */
extern char *data;
extern int curwrd;
extern int dptr;

/* local variables */
static TREE *curtree;
static char thiskey[WRDSIZE+1];

/* tnew - allocate a new avl tree */
TREE *tnew()
{
    TREE *tree;

    /* allocate the tree structure */
    if ((tree = (TREE *)malloc(sizeof(TREE))) == NULL)
	return (NULL);

    /* initialize the new tree */
    tree->tr_root = NULL;
    tree->tr_cnt = 0;

    /* return the new tree */
    return (tree);
}

/* tenter - add an entry to an avl tree */
int tenter(tree,key)
  TREE *tree; char *key;
{
    int h;
    curtree = tree;
    strncpy(thiskey,key,WRDSIZE); thiskey[WRDSIZE] = 0;
    return (tenter1(&tree->tr_root,&h));
}

/* tenter1 - internal insertion routine */
int tenter1(pnode,ph)
  TNODE **pnode; int *ph;
{
    TNODE *p,*q,*r;
    int val,c;

    /* check for the subtree being empty */
    if ((p = *pnode) == NULL) {
	if (p = (TNODE *)malloc(sizeof(TNODE))) {
	    curtree->tr_cnt++;
	    KEY(p) = save(thiskey);
	    WORD(p) = curwrd;
	    LLINK(p) = RLINK(p) = NULL;
	    B(p) = 0;
	    *pnode = p;
	    *ph = TRUE;
	    return (WORD(p));
	}
	else {
	    *ph = FALSE;
	    return (NIL);
	}
    }

    /* otherwise, check for a match at this node */
    else if ((c = strcmp(thiskey,KEY(p))) == 0) {
	*ph = FALSE;
	return (WORD(p));
    }

    /* otherwise, check the left subtree */
    else if (c < 0) {
	val = tenter1(&LLINK(p),ph);
	if (*ph)
	    switch (B(p)) {
	    case 1:
		B(p) = 0;
		*ph = FALSE;
		break;
	    case 0:
		B(p) = -1;
		break;
	    case -1:
		q = LLINK(p);
		if (B(q) == -1) {
		    LLINK(p) = RLINK(q);
		    RLINK(q) = p;
		    B(p) = 0;
		    p = q;
		}
		else {
		    r = RLINK(q);
		    RLINK(q) = LLINK(r);
		    LLINK(r) = q;
		    LLINK(p) = RLINK(r);
		    RLINK(r) = p;
		    B(p) = (B(r) == -1 ?  1 : 0);
		    B(q) = (B(r) ==  1 ? -1 : 0);
		    p = r;
		}
		B(p) = 0;
		*pnode = p;
		*ph = FALSE;
		break;
	    }
    }

    /* otherwise, check the right subtree */
    else {
	val = tenter1(&RLINK(p),ph);
	if (*ph)
	    switch (B(p)) {
	    case -1:
		B(p) = 0;
		*ph = FALSE;
		break;
	    case 0:
		B(p) = 1;
		break;
	    case 1:
		q = RLINK(p);
		if (B(q) == 1) {
		    RLINK(p) = LLINK(q);
		    LLINK(q) = p;
		    B(p) = 0;
		    p = q;
		}
		else {
		    r = LLINK(q);
		    LLINK(q) = RLINK(r);
		    RLINK(r) = q;
		    RLINK(p) = LLINK(r);
		    LLINK(r) = p;
		    B(p) = (B(r) ==  1 ? -1 : 0);
		    B(q) = (B(r) == -1 ?  1 : 0);
		    p = r;
		}
		B(p) = 0;
		*pnode = p;
		*ph = FALSE;
		break;
	    }
    }

    /* return the node found or inserted */
    return (val);
}

/* tfind - find an entry in an avl tree */
int tfind(tree,key)
  TREE *tree; char *key;
{
    strncpy(thiskey,key,WRDSIZE); thiskey[WRDSIZE] = 0;
    return (tfind1(tree->tr_root));
}

/* tfind1 - internal lookup routine */
int tfind1(node)
  TNODE *node;
{
    int c;

    /* check for the subtree being empty */
    if (node == NULL)
	return (NIL);

    /* otherwise, check for a match at this node */
    else if ((c = strcmp(thiskey,KEY(node))) == 0)
	return (WORD(node));

    /* otherwise, check the left subtree */
    else if (c < 0)
	return (tfind1(LLINK(node)));

    /* otherwise, check the right subtree */
    else
	return (tfind1(RLINK(node)));
}