avltree.h File Reference

#include <stdint.h>
#include <stddef.h>

Go to the source code of this file.

Classes
struct	bstree_node
struct	bstree
struct	rbtree_node
struct	rbtree
struct	avltree_node
struct	avltree
struct	splaytree_node
struct	splaytree
Defines
#define	bstree_container_of(node, type, member)   ((type *)((char *)(node) - offsetof(type, member)))
#define	rbtree_container_of(node, type, member)   ((type *)((char *)(node) - offsetof(type, member)))
#define	avltree_container_of(node, type, member)   ((type *)((char *)(node) - offsetof(type, member)))
#define	splaytree_container_of(node, type, member)   ((type *)((char *)(node) - offsetof(type, member)))
Typedefs
typedef int(*	bstree_cmp_fn_t )(const struct bstree_node *, const struct bstree_node *)
typedef int(*	rbtree_cmp_fn_t )(const struct rbtree_node *, const struct rbtree_node *)
typedef int(*	avltree_cmp_fn_t )(const struct avltree_node *, const struct avltree_node *)
typedef int(*	splaytree_cmp_fn_t )(const struct splaytree_node *, const struct splaytree_node *)
Enumerations
enum	rb_color { RB_BLACK, RB_RED }
Functions
struct bstree_node *	bstree_first (const struct bstree *tree)
struct bstree_node *	bstree_last (const struct bstree *tree)
struct bstree_node *	bstree_next (const struct bstree_node *node)
struct bstree_node *	bstree_prev (const struct bstree_node *node)
struct bstree_node *	bstree_lookup (const struct bstree_node *key, const struct bstree *tree)
struct bstree_node *	bstree_insert (struct bstree_node *node, struct bstree *tree)
void	bstree_remove (struct bstree_node *node, struct bstree *tree)
void	bstree_replace (struct bstree_node *old, struct bstree_node *new, struct bstree *tree)
int	bstree_init (struct bstree *tree, bstree_cmp_fn_t cmp, unsigned long flags)
struct rbtree_node *	rbtree_first (const struct rbtree *tree)
struct rbtree_node *	rbtree_last (const struct rbtree *tree)
struct rbtree_node *	rbtree_next (const struct rbtree_node *node)
struct rbtree_node *	rbtree_prev (const struct rbtree_node *node)
struct rbtree_node *	rbtree_lookup (const struct rbtree_node *key, const struct rbtree *tree)
struct rbtree_node *	rbtree_insert (struct rbtree_node *node, struct rbtree *tree)
void	rbtree_remove (struct rbtree_node *node, struct rbtree *tree)
void	rbtree_replace (struct rbtree_node *old, struct rbtree_node *new, struct rbtree *tree)
int	rbtree_init (struct rbtree *tree, rbtree_cmp_fn_t cmp, unsigned long flags)
struct avltree_node *	avltree_first (const struct avltree *tree)
struct avltree_node *	avltree_last (const struct avltree *tree)
struct avltree_node *	avltree_next (const struct avltree_node *node)
struct avltree_node *	avltree_prev (const struct avltree_node *node)
uint64_t	avltree_size (const struct avltree *tree)
struct avltree_node *	avltree_lookup (const struct avltree_node *key, const struct avltree *tree)
struct avltree_node *	avltree_inf (const struct avltree_node *key, const struct avltree *tree)
struct avltree_node *	avltree_sup (const struct avltree_node *key, const struct avltree *tree)
struct avltree_node *	avltree_insert (struct avltree_node *node, struct avltree *tree)
void	avltree_remove (struct avltree_node *node, struct avltree *tree)
void	avltree_replace (struct avltree_node *old, struct avltree_node *new, struct avltree *tree)
int	avltree_init (struct avltree *tree, avltree_cmp_fn_t cmp, unsigned long flags)
struct splaytree_node *	splaytree_first (const struct splaytree *tree)
struct splaytree_node *	splaytree_last (const struct splaytree *tree)
struct splaytree_node *	splaytree_next (const struct splaytree_node *node)
struct splaytree_node *	splaytree_prev (const struct splaytree_node *node)
struct splaytree_node *	splaytree_lookup (const struct splaytree_node *key, struct splaytree *tree)
struct splaytree_node *	splaytree_insert (struct splaytree_node *node, struct splaytree *tree)
void	splaytree_remove (struct splaytree_node *node, struct splaytree *tree)
void	splaytree_replace (struct splaytree_node *old, struct splaytree_node *new, struct splaytree *tree)
int	splaytree_init (struct splaytree *tree, splaytree_cmp_fn_t cmp, unsigned long flags)

