/* btlib.c */
#include <stdio.h>
#include <stdlib.h>
#include "btlib.h"

static void lib_delnode(struct Lib_node *pNdel)
{
    if (pNdel != NULL) {
        xfree(pNdel, MAGICBTLIB);
    }
	return;
}

/*---------------------------------------------------------*/
void lib_init_list(struct Lib_node **root)
{
    *root = NULL;
    return;
}

void *lib_add_list(struct Lib_node **p, void *data, int (*cmp_f)(void *, void *))
{
    struct Lib_node *new;
    int r;

    while (*p != NULL) {
        if ((r = (*cmp_f)(data, (*p)->data)) == 0)
            return (*p)->data;
        if (r < 0)
            p = &((*p)->left);
        else
            p = &((*p)->right);
    }
    new = (struct Lib_node *)xmalloc(sizeof(struct Lib_node), MAGICBTLIB);
    if (new == NULL)
        return NULL;
    new->data = data;
    new->left = new->right = NULL;
    *p = new;
    return data;
}

void *lib_delmin_list(struct Lib_node **p)
{
    struct Lib_node *q;
    void *data;

    if (*p == NULL)
        return NULL;
    while ((*p)->left != NULL)
        p = &((*p)->left);
    
    data = (*p)->data;
    q = *p;
    *p = (*p)->right;
    lib_delnode(q); /* = free(q); */
    return data;
}   

int lib_output(struct Lib_node *p, int (*out_f)(void *))
{
	p->next = NULL;
p_left:
	if (p->right != NULL)
		p->right->next = NULL;

	if (p->left != NULL) {
		p->left->next = p;
		p = p->left;
		goto p_left;
	}
p_right:
	if ((*out_f)(p->data) != OK)
		return ERR;

	if (p->right != NULL) {
		p->right->next = p;
		p = p->right;
		goto p_left;
	}
p_next:
	if (p->next != NULL) {
		p = p->next;
		if (p->right == NULL)
			goto p_right;
		if (p->right->next != p)
			goto p_right;
		else
			goto p_next;
	}
	return OK;
}

void lib_delall_list(struct Lib_node **p, void (*free_f)(void *))
{
    struct Lib_node **q;

	if (*p == NULL)
		return;
	(*p)->next = NULL;
	
p_left:
	if ((*p)->left != NULL) {
		(*p)->left->next = p;
		p = &((*p)->left);
		goto p_left;
	}
p_right:
	if ((*p)->right != NULL) {
		(*p)->right->next = p;
		p = &((*p)->right);
		goto p_left;
	}
p_next:
	if ((*p)->next != NULL) {
		q = (struct Lib_node **)((*p)->next);
		(*free_f)((*p)->data);
		lib_delnode(*p); /* = free(*p); */
		*p = NULL;
		p = q;
		goto p_right;
	}
	(*free_f)((*p)->data);
	lib_delnode(*p); /* free(*p); */
}

void *lib_find_list(struct Lib_node *p, void *data, int (*cmp_f)(void *, void *))
{
    int r;

    if (p == NULL)
        return NULL;
    while ((r = cmp_f(data, p->data)) != 0) {
        if (r < 0)
            p = p->left;
        else
            p = p ->right;
        if (p == NULL)
            return NULL;
    }
    return p->data;
}

/* end */