btree.c File Reference

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

Go to the source code of this file.

Classes
struct	ZixBTreeImpl
struct	ZixBTreeNodeImpl
struct	ZixBTreeIterFrame
struct	ZixBTreeIterImpl

Macros
#define	ZIX_BTREE_PAGE_SIZE   4096
#define	ZIX_BTREE_NODE_SPACE   (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint16_t))
#define	ZIX_BTREE_LEAF_VALS   ((ZIX_BTREE_NODE_SPACE / sizeof(void*)) - 1)
#define	ZIX_BTREE_INODE_VALS   (ZIX_BTREE_LEAF_VALS / 2)

Functions
ZIX_PRIVATE ZixBTreeNode *	zix_btree_node_new (const bool leaf)
ZIX_API ZixBTree *	zix_btree_new (const ZixComparator cmp, void *const cmp_data, const ZixDestroyFunc destroy)
ZIX_PRIVATE void	zix_btree_free_rec (ZixBTree *const t, ZixBTreeNode *const n)
ZIX_API void	zix_btree_free (ZixBTree *const t)
ZIX_API size_t	zix_btree_size (const ZixBTree *const t)
ZIX_PRIVATE uint16_t	zix_btree_max_vals (const ZixBTreeNode *const node)
ZIX_PRIVATE uint16_t	zix_btree_min_vals (const ZixBTreeNode *const node)
ZIX_PRIVATE void	zix_btree_ainsert (void **const array, const uint16_t n, const uint16_t i, void *const e)
ZIX_PRIVATE void *	zix_btree_aerase (void **const array, const uint16_t n, const uint16_t i)
ZIX_PRIVATE ZixBTreeNode *	zix_btree_split_child (ZixBTreeNode *const n, const uint16_t i, ZixBTreeNode *const lhs)
ZIX_PRIVATE uint16_t	zix_btree_node_find (const ZixBTree *const t, const ZixBTreeNode *const n, const void *const e, bool *const equal)
ZIX_API ZixStatus	zix_btree_insert (ZixBTree *const t, void *const e)
ZIX_PRIVATE ZixBTreeIter *	zix_btree_iter_new (const ZixBTree *const t)
ZIX_PRIVATE void	zix_btree_iter_set_frame (ZixBTreeIter *const ti, ZixBTreeNode *const n, const uint16_t i)
ZIX_PRIVATE bool	zix_btree_node_is_minimal (ZixBTreeNode *const n)
ZIX_PRIVATE ZixBTreeNode *	zix_btree_rotate_left (ZixBTreeNode *const parent, const uint16_t i)
ZIX_PRIVATE ZixBTreeNode *	zix_btree_rotate_right (ZixBTreeNode *const parent, const uint16_t i)
ZIX_PRIVATE ZixBTreeNode *	zix_btree_merge (ZixBTree *const t, ZixBTreeNode *const n, const uint16_t i)
ZIX_PRIVATE void *	zix_btree_remove_min (ZixBTree *const t, ZixBTreeNode *n)
ZIX_PRIVATE void *	zix_btree_remove_max (ZixBTree *const t, ZixBTreeNode *n)
ZIX_API ZixStatus	zix_btree_remove (ZixBTree *const t, const void *const e, void **const out, ZixBTreeIter **const next)
ZIX_API ZixStatus	zix_btree_find (const ZixBTree *const t, const void *const e, ZixBTreeIter **const ti)
ZIX_API ZixStatus	zix_btree_lower_bound (const ZixBTree *const t, const void *const e, ZixBTreeIter **const ti)
ZIX_API void *	zix_btree_get (const ZixBTreeIter *const ti)
ZIX_API ZixBTreeIter *	zix_btree_begin (const ZixBTree *const t)
ZIX_API bool	zix_btree_iter_is_end (const ZixBTreeIter *const i)
ZIX_API void	zix_btree_iter_increment (ZixBTreeIter *const i)
ZIX_API void	zix_btree_iter_free (ZixBTreeIter *const i)