---

Define Documentation

#define avltree_container_of	(		node,
			type,
			member
	)		((type *)((char *)(node) - offsetof(type, member)))

Definition at line 48 of file avltree.h.

#define bstree_container_of	(		node,
			type,
			member
	)		((type *)((char *)(node) - offsetof(type, member)))

Definition at line 44 of file avltree.h.

#define rbtree_container_of	(		node,
			type,
			member
	)		((type *)((char *)(node) - offsetof(type, member)))

Definition at line 46 of file avltree.h.

#define splaytree_container_of	(		node,
			type,
			member
	)		((type *)((char *)(node) - offsetof(type, member)))

Definition at line 50 of file avltree.h.

---

Typedef Documentation

typedef int(* avltree_cmp_fn_t)(const struct avltree_node *, const struct avltree_node *)

Definition at line 158 of file avltree.h.

typedef int(* bstree_cmp_fn_t)(const struct bstree_node *, const struct bstree_node *)

Definition at line 73 of file avltree.h.

typedef int(* rbtree_cmp_fn_t)(const struct rbtree_node *, const struct rbtree_node *)

Definition at line 118 of file avltree.h.

typedef int(* splaytree_cmp_fn_t)(const struct splaytree_node *, const struct splaytree_node *)

Definition at line 205 of file avltree.h.

---

Enumeration Type Documentation

enum rb_color

Enumerator:

RB_BLACK
RB_RED

Definition at line 96 of file avltree.h.

---

Function Documentation

struct avltree_node* avltree_first

(

const struct avltree *

tree

)

[read]

Definition at line 139 of file avl.c.

struct avltree_node* avltree_inf	(	const struct avltree_node *	key,
		const struct avltree *	tree
	)		[read]

Definition at line 271 of file avl.c.

int avltree_init	(	struct avltree *	tree,
		avltree_cmp_fn_t	cmp,
		unsigned long	flags
	)

Definition at line 660 of file avl.c.

struct avltree_node* avltree_insert	(	struct avltree_node *	node,
		struct avltree *	tree
	)		[read]

Definition at line 353 of file avl.c.

struct avltree_node* avltree_last

(

const struct avltree *

tree

)

[read]

Definition at line 144 of file avl.c.

struct avltree_node* avltree_lookup	(	const struct avltree_node *	key,
		const struct avltree *	tree
	)		[read]

Definition at line 262 of file avl.c.

struct avltree_node* avltree_next

(

const struct avltree_node *

node

)

[read]

Definition at line 149 of file avl.c.

struct avltree_node* avltree_prev

(

const struct avltree_node *

node

)

[read]

Definition at line 161 of file avl.c.

void avltree_remove	(	struct avltree_node *	node,
		struct avltree *	tree
	)

Definition at line 463 of file avl.c.

void avltree_replace	(	struct avltree_node *	old,
		struct avltree_node *	new,
		struct avltree *	tree
	)

Definition at line 632 of file avl.c.

uint64_t avltree_size

(

const struct avltree *

tree

)

Definition at line 173 of file avl.c.

struct avltree_node* avltree_sup	(	const struct avltree_node *	key,
		const struct avltree *	tree
	)		[read]

Definition at line 306 of file avl.c.

struct bstree_node* bstree_first

(

const struct bstree *

tree

)

[read]

