rbtree.c File Reference

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

(C) 2009 by the GRASS Development Team

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 free(), 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.

Referenced by line_check_intersection2(), Vect_break_polygons_mem(), and Vect_line_intersection2().

rbtree_debug()

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

Definition at line 530 of file rbtree.c.

References RB_NODE::data, G_warning(), RB_NODE::link, NULL, RB_TREE::rb_compare, and rbtree_debug().

Referenced by rbtree_debug().

rbtree_destroy()

void rbtree_destroy

(

struct RB_TREE *

tree

)

Definition at line 520 of file rbtree.c.

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

Referenced by line_check_intersection2(), Vect_break_polygons_mem(), and Vect_line_intersection2().

rbtree_find()

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

Definition at line 243 of file rbtree.c.

References assert, RB_NODE::data, RB_NODE::link, NULL, RB_TREE::rb_compare, and RB_TREE::root.

Referenced by Vect_break_polygons_mem().

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, and RB_TREE::root.

Referenced by line_check_intersection2(), and Vect_line_intersection2().

rbtree_insert()

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

Definition at line 73 of file rbtree.c.

References assert, RB_TREE::count, RB_NODE::data, RB_TREE::datasize, g, RB_NODE::link, NULL, RB_TREE::rb_compare, RB_NODE::red, RB_TREE::root, and t.

Referenced by line_check_intersection2(), Vect_break_polygons_mem(), and Vect_line_intersection2().

rbtree_remove()

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

Definition at line 154 of file rbtree.c.

References assert, RB_TREE::count, RB_NODE::data, free(), g, G_debug(), RB_NODE::link, NULL, RB_TREE::rb_compare, RB_NODE::red, and RB_TREE::root.

Referenced by line_check_intersection2(), and Vect_line_intersection2().

rbtree_traverse()

void * rbtree_traverse

(

struct RB_TRAV *

trav

)

Definition at line 281 of file rbtree.c.

References assert, G_debug(), and NULL.

Referenced by line_check_intersection2(), and Vect_line_intersection2().

rbtree_traverse_backwd()

void * rbtree_traverse_backwd

(

struct RB_TRAV *

trav

)

Definition at line 307 of file rbtree.c.

References assert, G_debug(), and NULL.

rbtree_traverse_start()

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

Definition at line 335 of file rbtree.c.

References assert, RB_NODE::data, G_warning(), and NULL.