Macro Definition Documentation

ZIX_BTREE_INODE_VALS

#define ZIX_BTREE_INODE_VALS   (ZIX_BTREE_LEAF_VALS / 2)

ZIX_BTREE_LEAF_VALS

#define ZIX_BTREE_LEAF_VALS   ((ZIX_BTREE_NODE_SPACE / sizeof(void*)) - 1)

ZIX_BTREE_NODE_SPACE

#define ZIX_BTREE_NODE_SPACE   (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint16_t))

ZIX_BTREE_PAGE_SIZE

#define ZIX_BTREE_PAGE_SIZE   4096

Function Documentation

zix_btree_aerase()

ZIX_PRIVATE void * zix_btree_aerase	(	void **const	array,
		const uint16_t	n,
		const uint16_t	i )

Erase element i in array of length n and return erased element.

zix_btree_ainsert()

ZIX_PRIVATE void zix_btree_ainsert	(	void **const	array,
		const uint16_t	n,
		const uint16_t	i,
		void *const	e )

Shift pointers in array of length n right starting at i.

zix_btree_free_rec()

ZIX_PRIVATE void zix_btree_free_rec	(	ZixBTree *const	t,
		ZixBTreeNode *const	n )

zix_btree_iter_new()

ZIX_PRIVATE ZixBTreeIter * zix_btree_iter_new

(

const ZixBTree *const

t

)

zix_btree_iter_set_frame()

ZIX_PRIVATE void zix_btree_iter_set_frame	(	ZixBTreeIter *const	ti,
		ZixBTreeNode *const	n,
		const uint16_t	i )

zix_btree_max_vals()

ZIX_PRIVATE uint16_t zix_btree_max_vals

(

const ZixBTreeNode *const

node

)

zix_btree_merge()

ZIX_PRIVATE ZixBTreeNode * zix_btree_merge	(	ZixBTree *const	t,
		ZixBTreeNode *const	n,
		const uint16_t	i )

Move n[i] down, merge the left and right child, return the merged node.

zix_btree_min_vals()

ZIX_PRIVATE uint16_t zix_btree_min_vals

(

const ZixBTreeNode *const

node

)

zix_btree_node_find()

ZIX_PRIVATE uint16_t zix_btree_node_find	(	const ZixBTree *const	t,
		const ZixBTreeNode *const	n,
		const void *const	e,
		bool *const	equal )

Find the first value in n that is not less than e (lower bound).

zix_btree_node_is_minimal()

ZIX_PRIVATE bool zix_btree_node_is_minimal

(

ZixBTreeNode *const

n

)

zix_btree_node_new()

ZIX_PRIVATE ZixBTreeNode * zix_btree_node_new

(

const bool

leaf

)

zix_btree_remove_max()

ZIX_PRIVATE void * zix_btree_remove_max	(	ZixBTree *const	t,
		ZixBTreeNode *	n )

Remove and return the max value from the subtree rooted at n.

zix_btree_remove_min()

ZIX_PRIVATE void * zix_btree_remove_min	(	ZixBTree *const	t,
		ZixBTreeNode *	n )

Remove and return the min value from the subtree rooted at n.

zix_btree_rotate_left()

ZIX_PRIVATE ZixBTreeNode * zix_btree_rotate_left	(	ZixBTreeNode *const	parent,
		const uint16_t	i )

Enlarge left child by stealing a value from its right sibling.

zix_btree_rotate_right()

ZIX_PRIVATE ZixBTreeNode * zix_btree_rotate_right	(	ZixBTreeNode *const	parent,
		const uint16_t	i )

Enlarge right child by stealing a value from its left sibling.

zix_btree_split_child()

ZIX_PRIVATE ZixBTreeNode * zix_btree_split_child	(	ZixBTreeNode *const	n,
		const uint16_t	i,
		ZixBTreeNode *const	lhs )

Split lhs, the i'th child of n, into two nodes.