---

Linked lists

Operations for linked lists. More...

Defines
#define	LINK_HEAD_INIT(extra)
	Linked list head static initializer. More...
#define	ll_verify(list)
	Linked list head verification macro. More...
#define	ll_count(list)
	Linked list count. More...
#define	ll_first(list)
	First element in linked list. More...
#define	ll_last(list)
	Last element in a linked list. More...
#define	ll_extra(list)
	Extra pointer data in a linked list. More...
#define	LINK_ELEM_INIT(obj)
	Linked list element static initializer. More...
#define	le_verify(element)
	Linked list element verification macro. More...
#define	le_next(elem)
	Linked list element next pointer. More...
#define	le_prev(elem)
	Linked list element previous pointer. More...
#define	le_object(elem)
	Linked list element object pointer. More...
#define	le_head(elem)
	Linked list element head pointer. More...
#define	le_flags(elem)
	Linked list element flags. More...
Typedefs
typedef struct _link_head_s	link_head_t
	Linked list head. More...
typedef struct _link_elem_s	link_elem_t
	Linked list element. More...
typedef unsigned long (*	link_iter_t )(link_head_t *, link_elem_t *, void *)
	Linked list iteration callback. More...
typedef unsigned long (*	link_comp_t )(db_key_t *, void *)
	Linked list comparison callback. More...
typedef enum _link_loc_e	link_loc_t
	Linked list location. More...
Enumerations
enum	_link_loc_e { LINK_LOC_HEAD, LINK_LOC_TAIL, LINK_LOC_BEFORE, LINK_LOC_AFTER }
	Linked list location. More...
Functions
unsigned long	ll_init (link_head_t *list, void *extra)
	Dynamically initialize a linked list head. More...
unsigned long	ll_add (link_head_t *list, link_elem_t *new, link_loc_t loc, link_elem_t *elem)
	Add an element to a linked list. More...
unsigned long	ll_move (link_head_t *list, link_elem_t *new, link_loc_t loc, link_elem_t *elem)
	Move an element within a linked list. More...
unsigned long	ll_remove (link_head_t *list, link_elem_t *elem)
	Remove an element from a linked list. More...
unsigned long	ll_find (link_head_t *list, link_elem_t **elem_p, link_comp_t comp_func, link_elem_t *start, db_key_t *key)
	Find an element in a linked list. More...
unsigned long	ll_iter (link_head_t *list, link_iter_t iter_func, void *extra)
	Iterate over each entry in a linked list. More...
unsigned long	ll_flush (link_head_t *list, link_iter_t flush_func, void *extra)
	Flush a linked list. More...
unsigned long	le_init (link_elem_t *elem, void *object)
	Dynamically initialize a linked list element. More...

---

Detailed Description

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 link_head_t 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 link_elem_t 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.

Elements may be added at any arbitrary location in the linked list with ll_add(); moved to any other arbitrary location in the linked list with ll_move(), or removed from the list with ll_remove(). In addition, the user may search the list using a user-defined comparison function with ll_find(); iterate over every element in the list with ll_iter(); or remove all items from the list with ll_flush(), optionally executing a user-specified clean-up function.

---

Define Documentation

#define LINK_ELEM_INIT( obj )

This macro statically initializes a link_elem_t. Parameters: obj   A pointer to void representing the object associated with the element.

#define LINK_HEAD_INIT( extra )

This macro statically initializes a link_head_t. Parameters: extra   Extra pointer data that should be associated with the list head.

#define le_flags( elem )

This macro retrieves a set of user-defined flags associated with the element. It may be used as an lvalue to set those flags. Parameters: elem   A pointer to a link_elem_t. Returns: An unsigned long containing the flags associated with the element.

#define le_head( elem )

This macro retrieves a pointer to the head of the linked list that the element is in. Parameters: elem   A pointer to a link_elem_t. Returns: A pointer to a link_head_t representing the head of the linked list the element is in.

#define le_next( elem )

This macro retrieves a pointer to the next element in the linked list. Parameters: elem   A pointer to a link_elem_t. Returns: A pointer to a link_elem_t representing the next element in the linked list.

#define le_object( elem )

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. Parameters: elem   A pointer to a link_elem_t. Returns: A pointer to void representing the object associated with the linked list element.

#define le_prev( elem )

This macro retrieves a pointer to the previous element in the linked list. Parameters: elem   A pointer to a link_elem_t. Returns: A pointer to a link_elem_t representing the previous element in the linked list.

#define le_verify( element )

This macro verifies that a given pointer actually does point to a linked list element. Parameters: element   A pointer to a link_elem_t. Returns: Boolean true if element is a valid linked list element or false otherwise.

#define ll_count( list )

This macro retrieves the number of elements in a linked list. Parameters: list   A pointer to a link_head_t. Returns: An unsigned long containing a count of the number of elements in the linked list.

#define ll_extra( list )

This macro retrieves the extra pointer data associated with a particular linked list. Parameters: list   A pointer to a link_head_t. Returns: A pointer to void.

#define ll_first( list )

This macro retrieves the first element in a linked list. Parameters: list   A pointer to a link_head_t. Returns: A pointer to a link_elem_t.

#define ll_last( list )

This macro retrieves the last element in a linked list. Parameters: list   A pointer to a link_head_t. Returns: A pointer to a link_elem_t.

#define ll_verify( list )

This macro verifies that a given pointer actually does point to a linked list head. Parameters: list   A pointer to a link_head_t. Returns: Boolean true if list is a valid linked list head or false otherwise.

