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

SPDX-FileCopyrightText: 2009 GRASS Development Team SPDX-License-Identifier: GPL-2.0-or-later

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 488 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 47 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 528 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 518 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 241 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 262 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 71 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 152 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 279 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 305 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 333 of file rbtree.c.

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