text: 
  
  /*----------------------------------------------------------------------------*
   |                                                                            |
   |                                   avl.c                                    |
   |                                                                            |
   |                by W.T.  11-MAR-91, last revision 11-OCT-96                 |
   |                                                                            |
   *----------------------------------------------------------------------------*/
  
  #ifdef _WIN32
  #pragma warning(push)
  #pragma warning(disable : 4113)
  #pragma warning(disable : 4996)
  #endif
  
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #define AVL_C
  #include "avl.h"
  #include "tcm.h"
  #define CASE \
  	break;   \
  	case
  #define __OR case
  #define DEFAULT \
  	break;      \
  	default
  
  #define LOOP for (;;)
  
  #ifndef TRUE
  #define TRUE 1
  #define FALSE 0
  #endif
  
  //#define NIL ((void *)0)
  
  typedef unsigned long ulong;
  
  #ifndef MACOSX
  
  typedef unsigned int uint;
  typedef unsigned short ushort;
  
  #endif
  
  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)
  
  #ifdef VAX
  #define SET_STRCMP(cmp, str1, str2)                                   \
  	{                                                                 \
  		char *p1, *p2;                                       \
  		for (p1 = (str1), p2 = (str2); *p1 && *p1 == *p2; p1++, p2++) \
  			;                                                         \
  		(cmp) = *(unsigned char *)p1 - *(unsigned char *)p2;          \
  	}
  #else
  #define SET_STRCMP(cmp, str1, str2)     \
  	{                                   \
  		(cmp) = strcmp((str1), (str2)); \
  	}
  #endif
  
  #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)))
  #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 (0x7FF0 / SIZEOF_LONG)
  #define PREALLOC_SIZE (PREALLOC_LONGS * SIZEOF_LONG)
  #define MALLOC_LONGS (0x7FE0 / 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;
  	}
  }
  
  /*---------------------------------------------------------------------------*/
  
  #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);   \
  	}
  
  #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 : __OR AVL_DUP_MBR : keyinfo |= USR_CMP;
  		CASE AVL_NODUP_PTR : __OR AVL_DUP_PTR : keyinfo |= USR_CMP;
  		CASE AVL_NODUP_STR : __OR AVL_DUP_STR : keyinfo |= STR_CMP;
  		CASE AVL_NODUP_LNG : __OR AVL_DUP_LNG : keyinfo |= VAL_CMP;
  		CASE AVL_NODUP_INT : __OR AVL_DUP_INT : keyinfo |= VAL_CMP;
  		CASE AVL_NODUP_SHT : __OR AVL_DUP_SHT : keyinfo |= VAL_CMP;
  		CASE AVL_NODUP_ULN : __OR AVL_DUP_ULN : keyinfo |= COR_CMP;
  		CASE AVL_NODUP_UIN : __OR AVL_DUP_UIN : keyinfo |= COR_CMP;
  		CASE AVL_NODUP_USH : __OR AVL_DUP_USH : keyinfo |= VAL_CMP;
  		CASE AVL_NODUP_CHR : __OR AVL_DUP_CHR : keyinfo |= VAL_CMP;
  	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;
  
  			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;
  
  			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;
  				CASE LEFT : root->bal = RIGHT;
  				half->bal = BAL;
  				CASE RIGHT : root->bal = BAL;
  				half->bal = LEFT;
  			}
  			newroot->left = half;
  			newroot->right = root;
  			newroot->bal = BAL;
  			*rootaddr = newroot;
  			return LESS;
  		}
  		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;
  
  			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;
  
  			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;
  				CASE RIGHT : root->bal = LEFT;
  				half->bal = BAL;
  				CASE LEFT : root->bal = BAL;
  				half->bal = RIGHT;
  			}
  			newroot->right = half;
  			newroot->left = root;
  			newroot->bal = BAL;
  			*rootaddr = newroot;
  			return LESS;
  		}
  	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;
  				CASE BAL : root->bal = LEFT;
  				return DEEPER;
  				CASE LEFT : root->bal = LEFTUNBAL;
  				return rebalance(rootaddr) == LESS ? INS : DEEPER;
  			}
  			CASE INS : return INS;
  			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;
  				CASE BAL : root->bal = RIGHT;
  				return DEEPER;
  				CASE RIGHT : root->bal = RIGHTUNBAL;
  				return rebalance(rootaddr) == LESS ? INS : DEEPER;
  			}
  			CASE INS : return INS;
  			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;
  				CASE BAL : root->bal = LEFT;
  				return DEEPER;
  				CASE LEFT : root->bal = LEFTUNBAL;
  				return rebalance(rootaddr) == LESS ? INS : DEEPER;
  			}
  			CASE INS : return INS;
  			CASE NOTINS : return NOTINS;
  		}
  	} 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;
  				CASE BAL : root->bal = RIGHT;
  				return DEEPER;
  				CASE RIGHT : root->bal = RIGHTUNBAL;
  				return rebalance(rootaddr) == LESS ? INS : DEEPER;
  			}
  			CASE INS : return INS;
  			CASE NOTINS : return NOTINS;
  		}
  	}
  	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);
  		CASE PTR_KEY : node->key.ptr = *(void **)((char *)data + tree->keyoffs);
  		CASE STR_KEY : node->key.ptr = *(void **)((char *)data + tree->keyoffs);
  		CASE LNG_KEY : node->key.val = *(long *)((char *)data + tree->keyoffs);
  		CASE INT_KEY : node->key.val = *(int *)((char *)data + tree->keyoffs);
  		CASE SHT_KEY : node->key.val = *(short *)((char *)data + tree->keyoffs);
  		CASE ULN_KEY : node->key.val =
  			CORRECT(*(ulong *)((char *)data + tree->keyoffs));
  		CASE UIN_KEY : node->key.val =
  			CORRECT(*(uint *)((char *)data + tree->keyoffs));
  		CASE USH_KEY : node->key.val = *(ushort *)((char *)data + tree->keyoffs);
  		CASE CHR_KEY : node->key.val = *((char *)data + tree->keyoffs);
  	DEFAULT:
  		FREE_NODE(node)
  		return FALSE;
  	}
  	if (tree->root) {
  		switch (LOCTYPE(keyinfo)) {
  			CASE USR_NODUP : ins = insert_ptr(&tree->root, node, tree->usrcmp, NODUP);
  			CASE STR_NODUP : ins = insert_ptr(&tree->root, node, AVL_AVLCMP, NODUP);
  			CASE COR_NODUP : __OR VAL_NODUP : ins = insert_val(&tree->root, node, NODUP);
  			CASE USR_DUP : ins = insert_ptr(&tree->root, node, tree->usrcmp, DUP);
  			CASE STR_DUP : ins = insert_ptr(&tree->root, node, AVL_AVLCMP, DUP);
  			CASE COR_DUP : __OR VAL_DUP : ins = insert_val(&tree->root, node, DUP);
  		}
  		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)
  		}
  		CASE STR_NODUP : while (node)
  		{
  			SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr)
  			SELECT_EQ_NODUP(node, cmp, 0)
  		}
  		CASE COR_NODUP : keyval = CORRECT(keyval);
  		__OR VAL_NODUP : while (node)
  							 SELECT_EQ_NODUP(node, keyval, node->key.val)
  
  								 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;
  
  		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;
  
  		CASE COR_DUP : keyval = CORRECT(keyval);
  		__OR 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)
  		}
  		CASE STR_NODUP : while (node)
  		{
  			SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr)
  			SELECT_GE_NODUP(node, cmp, 0, save)
  		}
  		CASE COR_NODUP : keyval = CORRECT(keyval);
  		__OR VAL_NODUP : while (node)
  							 SELECT_GE_NODUP(node, keyval, node->key.val, save)
  
  								 CASE USR_DUP : usrcmp = tree->usrcmp;
  		while (node) {
  			cmp = (*usrcmp)((void *)keyval, node->key.ptr);
  			SELECT_GE_DUP(node, cmp, 0, save)
  		}
  		CASE STR_DUP : while (node)
  		{
  			SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr)
  			SELECT_GE_DUP(node, cmp, 0, save)
  		}
  		CASE COR_DUP : keyval = CORRECT(keyval);
  		__OR 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)
  		}
  		CASE STR_CMP : while (node)
  		{
  			SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr)
  			SELECT_GT(node, cmp, 0, save)
  		}
  		CASE COR_CMP : keyval = CORRECT(keyval);
  		__OR 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)
  		}
  		CASE STR_NODUP : while (node)
  		{
  			SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr)
  			SELECT_LE_NODUP(node, cmp, 0, save)
  		}
  		CASE COR_NODUP : keyval = CORRECT(keyval);
  		__OR VAL_NODUP : while (node)
  							 SELECT_LE_NODUP(node, keyval, node->key.val, save)
  
  								 CASE USR_DUP : usrcmp = tree->usrcmp;
  		while (node) {
  			cmp = (*usrcmp)((void *)keyval, node->key.ptr);
  			SELECT_LE_DUP(node, cmp, 0, save)
  		}
  		CASE STR_DUP : while (node)
  		{
  			SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr)
  			SELECT_LE_DUP(node, cmp, 0, save)
  		}
  		CASE COR_DUP : keyval = CORRECT(keyval);
  		__OR 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)
  		}
  		CASE STR_CMP : while (node)
  		{
  			SET_STRCMP(cmp, (char *)keyval, (char *)node->key.ptr)
  			SELECT_LT(node, cmp, 0, save)
  		}
  		CASE COR_CMP : keyval = CORRECT(keyval);
  		__OR 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;
  					CASE BAL : root->bal = RIGHT;
  					node->bal = SAME;
  					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;
  				CASE BAL : root->bal = RIGHT;
  				node->bal = SAME;
  				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;
  				CASE BAL : root->bal = LEFT;
  				node->bal = SAME;
  				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;
  					CASE BAL : root->bal = RIGHT;
  					node->bal = SAME;
  					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;
  						CASE BAL : root->bal = LEFT;
  						node->bal = SAME;
  						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;
  				CASE BAL : root->bal = RIGHT;
  				node->bal = SAME;
  				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;
  				CASE BAL : root->bal = LEFT;
  				node->bal = SAME;
  				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;
  					CASE BAL : root->bal = RIGHT;
  					node->bal = SAME;
  					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;
  						CASE BAL : root->bal = LEFT;
  						node->bal = SAME;
  						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);
  			CASE STR_NODUP : node = remove_ptr(&tree->root, (void *)keyval, AVL_AVLCMP, NODUP);
  			CASE COR_NODUP : keyval = CORRECT(keyval);
  			__OR VAL_NODUP : node = remove_val(&tree->root, keyval, NODUP);
  			CASE USR_DUP : node = remove_ptr(&tree->root, (void *)keyval, tree->usrcmp, DUP);
  			CASE STR_DUP : node = remove_ptr(&tree->root, (void *)keyval, AVL_AVLCMP, DUP);
  			CASE COR_DUP : keyval = CORRECT(keyval);
  			__OR 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, void (*usrfun)(void *))
  {
  	if (root->left)
  		scan_subtree(root->left, usrfun);
  	(*usrfun)(root->data);
  	if (root->right)
  		scan_subtree(root->right, usrfun);
  }
  
  /*---------------------------------------------------------------------------*/
  
  static void backscan_subtree(NODE *root, void (*usrfun)(void *))
  {
  	if (root->right)
  		backscan_subtree(root->right, usrfun);
  	(*usrfun)(root->data);
  	if (root->left)
  		backscan_subtree(root->left, usrfun);
  }
  
  /*---------------------------------------------------------------------------*/
  
  void avl__scan(TREE *tree, void (*usrfun)(void *), 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;
  	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 = 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 : __OR 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)
  			}
  		CASE COR_NODUP : keyval = CORRECT(keyval);
  		__OR 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)
  		}
  		CASE USR_DUP : __OR 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)
  			}
  		CASE COR_DUP : keyval = CORRECT(keyval);
  		__OR 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, void (*usrfun)(void *))
  {
  	if (root->left)
  		release_subtree(root->left, usrfun);
  	if (root->right)
  		release_subtree(root->right, usrfun);
  	(*usrfun)(root->data);
  	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, void (*usrfun)(void *))
  {
  	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;
  }
  
  /*===========================================================================*/
  #ifdef LEVO
  int avl_porting_problems(void)
  {
  	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;
  }
  #endif
  //-----------------------------------------------------------------------------------------------
  
  #define CDB_TCALLOC(ptr, elem)                          \
  	{                                                   \
  		(ptr) = (void *)calloc((elem), sizeof(*(ptr))); \
  	}
  #define CDB_TMALLOC(ptr, elem)                           \
  	{                                                    \
  		(ptr) = (void *)malloc((elem) * sizeof(*(ptr))); \
  	}
  #define CDB_TREALLOC(ptr, elem)                                  \
  	{                                                            \
  		(ptr) = (void *)realloc((ptr), (elem) * sizeof(*(ptr))); \
  	}
  
  #define GET_STRING_FIELD(P, FIELD) \
  	(P ? (P->FIELD ? P->FIELD : "") : "")
  
  #define AVL_FOR(tree, p) for ((p) = avl_first(tree); (p); (p) = avl_next(tree))
  typedef struct
  	{
  	int index;
  	char *name;
  } COLOR_NAME;
  
  typedef struct
  	{
  	char *name;
  	char *value;
  } CDB_PARAM;
  
  typedef struct
  	{
  	char *name;
  	int num_params;
  	CDB_PARAM *param;
  } CDB_EFFECT;
  
  char *strsave(const char *str)
  {
  	char *neww;
  	if (!str)
  		return 0;
  	neww = malloc(strlen(str) + 1);
  
  	strcpy(neww, str);
  	return neww;
  }
  
  /*---------------------------------------------------------------------------*/
  
  char *strnsave(const char *str, int n)
  {
  	char *neww;
  
  	neww = malloc(n + 1);
  
  	strncpy(neww, str, n);
  	neww[n] = '\0';
  	return neww;
  }
  
  TREE *cdb_decode_all(char *names_in_plt_file, TCM_INFO tcm)
  {
  	TREE *tree;
  	char *c1, *c2, *endcol, *endstr, *ct;
  	char tmp[100];
  	int i, p;
  	CDB_TREE_ITEM *item;
  	CDB_EFFECT *effect;
  
  	tree = avl_tree_nodup_int(CDB_TREE_ITEM, index);
  
  	item = NIL;
  	endstr = strchr(names_in_plt_file, '\0');
  	c1 = names_in_plt_file;
  	c2 = NIL;
  	for (i = 0; i < tcm.n_colors + tcm.n_pencils; i++) {
  		CDB_TCALLOC(item, 1)
  		item->index = i;
  		//if (i < tcm.n_colors)
  		//  item->index = TCM_COLOR_INDEX (tcm, i);
  		//else
  		//  item->index = TCM_PENCIL_INDEX (tcm, i - tcm.n_colors);
  
  		endcol = strchr(c1, '|');
  		if (!endcol)
  			endcol = endstr;
  		c2 = strchr(c1, '\t');
  		if (!c2)
  			c2 = endcol;
  		if (*c2 == '\t') {
  			if (c2 - c1 == 1 && *c1 == '*')
  				item->group = strsave("");
  			else
  				item->group = strnsave(c1, c2 - c1);
  			c1 = c2 + 1;
  			c2 = strchr(c1, '\t');
  			if (!c2)
  				c2 = endcol;
  		} else {
  			item->group = strsave("");
  		}
  		while (*c1 == '<' && c1[1] == '!') {
  			c1 += 2;
  			ct = strstr(c1, "!>");
  			if (!ct)
  				goto error;
  			if (*c1 == 'A') {
  				c1++;
  				item->accelerator = strnsave(c1, ct - c1);
  			}
  			/* else if (*c1 == 'to be defined')... */
  			c1 = ct + 2;
  		}
  		if (c2 - c1 == 1 && *c1 == '*')
  			item->name = strsave("");
  		else
  			item->name = strnsave(c1, c2 - c1);
  
  		if (*c2 == '\t')
  			c1 = c2 + 1;
  		else
  			c1 = c2;
  		if (!*c1) {
  		} else if (*c1 == '|')
  			c1++;
  		else {
  			item->effects = avl_tree_nodup_str(CDB_EFFECT, name);
  			for (;;) {
  				ct = strstr(c1, " ! ");
  				if (ct)
  					NOT_MORE_THAN(ct, endcol)
  				ct = strstr(c1, "#! ");
  				if (ct)
  					NOT_MORE_THAN(ct, endcol)
  				c2 = strchr(c1, '#');
  				if (!c2 || c2 >= endcol)
  					break;
  				CDB_TCALLOC(effect, 1)
  				effect->name = strnsave(c1, c2 - c1);
  
  				c1 = c2 + 1;
  				c2 = strchr(c1, '#');
  				if (!c2)
  					goto error;
  				strncpy(tmp, c1, c2 - c1);
  				tmp[c2 - c1] = '\0';
  				effect->num_params = atoi(tmp);
  				if (effect->num_params)
  					CDB_TCALLOC(effect->param, effect->num_params)
  				c1 = c2 + 1;
  				for (p = 0; p < effect->num_params; p++) {
  					c2 = strchr(c1, '#');
  					if (!c2)
  						goto error;
  					effect->param[p].name = strnsave(c1, c2 - c1);
  					c1 = c2 + 1;
  					c2 = (p == effect->num_params - 1) ? endcol : strstr(c1, " : ");
  					if (!c2)
  						goto error;
  					effect->param[p].value = strnsave(c1, c2 - c1);
  					ct = effect->param[p].value + strlen(effect->param[p].value) - 1;
  					while (ct >= effect->param[p].value && (*ct == ' ' || *ct == '\t'))
  						*ct-- = '\0';
  					c1 = c2 + 3;
  				}
  				avl_insert(item->effects, effect);
  				item->num_effects++;
  				if (*endcol != '|')
  					c1 = endcol + 3;
  				else {
  					c1 = endcol + 1;
  					break;
  				}
  			}
  		}
  		avl_insert(tree, item);
  	}
  	return tree;
  
  error:
  
  	printf("error parsing color names and fx\n");
  
  	return tree;
  }
  