#include "util.h"
#include "btree.h"
#include <stdlib.h>
struct btree_node {
void *data;
struct btree_node *left;
struct btree_node *right;
};
struct btree {
struct btree_node *root;
int size;
fdata_t free_data; /* pointer to function that free's the data */
};
static struct btree_node *newnode(void *data);
static void free_under(struct btree *handle, struct btree_node *root);
static void free_data_of_node(struct btree *handle, struct btree_node *p);
void btree_init(struct btree **handle, fdata_t free_data)
{
struct btree *new = Malloc(sizeof(struct btree_node));
new->root = NULL;
new->size = 0;
new->free_data = free_data;
*handle = new;
}
void btree_free(struct btree *handle)
{
if (handle == NULL)
return;
free_under(handle, handle->root);
free(handle);
}
/* Same data would be overwritten */
int btree_append(struct btree *handle, void *data, cmp_t cmp)
{
struct btree_node *p, **tostore;
if (handle == NULL)
return -1;
tostore = &(handle->root);
p = *tostore;
while (p != NULL) {
int cond;
if ((cond = (*cmp)(p->data, data)) > 0) {
tostore = &(p->left);
} else if (cond < 0) {
tostore = &(p->right);
} else {
if (handle->free_data != NULL)
(*handle->free_data)(p->data);
p->data = data;
return handle->size;
}
p = *tostore;
}
*tostore = newnode(data);
return ++handle->size;
}
const void *btree_search(struct btree *handle, const void *data, cmp_t cmp)
{
int cond;
struct btree_node *p = handle->root;
while (p != NULL && (cond = (*cmp)(p->data, data)) != 0) {
p = cond > 0? p->left : p->right;
}
return p == NULL? NULL : p->data;
}
/* helper functions */
static struct btree_node *newnode(void *data)
{
struct btree_node *new = Malloc(sizeof(struct btree_node));
new->data = data;
new->left = NULL;
new->right = NULL;
return new;
}
/* NOTE: This function recursively free's the tree */
static void free_under(struct btree *handle, struct btree_node *root)
{
if (root == NULL)
return;
free_under(handle, root->left);
free_under(handle, root->right);
free_data_of_node(handle, root);
free(root);
}
static void free_data_of_node(struct btree *handle, struct btree_node *p)
{
if (p == NULL || handle == NULL)
return;
if (p->data != NULL && handle->free_data != NULL)
(*handle->free_data)(p->data);
}
바이너리트리 구현인데 깔쌈하게 만든듯
struct btree *new = Malloc(sizeof(struct btree_node)); 가 아니라 struct btree *new = Malloc(sizeof(struct btree)); 로 해야되는거 아님?
어 머야