gdsl_list.3

书籍上的数据结构源代码

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

.in +1c
.ti -1c
.RI "typedef _gdsl_list * \fBgdsl_list_t\fP"
.br
.RI "\fIGDSL doubly-linked list type. \fP"
.ti -1c
.RI "typedef _gdsl_list_cursor * \fBgdsl_list_cursor_t\fP"
.br
.RI "\fIGDSL doubly-linked list cursor type. \fP"
.in -1c
.SS "Functions"

.in +1c
.ti -1c
.RI "\fBgdsl_list_t\fP \fBgdsl_list_alloc\fP (const char *NAME, \fBgdsl_alloc_func_t\fP ALLOC_F, \fBgdsl_free_func_t\fP FREE_F)"
.br
.RI "\fICreate a new list. \fP"
.ti -1c
.RI "void \fBgdsl_list_free\fP (\fBgdsl_list_t\fP L)"
.br
.RI "\fIDestroy a list. \fP"
.ti -1c
.RI "void \fBgdsl_list_flush\fP (\fBgdsl_list_t\fP L)"
.br
.RI "\fIFlush a list. \fP"
.ti -1c
.RI "const char * \fBgdsl_list_get_name\fP (const \fBgdsl_list_t\fP L)"
.br
.RI "\fIGet the name of a list. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_list_get_size\fP (const \fBgdsl_list_t\fP L)"
.br
.RI "\fIGet the size of a list. \fP"
.ti -1c
.RI "\fBbool\fP \fBgdsl_list_is_empty\fP (const \fBgdsl_list_t\fP L)"
.br
.RI "\fICheck if a list is empty. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_get_head\fP (const \fBgdsl_list_t\fP L)"
.br
.RI "\fIGet the head of a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_get_tail\fP (const \fBgdsl_list_t\fP L)"
.br
.RI "\fIGet the tail of a list. \fP"
.ti -1c
.RI "\fBgdsl_list_t\fP \fBgdsl_list_set_name\fP (\fBgdsl_list_t\fP L, const char *NEW_NAME)"
.br
.RI "\fISet the name of a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_insert_head\fP (\fBgdsl_list_t\fP L, void *VALUE)"
.br
.RI "\fIInsert an element at the head of a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_insert_tail\fP (\fBgdsl_list_t\fP L, void *VALUE)"
.br
.RI "\fIInsert an element at the tail of a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_remove_head\fP (\fBgdsl_list_t\fP L)"
.br
.RI "\fIRemove the head of a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_remove_tail\fP (\fBgdsl_list_t\fP L)"
.br
.RI "\fIRemove the tail of a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_remove\fP (\fBgdsl_list_t\fP L, \fBgdsl_compare_func_t\fP COMP_F, const void *VALUE)"
.br
.RI "\fIRemove a particular element from a list. \fP"
.ti -1c
.RI "\fBgdsl_list_t\fP \fBgdsl_list_delete_head\fP (\fBgdsl_list_t\fP L)"
.br
.RI "\fIDelete the head of a list. \fP"
.ti -1c
.RI "\fBgdsl_list_t\fP \fBgdsl_list_delete_tail\fP (\fBgdsl_list_t\fP L)"
.br
.RI "\fIDelete the tail of a list. \fP"
.ti -1c
.RI "\fBgdsl_list_t\fP \fBgdsl_list_delete\fP (\fBgdsl_list_t\fP L, \fBgdsl_compare_func_t\fP COMP_F, const void *VALUE)"
.br
.RI "\fIDelete a particular element from a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_search\fP (const \fBgdsl_list_t\fP L, \fBgdsl_compare_func_t\fP COMP_F, const void *VALUE)"
.br
.RI "\fISearch for a particular element into a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_search_by_position\fP (const \fBgdsl_list_t\fP L, \fBulong\fP POS)"
.br
.RI "\fISearch for an element by its position in a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_search_max\fP (const \fBgdsl_list_t\fP L, \fBgdsl_compare_func_t\fP COMP_F)"
.br
.RI "\fISearch for the greatest element of a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_search_min\fP (const \fBgdsl_list_t\fP L, \fBgdsl_compare_func_t\fP COMP_F)"
.br
.RI "\fISearch for the lowest element of a list. \fP"
.ti -1c
.RI "\fBgdsl_list_t\fP \fBgdsl_list_sort\fP (\fBgdsl_list_t\fP L, \fBgdsl_compare_func_t\fP COMP_F)"
.br
.RI "\fISort a list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_map_forward\fP (const \fBgdsl_list_t\fP L, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a list from head to tail. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_map_backward\fP (const \fBgdsl_list_t\fP L, \fBgdsl_map_func_t\fP MAP_F, void *USER_DATA)"
.br
.RI "\fIParse a list from tail to head. \fP"
.ti -1c
.RI "void \fBgdsl_list_write\fP (const \fBgdsl_list_t\fP L, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite all the elements of a list to a file. \fP"
.ti -1c
.RI "void \fBgdsl_list_write_xml\fP (const \fBgdsl_list_t\fP L, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite the content of a list to a file into XML. \fP"
.ti -1c
.RI "void \fBgdsl_list_dump\fP (const \fBgdsl_list_t\fP L, \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIDump the internal structure of a list to a file. \fP"
.ti -1c
.RI "\fBgdsl_list_cursor_t\fP \fBgdsl_list_cursor_alloc\fP (const \fBgdsl_list_t\fP L)"
.br
.RI "\fICreate a new list cursor. \fP"
.ti -1c
.RI "void \fBgdsl_list_cursor_free\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIDestroy a list cursor. \fP"
.ti -1c
.RI "void \fBgdsl_list_cursor_move_to_head\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIPut a cursor on the head of its list. \fP"
.ti -1c
.RI "void \fBgdsl_list_cursor_move_to_tail\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIPut a cursor on the tail of its list. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_cursor_move_to_value\fP (\fBgdsl_list_cursor_t\fP C, \fBgdsl_compare_func_t\fP COMP_F, void *VALUE)"
.br
.RI "\fIPlace a cursor on a particular element. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_cursor_move_to_position\fP (\fBgdsl_list_cursor_t\fP C, \fBulong\fP POS)"
.br
.RI "\fIPlace a cursor on a element given by its position. \fP"
.ti -1c
.RI "void \fBgdsl_list_cursor_step_forward\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIMove a cursor one step forward of its list. \fP"
.ti -1c
.RI "void \fBgdsl_list_cursor_step_backward\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIMove a cursor one step backward of its list. \fP"
.ti -1c
.RI "\fBbool\fP \fBgdsl_list_cursor_is_on_head\fP (const \fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fICheck if a cursor is on the head of its list. \fP"
.ti -1c
.RI "\fBbool\fP \fBgdsl_list_cursor_is_on_tail\fP (const \fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fICheck if a cursor is on the tail of its list. \fP"
.ti -1c
.RI "\fBbool\fP \fBgdsl_list_cursor_has_succ\fP (const \fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fICheck if a cursor has a successor. \fP"
.ti -1c
.RI "\fBbool\fP \fBgdsl_list_cursor_has_pred\fP (const \fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fICheck if a cursor has a predecessor. \fP"
.ti -1c
.RI "void \fBgdsl_list_cursor_set_content\fP (\fBgdsl_list_cursor_t\fP C, \fBgdsl_element_t\fP E)"
.br
.RI "\fISet the content of the cursor. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_cursor_get_content\fP (const \fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIGet the content of a cursor. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_cursor_insert_after\fP (\fBgdsl_list_cursor_t\fP C, void *VALUE)"
.br
.RI "\fIInsert a new element after a cursor. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_cursor_insert_before\fP (\fBgdsl_list_cursor_t\fP C, void *VALUE)"
.br
.RI "\fIInsert a new element before a cursor. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_cursor_remove\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIRemovec the element under a cursor. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_cursor_remove_after\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIRemovec the element after a cursor. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP \fBgdsl_list_cursor_remove_before\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIRemove the element before a cursor. \fP"
.ti -1c
.RI "\fBgdsl_list_cursor_t\fP \fBgdsl_list_cursor_delete\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIDelete the element under a cursor. \fP"
.ti -1c
.RI "\fBgdsl_list_cursor_t\fP \fBgdsl_list_cursor_delete_after\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIDelete the element after a cursor. \fP"
.ti -1c
.RI "\fBgdsl_list_cursor_t\fP \fBgdsl_list_cursor_delete_before\fP (\fBgdsl_list_cursor_t\fP C)"
.br
.RI "\fIDelete the element before the cursor of a list. \fP"
.in -1c
.SH "Typedef Documentation"
.PP 
.SS "typedef struct _gdsl_list* \fBgdsl_list_t\fP"
.PP
GDSL doubly-linked list 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 51 of file gdsl_list.h.
.SS "typedef struct _gdsl_list_cursor* \fBgdsl_list_cursor_t\fP"
.PP
GDSL doubly-linked list cursor 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 59 of file gdsl_list.h.
.SH "Function Documentation"
.PP 
.SS "\fBgdsl_list_t\fP gdsl_list_alloc (const char * NAME, \fBgdsl_alloc_func_t\fP ALLOC_F, \fBgdsl_free_func_t\fP FREE_F)"
.PP
Create a new list. 
.PP
Allocate a new list data structure which name is set to a copy of NAME. The function pointers ALLOC_F and FREE_F could be used to respectively, alloc and free elements in the list. 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
.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 list to create 
.br
\fIALLOC_F\fP Function to alloc element when inserting it in the list 
.br
\fIFREE_F\fP Function to free element when removing it from the list 
.RE
.PP
\fBReturns:\fP
.RS 4
the newly allocated list in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_free()\fP 
.PP
\fBgdsl_list_flush()\fP 
.RE
.PP

