list.h File Reference

#include "core.h"
#include "list_impl.h"

Include dependency graph for list.h:

Go to the source code of this file.

Functions
void	list_create (list_t *, size_t, size_t)
void	list_destroy (list_t *)
void	list_insert_after (list_t *, void *, void *)
void	list_insert_before (list_t *, void *, void *)
void	list_insert_head (list_t *, void *)
void	list_insert_tail (list_t *, void *)
void	list_remove (list_t *, void *)
void *	list_remove_head (list_t *)
void *	list_remove_tail (list_t *)
void	list_move_tail (list_t *, list_t *)
void *	list_head (const list_t *)
void *	list_tail (const list_t *)
void *	list_next (const list_t *, const void *)
void *	list_prev (const list_t *, const void *)
void *	list_get_i (const list_t *, size_t)
int	list_is_empty (const list_t *)
void	list_link_init (list_node_t *)
void	list_link_replace (list_node_t *, list_node_t *)
int	list_link_active (const list_node_t *)
size_t	list_count (const list_t *)

Detailed Description

This is a general-purpose doubly-linked list system. It is designed to be easy to integrate into pre-existing data structures and has many functions to manipulate and examine the linked list.

See also

list_t

list_create()

Definition in file list.h.

Function Documentation

list_count()

size_t list_count

(

const list_t *

list

)

Returns

The number of items in the list.

Definition at line 543 of file list.c.

list_create()

void list_create	(	list_t *	list,
		size_t	size,
		size_t	offset
	)

Initializes a new linked list. This must be called before a list_t is used. When you are done with the linked list, you must deinitialize it using list_destroy().

Data structures to be held in the linked list must have a list_node_t field added to them. This is where the linked list will keep its lists node references. If you want to hold an object in more than one linked list, you will need a separate list_node_t for each linked list. A single list_node_t cannot be shared at the same time between multiple lists.

Parameters

list	The linked list to be initialized.
size	The size in bytes of the objects to be referenced in the linked list. This is mostly meant for error-checking for the placement of the list node.
offset	Offset within the data structures that will be contained in the list_t to where the list_node_t field is. You should use the standard offsetof() for this purpose.

Example:

typedef struct {
   int         foo;
   float       bar;
   list_node_t node;
} my_data_t;
 
// initializing a list_t to contain my_data_t structures:
list_t my_list;
list_create(&my_list, sizeof (my_data_t), offsetof(my_data_t, node));

See also

list_destroy()

Definition at line 113 of file list.c.

list_destroy()

void list_destroy

(

list_t *

list

)

Destroys a list_t structure which was previously initialized using list_create(). The list MUST be empty before this is done, otherwise an assertion failure is tripped.

Note

This doesn't call free() on the data structure. It simply cleans it up and frees any internal resources. If you allocated the list_t previously using malloc() or similar, you must free() the data yourself.

Definition at line 136 of file list.c.

list_get_i()

void * list_get_i	(	const list_t *	list,
		size_t	i
	)

Performs an iterative search through the list to retrieve a particular element in the list in order.

Note

This is an expensive operation, as it performs an O(n) search (iterating through the list), which can take long on very large lists. If you need frequent random access to items in large lists, you should consider using a simple array instead of a linked list.

Parameters

i	The index of the item in the list (counting from 0). This must be less than the total number of items in the list as returned by list_count().

Returns

The i'th object inside of the list.

Definition at line 412 of file list.c.

list_head()

void * list_head

(

const list_t *

list

)

Returns

The first object in the list. If the list is empty, returns NULL instead.

Definition at line 292 of file list.c.

list_insert_after()

void list_insert_after	(	list_t *	list,
		void *	object,
		void *	nobject
	)

Inserts a new object immediately after another object into a linked list.

Parameters

list	The list into which the insert will be performed.
object	The preceding object, after which the new object will be inserted.
nobject	The new object being inserted. It will be inserted immediately following object.

Note

The new object being inserted must NOT already be a member of this list.

Definition at line 159 of file list.c.

list_insert_before()

void list_insert_before	(	list_t *	list,
		void *	object,
		void *	nobject
	)

Inserts a new object immediately in front of another object into a linked list.

Parameters

list	The list into which the insert will be performed.
object	The following object, in front of which the new object will be inserted.
nobject	The new object being inserted. It will be inserted immediately in front of object.

Note

The new object being inserted must NOT already be a member of this list.

Definition at line 181 of file list.c.

list_insert_head()

void list_insert_head	(	list_t *	list,
		void *	object
	)

Inserts an object at the head (start) of a linked list.

Parameters

list	The list into which the insert will be performed.
object	The object to be inserted at the head of the list.

Note

The new object being inserted must NOT already be a member of this list.

Definition at line 199 of file list.c.

list_insert_tail()

void list_insert_tail	(	list_t *	list,
		void *	object
	)

Inserts an object at the tail (end) of a linked list.

Parameters

list	The list into which the insert will be performed.
object	The object to be inserted at the head of the list.

Note

The new object being inserted must NOT already be a member of this list.

Definition at line 213 of file list.c.

list_is_empty()

int list_is_empty

(

const list_t *

list

)

Returns

True if the list is empty, otherwise false.

Definition at line 534 of file list.c.

list_link_active()

int list_link_active

(

const list_node_t *

link

)

Returns

True if the given list_node_t is active, i.e. the object containing the node is currently part of a list.

