gdsl  1.6
Red-black tree manipulation module

Typedefs

typedef struct gdsl_rbtree * gdsl_rbtree_t

Functions

gdsl_rbtree_t gdsl_rbtree_alloc (const char *NAME, gdsl_alloc_func_t ALLOC_F, gdsl_free_func_t FREE_F, gdsl_compare_func_t COMP_F)
 Create a new red-black tree.
void gdsl_rbtree_free (gdsl_rbtree_t T)
 Destroy a red-black tree.
void gdsl_rbtree_flush (gdsl_rbtree_t T)
 Flush a red-black tree.
char * gdsl_rbtree_get_name (const gdsl_rbtree_t T)
 Get the name of a red-black tree.
bool gdsl_rbtree_is_empty (const gdsl_rbtree_t T)
 Check if a red-black tree is empty.
gdsl_element_t gdsl_rbtree_get_root (const gdsl_rbtree_t T)
 Get the root of a red-black tree.
ulong gdsl_rbtree_get_size (const gdsl_rbtree_t T)
 Get the size of a red-black tree.
ulong gdsl_rbtree_height (const gdsl_rbtree_t T)
 Get the height of a red-black tree.
gdsl_rbtree_t gdsl_rbtree_set_name (gdsl_rbtree_t T, const char *NEW_NAME)
 Set the name of a red-black tree.
gdsl_element_t gdsl_rbtree_insert (gdsl_rbtree_t T, void *VALUE, int *RESULT)
 Insert an element into a red-black tree if it's not found or return it.
gdsl_element_t gdsl_rbtree_remove (gdsl_rbtree_t T, void *VALUE)
 Remove an element from a red-black tree.
gdsl_rbtree_t gdsl_rbtree_delete (gdsl_rbtree_t T, void *VALUE)
 Delete an element from a red-black tree.
gdsl_element_t gdsl_rbtree_search (const gdsl_rbtree_t T, gdsl_compare_func_t COMP_F, void *VALUE)
 Search for a particular element into a red-black tree.
