Tree datastructure in C

btree.c

/*
 * -------------------------------  btree.c  ---------------------------------
 *
 * Copyright (c) 2015, Yorick de Wid <yorick17 at outlook dot com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 * Simple tree structure. It is a btree but not a binary search tree.
 *
 * Compile as:
 *     cc -std=c99 -DTEST -Wall btree.c -o btree
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <assert.h>

#include "btree.h"

static btree_node_t *btree_min(btree_node_t *x) {
	if (!x)
		return NULL;

	while(x->left)
		x = x->left;

	return x;
}

static btree_node_t *btree_max(btree_node_t *x) {
	if (!x)
		return NULL;

	while(x->right)
		x = x->right;

	return x;
}

static btree_node_t *btree_successor(btree_node_t *x) {
	btree_node_t *y;

	if (x->right)
		return btree_min(x->right);

	y = x->parent;
	while (y && x == y->right) {
		x = y;
		y = y->parent;
	}

	return y;
}

static btree_node_t *btree_search(btree_node_t *x, uint32_t key) {
	while (x && key != x->key) {
		if (key < x->key)
			x = x->left;
		else
			x = x->right;
	}
	return x;
}

static void btree_insert_node(btree_t *tree, btree_node_t *z) {
	btree_node_t *x, *y;

	y = NULL;
	x = tree->root;
	while (x) {
		y = x;
		assert(z->key != x->key);
		if (z->key < x->key)
			x = x->left;
		else
			x = x->right;
	}

	z->parent = y;
	if (!y) {
		tree->root = z;
	} else if (z->key < y->key) {
		y->left = z;
	} else {
		y->right = z;
	}
	tree->count++;
}

static btree_node_t *btree_delete_node(btree_t *tree, btree_node_t *z) {
	btree_node_t *x, *y;

	if (!z->left || !z->right)
		y = z;
	else
		y = btree_successor(z);

	if (y->left)
		x = y->left;
	else
		x = y->right;

	if (x)
		x->parent = y->parent;

	if (!y->parent) {
		tree->root = x;
	} else if (y == y->parent->left) {
		y->parent->left = x;
	} else {
		y->parent->right = x;
	}

	z->key  = y->key;
	z->data = y->data;

	tree->count--;
	return y;
}

int btree_create(btree_t **tree) {
	btree_t *t = (btree_t*)malloc(sizeof(btree_t));
	if (t) {
		t->count = 0;
		t->root = NULL;
		*tree = t;
		return 1;
	}
	return 0;
}

int btree_destroy(btree_t **tree) {
	btree_t *t = *tree;

	if (t->root) {
		printf("Tree not empty - cannot destroy\n");
		return 0;
	}

	free(t);
	*tree = NULL;
	return 1;
}

int btree_find(btree_t *tree, uint32_t key, void **d) {
	btree_node_t *x;

	x = btree_search(tree->root, key);
	if (x) {
		*d = x->data;
		return 1;
	}
	return 0;
}

int btree_add(btree_t *tree, uint32_t key, void *data) {
	btree_node_t *x;

	x = btree_search(tree->root, key);
	if (x) {
		printf("Item already exists - key %ul\n", key);
		return 0;
	}

	x = (btree_node_t *)malloc(sizeof(btree_node_t));
	x->key    = key;
	x->data   = data;
	x->parent = NULL;
	x->left   = NULL;
	x->right  = NULL;
	btree_insert_node(tree, x);

	return 1;
}

int btree_remove(btree_t *tree, uint32_t key, void **data) {
	btree_node_t *x;

	x = btree_search(tree->root, key);
	if (!x) {
		printf("Item not on tree - key %ul\n", key);
		*data = NULL;
		return 0;
	}

	/* Note value that gets freed is not necessarily the the same
	 * as node that gets removed from tree since there is an
	 * optimization to avoid pointer updates in tree which means
	 * sometimes we just copy key and data from one node to
	 * another.
	 */

	*data = x->data;
	x = btree_delete_node(tree, x);
	free(x);

	return 1;
}

int btree_get_min_key(btree_t *tree, uint32_t *key) {
	btree_node_t *x;

	if (!tree->root)
		return 0;

	x = btree_min(tree->root);
	if (!x)
		return 0;

	*key = x->key;
	return 1;
}

int btree_get_max_key(btree_t *tree, uint32_t *key) {
	btree_node_t *x;

	if (!tree->root)
		return 0;

	x = btree_max(tree->root);
	if (!x)
		return 0;

	*key = x->key;
	return 1;
}