---

Typedef Documentation

typedef unsigned long(* link_comp_t)(db_key_t *, void *)

This function pointer references a callback used by ll_find(). It should return 0 if the entry passed as the second argument matches the key passed as the first argument.

typedef struct _link_elem_s link_elem_t

This structure represents a single element of a linked list.

typedef struct _link_head_s link_head_t

This structure is the head of all linked lists maintained by this library.

typedef unsigned long(* link_iter_t)(link_head_t *, link_elem_t *, void *)

This function pointer references a callback used by ll_iter() and ll_flush(). It should return 0 for success. A non-zero return value will terminate the operation and will become the return value of the ll_iter() or ll_flush() call.

typedef enum _link_loc_e link_loc_t

See the documentation for the enumeration _link_loc_e.

---

Enumeration Type Documentation

enum _link_loc_e

This enumeration is used to specify where an element in a linked list should be placed. It should be referenced by the typedef link_loc_t. Enumeration values: LINK_LOC_HEAD   Element should be inserted at head of list. LINK_LOC_TAIL   Element should be inserted at tail of list. LINK_LOC_BEFORE   Element should be inserted before specified element. LINK_LOC_AFTER   Element should be inserted after specified element.

---

Function Documentation

unsigned long le_init ( link_elem_t * elem, void * object )

This function dynamically initializes a linked list element. Parameters: elem   A pointer to a link_elem_t to be initialized. object   A pointer to void used to represent the object associated with the element. May not be NULL. Return values: DB_ERR_BADARGS   A NULL pointer was passed for elem or object.

unsigned long ll_add ( link_head_t * list, link_elem_t * new, link_loc_t loc, link_elem_t * elem )

This function adds a given element to a specified linked list in the specified location. Parameters: list   A pointer to a link_head_t. new   A pointer to the link_elem_t to be added to the linked list. loc   A link_loc_t indicating where the entry should be added. elem   A pointer to a link_elem_t describing another element in the list if loc is LINK_LOC_BEFORE or LINK_LOC_AFTER. Return values: DB_ERR_BADARGS   An argument was invalid. DB_ERR_BUSY   The element is already in a list. DB_ERR_WRONGTABLE   elem is in a different list. DB_ERR_UNUSED   elem is not in any list.

unsigned long ll_find ( link_head_t * list, link_elem_t ** elem_p, link_comp_t comp_func, link_elem_t * start, db_key_t * key )

This function iterates through a linked list looking for an element that matches the given key. Parameters: list   A pointer to a link_head_t. elem_p   A pointer to a pointer to a link_elem_t. This is a result parameter. NULL is an invalid value. comp_func   A pointer to a comparison function used to compare the key to a particular element. See the documentation for link_comp_t for more information. start   A pointer to a link_elem_t describing where in the linked list to start. If NULL is passed, the beginning of the list will be assumed. key   A key to search for. Return values: DB_ERR_BADARGS   An argument was invalid. DB_ERR_WRONGTABLE   start is not in this linked list. DB_ERR_NOENTRY   No matching entry was found.

unsigned long ll_flush ( link_head_t * list, link_iter_t flush_func, void * extra )

This function flushes a linked list--that is, it removes each element from the list. If a flush_func is specified, it will be called on the entry after it has been removed from the list, and may safely call free(). Parameters: list   A pointer to a link_head_t. flush_func   A pointer to a callback function used to perform user-specified actions on an element after removing it from the list. May be NULL. See the documentation for link_iter_t for more information. extra   A void pointer that will be passed to flush_func. Return values: DB_ERR_BADARGS   An argument was invalid.

unsigned long ll_init ( link_head_t * list, void * extra )

This function dynamically initializes a linked list head. Parameters: list   A pointer to a link_head_t to be initialized. extra   A pointer to void containing extra pointer data associated with the linked list. Return values: DB_ERR_BADARGS   A NULL pointer was passed for list.

unsigned long ll_iter ( link_head_t * list, link_iter_t iter_func, void * extra )

This function iterates over a linked list, executing the given iter_func for each entry. Parameters: list   A pointer to a link_head_t. iter_func   A pointer to a callback function used to perform user-specified actions on an element in a linked list. NULL is an invalid value. See the documentation for link_iter_t for more information. extra   A void pointer that will be passed to iter_func. Return values: DB_ERR_BADARGS   An argument was invalid.

unsigned long ll_move ( link_head_t * list, link_elem_t * elem, link_loc_t loc, link_elem_t * elem2 )

This function moves a specified element within the linked list. Parameters: list   A pointer to a link_head_t. elem   A pointer to the link_elem_t describing the element to be moved. loc   A link_loc_t indicating where the entry should be moved to. elem2   A pointer to a link_elem_t describing another element in the list if loc is LINK_LOC_BEFORE or LINK_LOC_AFTER. Return values: DB_ERR_BADARGS   An argument was invalid. DB_ERR_BUSY   elem and elem2 are the same element. DB_ERR_WRONGTABLE   elem or elem2 are in a different list. DB_ERR_UNUSED   elem or elem2 are not in any list.

unsigned long ll_remove ( link_head_t * list, link_elem_t * elem )

This function removes a specified element from a linked list. Parameters: list   A pointer to a link_head_t. elem   A pointer to the link_elem_t describing the element to be removed. Return values: DB_ERR_BADARGS   An argument was invalid. DB_ERR_UNUSED   elem is not in a linked list. DB_ERR_WRONGTABLE   elem is not in this linked list.

---