tree.c File Reference

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "zix/common.h"
#include "zix/tree.h"

Classes
struct	ZixTreeImpl
struct	ZixTreeNodeImpl

Macros
#define	MIN(a, b)
#define	MAX(a, b)
#define	ASSERT_BALANCE(n)
#define	DUMP(t)
#define	DEBUG_PRINTF(fmt, ...)

Functions
ZIX_API ZixTree *	zix_tree_new (bool allow_duplicates, ZixComparator cmp, void *cmp_data, ZixDestroyFunc destroy)
ZIX_PRIVATE void	zix_tree_free_rec (ZixTree *t, ZixTreeNode *n)
ZIX_API void	zix_tree_free (ZixTree *t)
ZIX_API size_t	zix_tree_size (const ZixTree *t)
ZIX_PRIVATE void	rotate (ZixTreeNode *p, ZixTreeNode *q)
ZIX_PRIVATE ZixTreeNode *	rotate_left (ZixTreeNode *p, int *height_change)
ZIX_PRIVATE ZixTreeNode *	rotate_right (ZixTreeNode *p, int *height_change)
ZIX_PRIVATE ZixTreeNode *	rotate_left_right (ZixTreeNode *p, int *height_change)
ZIX_PRIVATE ZixTreeNode *	rotate_right_left (ZixTreeNode *p, int *height_change)
ZIX_PRIVATE ZixTreeNode *	zix_tree_rebalance (ZixTree *t, ZixTreeNode *node, int *height_change)
ZIX_API ZixStatus	zix_tree_insert (ZixTree *t, void *e, ZixTreeIter **ti)
ZIX_API ZixStatus	zix_tree_remove (ZixTree *t, ZixTreeIter *ti)
ZIX_API ZixStatus	zix_tree_find (const ZixTree *t, const void *e, ZixTreeIter **ti)
ZIX_API void *	zix_tree_get (const ZixTreeIter *ti)
ZIX_API ZixTreeIter *	zix_tree_begin (ZixTree *t)
ZIX_API ZixTreeIter *	zix_tree_end (ZixTree *t)
ZIX_API ZixTreeIter *	zix_tree_rbegin (ZixTree *t)
ZIX_API ZixTreeIter *	zix_tree_rend (ZixTree *t)
ZIX_API bool	zix_tree_iter_is_end (const ZixTreeIter *i)
ZIX_API bool	zix_tree_iter_is_rend (const ZixTreeIter *i)
ZIX_API ZixTreeIter *	zix_tree_iter_next (ZixTreeIter *i)
ZIX_API ZixTreeIter *	zix_tree_iter_prev (ZixTreeIter *i)

Macro Definition Documentation

ASSERT_BALANCE

#define ASSERT_BALANCE

(

n

)

DEBUG_PRINTF

#define DEBUG_PRINTF	(		fmt,
			... )

DUMP

#define DUMP

(

t

)

MAX

#define MAX	(		a,
			b )

Value:

(((a) > (b)) ? (a) : (b))

MIN

#define MIN	(		a,
			b )

Value:

(((a) < (b)) ? (a) : (b))

Function Documentation

rotate()

ZIX_PRIVATE void rotate	(	ZixTreeNode *	p,
		ZixTreeNode *	q )

rotate_left()

ZIX_PRIVATE ZixTreeNode * rotate_left	(	ZixTreeNode *	p,
		int *	height_change )

Rotate left about p.

p q / \ / \ A q => p C / \ / \ B C A B

rotate_left_right()

ZIX_PRIVATE ZixTreeNode * rotate_left_right	(	ZixTreeNode *	p,
		int *	height_change )

Rotate left about p->left then right about p.

 p             r
/ \           / \

q D => q p / \ / \ / \ A r A B C D / \ B C

rotate_right()

ZIX_PRIVATE ZixTreeNode * rotate_right	(	ZixTreeNode *	p,
		int *	height_change )

Rotate right about p.

 p          q
/ \        / \

q C => A p / \ / \ A B B C

rotate_right_left()

ZIX_PRIVATE ZixTreeNode * rotate_right_left	(	ZixTreeNode *	p,
		int *	height_change )

Rotate right about p->right then right about p.

p r / \ / \ A q => p q / \ / \ / \ r D A B C D / \ B C

zix_tree_free_rec()

ZIX_PRIVATE void zix_tree_free_rec	(	ZixTree *	t,
		ZixTreeNode *	n )

zix_tree_rebalance()

ZIX_PRIVATE ZixTreeNode * zix_tree_rebalance	(	ZixTree *	t,
		ZixTreeNode *	node,
		int *	height_change )