Linked lists

---

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.

Data Structures
struct	_link_head_s
	Linked list head structure. More...
struct	_link_elem_s
	Linked list element structure. More...
Defines
#define	LINK_HEAD_MAGIC
	Linked list head magic number.
#define	LINK_HEAD_INIT(extra)
	Linked list head static initializer.
#define	ll_verify(list)
	Linked list head verification macro.
#define	ll_count(list)
	Linked list count.
#define	ll_first(list)
	First element in linked list.
#define	ll_last(list)
	Last element in a linked list.
#define	ll_extra(list)
	Extra pointer data in a linked list.
#define	LINK_ELEM_MAGIC
	Linked list element magic number.
#define	LINK_ELEM_INIT(obj)
	Linked list element static initializer.
#define	le_verify(element)
	Linked list element verification macro.
#define	le_next(elem)
	Linked list element next pointer.
#define	le_prev(elem)
	Linked list element previous pointer.
#define	le_object(elem)
	Linked list element object pointer.
#define	le_head(elem)
	Linked list element head pointer.
#define	le_flags(elem)
	Linked list element flags.
Typedefs
typedef _link_head_s	link_head_t
	Linked list head.
typedef _link_elem_s	link_elem_t
	Linked list element.
typedef unsigned long(*	link_iter_t )(link_head_t *list, link_elem_t *elem, void *extra)
	Linked list iteration callback.
typedef unsigned long(*	link_comp_t )(db_key_t *key, void *obj)
	Linked list comparison callback.
typedef enum _link_loc_e	link_loc_t
	Linked list location.
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.
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.
unsigned long	ll_move (link_head_t *list, link_elem_t *elem, link_loc_t loc, link_elem_t *elem2)
	Move an element within a linked list.
unsigned long	ll_remove (link_head_t *list, link_elem_t *elem)
	Remove an element from a linked 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)
	Find an element in a linked list.
unsigned long	ll_iter (link_head_t *list, link_elem_t *start, link_iter_t iter_func, void *extra, unsigned long flags)
	Iterate over each entry in a linked list.
unsigned long	ll_flush (link_head_t *list, link_iter_t flush_func, void *extra)
	Flush a linked list.
unsigned long	le_init (link_elem_t *elem, void *object)
	Dynamically initialize a linked list element.

---

Define Documentation

#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: [in]  elem  A pointer to a link_elem_t. Returns: An unsigned long containing the flags associated with the element. Definition at line 1003 of file dbprim.h.

#define le_head (  elem   )

This macro retrieves a pointer to the head of the linked list that the element is in. Parameters: [in]  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. Definition at line 990 of file dbprim.h.

#define le_next (  elem   )

This macro retrieves a pointer to the next element in the linked list. Parameters: [in]  elem  A pointer to a link_elem_t. Returns: A pointer to a link_elem_t representing the next element in the linked list. Definition at line 950 of file dbprim.h. Referenced by ht_find(), and ht_iter().

#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: [in]  elem  A pointer to a link_elem_t. Returns: A pointer to void representing the object associated with the linked list element. Definition at line 977 of file dbprim.h. Referenced by _sh_flush_iter(), _sh_iter_iter(), _smat_alloc(), _smat_free(), ht_add(), ht_find(), ht_flush(), ht_iter(), ht_resize(), sh_find(), and smat_cleanup().

#define le_prev (  elem   )

This macro retrieves a pointer to the previous element in the linked list. Parameters: [in]  elem  A pointer to a link_elem_t. Returns: A pointer to a link_elem_t representing the previous element in the linked list. Definition at line 963 of file dbprim.h.

#define le_verify (  element   )

This macro verifies that a given pointer actually does point to a linked list element. Warning: This macro evaluates the element argument twice. Parameters: [in]  element  A pointer to a link_elem_t. Returns: Boolean true if element is a valid linked list element or false otherwise. Definition at line 936 of file dbprim.h. Referenced by ll_add(), ll_find(), ll_iter(), ll_move(), and ll_remove().