See also

For this function to work properly, the object containing the list_node_t must either have been pre-initialized to all zeros during allocation, or you have explicitly initialized the list_node_t itself using list_link_init().

Definition at line 525 of file list.c.

list_link_init()

void list_link_init

(

list_node_t *

link

)

Initializes a list_node_t so that subsequent calls to list_link_active() can determine the activity status of that node correctly. This is equivalent to just setting the contents of the node to NULL, so you can achieve the same effect of this function by simply allocating the structure containing the list_node_t using an allocation function which zeros out the memory contents during allocation (such as calloc()).

Definition at line 510 of file list.c.

list_link_replace()

void list_link_replace	(	list_node_t *	lold,
		list_node_t *	lnew
	)

Replaces an object in a linked list with another object, without the need to have a reference to the original list_t.

Parameters

lold	A pointer to the list_node_t of the old object, which is to be replaced by the new object. This object MUST be in a list (list_link_active() returns true).
lnew	A pointer to the list_node_t of the new object, which is to replace the old object. This object must NOT be in a list (list_link_active() returns false).

Note

The two objects must be of the same type and hold their list_node_t at the exact same offset within the parent structure. This function is NOT meant to replace one type of object with a different type of object within the same list.

Example

typedef struct {
   int         foo;
   float       bar;
   list_node_t node;
} my_data_t;
my_data_t *old_object;
[...]
// old_object gets placed into a list and we want to replace it
[...]
my_data_t *new_object;
list_link_replace(&old_object->node, &new_object->node);
// now old_object is no longer in its containing list and new_object
// took its place

Definition at line 489 of file list.c.

list_move_tail()

void list_move_tail	(	list_t *	dst,
		list_t *	src
	)

Transfers the contents of one list to another, by appending them. This is faster than moving items one by one, as it simply manipulates the list references for the first and last item. Thus this is a constant-time algorithm.

Parameters

dst	Destination list to which to append all items in src.
src	Source list, from which to append all items to the end of dst. Afterwards, the src list will be empty.

Definition at line 436 of file list.c.

list_next()

void * list_next	(	const list_t *	list,
		const void *	object
	)

Iterates through the list forward (towards the tail) by 1 object.

Parameters

list	The list being iterated.
object	The object from which the next object will be returned. This must not be NULL.

Returns

The next object following object in the second argument. If there are no more objects following object, returns NULL instead.

Example

Iterating through a list forwards:

for (my_data_t *data = list_head(&my_list); data != NULL;
    data = list_next(&my_list, data)) {
   // do something with data
}

Note

If you plan on removing items from the list while iterating through it, be careful to structure your for() loop correctly so as to avoid using a removed reference for the iteration. Grab the next item reference early, before potentially removing the current item:

for (my_data_t *data = list_head(&my_list), *next_data = NULL;
    data != NULL; data = next_data) {
   // grab next_data now, before we remove the current item
   next_data = list_next(&my_list, data);
   if (should_remove(data)) {
       // now we can safely remove the item from the list
       list_remove(&my_list, data);
   }
}

Definition at line 344 of file list.c.

list_prev()

void * list_prev	(	const list_t *	list,
		const void *	object
	)

Iterates through the list backward (towards the head) by 1 object.

Parameters

list	The list being iterated.
object	The object from which the previous object will be returned. This must not be NULL.

Returns

The nearest object preceding object in the second argument. If there are no more objects preceding object, returns NULL instead.

Example

Iterating through a list backwards:

for (my_data_t *data = list_tail(&my_list); data != NULL;
    data = list_prev(&my_list, data)) {
   // do something with data
}

Note

If you plan on removing items from the list while iterating through it, be careful to structure your for() loop correctly so as to avoid using a removed reference for the iteration. Grab the next item reference early, before potentially removing the current item:

for (my_data_t *data = list_tail(&my_list), *prev_data = NULL;
    data != NULL; data = prev_data) {
   // grab prev_data now, before we remove the current item
   prev_data = list_prev(&my_list, data);
   if (should_remove(data)) {
       // now we can safely remove the item from the list
       list_remove(&my_list, data);
   }
}

Definition at line 388 of file list.c.

list_remove()

void list_remove	(	list_t *	list,
		void *	object
	)

Removes an object from the list.

Parameters

list	The list from which the object is to be removed.
object	The object to be removed from the list.

Note

The object being removed must be a member of this list.

Definition at line 226 of file list.c.

list_remove_head()

void * list_remove_head

(

list_t *

list

)

Removes an object from the head (start) of the list.

Returns

The object which was removed from the head of the list. If the list was already empty, returns NULL instead.

Example

This function is commonly used to empty out a list by removing all members, like this:

my_data_t *data;
while ((data = list_remove_head(&my_list)) != NULL) {
   free(data);
}

Definition at line 251 of file list.c.

list_remove_tail()

void * list_remove_tail

(

list_t *

list

)

Removes an object from the tail (end) of the list.

Returns

The object which was removed from the tail of the list. If the list was already empty, returns NULL instead.

Example

This function is commonly used to empty out a list by removing all members, like this:

my_data_t *data;
while ((data = list_remove_tail(&my_list)) != NULL) {
   free(data);
}

Definition at line 277 of file list.c.

list_tail()

void * list_tail

(

const list_t *

list

)

Returns

The last object in the list. If the list is empty, returns NULL instead.

Definition at line 304 of file list.c.