int btree_get_next_key(btree_t *tree, uint32_t cur_key, uint32_t *next_key) {
	btree_node_t *x;

	x = btree_search(tree->root, cur_key);
	if (!x)
		return 0;

	x = btree_successor(x);
	if (!x)
		return 0;

	*next_key = x->key;
	return 1;
}

#ifdef TEST

static int btree_depth(btree_node_t *x) {
	int l, r;

	if (!x)
		return 0;

	l = btree_depth(x->left);
	r = btree_depth(x->right);

	if (l > r)
		return l+1;
	else
		return r+1;
}

static void btree_dump_node(btree_node_t *x, int depth, int c, int w) {
	if (!x)
		return;

	printf("%u ", x->key);

	btree_dump_node(x->left, depth+1, c-w/2, w/2);
	btree_dump_node(x->right, depth+1, c+w/2, w/2);
}

static void btree_dump(btree_t *b) {
	btree_dump_node(b->root, 0, 40, 48);
	putchar('\n');
}

int main() {
	btree_t *b;
	uint32_t i, *x;
	uint32_t v[] = {15, 5, 16, 3, 12, 20, 10, 13, 18, 23, 6, 7};
	uint32_t nv = sizeof(v) / sizeof(v[0]);

	btree_create(&b);

	for(i=0; i<nv; ++i) {
		x = (uint32_t*)malloc(sizeof(uint32_t));
		*x = (uint32_t)rand();
		printf(">>%u\n", *x);
		if (!btree_add(b, v[i], (void*)x))
			printf("Fail Add %u %u\n", v[i], *x);
	}

	printf("depth %d\n", btree_depth(b->root));
	btree_dump(b);

	btree_remove(b, 5, (void*)&x);
	free(x);
	btree_dump(b);

	btree_remove(b, 16, (void*)&x);
	free(x);
	btree_dump(b);

	btree_remove(b, 13, (void*)&x);
	free(x);
	btree_dump(b);

	while (btree_get_min_key(b, &i)) {
		if (!btree_remove(b, i, (void*)&x))
			fprintf(stderr, "Failed to remove %u\n", i);
		free(x);
		btree_dump(b);
	}

	if (!btree_destroy(&b))
		printf("Failed to destroy \n");

	return 0;
}

#endif

btree.h

/*
 * -------------------------------  btree.h  ---------------------------------
 *
 * Copyright (c) 2015, Yorick de Wid <yorick17 at outlook dot com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 * Simple tree structure. It is a btree but not a binary search tree.
 *
 * Compile as:
 *     cc -std=c99 -DTEST -Wall btree.c -o btree
 */

#ifndef __BTREE_H__
#define __BTREE_H__

typedef struct s_btree_node {
	uint32_t key;
	void *data;
	struct s_btree_node *parent;
	struct s_btree_node *left;
	struct s_btree_node *right;
} btree_node_t;

struct s_btree {
	btree_node_t *root;
	int count;
};

typedef struct s_btree btree_t;

/* btree_create fills the *tree with a new binary tree.  Returns TRUE on     */
/* success and FALSE on failure.                                             */

int btree_create(btree_t **tree);

/* btree_destroy destroys tree.  If tree is not empty it cannot be destroyed */
/* and call returns FALSE.  On success returns TRUE.                         */

int btree_destroy(btree_t **tree);

/* btree_add adds data for key to tree.  Returns TRUE on success, or FALSE   */
/* if key is already on tree.  */

int btree_add(btree_t *tree, uint32_t key, void *data);

/* btree_remove attempts to remove data from tree.  Returns TRUE on success  */
/* and points *d at value stored for key.  FALSE is returned if key is not   */
/* on tree.                                                                  */

int btree_remove(btree_t *tree, uint32_t key, void **d);

/* btree_find locates data for key and make *d point to it.  Returns TRUE if */
/* data for key is found, FALSE otherwise.                                   */

int btree_find(btree_t *tree, uint32_t key, void **d);

/* btree_get_min_key attempts to return minimum key of tree.  Function       */
/* intended to help if list of keys is not stored elsewhere.  Returns TRUE   */
/* and fills key with key if possible, FALSE otherwise                       */

int btree_get_min_key(btree_t *tree, uint32_t *key);
int btree_get_max_key(btree_t *tree, uint32_t *key);

/* btree_get_next_key attempts to get the key above cur_key.  Returns        */
/* TRUE and fills key with key if possible, FALSE otherwise.                 */

int btree_get_next_key(btree_t *tree, uint32_t cur_key, uint32_t *next_key);

#endif /* __BTREE_H__ */