1 .TH "Linked lists" 3 "6 Mar 2003" "dbprim" \" -*- nroff -*-
5 Linked lists \- Operations for linked lists.
11 .RI "#define \fBLINK_HEAD_INIT\fP(extra)"
13 .RI "\fILinked list head static initializer.\fP"
15 .RI "#define \fBll_verify\fP(list)"
17 .RI "\fILinked list head verification macro.\fP"
19 .RI "#define \fBll_count\fP(list)"
21 .RI "\fILinked list count.\fP"
23 .RI "#define \fBll_first\fP(list)"
25 .RI "\fIFirst element in linked list.\fP"
27 .RI "#define \fBll_last\fP(list)"
29 .RI "\fILast element in a linked list.\fP"
31 .RI "#define \fBll_extra\fP(list)"
33 .RI "\fIExtra pointer data in a linked list.\fP"
35 .RI "#define \fBLINK_ELEM_INIT\fP(obj)"
37 .RI "\fILinked list element static initializer.\fP"
39 .RI "#define \fBle_verify\fP(element)"
41 .RI "\fILinked list element verification macro.\fP"
43 .RI "#define \fBle_next\fP(elem)"
45 .RI "\fILinked list element next pointer.\fP"
47 .RI "#define \fBle_prev\fP(elem)"
49 .RI "\fILinked list element previous pointer.\fP"
51 .RI "#define \fBle_object\fP(elem)"
53 .RI "\fILinked list element object pointer.\fP"
55 .RI "#define \fBle_head\fP(elem)"
57 .RI "\fILinked list element head pointer.\fP"
59 .RI "#define \fBle_flags\fP(elem)"
61 .RI "\fILinked list element flags.\fP"
67 .RI "typedef struct _link_head_s \fBlink_head_t\fP"
69 .RI "\fILinked list head.\fP"
71 .RI "typedef struct _link_elem_s \fBlink_elem_t\fP"
73 .RI "\fILinked list element.\fP"
75 .RI "typedef unsigned long (* \fBlink_iter_t\fP )(\fBlink_head_t\fP *, \fBlink_elem_t\fP *, void *)"
77 .RI "\fILinked list iteration callback.\fP"
79 .RI "typedef unsigned long (* \fBlink_comp_t\fP )(\fBdb_key_t\fP *, void *)"
81 .RI "\fILinked list comparison callback.\fP"
83 .RI "typedef enum \fB_link_loc_e\fP \fBlink_loc_t\fP"
85 .RI "\fILinked list location.\fP"
91 .RI "enum \fB_link_loc_e\fP { \fBLINK_LOC_HEAD\fP, \fBLINK_LOC_TAIL\fP, \fBLINK_LOC_BEFORE\fP, \fBLINK_LOC_AFTER\fP }"
93 .RI "\fILinked list location.\fP"
99 .RI "unsigned long \fBll_init\fP (\fBlink_head_t\fP *list, void *extra)"
101 .RI "\fIDynamically initialize a linked list head.\fP"
103 .RI "unsigned long \fBll_add\fP (\fBlink_head_t\fP *list, \fBlink_elem_t\fP *new, \fBlink_loc_t\fP loc, \fBlink_elem_t\fP *elem)"
105 .RI "\fIAdd an element to a linked list.\fP"
107 .RI "unsigned long \fBll_move\fP (\fBlink_head_t\fP *list, \fBlink_elem_t\fP *new, \fBlink_loc_t\fP loc, \fBlink_elem_t\fP *elem)"
109 .RI "\fIMove an element within a linked list.\fP"
111 .RI "unsigned long \fBll_remove\fP (\fBlink_head_t\fP *list, \fBlink_elem_t\fP *elem)"
113 .RI "\fIRemove an element from a linked list.\fP"
115 .RI "unsigned long \fBll_find\fP (\fBlink_head_t\fP *list, \fBlink_elem_t\fP **elem_p, \fBlink_comp_t\fP comp_func, \fBlink_elem_t\fP *start, \fBdb_key_t\fP *key)"
117 .RI "\fIFind an element in a linked list.\fP"
119 .RI "unsigned long \fBll_iter\fP (\fBlink_head_t\fP *list, \fBlink_iter_t\fP iter_func, void *extra)"
121 .RI "\fIIterate over each entry in a linked list.\fP"
123 .RI "unsigned long \fBll_flush\fP (\fBlink_head_t\fP *list, \fBlink_iter_t\fP flush_func, void *extra)"
125 .RI "\fIFlush a linked list.\fP"
127 .RI "unsigned long \fBle_init\fP (\fBlink_elem_t\fP *elem, void *object)"
129 .RI "\fIDynamically initialize a linked list element.\fP"
131 .SH "DETAILED DESCRIPTION"
133 Linked lists are a very basic data structure used in building databases. This library provides a simple yet powerful implementation of generic linked lists, based on two caller-allocated structures. The \fBlink_head_t\fP structure describes the head of a linked list and contains information regarding the number of elements in the linked list as well as pointers referencing the first and last elements in the list. The \fBlink_elem_t\fP structure describes a specific element in the linked list and contains pointers referencing the next and previous elements in the list, as well as a pointer to the object, a pointer to the head of the linked list, and a set of user-specified flags.
135 Elements may be added at any arbitrary location in the linked list with \fBll_add\fP(); moved to any other arbitrary location in the linked list with \fBll_move\fP(), or removed from the list with \fBll_remove\fP(). In addition, the user may search the list using a user-defined comparison function with \fBll_find\fP(); iterate over every element in the list with \fBll_iter\fP(); or remove all items from the list with \fBll_flush\fP(), optionally executing a user-specified clean-up function.
136 .SH "DEFINE DOCUMENTATION"
138 .SS "#define LINK_ELEM_INIT(obj)"
141 This macro statically initializes a \fBlink_elem_t\fP.
147 A pointer to \fCvoid\fP representing the object associated with the element.
148 .SS "#define LINK_HEAD_INIT(extra)"
151 This macro statically initializes a \fBlink_head_t\fP.
157 Extra pointer data that should be associated with the list head.
158 .SS "#define le_flags(elem)"
161 This macro retrieves a set of user-defined flags associated with the element. It may be used as an lvalue to set those flags.
167 A pointer to a \fBlink_elem_t\fP.
171 An \fCunsigned long\fP containing the flags associated with the element.
172 .SS "#define le_head(elem)"
175 This macro retrieves a pointer to the head of the linked list that the element is in.
181 A pointer to a \fBlink_elem_t\fP.
185 A pointer to a \fBlink_head_t\fP representing the head of the linked list the element is in.
186 .SS "#define le_next(elem)"
189 This macro retrieves a pointer to the next element in the linked list.
195 A pointer to a \fBlink_elem_t\fP.
199 A pointer to a \fBlink_elem_t\fP representing the next element in the linked list.
200 .SS "#define le_object(elem)"
203 This macro retrieves a pointer to the object represented by the element. It may be used as an lvalue to change the object pointed to. Care should be taken when using this feature.
209 A pointer to a \fBlink_elem_t\fP.
213 A pointer to \fCvoid\fP representing the object associated with the linked list element.
214 .SS "#define le_prev(elem)"
217 This macro retrieves a pointer to the previous element in the linked list.
223 A pointer to a \fBlink_elem_t\fP.
227 A pointer to a \fBlink_elem_t\fP representing the previous element in the linked list.
228 .SS "#define le_verify(element)"
231 This macro verifies that a given pointer actually does point to a linked list element.
237 A pointer to a \fBlink_elem_t\fP.
241 Boolean true if \fCelement\fP is a valid linked list element or false otherwise.
242 .SS "#define ll_count(list)"
245 This macro retrieves the number of elements in a linked list.
251 A pointer to a \fBlink_head_t\fP.
255 An \fCunsigned long\fP containing a count of the number of elements in the linked list.
256 .SS "#define ll_extra(list)"
259 This macro retrieves the extra pointer data associated with a particular linked list.
265 A pointer to a \fBlink_head_t\fP.
269 A pointer to \fCvoid\fP.
270 .SS "#define ll_first(list)"
273 This macro retrieves the first element in a linked list.
279 A pointer to a \fBlink_head_t\fP.
283 A pointer to a \fBlink_elem_t\fP.
284 .SS "#define ll_last(list)"
287 This macro retrieves the last element in a linked list.
293 A pointer to a \fBlink_head_t\fP.
297 A pointer to a \fBlink_elem_t\fP.
298 .SS "#define ll_verify(list)"
301 This macro verifies that a given pointer actually does point to a linked list head.
307 A pointer to a \fBlink_head_t\fP.
311 Boolean true if \fClist\fP is a valid linked list head or false otherwise.
312 .SH "TYPEDEF DOCUMENTATION"
314 .SS "typedef unsigned long(* link_comp_t)(\fBdb_key_t\fP *, void *)"
317 This function pointer references a callback used by \fBll_find\fP(). It should return 0 if the entry passed as the second argument matches the key passed as the first argument.
318 .SS "typedef struct _link_elem_s link_elem_t"
321 This structure represents a single element of a linked list.
322 .SS "typedef struct _link_head_s link_head_t"
325 This structure is the head of all linked lists maintained by this library.
326 .SS "typedef unsigned long(* link_iter_t)(\fBlink_head_t\fP *, \fBlink_elem_t\fP *, void *)"
329 This function pointer references a callback used by \fBll_iter\fP() and \fBll_flush\fP(). It should return 0 for success. A non-zero return value will terminate the operation and will become the return value of the \fBll_iter\fP() or \fBll_flush\fP() call.
330 .SS "typedef enum \fB_link_loc_e\fP link_loc_t"
333 See the documentation for the enumeration \fB_link_loc_e\fP.
334 .SH "ENUMERATION TYPE DOCUMENTATION"
336 .SS "enum _link_loc_e"
339 This enumeration is used to specify where an element in a linked list should be placed. It should be referenced by the typedef \fBlink_loc_t\fP.
341 \fBEnumeration values:\fP
344 \fB\fILINK_LOC_HEAD\fP \fP
345 Element should be inserted at head of list.
347 \fB\fILINK_LOC_TAIL\fP \fP
348 Element should be inserted at tail of list.
350 \fB\fILINK_LOC_BEFORE\fP \fP
351 Element should be inserted before specified element.
353 \fB\fILINK_LOC_AFTER\fP \fP
354 Element should be inserted after specified element.
355 .SH "FUNCTION DOCUMENTATION"
357 .SS "unsigned long le_init (\fBlink_elem_t\fP * elem, void * object)"
360 This function dynamically initializes a linked list element.
366 A pointer to a \fBlink_elem_t\fP to be initialized.
369 A pointer to \fCvoid\fP used to represent the object associated with the element. May not be \fCNULL\fP.
371 \fBReturn values: \fP
374 \fB\fIDB_ERR_BADARGS\fP\fP
375 A \fCNULL\fP pointer was passed for \fCelem\fP or \fCobject\fP.
376 .SS "unsigned long ll_add (\fBlink_head_t\fP * list, \fBlink_elem_t\fP * new, \fBlink_loc_t\fP loc, \fBlink_elem_t\fP * elem)"
379 This function adds a given element to a specified linked list in the specified location.
385 A pointer to a \fBlink_head_t\fP.
388 A pointer to the \fBlink_elem_t\fP to be added to the linked list.
391 A \fBlink_loc_t\fP indicating where the entry should be added.
394 A pointer to a \fBlink_elem_t\fP describing another element in the list if \fCloc\fP is \fBLINK_LOC_BEFORE\fP or \fBLINK_LOC_AFTER\fP.
396 \fBReturn values: \fP
399 \fB\fIDB_ERR_BADARGS\fP\fP
400 An argument was invalid.
402 \fB\fIDB_ERR_BUSY\fP\fP
403 The element is already in a list.
405 \fB\fIDB_ERR_WRONGTABLE\fP\fP
406 \fCelem\fP is in a different list.
408 \fB\fIDB_ERR_UNUSED\fP\fP
409 \fCelem\fP is not in any list.
410 .SS "unsigned long ll_find (\fBlink_head_t\fP * list, \fBlink_elem_t\fP ** elem_p, \fBlink_comp_t\fP comp_func, \fBlink_elem_t\fP * start, \fBdb_key_t\fP * key)"
413 This function iterates through a linked list looking for an element that matches the given \fCkey\fP.
419 A pointer to a \fBlink_head_t\fP.
422 A pointer to a pointer to a \fBlink_elem_t\fP. This is a result parameter. \fCNULL\fP is an invalid value.
424 \fB\fIcomp_func\fP\fP
425 A pointer to a comparison function used to compare the key to a particular element. See the documentation for \fBlink_comp_t\fP for more information.
428 A pointer to a \fBlink_elem_t\fP describing where in the linked list to start. If \fCNULL\fP is passed, the beginning of the list will be assumed.
433 \fBReturn values: \fP
436 \fB\fIDB_ERR_BADARGS\fP\fP
437 An argument was invalid.
439 \fB\fIDB_ERR_WRONGTABLE\fP\fP
440 \fCstart\fP is not in this linked list.
442 \fB\fIDB_ERR_NOENTRY\fP\fP
443 No matching entry was found.
444 .SS "unsigned long ll_flush (\fBlink_head_t\fP * list, \fBlink_iter_t\fP flush_func, void * extra)"
447 This function flushes a linked list--that is, it removes each element from the list. If a \fCflush_func\fP is specified, it will be called on the entry after it has been removed from the list, and may safely call \fCfree()\fP.
453 A pointer to a \fBlink_head_t\fP.
455 \fB\fIflush_func\fP\fP
456 A pointer to a callback function used to perform user-specified actions on an element after removing it from the list. May be \fCNULL\fP. See the documentation for \fBlink_iter_t\fP for more information.
459 A \fCvoid\fP pointer that will be passed to \fCflush_func\fP.
461 \fBReturn values: \fP
464 \fB\fIDB_ERR_BADARGS\fP\fP
465 An argument was invalid.
466 .SS "unsigned long ll_init (\fBlink_head_t\fP * list, void * extra)"
469 This function dynamically initializes a linked list head.
475 A pointer to a \fBlink_head_t\fP to be initialized.
478 A pointer to \fCvoid\fP containing extra pointer data associated with the linked list.
480 \fBReturn values: \fP
483 \fB\fIDB_ERR_BADARGS\fP\fP
484 A \fCNULL\fP pointer was passed for \fClist\fP.
485 .SS "unsigned long ll_iter (\fBlink_head_t\fP * list, \fBlink_iter_t\fP iter_func, void * extra)"
488 This function iterates over a linked list, executing the given \fCiter_func\fP for each entry.
494 A pointer to a \fBlink_head_t\fP.
496 \fB\fIiter_func\fP\fP
497 A pointer to a callback function used to perform user-specified actions on an element in a linked list. \fCNULL\fP is an invalid value. See the documentation for \fBlink_iter_t\fP for more information.
500 A \fCvoid\fP pointer that will be passed to \fCiter_func\fP.
502 \fBReturn values: \fP
505 \fB\fIDB_ERR_BADARGS\fP\fP
506 An argument was invalid.
507 .SS "unsigned long ll_move (\fBlink_head_t\fP * list, \fBlink_elem_t\fP * elem, \fBlink_loc_t\fP loc, \fBlink_elem_t\fP * elem2)"
510 This function moves a specified element within the linked list.
516 A pointer to a \fBlink_head_t\fP.
519 A pointer to the \fBlink_elem_t\fP describing the element to be moved.
522 A \fBlink_loc_t\fP indicating where the entry should be moved to.
525 A pointer to a \fBlink_elem_t\fP describing another element in the list if \fCloc\fP is \fBLINK_LOC_BEFORE\fP or \fBLINK_LOC_AFTER\fP.
527 \fBReturn values: \fP
530 \fB\fIDB_ERR_BADARGS\fP\fP
531 An argument was invalid.
533 \fB\fIDB_ERR_BUSY\fP\fP
534 \fCelem\fP and \fCelem2\fP are the same element.
536 \fB\fIDB_ERR_WRONGTABLE\fP\fP
537 \fCelem\fP or \fCelem2\fP are in a different list.
539 \fB\fIDB_ERR_UNUSED\fP\fP
540 \fCelem\fP or \fCelem2\fP are not in any list.
541 .SS "unsigned long ll_remove (\fBlink_head_t\fP * list, \fBlink_elem_t\fP * elem)"
544 This function removes a specified element from a linked list.
550 A pointer to a \fBlink_head_t\fP.
553 A pointer to the \fBlink_elem_t\fP describing the element to be removed.
555 \fBReturn values: \fP
558 \fB\fIDB_ERR_BADARGS\fP\fP
559 An argument was invalid.
561 \fB\fIDB_ERR_UNUSED\fP\fP
562 \fCelem\fP is not in a linked list.
564 \fB\fIDB_ERR_WRONGTABLE\fP\fP
565 \fCelem\fP is not in this linked list.