/*----------------------------------------------------------------------------*
| |
| 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) \
{ \
register 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;
}