.SS "void gdsl_list_free (\fBgdsl_list_t\fP L)"
.PP
Destroy a list. 
.PP
Flush and destroy the list L. All the elements of L are freed using L's FREE_F function passed to \fBgdsl_list_alloc()\fP.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |L| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to destroy 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_alloc()\fP 
.PP
\fBgdsl_list_flush()\fP 
.RE
.PP

.SS "void gdsl_list_flush (\fBgdsl_list_t\fP L)"
.PP
Flush a list. 
.PP
Destroy all the elements of the list L by calling L's FREE_F function passed to \fBgdsl_list_alloc()\fP. L is not deallocated itself and L's name is not modified.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |L| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to flush 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_alloc()\fP 
.PP
\fBgdsl_list_free()\fP 
.RE
.PP

.SS "const char* gdsl_list_get_name (const \fBgdsl_list_t\fP L)"
.PP
Get the name of a list. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBPostcondition:\fP
.RS 4
The returned string MUST NOT be freed. 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to get the name from 
.RE
.PP
\fBReturns:\fP
.RS 4
the name of the list L. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_set_name()\fP 
.RE
.PP

.SS "\fBulong\fP gdsl_list_get_size (const \fBgdsl_list_t\fP L)"
.PP
Get the size of a list. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to get the size from 
.RE
.PP
\fBReturns:\fP
.RS 4
the number of elements of the list L (noted |L|). 
.RE
.PP

