gdsl  1.7
Heap manipulation module

Typedefs

typedef struct heap * gdsl_heap_t
 GDSL heap type.

Functions

gdsl_heap_t gdsl_heap_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 heap.
void gdsl_heap_free (gdsl_heap_t H)
 Destroy a heap.
void gdsl_heap_flush (gdsl_heap_t H)
 Flush a heap.
const char * gdsl_heap_get_name (const gdsl_heap_t H)
 Get the name of a heap.
ulong gdsl_heap_get_size (const gdsl_heap_t H)
 Get the size of a heap.
gdsl_element_t gdsl_heap_get_top (const gdsl_heap_t H)
 Get the top of a heap.
bool gdsl_heap_is_empty (const gdsl_heap_t H)
 Check if a heap is empty.
gdsl_heap_t gdsl_heap_set_name (gdsl_heap_t H, const char *NEW_NAME)
 Set the name of a heap.
gdsl_element_t gdsl_heap_set_top (gdsl_heap_t H, void *VALUE)
 Substitute the top element of a heap by a lesser one.
gdsl_element_t gdsl_heap_insert (gdsl_heap_t H, void *VALUE)
 Insert an element into a heap (PUSH).
gdsl_element_t gdsl_heap_remove_top (gdsl_heap_t H)
 Remove the top element from a heap (POP).
gdsl_heap_t gdsl_heap_delete_top (gdsl_heap_t H)
 Delete the top element from a heap.
gdsl_element_t gdsl_heap_map_forward (const gdsl_heap_t H, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a heap.
void gdsl_heap_write (const gdsl_heap_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write all the elements of a heap to a file.
void gdsl_heap_write_xml (const gdsl_heap_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of a heap to a file into XML.
void gdsl_heap_dump (const gdsl_heap_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Dump the internal structure of a heap to a file.

Typedef Documentation

typedef struct heap* gdsl_heap_t

GDSL heap 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 54 of file gdsl_heap.h.


Function Documentation

gdsl_heap_t gdsl_heap_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 heap.

Allocate a new heap 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 heap. 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 heap to create
ALLOC_FFunction to alloc element when inserting it in the heap
FREE_FFunction to free element when removing it from the heap
COMP_FFunction to compare elements into the heap
Returns:
the newly allocated heap in case of success.
NULL in case of insufficient memory.
See also:
gdsl_heap_free()
gdsl_heap_flush()

Destroy a heap.

Deallocate all the elements of the heap H by calling H's FREE_F function passed to gdsl_heap_alloc(). The name of H is deallocated and H is deallocated itself too.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to destroy
See also:
gdsl_heap_alloc()
gdsl_heap_flush()

Flush a heap.

Deallocate all the elements of the heap H by calling H's FREE_F function passed to gdsl_heap_alloc(). H is not deallocated itself and H's name is not modified.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to flush
See also:
gdsl_heap_alloc()
gdsl_heap_free()
const char* gdsl_heap_get_name ( const gdsl_heap_t  H)

Get the name of a heap.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_heap_t
Postcondition:
The returned string MUST NOT be freed.
Parameters:
HThe heap to get the name from
Returns:
the name of the heap H.
See also:
gdsl_heap_set_name()

Get the size of a heap.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to get the size from
Returns:
the number of elements of H (noted |H|).

Get the top of a heap.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to get the top from
Returns:
the element contained at the top position of the heap H if H is not empty. The returned element is not removed from H.
NULL if the heap H is empty.
See also:
gdsl_heap_set_top()

Check if a heap is empty.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to check
Returns:
TRUE if the heap H is empty.
FALSE if the heap H is not empty.
gdsl_heap_t gdsl_heap_set_name ( gdsl_heap_t  H,
const char *  NEW_NAME 
)

Set the name of a heap.

Change the previous name of the heap H to a copy of NEW_NAME.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to change the name
NEW_NAMEThe new name of H
Returns:
the modified heap in case of success.
NULL in case of insufficient memory.
See also:
gdsl_heap_get_name()
gdsl_element_t gdsl_heap_set_top ( gdsl_heap_t  H,
void *  VALUE 
)

Substitute the top element of a heap by a lesser one.

Try to replace the top element of a heap by a lesser one.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to substitute the top element
VALUEthe value to substitute to the top
Returns:
The old top element value in case VALUE is lesser than all other H elements.
NULL in case of VALUE is greather or equal to all other H elements.
See also:
gdsl_heap_get_top()
gdsl_element_t gdsl_heap_insert ( gdsl_heap_t  H,
void *  VALUE 
)

Insert an element into a heap (PUSH).

Allocate a new element E by calling H's ALLOC_F function on VALUE. The element E is then inserted into H at the good position to ensure H is always a heap.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to modify
VALUEThe value used to make the new element to insert into H
Returns:
the inserted element E in case of success.
NULL in case of insufficient memory.
See also:
gdsl_heap_alloc()
gdsl_heap_remove()
gdsl_heap_delete()
gdsl_heap_get_size()

Remove the top element from a heap (POP).

Remove the top element from the heap H. The element is removed from H and is also returned.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to modify
Returns:
the removed top element.
NULL if the heap is empty.
See also:
gdsl_heap_insert()
gdsl_heap_delete_top()

Delete the top element from a heap.

Remove the top element from the heap H. The element is removed from H and is also deallocated using H's FREE_F function passed to gdsl_heap_alloc(), then H is returned.

Note:
Complexity: O( log ( |H| ) )
Precondition:
H must be a valid gdsl_heap_t
Parameters:
HThe heap to modify
Returns:
the modified heap after removal of top element.
NULL if heap is empty.
See also:
gdsl_heap_insert()
gdsl_heap_remove_top()
gdsl_element_t gdsl_heap_map_forward ( const gdsl_heap_t  H,
gdsl_map_func_t  MAP_F,
void *  USER_DATA 
)

Parse a heap.

Parse all elements of the heap H. The MAP_F function is called on each H's element with USER_DATA argument. If MAP_F returns GDSL_MAP_STOP then gdsl_heap_map() stops and returns its last examinated element.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_heap_t & MAP_F != NULL
Parameters:
HThe heap 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.
void gdsl_heap_write ( const gdsl_heap_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write all the elements of a heap to a file.

Write the elements of the heap H to OUTPUT_FILE, using WRITE_F function. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_heap_t & OUTPUT_FILE != NULL & WRITE_F != NULL
Parameters:
HThe heap to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write H's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_heap_write_xml()
gdsl_heap_dump()
void gdsl_heap_write_xml ( const gdsl_heap_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write the content of a heap to a file into XML.

Write the elements of the heap H to OUTPUT_FILE, into XML language. If WRITE_F != NULL, then uses WRITE_F to write H's elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_heap_t & OUTPUT_FILE != NULL
Parameters:
HThe heap to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write H's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_heap_write()
gdsl_heap_dump()
void gdsl_heap_dump ( const gdsl_heap_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Dump the internal structure of a heap to a file.

Dump the structure of the heap H to OUTPUT_FILE. If WRITE_F != NULL, then uses WRITE_F to write H's elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_heap_t & OUTPUT_FILE != NULL
Parameters:
HThe heap to write
WRITE_FThe write function
OUTPUT_FILEThe file where to write H's elements
USER_DATAUser's datas passed to WRITE_F
See also:
gdsl_heap_write()
gdsl_heap_write_xml()