binary search tree More...

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <grass/gis.h>
#include <grass/glocale.h>
#include <grass/rbtree.h>

Include dependency graph for rbtree.c:

Go to the source code of this file.

Functions
struct RB_TREE *	rbtree_create (rb_compare_fn *compare, size_t rb_datasize)

int	rbtree_insert (struct RB_TREE tree, void data)

int	rbtree_remove (struct RB_TREE tree, const void data)

void *	rbtree_find (struct RB_TREE tree, const void data)

int	rbtree_init_trav (struct RB_TRAV trav, struct RB_TREE tree)

void *	rbtree_traverse (struct RB_TRAV *trav)

void *	rbtree_traverse_backwd (struct RB_TRAV *trav)

void *	rbtree_traverse_start (struct RB_TRAV trav, const void data)

void	rbtree_clear (struct RB_TREE *tree)

void	rbtree_destroy (struct RB_TREE *tree)

int	rbtree_debug (struct RB_TREE tree, struct RB_NODE root)

Detailed Description

binary search tree

Generic balanced binary search tree (Red Black Tree) implementation

This program is free software under the GNU General Public License (>=v2). Read the file COPYING that comes with GRASS for details.

Author: Original author Julienne Walker 2003, 2008 GRASS implementation Markus Metz, 2009

Definition in file rbtree.c.

Function Documentation

◆ rbtree_clear()

void rbtree_clear ( struct RB_TREE * tree )

Definition at line 490 of file rbtree.c.

References RB_NODE::data, free(), RB_NODE::link, NULL, and RB_TREE::root.

Referenced by rbtree_destroy().

◆ rbtree_create()

struct RB_TREE* rbtree_create	(	rb_compare_fn *	compare,
		size_t	rb_datasize
	)

Definition at line 49 of file rbtree.c.

References assert, compare(), RB_TREE::count, RB_TREE::datasize, G_warning(), malloc(), NULL, RB_TREE::rb_compare, and RB_TREE::root.

◆ rbtree_debug()

int rbtree_debug	(	struct RB_TREE *	tree,
		struct RB_NODE *	root
	)

Definition at line 530 of file rbtree.c.

References RB_NODE::link, and NULL.

◆ rbtree_destroy()

void rbtree_destroy ( struct RB_TREE * tree )

Definition at line 520 of file rbtree.c.

References free(), NULL, and rbtree_clear().

◆ rbtree_find()

void* rbtree_find	(	struct RB_TREE *	tree,
		const void *	data
	)

Definition at line 243 of file rbtree.c.

◆ rbtree_init_trav()

int rbtree_init_trav	(	struct RB_TRAV *	trav,
		struct RB_TREE *	tree
	)

Definition at line 264 of file rbtree.c.

References assert, RB_TRAV::curr_node, RB_TRAV::first, RB_TREE::root, RB_TRAV::top, and RB_TRAV::tree.

◆ rbtree_insert()

int rbtree_insert	(	struct RB_TREE *	tree,
		void *	data
	)

Definition at line 73 of file rbtree.c.

◆ rbtree_remove()

int rbtree_remove	(	struct RB_TREE *	tree,
		const void *	data
	)

Definition at line 154 of file rbtree.c.

◆ rbtree_traverse()

void* rbtree_traverse ( struct RB_TRAV * trav )

Definition at line 281 of file rbtree.c.

References assert, RB_TRAV::curr_node, RB_TRAV::first, G_debug(), and NULL.

◆ rbtree_traverse_backwd()

void* rbtree_traverse_backwd ( struct RB_TRAV * trav )

Definition at line 307 of file rbtree.c.