.SS "\fBbool\fP gdsl_list_is_empty (const \fBgdsl_list_t\fP L)"
.PP
Check if a list is empty. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to check 
.RE
.PP
\fBReturns:\fP
.RS 4
TRUE if the list L is empty. 
.PP
FALSE if the list L is not empty. 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_list_get_head (const \fBgdsl_list_t\fP L)"
.PP
Get the head of a list. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to get the head from 
.RE
.PP
\fBReturns:\fP
.RS 4
the element at L's head position if L is not empty. The returned element is not removed from L. 
.PP
NULL if the list L is empty. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_get_tail()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_list_get_tail (const \fBgdsl_list_t\fP L)"
.PP
Get the tail of a list. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to get the tail from 
.RE
.PP
\fBReturns:\fP
.RS 4
the element at L's tail position if L is not empty. The returned element is not removed from L. 
.PP
NULL if L is empty. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_get_head()\fP 
.RE
.PP

.SS "\fBgdsl_list_t\fP gdsl_list_set_name (\fBgdsl_list_t\fP L, const char * NEW_NAME)"
.PP
Set the name of a list. 
.PP
Changes the previous name of the list L to a copy of NEW_NAME.
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to change the name 
.br
\fINEW_NAME\fP The new name of L 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified list in case of success. 
.PP
NULL in case of failure. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_get_name()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_list_insert_head (\fBgdsl_list_t\fP L, void * VALUE)"
.PP
Insert an element at the head of a list. 
.PP
Allocate a new element E by calling L's ALLOC_F function on VALUE. ALLOC_F is the function pointer passed to \fBgdsl_list_alloc()\fP. The new element E is then inserted at the header position of the list L.
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to insert into 
.br
\fIVALUE\fP The value used to make the new element to insert into L 
.RE
.PP
\fBReturns:\fP
.RS 4
the inserted element E in case of success. 
.PP
NULL in case of failure. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_insert_tail()\fP 
.PP
\fBgdsl_list_remove_head()\fP 
.PP
\fBgdsl_list_remove_tail()\fP 
.PP
\fBgdsl_list_remove()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_list_insert_tail (\fBgdsl_list_t\fP L, void * VALUE)"
.PP
Insert an element at the tail of a list. 
.PP
Allocate a new element E by calling L's ALLOC_F function on VALUE. ALLOC_F is the function pointer passed to \fBgdsl_list_alloc()\fP. The new element E is then inserted at the footer position of the list L.
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to insert into 
.br
\fIVALUE\fP The value used to make the new element to insert into L 
.RE
.PP
\fBReturns:\fP
.RS 4
the inserted element E in case of success. 
.PP
NULL in case of failure. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_insert_head()\fP 
.PP
\fBgdsl_list_remove_head()\fP 
.PP
\fBgdsl_list_remove_tail()\fP 
.PP
\fBgdsl_list_remove()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_list_remove_head (\fBgdsl_list_t\fP L)"
.PP
Remove the head of a list. 
.PP
Remove the element at the head of the list L.
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
L must be a valid gdsl_list_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIL\fP The list to remove the head from 
.RE
.PP
\fBReturns:\fP
.RS 4
the removed element in case of success. 
.PP
NULL in case of L is empty. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_list_insert_head()\fP 
.PP
\fBgdsl_list_insert_tail()\fP 
.PP
\fBgdsl_list_remove_tail()\fP 
.PP
\fBgdsl_list_remove()\fP 
.RE
.PP