gdsl_rbtree.3

一个通用的C语言实现的数据结构

.TH "Red-black tree manipulation module" 3 "22 Jun 2006" "Version 1.4" "gdsl" \" -*- nroff -*-
.ad l
.nh
.SH NAME
Red-black tree manipulation module \- 
.PP
.SS "Typedefs"

.in +1c
.ti -1c
.RI "typedef gdsl_rbtree * \fBgdsl_rbtree_t\fP"
.br
.in -1c
.SS "Functions"

.in +1c
.ti -1c
.RI "\fBgdsl_rbtree_t\fP \fBgdsl_rbtree_alloc\fP (const char *NAME, \fBgdsl_alloc_func_t\fP ALLOC_F, \fBgdsl_free_func_t\fP FREE_F, \fBgdsl_compare_func_t\fP COMP_F)"
.br
.RI "\fICreate a new red-black tree. \fP"
.ti -1c
.RI "void \fBgdsl_rbtree_free\fP (\fBgdsl_rbtree_t\fP T)"
.br
.RI "\fIDestroy a red-black tree. \fP"
.ti -1c
.RI "void \fBgdsl_rbtree_flush\fP (\fBgdsl_rbtree_t\fP T)"
.br
.RI "\fIFlush a red-black tree. \fP"
.ti -1c
.RI "char * \fBgdsl_rbtree_get_name\fP (const \fBgdsl_rbtree_t\fP T)"
.br
.RI "\fIGet the name of a red-black tree. \fP"
.ti -1c
.RI "\fBbool\fP \fBgdsl_rbtree_is_empty\fP (const \fBgdsl_rbtree_t\fP T)"
.br
.RI "\fICheck if a red-black tree is empty. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_rbtree_get_root\fP (const \fBgdsl_rbtree_t\fP T)"
.br
.RI "\fIGet the root of a red-black tree. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_rbtree_get_size\fP (const \fBgdsl_rbtree_t\fP T)"
.br
.RI "\fIGet the size of a red-black tree. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_rbtree_height\fP (const \fBgdsl_rbtree_t\fP T)"
.br
.RI "\fIGet the height of a red-black tree. \fP"
.ti -1c
.RI "\fBgdsl_rbtree_t\fP \fBgdsl_rbtree_set_name\fP (\fBgdsl_rbtree_t\fP T, const char *NEW_NAME)"
.br
.RI "\fISet the name of a red-black tree. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_rbtree_insert\fP (\fBgdsl_rbtree_t\fP T, void *VALUE, int *RESULT)"
.br
.RI "\fIInsert an element into a red-black tree if it's not found or return it. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_rbtree_remove\fP (\fBgdsl_rbtree_t\fP T, void *VALUE)"
.br
.RI "\fIRemove an element from a red-black tree. \fP"
.ti -1c
.RI "\fBgdsl_rbtree_t\fP \fBgdsl_rbtree_delete\fP (\fBgdsl_rbtree_t\fP T, void *VALUE)"
.br
.RI "\fIDelete an element from a red-black tree. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_rbtree_search\fP (const \fBgdsl_rbtree_t\fP T, \fBgdsl_compare_func_t\fP COMP_F, void *VALUE)"
.br
.RI "\fISearch for a particular element into a red-black tree. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_rbtree_map_prefix\fP (const \fBgdsl_rbtree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a red-black tree in prefixed order. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_rbtree_map_infix\fP (const \fBgdsl_rbtree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a red-black tree in infixed order. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_rbtree_map_postfix\fP (const \fBgdsl_rbtree_t\fP T, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a red-black tree in postfixed order. \fP"
.ti -1c
.RI "void \fBgdsl_rbtree_write\fP (const \fBgdsl_rbtree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite the element of each node of a red-black tree to a file. \fP"
.ti -1c
.RI "void \fBgdsl_rbtree_write_xml\fP (const \fBgdsl_rbtree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite the content of a red-black tree to a file into XML. \fP"
.ti -1c
.RI "void \fBgdsl_rbtree_dump\fP (const \fBgdsl_rbtree_t\fP T, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIDump the internal structure of a red-black tree to a file. \fP"
.in -1c
.SH "Typedef Documentation"
.PP 
.SS "typedef struct gdsl_rbtree* \fBgdsl_rbtree_t\fP"
.PP
GDSL red-black tree type.
.PP
This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module. 
.PP
Definition at line 52 of file gdsl_rbtree.h.
.SH "Function Documentation"
.PP 
.SS "\fBgdsl_rbtree_t\fP gdsl_rbtree_alloc (const char * NAME, \fBgdsl_alloc_func_t\fP ALLOC_F, \fBgdsl_free_func_t\fP FREE_F, \fBgdsl_compare_func_t\fP COMP_F)"
.PP
Create a new red-black tree. 
.PP
Allocate a new red-black tree data structure which name is set to a copy of NAME. The function pointers ALLOC_F, FREE_F and COMP_F could be used to respectively, alloc, free and compares elements in the tree. These pointers could be set to NULL to use the default ones:
.IP "\(bu" 2
the default ALLOC_F simply returns its argument
.IP "\(bu" 2
the default FREE_F does nothing
.IP "\(bu" 2
the default COMP_F always returns 0
.PP
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
nothing 
.RE
.PP
\fBParameters:\fP
.RS 4
\fINAME\fP The name of the new red-black tree to create 
.br
\fIALLOC_F\fP Function to alloc element when inserting it in a r-b tree 
.br
\fIFREE_F\fP Function to free element when removing it from a r-b tree 
.br
\fICOMP_F\fP Function to compare elements into the r-b tree 
.RE
.PP
\fBReturns:\fP
.RS 4
the newly allocated red-black tree in case of success. 
.PP
NULL in case of failure. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_rbtree_free()\fP 
.PP
\fBgdsl_rbtree_flush()\fP 
.RE
.PP