#define LINK_ELEM_INIT (  obj   )

This macro statically initializes a link_elem_t. Parameters: [in]  obj  A pointer to void representing the object associated with the element. Definition at line 921 of file dbprim.h.

#define LINK_ELEM_MAGIC

For internal use only. This is the magic number used for the linked list element structure. Definition at line 911 of file dbprim.h. Referenced by le_init().

#define LINK_HEAD_INIT (  extra   )

This macro statically initializes a link_head_t. Parameters: [in]  extra  Extra pointer data that should be associated with the list head. Definition at line 661 of file dbprim.h.

#define LINK_HEAD_MAGIC

For internal use only. This is the magic number used for the linked list head structure. Definition at line 651 of file dbprim.h. Referenced by ll_init().

#define ll_count (  list   )

This macro retrieves the number of elements in a linked list. Parameters: [in]  list  A pointer to a link_head_t. Returns: An unsigned long containing a count of the number of elements in the linked list. Definition at line 689 of file dbprim.h. Referenced by _smat_alloc(), and smat_freemem().

#define ll_extra (  list   )

This macro retrieves the extra pointer data associated with a particular linked list. Parameters: [in]  list  A pointer to a link_head_t. Returns: A pointer to void. Definition at line 723 of file dbprim.h.

#define ll_first (  list   )

This macro retrieves the first element in a linked list. Parameters: [in]  list  A pointer to a link_head_t. Returns: A pointer to a link_elem_t. Definition at line 700 of file dbprim.h. Referenced by _smat_alloc(), ht_find(), ht_flush(), ht_iter(), ht_resize(), and smat_cleanup().

#define ll_last (  list   )

This macro retrieves the last element in a linked list. Parameters: [in]  list  A pointer to a link_head_t. Returns: A pointer to a link_elem_t. Definition at line 711 of file dbprim.h.

#define ll_verify (  list   )

This macro verifies that a given pointer actually does point to a linked list head. Warning: This macro evaluates the list argument twice. Parameters: [in]  list  A pointer to a link_head_t. Returns: Boolean true if list is a valid linked list head or false otherwise. Definition at line 676 of file dbprim.h. Referenced by ll_add(), ll_find(), ll_flush(), ll_iter(), ll_move(), and ll_remove().

---

Typedef Documentation

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

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. Parameters: [in]  key  The database key being searched for. [in]  obj  The object to compare with the key. Returns: Zero if key matches obj, non-zero otherwise. Definition at line 357 of file dbprim.h.

typedef struct _link_elem_s link_elem_t

This structure represents a single element of a linked list. Definition at line 269 of file dbprim.h.

typedef struct _link_head_s link_head_t

This structure is the head of all linked lists maintained by this library. Definition at line 262 of file dbprim.h.

typedef unsigned long(* link_iter_t)(link_head_t *list, link_elem_t *elem, void *extra)

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. Parameters: [in]  head  A pointer to a link_head_t. [in]  elem  A pointer to the link_elem_t being considered. [in]  extra  A void pointer passed to ll_iter() or ll_flush(). Returns: Zero for success, or non-zero to terminate the iteration. Definition at line 342 of file dbprim.h.

typedef enum _link_loc_e link_loc_t

See the documentation for the enumeration _link_loc_e. Definition at line 537 of file dbprim.h.

---

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. Enumerator: 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. Definition at line 523 of file dbprim.h.

---

Function Documentation

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