gdsl_element_t gdsl_rbtree_map_prefix (const gdsl_rbtree_t T, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a red-black tree in prefixed order.
gdsl_element_t gdsl_rbtree_map_infix (const gdsl_rbtree_t T, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a red-black tree in infixed order.
gdsl_element_t gdsl_rbtree_map_postfix (const gdsl_rbtree_t T, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a red-black tree in postfixed order.
void gdsl_rbtree_write (const gdsl_rbtree_t T, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the element of each node of a red-black tree to a file.
void gdsl_rbtree_write_xml (const gdsl_rbtree_t T, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of a red-black tree to a file into XML.
void gdsl_rbtree_dump (const gdsl_rbtree_t T, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Dump the internal structure of a red-black tree to a file.

Typedef Documentation

typedef struct gdsl_rbtree* gdsl_rbtree_t

GDSL red-black tree type.

This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module.

Definition at line 52 of file gdsl_rbtree.h.


Function Documentation

gdsl_rbtree_t gdsl_rbtree_alloc ( const char *  NAME,
gdsl_alloc_func_t  ALLOC_F,
gdsl_free_func_t  FREE_F,
gdsl_compare_func_t  COMP_F 
)

Create a new red-black tree.

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:

  • the default ALLOC_F simply returns its argument
  • the default FREE_F does nothing
  • the default COMP_F always returns 0
Note:
Complexity: O( 1 )
Precondition:
nothing
Parameters:
NAMEThe name of the new red-black tree to create
ALLOC_FFunction to alloc element when inserting it in a r-b tree
FREE_FFunction to free element when removing it from a r-b tree
COMP_FFunction to compare elements into the r-b tree
Returns:
the newly allocated red-black tree in case of success.
NULL in case of failure.
See also:
gdsl_rbtree_free()
gdsl_rbtree_flush()

Destroy a red-black tree.

Deallocate all the elements of the red-black tree T by calling T's FREE_F function passed to gdsl_rbtree_alloc(). The name of T is deallocated and T is deallocated itself too.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to deallocate
See also:
gdsl_rbtree_alloc()
gdsl_rbtree_flush()

Flush a red-black tree.

Deallocate all the elements of the red-black tree T by calling T's FREE_F function passed to gdsl_rbtree_alloc(). The red-black tree T is not deallocated itself and its name is not modified.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t
See also:
gdsl_rbtree_alloc()
gdsl_rbtree_free()
char* gdsl_rbtree_get_name ( const gdsl_rbtree_t  T)

Get the name of a red-black tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_rbtree_t
Postcondition:
The returned string MUST NOT be freed.
Parameters:
TThe red-black tree to get the name from
Returns:
the name of the red-black tree T.
See also:
gdsl_rbtree_set_name()

Check if a red-black tree is empty.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to check
Returns:
TRUE if the red-black tree T is empty.
FALSE if the red-black tree T is not empty.

Get the root of a red-black tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to get the root element from
Returns:
the element at the root of the red-black tree T.

Get the size of a red-black tree.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to get the size from
Returns:
the size of the red-black tree T (noted |T|).
See also:
gdsl_rbtree_get_height()

Get the height of a red-black tree.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to compute the height from
Returns:
the height of the red-black tree T (noted h(T)).
See also:
gdsl_rbtree_get_size()
gdsl_rbtree_t gdsl_rbtree_set_name ( gdsl_rbtree_t  T,
const char *  NEW_NAME 
)

Set the name of a red-black tree.

Change the previous name of the red-black tree T to a copy of NEW_NAME.

Note:
Complexity: O( 1 )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to change the name
NEW_NAMEThe new name of T
Returns:
the modified red-black tree in case of success.
NULL in case of insufficient memory.
See also:
gdsl_rbtree_get_name()
gdsl_element_t gdsl_rbtree_insert ( gdsl_rbtree_t  T,
void *  VALUE,
int *  RESULT 
)

Insert an element into a red-black tree if it's not found or return it.

Search for the first element E equal to VALUE into the red-black tree T, by using T's COMP_F function passed to gdsl_rbtree_alloc to find it. If E is found, then it's returned. If E isn't found, then a new element E is allocated using T's ALLOC_F function passed to gdsl_rbtree_alloc and is inserted and then returned.

Note:
Complexity: O( log( |T| ) )
Precondition:
T must be a valid gdsl_rbtree_t & RESULT != NULL
Parameters:
TThe red-black tree to modify
VALUEThe value used to make the new element to insert into T
RESULTThe address where the result code will be stored.
Returns:
the element E and RESULT = GDSL_OK if E is inserted into T.
the element E and RESULT = GDSL_ERR_DUPLICATE_ENTRY if E is already present in T.
NULL and RESULT = GDSL_ERR_MEM_ALLOC in case of insufficient memory.
See also:
gdsl_rbtree_remove()
gdsl_rbtree_delete()
gdsl_element_t gdsl_rbtree_remove ( gdsl_rbtree_t  T,
void *  VALUE 
)

Remove an element from a red-black tree.

Remove from the red-black tree T the first founded element E equal to VALUE, by using T's COMP_F function passed to gdsl_rbtree_alloc(). If E is found, it is removed from T and then returned.

Note:
Complexity: O( log ( |T| ) )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to modify
VALUEThe value used to find the element to remove
Returns:
the first founded element equal to VALUE in T in case is found.
NULL in case no element equal to VALUE is found in T.
See also:
gdsl_rbtree_insert()
gdsl_rbtree_delete()
gdsl_rbtree_t gdsl_rbtree_delete ( gdsl_rbtree_t  T,
void *  VALUE 
)

Delete an element from a red-black tree.

Remove from the red-black tree the first founded element E equal to VALUE, by using T's COMP_F function passed to gdsl_rbtree_alloc(). If E is found, it is removed from T and E is deallocated using T's FREE_F function passed to gdsl_rbtree_alloc(), then T is returned.

Note:
Complexity: O( log( |T| ) )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to remove an element from
VALUEThe value used to find the element to remove
Returns:
the modified red-black tree after removal of E if E was found.
NULL if no element equal to VALUE was found.
See also:
gdsl_rbtree_insert()
gdsl_rbtree_remove()
gdsl_element_t gdsl_rbtree_search ( const gdsl_rbtree_t  T,
gdsl_compare_func_t  COMP_F,
void *  VALUE 
)

Search for a particular element into a red-black tree.

Search the first element E equal to VALUE in the red-black tree T, by using COMP_F function to find it. If COMP_F == NULL, then the COMP_F function passed to gdsl_rbtree_alloc() is used.

Note:
Complexity: O( log( |T| ) )
Precondition:
T must be a valid gdsl_rbtree_t
Parameters:
TThe red-black tree to use.
COMP_FThe comparison function to use to compare T's element with VALUE to find the element E (or NULL to use the default T's COMP_F)
VALUEThe value that must be used by COMP_F to find the element E
Returns:
the first founded element E equal to VALUE.
NULL if VALUE is not found in T.
See also:
gdsl_rbtree_insert()
gdsl_rbtree_remove()
gdsl_rbtree_delete()
gdsl_element_t gdsl_rbtree_map_prefix ( const gdsl_rbtree_t  T,
gdsl_map_func_t  MAP_F,
void *  USER_DATA 
)

Parse a red-black tree in prefixed order.

Parse all nodes of the red-black tree T in prefixed order. The MAP_F function is called on the element contained in each node with the USER_DATA argument. If MAP_F returns GDSL_MAP_STOP, then gdsl_rbtree_map_prefix() stops and returns its last examinated element.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t & MAP_F != NULL
Parameters:
TThe red-black tree to map.
MAP_FThe map function.
USER_DATAUser's datas passed to MAP_F
Returns:
the first element for which MAP_F returns GDSL_MAP_STOP.
NULL when the parsing is done.
See also:
gdsl_rbtree_map_infix()
gdsl_rbtree_map_postfix()
gdsl_element_t gdsl_rbtree_map_infix ( const gdsl_rbtree_t  T,
gdsl_map_func_t  MAP_F,
void *  USER_DATA 
)

Parse a red-black tree in infixed order.

Parse all nodes of the red-black tree T in infixed order. The MAP_F function is called on the element contained in each node with the USER_DATA argument. If MAP_F returns GDSL_MAP_STOP, then gdsl_rbtree_map_infix() stops and returns its last examinated element.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t & MAP_F != NULL
Parameters:
TThe red-black tree to map.
MAP_FThe map function.
USER_DATAUser's datas passed to MAP_F
Returns:
the first element for which MAP_F returns GDSL_MAP_STOP.
NULL when the parsing is done.
See also:
gdsl_rbtree_map_prefix()
gdsl_rbtree_map_postfix()
gdsl_element_t gdsl_rbtree_map_postfix ( const gdsl_rbtree_t  T,
gdsl_map_func_t  MAP_F,
void *  USER_DATA 
)

Parse a red-black tree in postfixed order.

Parse all nodes of the red-black tree T in postfixed order. The MAP_F function is called on the element contained in each node with the USER_DATA argument. If MAP_F returns GDSL_MAP_STOP, then gdsl_rbtree_map_postfix() stops and returns its last examinated element.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t & MAP_F != NULL
Parameters:
TThe red-black tree to map.
MAP_FThe map function.
USER_DATAUser's datas passed to MAP_F
Returns:
the first element for which MAP_F returns GDSL_MAP_STOP.
NULL when the parsing is done.
See also:
gdsl_rbtree_map_prefix()
gdsl_rbtree_map_infix()
void gdsl_rbtree_write ( const gdsl_rbtree_t  T,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write the element of each node of a red-black tree to a file.

Write the nodes elements of the red-black tree T to OUTPUT_FILE, using WRITE_F function. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t & WRITE_F != NULL & OUTPUT_FILE != NULL
Parameters:
TThe red-black tree to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write T's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_rbtree_write_xml()
gdsl_rbtree_dump()
void gdsl_rbtree_write_xml ( const gdsl_rbtree_t  T,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write the content of a red-black tree to a file into XML.

Write the nodes elements of the red-black tree T to OUTPUT_FILE, into XML language. If WRITE_F != NULL, then use WRITE_F to write T's nodes elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t & OUTPUT_FILE != NULL
Parameters:
TThe red-black tree to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write T's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_rbtree_write()
gdsl_rbtree_dump()
void gdsl_rbtree_dump ( const gdsl_rbtree_t  T,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Dump the internal structure of a red-black tree to a file.

Dump the structure of the red-black tree T to OUTPUT_FILE. If WRITE_F != NULL, then use WRITE_F to write T's nodes elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |T| )
Precondition:
T must be a valid gdsl_rbtree_t & OUTPUT_FILE != NULL
Parameters:
TThe red-black tree to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write T's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_rbtree_write()
gdsl_rbtree_write_xml()