/*
Zz Dynamic Parser Library
Copyright (C) 1989 - I.N.F.N - S.Cabasino, P.S.Paolucci, G.M.Todesco
The Zz Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
The Zz Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
/* $Id: avl.c,v 1.3 2002/05/09 17:23:49 kibun Exp $ */
#include <stdlib.h>
#include <assert.h>
#define AVL_C
#include "avl.h"
#define LOOP for (;;)
#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif
#define NIL 0
#define NILARG ((void *)0)
typedef unsigned long ulong;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef struct avl_node NODE;
typedef struct avl_path PATH;
#define MBR_KEY (AVL_NODUP_MBR >> 1)
#define PTR_KEY (AVL_NODUP_PTR >> 1)
#define STR_KEY (AVL_NODUP_STR >> 1)
#define LNG_KEY (AVL_NODUP_LNG >> 1)
#define INT_KEY (AVL_NODUP_INT >> 1)
#define SHT_KEY (AVL_NODUP_SHT >> 1)
#define ULN_KEY (AVL_NODUP_ULN >> 1)
#define UIN_KEY (AVL_NODUP_UIN >> 1)
#define USH_KEY (AVL_NODUP_USH >> 1)
#define CHR_KEY (AVL_NODUP_CHR >> 1)
#define USR_CMP 0
#define STR_CMP 1
#define VAL_CMP 2
#define COR_CMP 3
#define NODUP 0
#define DUP 1
#define USR_NODUP (USR_CMP | NODUP << 2)
#define STR_NODUP (STR_CMP | NODUP << 2)
#define VAL_NODUP (VAL_CMP | NODUP << 2)
#define COR_NODUP (COR_CMP | NODUP << 2)
#define USR_DUP (USR_CMP | DUP << 2)
#define STR_DUP (STR_CMP | DUP << 2)
#define VAL_DUP (VAL_CMP | DUP << 2)
#define COR_DUP (COR_CMP | DUP << 2)
/* keyinfo: bits 6-3: KEYTYPE, bit 2: DUP, bits 1-0: CMPTYPE */
/* bits 6-2: TREETYPE, bits 2-0: LOCTYPE */
#define KEYTYPE(keyinfo) ((keyinfo) >> 3)
#define TREETYPE(keyinfo) ((keyinfo) >> 2)
#define CMPTYPE(keyinfo) ((keyinfo) & 0x3)
#define LOCTYPE(keyinfo) ((keyinfo) & 0x7)
#define MAXUSHORT (((unsigned short)(~0))>>1)
#define MINLONG ((long)~(((unsigned long)(~0L))>>1))
#define CORRECT(u) ((long)(u) + MINLONG)
#define SET_STRCMP(cmp, str1, str2) \
{ \
register char *p1, *p2; \
for (p1 = (str1), p2 = (str2); *p1 && *p1 == *p2; p1++, p2++) \
; \
(cmp) = *p1 - *p2; \
}
#define SET_PTRCMP(cmp, usrcmp, ptr1, ptr2) \
{ \
if (usrcmp) \
(cmp) = (*(usrcmp)) ((ptr1), (ptr2)); \
else \
SET_STRCMP ((cmp), (char *)(ptr1), (char *)(ptr2)) \
}
#define ERROR (-1)
#define BAL 0
#define LEFT 1
#define RIGHT 2
#define LEFTUNBAL 3
#define RIGHTUNBAL 4
#define LESS 3
#define SAME 4
#define NOTINS 0
#define INS 1
#define DEEPER 2
#define NODE_LIST 0
#define TREE_LIST (NODE_LIST + (sizeof (NODE) != sizeof(TREE))?1:0)
#define PATH_LIST (TREE_LIST + 1)
#define FREE_LISTS (PATH_LIST + 1)
#define LONG_ALIGNED_SIZE(obj) ((sizeof(obj)+sizeof(long)-1)&~(sizeof(long)-1))
#define SIZEOF_NODE LONG_ALIGNED_SIZE (NODE)
#define SIZEOF_TREE LONG_ALIGNED_SIZE (TREE)
#define SIZEOF_PATH LONG_ALIGNED_SIZE (PATH)
#define SIZEOF_LONG sizeof (long)
#define PREALLOC_LONGS ((32768 - 16) / SIZEOF_LONG)
#define PREALLOC_SIZE (PREALLOC_LONGS * SIZEOF_LONG)
#define MALLOC_LONGS ((32768 - 32) / SIZEOF_LONG)
#define MALLOC_SIZE (MALLOC_LONGS * SIZEOF_LONG)
static long Prealloc[PREALLOC_LONGS];
static void *Free_List[FREE_LISTS]; /* init to 0 by C */
static char *Avail_Base = (char *)Prealloc;
static uint Avail_Size = PREALLOC_SIZE;
/*===========================================================================*/
static void *new_memory (uint size)
{
char *base;
while (Avail_Size >= SIZEOF_NODE)
{
base = Avail_Base + (Avail_Size -= SIZEOF_NODE);
*(void **)base = Free_List[NODE_LIST];
Free_List[NODE_LIST] = (void *)base;
}
if (Avail_Base = (char *)malloc (MALLOC_SIZE))
{
Avail_Size = MALLOC_SIZE - size;
return (void *)(Avail_Base + Avail_Size);
}
else
{
Avail_Size = 0;
return NIL;
}
}
#if 0
#warning "memmgr: original implementation"
/*
this version seems to trigger a 'bug' of gcc-2.96-98 (RH7.2)
maybe due to aliasing of this inlined code
*/
#define ALLOC_OBJ(ptr, ptr_type, size, list) \
{ \
if (Free_List[list]) \
{ \
(ptr) = (ptr_type) Free_List[list]; \
Free_List[list] = *(void **)(ptr); \
} \
else if (Avail_Size >= size) \
(ptr) = (ptr_type) (Avail_Base + \
(Avail_Size -= size)); \
else \
(ptr) = (ptr_type) new_memory (size); \
}
#define FREE_OBJ(ptr, list) \
{ \
*(void **)(ptr) = Free_List[list]; \
Free_List[list] = (void *)(ptr); \
}
#elif 1
#warning "memmgr: mixed macro/inlinefun implementation"
static inline void* __alloc_obj(uint size, uint list)
{
void* ptr=0;
if (Free_List[list])
{
ptr = Free_List[list];
Free_List[list] = *(void **)(ptr);
}
else if (Avail_Size >= size)
ptr = (Avail_Base + (Avail_Size -= size));
else
ptr = new_memory (size);
return ptr;
}
static inline void __free_obj(void* ptr, uint list)
{
*(void **)(ptr) = Free_List[list];
Free_List[list] = (void *)(ptr);
}
#define ALLOC_OBJ(ptr, ptr_type, size, list) \
do { (ptr) = (ptr_type) __alloc_obj(size,list); } while(0)
#define FREE_OBJ(ptr, list) \
do { __free_obj(ptr,list); } while(0)
#else
#warning "memmgr: plain malloc/free implementation"
#define ALLOC_OBJ(ptr, ptr_type, size, list) \
do {(ptr) = (ptr_type) malloc (size);} while(0)
#define FREE_OBJ(ptr, list) \
do { free(ptr); } while(0)
#endif
#define ALLOC_NODE(node) ALLOC_OBJ (node, NODE *, SIZEOF_NODE, NODE_LIST)
#define ALLOC_TREE(tree) ALLOC_OBJ (tree, TREE *, SIZEOF_TREE, TREE_LIST)
#define ALLOC_PATH(path) ALLOC_OBJ (path, PATH *, SIZEOF_PATH, PATH_LIST)
#define FREE_NODE(node) FREE_OBJ (node, NODE_LIST)
#define FREE_TREE(tree) FREE_OBJ (tree, TREE_LIST)
#define FREE_PATH(path) FREE_OBJ (path, PATH_LIST)
/*===========================================================================*/
TREE *avl__tree (int treetype, uint keyoffs, int(*usrcmp)(void *,void *))
{
TREE *tree;
int keyinfo;
keyinfo = treetype << 2;
switch (treetype)
{
case AVL_NODUP_MBR:case AVL_DUP_MBR: keyinfo |= USR_CMP;break;
case AVL_NODUP_PTR:case AVL_DUP_PTR: keyinfo |= USR_CMP;break;
case AVL_NODUP_STR:case AVL_DUP_STR: keyinfo |= STR_CMP;break;
case AVL_NODUP_LNG:case AVL_DUP_LNG: keyinfo |= VAL_CMP;break;
case AVL_NODUP_INT:case AVL_DUP_INT: keyinfo |= VAL_CMP;break;
case AVL_NODUP_SHT:case AVL_DUP_SHT: keyinfo |= VAL_CMP;break;
case AVL_NODUP_ULN:case AVL_DUP_ULN: keyinfo |= COR_CMP;break;
case AVL_NODUP_UIN:case AVL_DUP_UIN: keyinfo |= COR_CMP;break;
case AVL_NODUP_USH:case AVL_DUP_USH: keyinfo |= VAL_CMP;break;
case AVL_NODUP_CHR:case AVL_DUP_CHR: keyinfo |= VAL_CMP;break;
default:
return NIL;
}
ALLOC_TREE (tree);
if (!tree)
return NIL;
tree->root = NIL;
tree->keyinfo = (ushort)keyinfo;
tree->keyoffs = (ushort)keyoffs;
tree->usrcmp = usrcmp;
tree->nodes = 0L;
tree->path = NIL;
return tree;
}
/*===========================================================================*/
static int rebalance (NODE **rootaddr)
{
NODE *root = *rootaddr;
NODE *newroot;
NODE *half;
switch (root->bal)
{
case LEFTUNBAL:
switch (root->left->bal)
{
case LEFT: /* simple rotation, tree depth decreased */
newroot = root->left;
root->left = newroot->right;
root->bal = BAL;
newroot->right = root;
newroot->bal = BAL;
*rootaddr = newroot;
return LESS;
break;
case BAL: /* simple rotation, tree depth unchanged */
newroot = root->left;
root->left = newroot->right;
root->bal = LEFT;
newroot->right = root;
newroot->bal = RIGHT;
*rootaddr = newroot;
return SAME;
break;
case RIGHT: /* double rotation */
half = root->left;
newroot = half->right;
root->left = newroot->right;
half->right = newroot->left;
switch (newroot->bal)
{
case BAL:
root->bal = BAL;
half->bal = BAL;
break;
case LEFT:
root->bal = RIGHT;
half->bal = BAL;
break;
case RIGHT:
root->bal = BAL;
half->bal = LEFT;
break;
}
newroot->left = half;
newroot->right = root;
newroot->bal = BAL;
*rootaddr = newroot;
return LESS;
break;
}
break;
case RIGHTUNBAL:
switch (root->right->bal)
{
case RIGHT: /* simple rotation, tree depth decreased */
newroot = root->right;
root->right = newroot->left;
root->bal = BAL;
newroot->left = root;
newroot->bal = BAL;
*rootaddr = newroot;
return LESS;
break;
case BAL: /* simple rotation, tree depth unchanged */
newroot = root->right;
root->right = newroot->left;
root->bal = RIGHT;
newroot->left = root;
newroot->bal = LEFT;
*rootaddr = newroot;
return SAME;
break;
case LEFT: /* double rotation */
half = root->right;
newroot = half->left;
root->right = newroot->left;
half->left = newroot->right;
switch (newroot->bal)
{
case BAL:
root->bal = BAL;
half->bal = BAL;
break;
case RIGHT:
root->bal = LEFT;
half->bal = BAL;
break;
case LEFT:
root->bal = BAL;
half->bal = RIGHT;
break;
}
newroot->right = half;
newroot->left = root;
newroot->bal = BAL;
*rootaddr = newroot;
return LESS;
break;
}
break;
default:
return SAME;
}
return ERROR;
}
/*===========================================================================*/
static int insert_ptr (NODE **rootaddr,NODE *node,int (*usrcmp)(void *,void *),int dup)
{
NODE *root = *rootaddr;
int cmp;
int ins;
SET_PTRCMP (cmp, usrcmp, node->key.ptr, root->key.ptr)
if (cmp < 0)
{
if (root->left)
ins = insert_ptr (&root->left, node, usrcmp, dup);
else
{
root->left = node;
ins = DEEPER;
}
switch (ins)
{
case DEEPER:
switch (root->bal)
{
case RIGHT:
root->bal = BAL;
return INS;
break;
case BAL:
root->bal = LEFT;
return DEEPER;
break;
case LEFT:
root->bal = LEFTUNBAL;
return rebalance (rootaddr) == LESS ? INS : DEEPER;
}
break;
case INS:
return INS;
break;
case NOTINS:
return NOTINS;
}
}
else if (cmp > 0 || dup)
{
if (root->right)
ins = insert_ptr (&root->right, node, usrcmp, dup);
else
{
root->right = node;
ins = DEEPER;
}
switch (ins)
{
case DEEPER:
switch (root->bal)
{
case LEFT:
root->bal = BAL;
return INS;
break;
case BAL:
root->bal = RIGHT;
return DEEPER;
break;
case RIGHT:
root->bal = RIGHTUNBAL;
return rebalance (rootaddr) == LESS ? INS : DEEPER;
}
break;
case INS:
return INS;
break;
case NOTINS:
return NOTINS;
}
}
return NOTINS;
}
/*---------------------------------------------------------------------------*/
static int insert_val (NODE **rootaddr, NODE *node,int dup)
{
NODE *root = *rootaddr;
int ins;
if (node->key.val < root->key.val)
{
if (root->left)
ins = insert_val (&root->left, node, dup);
else
{
root->left = node;
ins = DEEPER;
}
switch (ins)
{
case DEEPER:
switch (root->bal)
{
case RIGHT:
root->bal = BAL;
return INS;
break;
case BAL:
root->bal = LEFT;
return DEEPER;
break;
case LEFT:
root->bal = LEFTUNBAL;
return rebalance (rootaddr) == LESS ? INS : DEEPER;
break;
}
break;
case INS:
return INS;
break;
case NOTINS:
return NOTINS;
break;
}
}
else if (node->key.val > root->key.val || dup)
{
if (root->right)
ins = insert_val (&root->right, node, dup);
else
{
root->right = node;
ins = DEEPER;
}
switch (ins)
{
case DEEPER:
switch (root->bal)
{
case LEFT:
root->bal = BAL;
return INS;
break;
case BAL:
root->bal = RIGHT;
return DEEPER;
break;
case RIGHT:
root->bal = RIGHTUNBAL;
return rebalance (rootaddr) == LESS ? INS : DEEPER;
break;
}
break;
case INS:
return INS;
break;
case NOTINS:
return NOTINS;
break;
}
}
return NOTINS;
}
/*---------------------------------------------------------------------------*/
int avl_insert (TREE *tree,void *data)
{
NODE *node;
int keyinfo;
int ins;
ALLOC_NODE (node);
if (!node)
return FALSE;
node->data = data;
node->left = NIL;
node->right = NIL;
node->bal = BAL;
keyinfo = tree->keyinfo;
switch (KEYTYPE (keyinfo))
{
case MBR_KEY: node->key.ptr = (void *)((char *)data + tree->keyoffs);
break;
case PTR_KEY: node->key.ptr = *(void **)((char *)data + tree->keyoffs);
break;
case STR_KEY: node->key.ptr = *(void **)((char *)data + tree->keyoffs);
break;
case LNG_KEY: node->key.val = *(long *)((char *)data + tree->keyoffs);
break;
case INT_KEY: node->key.val = *(int *)((char *)data + tree->keyoffs);
break;
case SHT_KEY: node->key.val = *(short *)((char *)data + tree->keyoffs);
break;
case ULN_KEY: node->key.val =
CORRECT (*(ulong *)((char *)data + tree->keyoffs));
break;
case UIN_KEY: node->key.val =
CORRECT (*(uint *)((char *)data + tree->keyoffs));
break;
case USH_KEY: node->key.val = *(ushort *)((char *)data + tree->keyoffs);
break;
case CHR_KEY: node->key.val = * ((char *)data + tree->keyoffs);
break;
default:
FREE_NODE (node);
return FALSE;
}
if (tree->root)
{
switch (LOCTYPE (keyinfo))
{
case USR_NODUP: ins = insert_ptr (&tree->root, node, tree->usrcmp, NODUP);
break;
case STR_NODUP: ins = insert_ptr (&tree->root, node, AVL_AVLCMP, NODUP);
break;
case COR_NODUP:
case VAL_NODUP: ins = insert_val (&tree->root, node, NODUP);
break;
case USR_DUP: ins = insert_ptr (&tree->root, node, tree->usrcmp, DUP);
break;
case STR_DUP: ins = insert_ptr (&tree->root, node, AVL_AVLCMP, DUP);
break;
case COR_DUP:
case VAL_DUP: ins = insert_val (&tree->root, node, DUP);
break;
}
if (ins == NOTINS)
{
FREE_NODE (node);
return FALSE;
}
}
else
{
tree->root = node;
}
tree->nodes++;
if (tree->path)
{
FREE_PATH (tree->path);
tree->path = NIL;
}
return TRUE;
}
/*===========================================================================*/
#define SELECT_EQ_NODUP(node, val, this) \
{ \
if (this < val ) node = node->right; \
else if ( val < this) node = node->left; \
else return node->data; \
}
#define SELECT_EQ_DUP(node, val, this, save) \
{ \
if (this < val ) node = node->right; \
else if ( val < this) node = node->left; \
else { save = node; node = node->left; } \
}
#define SELECT_GE_NODUP(node, val, this, save) \
{ \
if ( val < this) { save = node; node = node->left; } \
else if (this < val ) node = node->right; \
else return node->data; \
}
#define SELECT_GE_DUP(node, val, this, save) \
{ \
if (this < val ) node = node->right; \
else { save = node; node = node->left; } \
}
#define SELECT_GT(node, val, this, save) \
{ \
if ( val < this) { save = node; node = node->left; } \
else node = node->right; \
}
#define SELECT_LE_NODUP(node, val, this, save) \
{ \
if (this < val ) { save = node; node = node->right; } \
else if ( val < this) node = node->left; \
else return node->data; \
}
#define SELECT_LE_DUP(node, val, this, save) \
{ \
if ( val < this) node = node->left; \
else { save = node; node = node->right; } \
}
#define SELECT_LT(node, val, this, save) \
{ \
if (this < val ) { save = node; node = node->right; } \
else node = node->left; \
}
/*---------------------------------------------------------------------------*/
void *avl__locate (TREE *tree, long keyval)
{
NODE *node;
NODE *save;
int (*usrcmp)(void *,void *);
int cmp;
node = tree->root;
switch (LOCTYPE (tree->keyinfo))
{
case USR_NODUP:
usrcmp = tree->usrcmp;
while (node)
{
cmp = (*usrcmp) ((void *)keyval, node->key.ptr);
SELECT_EQ_NODUP (node, cmp, 0)
}
break;
case STR_NODUP:
while (node)
{
SET_STRCMP (cmp, (char *)keyval, (char *)node->key.ptr)
SELECT_EQ_NODUP (node, cmp, 0)
}
break;
case COR_NODUP: keyval = CORRECT (keyval);
case VAL_NODUP:
while (node)
SELECT_EQ_NODUP (node, keyval, node->key.val)
break;
case USR_DUP:
save = NIL;
usrcmp = tree->usrcmp;
while (node)
{
cmp = (*usrcmp) ((void *)keyval, node->key.ptr);
SELECT_EQ_DUP (node, cmp, 0, save)
}
if (save)
return save->data;
break;
case STR_DUP:
save = NIL;
while (node)
{
SET_STRCMP (cmp, (char *)keyval, (char *)node->key.ptr)
SELECT_EQ_DUP (node, cmp, 0, save)
}
if (save)
return save->data;
break;
case COR_DUP: keyval = CORRECT (keyval);
case VAL_DUP:
save = NIL;
while (node)
SELECT_EQ_DUP (node, keyval, node->key.val, save)
if (save)
return save->data;
}
return NIL;
}
/*---------------------------------------------------------------------------*/
void *avl__locate_ge (TREE *tree, long keyval)
{
NODE *node;
NODE *save;
int (*usrcmp)(void *,void *);
int cmp;
node = tree->root;
save = NIL;
switch (LOCTYPE (tree->keyinfo))
{
case USR_NODUP:
usrcmp = tree->usrcmp;
while (node)
{
cmp = (*usrcmp) ((void *)keyval, node->key.ptr);
SELECT_GE_NODUP (node, cmp, 0, save)
}
break;
case STR_NODUP:
while (node)
{
SET_STRCMP (cmp, (char *)keyval, (char *)node->key.ptr)
SELECT_GE_NODUP (node, cmp, 0, save)
}
break;
case COR_NODUP: keyval = CORRECT (keyval);
case VAL_NODUP:
while (node)
SELECT_GE_NODUP (node, keyval, node->key.val, save)
break;
case USR_DUP:
usrcmp = tree->usrcmp;
while (node)
{
cmp = (*usrcmp) ((void *)keyval, node->key.ptr);
SELECT_GE_DUP (node, cmp, 0, save)
}
break;
case STR_DUP:
while (node)
{
SET_STRCMP (cmp, (char *)keyval, (char *)node->key.ptr)
SELECT_GE_DUP (node, cmp, 0, save)
}
break;
case COR_DUP: keyval = CORRECT (keyval);
case VAL_DUP:
while (node)
SELECT_GE_DUP (node, keyval, node->key.val, save)
}
if (save)
return save->data;
else
return NIL;
}
/*---------------------------------------------------------------------------*/
void *avl__locate_gt (TREE *tree, long keyval)
{
NODE *node;
NODE *save;
int (*usrcmp)(void *,void *);
int cmp;
node = tree->root;
save = NIL;
switch (CMPTYPE (tree->keyinfo))
{
case USR_CMP:
usrcmp = tree->usrcmp;
while (node)
{
cmp = (*usrcmp) ((void *)keyval, node->key.ptr);
SELECT_GT (node, cmp, 0, save)
}
break;
case STR_CMP:
while (node)
{
SET_STRCMP (cmp, (char *)keyval, (char *)node->key.ptr)
SELECT_GT (node, cmp, 0, save)
}
break;
case COR_CMP: keyval = CORRECT (keyval);
case VAL_CMP:
while (node)
SELECT_GT (node, keyval, node->key.val, save)
}
if (save)
return save->data;
else
return NIL;
}
/*---------------------------------------------------------------------------*/
void *avl__locate_le (TREE *tree,long keyval)
{
NODE *node;
NODE *save;
int (*usrcmp)(void *, void *);
int cmp;
node = tree->root;
save = NIL;
switch (LOCTYPE (tree->keyinfo))
{
case USR_NODUP:
usrcmp = tree->usrcmp;
while (node)
{
cmp = (*usrcmp) ((void *)keyval, node->key.ptr);
SELECT_LE_NODUP (node, cmp, 0, save)
}
break;
case STR_NODUP:
while (node)
{
SET_STRCMP (cmp, (char *)keyval, (char *)node->key.ptr)
SELECT_LE_NODUP (node, cmp, 0, save)
}
break;
case COR_NODUP: keyval = CORRECT (keyval);
case VAL_NODUP:
while (node)
SELECT_LE_NODUP (node, keyval, node->key.val, save)
break;
case USR_DUP:
usrcmp = tree->usrcmp;
while (node)
{
cmp = (*usrcmp) ((void *)keyval, node->key.ptr);
SELECT_LE_DUP (node, cmp, 0, save)
}
break;
case STR_DUP:
while (node)
{
SET_STRCMP (cmp, (char *)keyval, (char *)node->key.ptr)
SELECT_LE_DUP (node, cmp, 0, save)
}
break;
case COR_DUP: keyval = CORRECT (keyval);
case VAL_DUP:
while (node)
SELECT_LE_DUP (node, keyval, node->key.val, save)
}
if (save)
return save->data;
else
return NIL;
}
/*---------------------------------------------------------------------------*/
void *avl__locate_lt (TREE *tree, long keyval)
{
NODE *node;
NODE *save;
int (*usrcmp)(void *,void *);
int cmp;
node = tree->root;
save = NIL;
switch (CMPTYPE (tree->keyinfo))
{
case USR_CMP:
usrcmp = tree->usrcmp;
while (node)
{
cmp = (*usrcmp) ((void *)keyval, node->key.ptr);
SELECT_LT (node, cmp, 0, save)
}
break;
case STR_CMP:
while (node)
{
SET_STRCMP (cmp, (char *)keyval, (char *)node->key.ptr)
SELECT_LT (node, cmp, 0, save)
}
break;
case COR_CMP: keyval = CORRECT (keyval);
case VAL_CMP:
while (node)
SELECT_LT (node, keyval, node->key.val, save)
}
if (save)
return save->data;
else
return NIL;
}
/*---------------------------------------------------------------------------*/
void *avl_locate_first (TREE *tree)
{
NODE *node, *leftnode;
node = tree->root;
if (!node)
return NIL;
while (leftnode = node->left)
node = leftnode;
return node->data;
}
/*---------------------------------------------------------------------------*/
void *avl_locate_last (TREE *tree)
{
NODE *node, *rightnode;
node = tree->root;
if (!node)
return NIL;
while (rightnode = node->right)
node = rightnode;
return node->data;
}
/*===========================================================================*/
static NODE *leftmost (NODE **rootaddr)
{
NODE *root = *rootaddr;
NODE *node;
if (root)
{
if (root->left)
{
node = leftmost (&root->left);
if (node->bal == LESS)
{
/* left subtree depth decreased */
switch (root->bal)
{
case LEFT:
root->bal = BAL;
break;
case BAL:
root->bal = RIGHT;
node->bal = SAME;
break;
case RIGHT:
root->bal = RIGHTUNBAL;
node->bal = rebalance (rootaddr);
}
}
return node;
}
else
{
*rootaddr = root->right;
root->bal = LESS;
return root;
}
}
else
return NIL;
}
/*---------------------------------------------------------------------------*/
static NODE *remove_ptr (NODE **rootaddr, void *keyptr,int (*usrcmp)(void *,void *),int dup)
{
NODE *root = *rootaddr;
NODE *node;
int cmp;
SET_PTRCMP (cmp, usrcmp, keyptr, root->key.ptr)
if (cmp < 0)
{
if (!root->left)
return NIL;
node = remove_ptr (&root->left, keyptr, usrcmp, dup);
if (node && node->bal == LESS)
{
/* left subtree depth decreased */
switch (root->bal)
{
case LEFT:
root->bal = BAL;
break;
case BAL:
root->bal = RIGHT;
node->bal = SAME;
break;
case RIGHT:
root->bal = RIGHTUNBAL;
node->bal = rebalance (rootaddr);
}
}
}
else if (cmp > 0)
{
if (!root->right)
return NIL;
node = remove_ptr (&root->right, keyptr, usrcmp, dup);
if (node && node->bal == LESS)
{
/* right subtree depth decreased */
switch (root->bal)
{
case RIGHT:
root->bal = BAL;
break;
case BAL:
root->bal = LEFT;
node->bal = SAME;
break;
case LEFT:
root->bal = LEFTUNBAL;
node->bal = rebalance (rootaddr);
}
}
}
else
{
if (dup && root->left
&& (node = remove_ptr (&root->left, keyptr, usrcmp, dup)))
{
if (node->bal == LESS)
{
/* left subtree depth decreased */
switch (root->bal)
{
case LEFT:
root->bal = BAL;
break;
case BAL:
root->bal = RIGHT;
node->bal = SAME;
break;
case RIGHT:
root->bal = RIGHTUNBAL;
node->bal = rebalance (rootaddr);
}
}
}
else
{
node = root;
if (!node->right)
{
*rootaddr = node->left;
node->bal = LESS;
}
else if (!node->left)
{
*rootaddr = node->right;
node->bal = LESS;
}
else /* replace by the leftmost node of the right subtree */
{
root = leftmost (&node->right);
root->left = node->left;
root->right = node->right;
if (root->bal == LESS)
{
/* right subtree depth decreased */
switch (node->bal)
{
case RIGHT:
root->bal = BAL;
node->bal = LESS;
break;
case BAL:
root->bal = LEFT;
node->bal = SAME;
break;
case LEFT:
root->bal = LEFTUNBAL;
node->bal = rebalance (&root);
}
}
else
{
root->bal = node->bal;
node->bal = SAME;
}
*rootaddr = root;
}
}
}
return node;
}
/*---------------------------------------------------------------------------*/
static NODE *remove_val (NODE **rootaddr,long keyval,int dup)
{
NODE *root = *rootaddr;
NODE *node;
if (keyval < root->key.val)
{
if (!root->left)
return NIL;
node = remove_val (&root->left, keyval, dup);
if (node && node->bal == LESS)
{
/* left subtree depth decreased */
switch (root->bal)
{
case LEFT:
root->bal = BAL;
break;
case BAL:
root->bal = RIGHT;
node->bal = SAME;
break;
case RIGHT:
root->bal = RIGHTUNBAL;
node->bal = rebalance (rootaddr);
}
}
}
else if (keyval > root->key.val)
{
if (!root->right)
return NIL;
node = remove_val (&root->right, keyval, dup);
if (node && node->bal == LESS)
{
/* right subtree depth decreased */
switch (root->bal)
{
case RIGHT:
root->bal = BAL;
break;
case BAL:
root->bal = LEFT;
node->bal = SAME;
break;
case LEFT:
root->bal = LEFTUNBAL;
node->bal = rebalance (rootaddr);
}
}
}
else
{
if (dup && root->left
&& (node = remove_val (&root->left, keyval, dup)))
{
if (node->bal == LESS)
{
/* left subtree depth decreased */
switch (root->bal)
{
case LEFT:
root->bal = BAL;
break;
case BAL:
root->bal = RIGHT;
node->bal = SAME;
break;
case RIGHT:
root->bal = RIGHTUNBAL;
node->bal = rebalance (rootaddr);
}
}
}
else
{
node = root;
if (!node->right)
{
*rootaddr = node->left;
node->bal = LESS;
}
else if (!node->left)
{
*rootaddr = node->right;
node->bal = LESS;
}
else /* replace by the leftmost node of the right subtree */
{
root = leftmost (&node->right);
root->left = node->left;
root->right = node->right;
if (root->bal == LESS)
{
/* right subtree depth decreased */
switch (node->bal)
{
case RIGHT:
root->bal = BAL;
node->bal = LESS;
break;
case BAL:
root->bal = LEFT;
node->bal = SAME;
break;
case LEFT:
root->bal = LEFTUNBAL;
node->bal = rebalance (&root);
}
}
else
{
root->bal = node->bal;
node->bal = SAME;
}
*rootaddr = root;
}
}
}
return node;
}
/*---------------------------------------------------------------------------*/
void *avl__remove (TREE *tree,long keyval)
{
NODE *node;
void *data;
if (tree->root)
{
switch (LOCTYPE (tree->keyinfo))
{
case USR_NODUP:
node = remove_ptr (&tree->root, (void *)keyval, tree->usrcmp, NODUP);
break;
case STR_NODUP:
node = remove_ptr (&tree->root, (void *)keyval, AVL_AVLCMP, NODUP);
break;
case COR_NODUP: keyval = CORRECT (keyval);
case VAL_NODUP:
node = remove_val (&tree->root, keyval, NODUP);
break;
case USR_DUP:
node = remove_ptr (&tree->root, (void *)keyval, tree->usrcmp, DUP);
break;
case STR_DUP:
node = remove_ptr (&tree->root, (void *)keyval, AVL_AVLCMP, DUP);
break;
case COR_DUP: keyval = CORRECT (keyval);
case VAL_DUP:
node = remove_val (&tree->root, keyval, DUP);
}
if (node)
{
tree->nodes--;
if (tree->path)
{
FREE_PATH (tree->path);
tree->path = NIL;
}
data = node->data;
FREE_NODE (node);
return data;
}
}
return NIL;
}
/*===========================================================================*/
static void scan_subtree (NODE *root, UsrFun usrfun)
{
if (root->left) scan_subtree (root->left, usrfun);
(*usrfun) (root->data,0);
if (root->right) scan_subtree (root->right, usrfun);
}
/*---------------------------------------------------------------------------*/
static void backscan_subtree (NODE *root,UsrFun usrfun)
{
if (root->right) backscan_subtree (root->right, usrfun);
(*usrfun) (root->data,0);
if (root->left) backscan_subtree (root->left, usrfun);
}
/*---------------------------------------------------------------------------*/
void avl__scan (TREE *tree, UsrFun usrfun, int back)
{
if (tree->root)
{
if (back)
backscan_subtree (tree->root, usrfun);
else
scan_subtree (tree->root, usrfun);
}
}
/*===========================================================================*/
void *avl_first (TREE *tree)
{
PATH *path=0;
char *pathright=0;
NODE **pathnode=0;
NODE *node=0;
if (!tree->root)
return NIL;
if (!tree->path)
{
ALLOC_PATH(path);
if (!path)
return NIL;
tree->path = path;
}
else
{
path = tree->path;
}
pathnode = &(path->node[0]);
pathright = &(path->right[1]);
* pathnode = NIL; /* sentinels */
* pathright = TRUE;
*++pathnode = NIL;
*++pathright = FALSE;
*++pathnode = node = tree->root;
while (node = node->left)
{
*++pathright = FALSE;
*++pathnode = node;
}
path->pathright = pathright;
path->pathnode = pathnode;
return (*pathnode)->data;
}
/*---------------------------------------------------------------------------*/
void *avl_last (TREE *tree)
{
PATH *path;
char *pathright;
NODE **pathnode;
NODE *node;
if (!tree->root)
return NIL;
if (!tree->path)
{
ALLOC_PATH (path);
if (!path)
return NIL;
tree->path = path;
}
else
{
path = tree->path;
}
pathnode = &path->node [0];
pathright = &path->right[1];
* pathnode = NIL; /* sentinels */
* pathright = FALSE;
*++pathnode = NIL;
*++pathright = TRUE;
*++pathnode = node = tree->root;
while (node = node->right)
{
*++pathright = TRUE;
*++pathnode = node;
}
path->pathright = pathright;
path->pathnode = pathnode;
return (*pathnode)->data;
}
/*---------------------------------------------------------------------------*/
#define DOWN_RIGHT_OR_BREAK(node, pathright, pathnode) \
{ \
if (node = node->right) \
{ \
*++pathright = TRUE; \
*++pathnode = node; \
} \
else \
break; \
}
#define DOWN_LEFT_OR_BREAK(node, pathright, pathnode) \
{ \
if (node = node->left) \
{ \
*++pathright = FALSE; \
*++pathnode = node; \
} \
else \
break; \
}
#define START_OK_AND_RETURN(path, _pathright, _pathnode) \
{ \
path->pathright = _pathright; \
path->pathnode = _pathnode; \
return (*_pathnode)->data; \
}
/*---------------------------------------------------------------------------*/
void *avl__start (TREE *tree, long keyval, int back)
{
PATH *path;
char *pathright;
NODE **pathnode;
NODE *node;
char *saveright;
NODE **savenode;
int (*usrcmp)(void *,void *);
int cmp;
if (!tree->root)
return NIL;
if (!tree->path)
{
ALLOC_PATH (path);
if (!path)
return NIL;
tree->path = path;
}
else
{
path = tree->path;
}
pathnode = &path->node [0];
pathright = &path->right[1];
saveright = NIL;
savenode = NIL;
* pathnode = NIL; /* sentinels */
* pathright = !back;
*++pathnode = NIL;
*++pathright = back;
*++pathnode = node = tree->root;
switch (LOCTYPE (tree->keyinfo))
{
case USR_NODUP:
case STR_NODUP:
usrcmp = tree->usrcmp;
if (back)
LOOP
{
SET_PTRCMP (cmp, usrcmp, (void *)keyval, node->key.ptr)
if (cmp > 0)
{
saveright = pathright;
savenode = pathnode;
DOWN_RIGHT_OR_BREAK (node, pathright, pathnode)
}
else if (cmp < 0)
DOWN_LEFT_OR_BREAK (node, pathright, pathnode)
else
START_OK_AND_RETURN (path, pathright, pathnode)
}
else
LOOP
{
SET_PTRCMP (cmp, usrcmp, (void *)keyval, node->key.ptr)
if (cmp < 0)
{
saveright = pathright;
savenode = pathnode;
DOWN_LEFT_OR_BREAK (node, pathright, pathnode)
}
else if (cmp > 0)
DOWN_RIGHT_OR_BREAK (node, pathright, pathnode)
else
START_OK_AND_RETURN (path, pathright, pathnode)
}
break;
case COR_NODUP: keyval = CORRECT (keyval);
case VAL_NODUP:
if (back)
LOOP
{
if (keyval > node->key.val)
{
saveright = pathright;
savenode = pathnode;
DOWN_RIGHT_OR_BREAK (node, pathright, pathnode)
}
else if (keyval < node->key.val)
DOWN_LEFT_OR_BREAK (node, pathright, pathnode)
else
START_OK_AND_RETURN (path, pathright, pathnode)
}
else
LOOP
{
if (keyval < node->key.val)
{
saveright = pathright;
savenode = pathnode;
DOWN_LEFT_OR_BREAK (node, pathright, pathnode)
}
else if (keyval > node->key.val)
DOWN_RIGHT_OR_BREAK (node, pathright, pathnode)
else
START_OK_AND_RETURN (path, pathright, pathnode)
}
break;
case USR_DUP:
case STR_DUP:
usrcmp = tree->usrcmp;
if (back)
LOOP
{
SET_PTRCMP (cmp, usrcmp, (void *)keyval, node->key.ptr)
if (cmp >= 0)
{
saveright = pathright;
savenode = pathnode;
DOWN_RIGHT_OR_BREAK (node, pathright, pathnode)
}
else
DOWN_LEFT_OR_BREAK (node, pathright, pathnode)
}
else
LOOP
{
SET_PTRCMP (cmp, usrcmp, (void *)keyval, node->key.ptr)
if (cmp <= 0)
{
saveright = pathright;
savenode = pathnode;
DOWN_LEFT_OR_BREAK (node, pathright, pathnode)
}
else
DOWN_RIGHT_OR_BREAK (node, pathright, pathnode)
}
break;
case COR_DUP: keyval = CORRECT (keyval);
case VAL_DUP:
if (back)
LOOP
{
if (keyval >= node->key.val)
{
saveright = pathright;
savenode = pathnode;
DOWN_RIGHT_OR_BREAK (node, pathright, pathnode)
}
else
DOWN_LEFT_OR_BREAK (node, pathright, pathnode)
}
else
LOOP
{
if (keyval <= node->key.val)
{
saveright = pathright;
savenode = pathnode;
DOWN_LEFT_OR_BREAK (node, pathright, pathnode)
}
else
DOWN_RIGHT_OR_BREAK (node, pathright, pathnode)
}
}
if (savenode)
{
path->pathright = saveright;
path->pathnode = savenode;
return (*savenode)->data;
}
else
{
FREE_PATH (path);
tree->path = NIL;
return NIL;
}
}
/*---------------------------------------------------------------------------*/
void *avl_next (TREE *tree)
{
PATH *path;
char *pathright;
NODE **pathnode;
NODE *node;
path = tree->path;
if (!path)
return NIL;
pathright = path->pathright;
pathnode = path->pathnode;
if (node = (*pathnode)->right)
{
*++pathright = TRUE;
*++pathnode = node;
while (node = node->left)
{
*++pathright = FALSE;
*++pathnode = node;
}
}
else
{
while (*pathright)
{
--pathright;
--pathnode;
}
--pathright;
--pathnode;
if (!*pathnode)
{
FREE_PATH (path);
tree->path = NIL;
return NIL;
}
}
path->pathright = pathright;
path->pathnode = pathnode;
return (*pathnode)->data;
}
/*---------------------------------------------------------------------------*/
void *avl_prev (TREE *tree)
{
PATH *path;
char *pathright;
NODE **pathnode;
NODE *node;
path = tree->path;
if (!path)
return NIL;
pathright = path->pathright;
pathnode = path->pathnode;
if (node = (*pathnode)->left)
{
*++pathright = FALSE;
*++pathnode = node;
while (node = node->right)
{
*++pathright = TRUE;
*++pathnode = node;
}
}
else
{
while (!*pathright)
{
--pathright;
--pathnode;
}
--pathright;
--pathnode;
if (!*pathnode)
{
FREE_PATH (path);
tree->path = NIL;
return NIL;
}
}
path->pathright = pathright;
path->pathnode = pathnode;
return (*pathnode)->data;
}
/*---------------------------------------------------------------------------*/
void avl_stop (TREE *tree)
{
if (tree->path)
{
FREE_PATH (tree->path);
tree->path = NIL;
}
}
/*===========================================================================*/
static uint Offset;
static void *Save;
/*---------------------------------------------------------------------------*/
static void link_subtree (NODE *node)
{
if (node->right) link_subtree (node->right);
*(void **)((char *)node->data + Offset) = Save;
Save = node->data;
if (node->left) link_subtree (node->left);
}
/*---------------------------------------------------------------------------*/
static void backlink_subtree (NODE *node)
{
if (node->left) backlink_subtree (node->left);
*(void **)((char *)node->data + Offset) = Save;
Save = node->data;
if (node->right) backlink_subtree (node->right);
}
/*---------------------------------------------------------------------------*/
void *avl__link (TREE *tree, uint ptroffs, int back)
{
Offset = ptroffs;
Save = NIL;
if (tree->root)
{
if (back)
backlink_subtree (tree->root);
else
link_subtree (tree->root);
}
return Save;
}
/*===========================================================================*/
static void release_subtree (NODE *root, UsrFun usrfun)
{
if (root->left) release_subtree (root->left, usrfun);
if (root->right) release_subtree (root->right, usrfun);
(*usrfun) (root->data,0);
FREE_NODE (root);
}
/*---------------------------------------------------------------------------*/
static void reset_subtree (NODE *root)
{
if (root->left) reset_subtree (root->left);
if (root->right) reset_subtree (root->right);
FREE_NODE (root);
}
/*---------------------------------------------------------------------------*/
void avl_release (TREE *tree, UsrFun usrfun)
{
if (tree->root)
release_subtree (tree->root, usrfun);
tree->root = NIL;
tree->nodes = 0;
if (tree->path)
{
FREE_PATH (tree->path);
tree->path = NIL;
}
}
/*---------------------------------------------------------------------------*/
void avl_reset (TREE *tree)
{
if (tree->root)
reset_subtree (tree->root);
tree->root = NIL;
tree->nodes = 0;
if (tree->path)
{
FREE_PATH (tree->path);
tree->path = NIL;
}
}
/*---------------------------------------------------------------------------*/
void avl_close (TREE *tree)
{
if (tree->root)
reset_subtree (tree->root);
if (tree->path)
FREE_PATH (tree->path);
tree->keyinfo = (ushort)ERROR;
FREE_TREE (tree);
}
/*===========================================================================*/
static int copy_subtree (NODE *newroot, NODE *root)
{
newroot->key = root->key;
newroot->data = root->data;
newroot->bal = root->bal;
if (root->left)
{
ALLOC_NODE (newroot->left);
if (!newroot->left)
return FALSE;
if (!copy_subtree (newroot->left, root->left))
{
FREE_NODE (newroot->left);
return FALSE;
}
}
else
newroot->left = NIL;
if (root->right)
{
ALLOC_NODE (newroot->right);
if (!newroot->right)
return FALSE;
if (!copy_subtree (newroot->right, root->right))
{
FREE_NODE (newroot->right);
return FALSE;
}
}
else
newroot->right = NIL;
return TRUE;
}
/*---------------------------------------------------------------------------*/
TREE *avl_copy (TREE *tree)
{
TREE *newtree;
ALLOC_TREE (newtree);
if (!newtree)
return NIL;
newtree->keyinfo = tree->keyinfo;
newtree->keyoffs = tree->keyoffs;
newtree->usrcmp = tree->usrcmp;
newtree->nodes = tree->nodes;
newtree->path = NIL;
if (tree->root)
{
ALLOC_NODE (newtree->root);
if (!copy_subtree (newtree->root, tree->root))
{
FREE_NODE (newtree->root);
avl_close (newtree);
return NIL;
}
}
else
{
newtree->root = NIL;
}
return newtree;
}
/*===========================================================================*/
static void **Dat;
static int *Lev;
static int *Pos;
static int Nod;
static int Max_Lev;
/*---------------------------------------------------------------------------*/
static void dump_subtree (struct avl_node *root, int lev, int pos)
{
if (root->left) dump_subtree (root->left, lev + 1, pos * 2 );
Dat[Nod] = root->data;
Lev[Nod] = lev;
Pos[Nod] = pos;
if (lev > Max_Lev)
Max_Lev = lev;
Nod++;
if (root->right) dump_subtree (root->right, lev + 1, pos * 2 + 1);
}
/*---------------------------------------------------------------------------*/
int avl_dump (TREE *tree, void **dat_vect, int *lev_vect, int *pos_vect)
{
Dat = dat_vect;
Lev = lev_vect;
Pos = pos_vect;
Nod = 0;
Max_Lev = -1;
if (tree->root)
dump_subtree (tree->root, 0, 0);
return Max_Lev + 1;
}
/*===========================================================================*/
int avl_porting_problems ()
{
long lng1, lng2;
ushort ush1, ush2;
char chr1, chr2;
void *ptr1, *ptr2;
struct s { char c[4]; } *ps;
int problems;
#define PROBLEM(n) (problems |= 1 | (1 << (n)))
problems = 0;
Avl_Dummy[0] = 0.0;
Avl_Dummy[1] = 0.0;
((char *)Avl_Dummy)[1] = 0x15;
ptr1 = (void *)((char *)Avl_Dummy + 1);
lng1 = (long)ptr1;
ptr2 = (void *)lng1;
if (*(char *)ptr2 != (char)0x15)
PROBLEM (1);
ps = (struct s *)malloc (sizeof (struct s));
ps->c[0] = 0;
ps->c[1] = 0x15;
ps->c[2] = 0;
ps->c[3] = 0;
ptr1 = (void *)&ps->c[1];
lng1 = (long)ptr1;
ptr2 = (void *)lng1;
if (*(char *)ptr2 != (char)0x15)
PROBLEM (2);
free (ps);
chr1 = 1;
chr2 = 250;
lng1 = chr1;
lng2 = chr2;
if ((chr1 > chr2) && (lng1 < lng2) || (chr1 < chr2) && (lng1 > lng2))
PROBLEM (3);
if (sizeof (long) == sizeof (short))
PROBLEM (4);
if (sizeof (char) != 1)
PROBLEM (5);
ush1 = (ushort)-1;
ush2 = (ushort)-2;
lng1 = CORRECT (ush1);
lng2 = CORRECT (ush2);
if (!(lng1 > lng2))
PROBLEM (6);
lng1 = CORRECT (0L);
lng2 = lng1 - 1;
if (!((lng1 < 0) && (lng2 > 0)))
PROBLEM (7);
return problems;
}