This function dynamically initializes a linked list element. Parameters: [in]  elem  A pointer to a link_elem_t to be initialized. [in]  object  A pointer to void used to represent the object associated with the element. Return values: DB_ERR_BADARGS  A NULL pointer was passed for elem or object. Definition at line 34 of file le_init.c. References _link_elem_s::le_flags, _link_elem_s::le_head, _link_elem_s::le_magic, _link_elem_s::le_next, _link_elem_s::le_object, _link_elem_s::le_prev, and LINK_ELEM_MAGIC. Referenced by _smat_alloc(), and he_init().

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: [in]  list  A pointer to a link_head_t. [in]  new  A pointer to the link_elem_t to be added to the linked list. [in]  loc  A link_loc_t indicating where the entry should be added. [in]  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. Definition at line 34 of file ll_add.c. References _link_elem_s::le_head, _link_elem_s::le_next, _link_elem_s::le_prev, le_verify, _link_head_s::lh_count, _link_head_s::lh_first, _link_head_s::lh_last, LINK_LOC_AFTER, LINK_LOC_BEFORE, LINK_LOC_HEAD, LINK_LOC_TAIL, and ll_verify. Referenced by _smat_free(), ht_add(), ht_move(), ht_resize(), and st_add().

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: [in]  list  A pointer to a link_head_t. [out]  elem_p  A pointer to a pointer to a link_elem_t. NULL is an invalid value. [in]  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. [in]  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. [in]  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. Definition at line 34 of file ll_find.c. References _link_elem_s::le_head, _link_elem_s::le_next, _link_elem_s::le_object, le_verify, _link_head_s::lh_first, and ll_verify. Referenced by sh_find().

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: [in]  list  A pointer to a link_head_t. [in]  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. [in]  extra  A void pointer that will be passed to flush_func. Return values: DB_ERR_BADARGS  An argument was invalid. Definition at line 34 of file ll_flush.c. References _link_head_s::lh_count, _link_head_s::lh_first, _link_head_s::lh_last, ll_remove(), and ll_verify. Referenced by sh_flush(). Here is the call graph for this function:

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

This function dynamically initializes a linked list head. Parameters: [in]  list  A pointer to a link_head_t to be initialized. [in]  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. Definition at line 34 of file ll_init.c. References _link_head_s::lh_count, _link_head_s::lh_extra, _link_head_s::lh_first, _link_head_s::lh_last, _link_head_s::lh_magic, and LINK_HEAD_MAGIC. Referenced by ht_init(), ht_resize(), and sh_init().

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

This function iterates over a linked list, executing the given iter_func for each entry. Parameters: [in]  list  A pointer to a link_head_t. [in]  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. [in]  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. [in]  extra  A void pointer that will be passed to iter_func. [in]  flags  If DB_FLAG_REVERSE is given, iteration will be done from the end of the list backwards towards the head. Return values: DB_ERR_BADARGS  An argument was invalid. DB_ERR_WRONGTABLE  start is not in this linked list. Definition at line 34 of file ll_iter.c. References DB_FLAG_REVERSE, _link_elem_s::le_head, _link_elem_s::le_next, _link_elem_s::le_prev, le_verify, _link_head_s::lh_first, _link_head_s::lh_last, and ll_verify. Referenced by sh_iter().

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: [in]  list  A pointer to a link_head_t. [in]  elem  A pointer to the link_elem_t describing the element to be moved. [in]  loc  A link_loc_t indicating where the entry should be moved to. [in]  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  new and elem are the same element. DB_ERR_WRONGTABLE  new or elem are in a different list. DB_ERR_UNUSED  new or elem are not in any list. Definition at line 35 of file ll_move.c. References _link_elem_s::le_head, _link_elem_s::le_next, _link_elem_s::le_prev, le_verify, _link_head_s::lh_first, _link_head_s::lh_last, LINK_LOC_AFTER, LINK_LOC_BEFORE, LINK_LOC_HEAD, LINK_LOC_TAIL, and ll_verify. Referenced by sh_move().

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

This function removes a specified element from a linked list. Parameters: [in]  list  A pointer to a link_head_t. [in]  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. Definition at line 34 of file ll_remove.c. References _link_elem_s::le_head, _link_elem_s::le_next, _link_elem_s::le_prev, le_verify, _link_head_s::lh_count, _link_head_s::lh_first, _link_head_s::lh_last, and ll_verify. Referenced by _smat_alloc(), _st_remove(), ht_move(), ht_remove(), ht_resize(), ll_flush(), smat_cleanup(), and st_add().

---