Definition at line 159 of file bst.c.

int bstree_init	(	struct bstree *	tree,
		bstree_cmp_fn_t	cmp,
		unsigned long	flags
	)

Definition at line 347 of file bst.c.

struct bstree_node* bstree_insert	(	struct bstree_node *	node,
		struct bstree *	tree
	)		[read]

Definition at line 224 of file bst.c.

struct bstree_node* bstree_last

(

const struct bstree *

tree

)

[read]

Definition at line 166 of file bst.c.

struct bstree_node* bstree_lookup	(	const struct bstree_node *	key,
		const struct bstree *	tree
	)		[read]

Definition at line 215 of file bst.c.

struct bstree_node* bstree_next

(

const struct bstree_node *

node

)

[read]

Definition at line 173 of file bst.c.

struct bstree_node* bstree_prev

(

const struct bstree_node *

node

)

[read]

Definition at line 181 of file bst.c.

void bstree_remove	(	struct bstree_node *	node,
		struct bstree *	tree
	)

Definition at line 262 of file bst.c.

void bstree_replace	(	struct bstree_node *	old,
		struct bstree_node *	new,
		struct bstree *	tree
	)

Definition at line 327 of file bst.c.

struct rbtree_node* rbtree_first

(

const struct rbtree *

tree

)

[read]

Definition at line 117 of file rb.c.

int rbtree_init	(	struct rbtree *	tree,
		rbtree_cmp_fn_t	cmp,
		unsigned long	flags
	)

Definition at line 479 of file rb.c.

struct rbtree_node* rbtree_insert	(	struct rbtree_node *	node,
		struct rbtree *	tree
	)		[read]

Definition at line 243 of file rb.c.

struct rbtree_node* rbtree_last

(

const struct rbtree *

tree

)

[read]

Definition at line 122 of file rb.c.

struct rbtree_node* rbtree_lookup	(	const struct rbtree_node *	key,
		const struct rbtree *	tree
	)		[read]

Definition at line 226 of file rb.c.

struct rbtree_node* rbtree_next

(

const struct rbtree_node *

node

)

[read]

Definition at line 127 of file rb.c.

struct rbtree_node* rbtree_prev

(

const struct rbtree_node *

node

)

[read]

Definition at line 139 of file rb.c.

void rbtree_remove	(	struct rbtree_node *	node,
		struct rbtree *	tree
	)

Definition at line 322 of file rb.c.

void rbtree_replace	(	struct rbtree_node *	old,
		struct rbtree_node *	new,
		struct rbtree *	tree
	)

Definition at line 456 of file rb.c.

struct splaytree_node* splaytree_first

(

const struct splaytree *

tree

)

[read]

Definition at line 154 of file splay.c.

int splaytree_init	(	struct splaytree *	tree,
		splaytree_cmp_fn_t	cmp,
		unsigned long	flags
	)

Definition at line 364 of file splay.c.

struct splaytree_node* splaytree_insert	(	struct splaytree_node *	node,
		struct splaytree *	tree
	)		[read]

Definition at line 280 of file splay.c.

struct splaytree_node* splaytree_last

(

const struct splaytree *

tree

)

[read]

Definition at line 159 of file splay.c.

struct splaytree_node* splaytree_lookup	(	const struct splaytree_node *	key,
		struct splaytree *	tree
	)		[read]

Definition at line 270 of file splay.c.

struct splaytree_node* splaytree_next

(

const struct splaytree_node *

node

)

[read]

Definition at line 164 of file splay.c.

struct splaytree_node* splaytree_prev

(

const struct splaytree_node *

node

)

[read]

Definition at line 172 of file splay.c.

void splaytree_remove	(	struct splaytree_node *	node,
		struct splaytree *	tree
	)

Definition at line 324 of file splay.c.

void splaytree_replace	(	struct splaytree_node *	old,
		struct splaytree_node *	new,
		struct splaytree *	tree
	)

Definition at line 349 of file splay.c.