.SS "void gdsl_rbtree_free (\fBgdsl_rbtree_t\fP T)"
.PP
Destroy a red-black tree. 
.PP
Deallocate all the elements of the red-black tree T by calling T's FREE_F function passed to \fBgdsl_rbtree_alloc()\fP. The name of T is deallocated and T is deallocated itself too.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_rbtree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The red-black tree to deallocate 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_rbtree_alloc()\fP 
.PP
\fBgdsl_rbtree_flush()\fP 
.RE
.PP

.SS "void gdsl_rbtree_flush (\fBgdsl_rbtree_t\fP T)"
.PP
Flush a red-black tree. 
.PP
Deallocate all the elements of the red-black tree T by calling T's FREE_F function passed to \fBgdsl_rbtree_alloc()\fP. The red-black tree T is not deallocated itself and its name is not modified.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_rbtree_t 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_rbtree_alloc()\fP 
.PP
\fBgdsl_rbtree_free()\fP 
.RE
.PP

.SS "char* gdsl_rbtree_get_name (const \fBgdsl_rbtree_t\fP T)"
.PP
Get the name of a red-black tree. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_rbtree_t 
.RE
.PP
\fBPostcondition:\fP
.RS 4
The returned string MUST NOT be freed. 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The red-black tree to get the name from 
.RE
.PP
\fBReturns:\fP
.RS 4
the name of the red-black tree T. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_rbtree_set_name()\fP 
.RE
.PP

.SS "\fBbool\fP gdsl_rbtree_is_empty (const \fBgdsl_rbtree_t\fP T)"
.PP
Check if a red-black tree is empty. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_rbtree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The red-black tree to check 
.RE
.PP
\fBReturns:\fP
.RS 4
TRUE if the red-black tree T is empty. 
.PP
FALSE if the red-black tree T is not empty. 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_rbtree_get_root (const \fBgdsl_rbtree_t\fP T)"
.PP
Get the root of a red-black tree. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_rbtree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The red-black tree to get the root element from 
.RE
.PP
\fBReturns:\fP
.RS 4
the element at the root of the red-black tree T. 
.RE
.PP

.SS "\fBulong\fP gdsl_rbtree_get_size (const \fBgdsl_rbtree_t\fP T)"
.PP
Get the size of a red-black tree. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_rbtree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The red-black tree to get the size from 
.RE
.PP
\fBReturns:\fP
.RS 4
the size of the red-black tree T (noted |T|). 
.RE
.PP
\fBSee also:\fP
.RS 4
gdsl_rbtree_get_height() 
.RE
.PP

.SS "\fBulong\fP gdsl_rbtree_height (const \fBgdsl_rbtree_t\fP T)"
.PP
Get the height of a red-black tree. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( |T| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_rbtree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The red-black tree to compute the height from 
.RE
.PP
\fBReturns:\fP
.RS 4
the height of the red-black tree T (noted h(T)). 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_rbtree_get_size()\fP 
.RE
.PP

.SS "\fBgdsl_rbtree_t\fP gdsl_rbtree_set_name (\fBgdsl_rbtree_t\fP T, const char * NEW_NAME)"
.PP
Set the name of a red-black tree. 
.PP
Change the previous name of the red-black tree T to a copy of NEW_NAME.
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
T must be a valid gdsl_rbtree_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIT\fP The red-black tree to change the name 
.br
\fINEW_NAME\fP The new name of T 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified red-black tree in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_rbtree_get_name()\fP 
.RE
.PP