plist.h File Reference

Singly linked list. More...

#include <pmacros.h>
#include <ptypes.h>

Go to the source code of this file.

Data Structures
struct	PList_
	Node for a singly linked list. More...

Typedefs
typedef struct PList_	PList
	Typedef for a list node.

Functions
P_LIB_API PList *	p_list_append (PList *list, ppointer data) P_GNUC_WARN_UNUSED_RESULT
	Appends data to a list.
P_LIB_API PList *	p_list_remove (PList *list, pconstpointer data) P_GNUC_WARN_UNUSED_RESULT
	Removes data from a list.
P_LIB_API void	p_list_foreach (PList *list, PFunc func, ppointer user_data)
	Calls a specified function for each list node.
P_LIB_API void	p_list_free (PList *list)
	Frees list memory.
P_LIB_API PList *	p_list_last (PList *list)
	Gets the last node from the list.
P_LIB_API psize	p_list_length (const PList *list)
	Gets the number of list nodes.
P_LIB_API PList *	p_list_prepend (PList *list, ppointer data) P_GNUC_WARN_UNUSED_RESULT
	Prepends data to a list.
P_LIB_API PList *	p_list_reverse (PList *list) P_GNUC_WARN_UNUSED_RESULT
	Reverses the list order.

Detailed Description

Singly linked list.

Author

Alexander Saprykin

A singly linked list is a data structure consists of the nodes which represent a sequence. Each node contains a data pointer and a pointer to the next node. Every node has a link only to the next node, hence list is a singly linked (in a single direction).

As the singly linked list is a linear collection of the nodes with the sequential access, it has an O(N) average complexity for appending, removing and searching operations. Prepending a node takes O(1) constant time. Thus it is not intended for heavy usage, please refer to PHashTable or PTree if you are working with large data sets.

Before the first usage you must initialize a PList variable to NULL. After that you can use the p_list_append(), p_list_prepend(), p_list_remove() and p_list_reverse() routines to update that variable:

PList       *list;
ppointer    data;
 
list = NULL;
data = my_obj_new ();
 
list = p_list_append (list, data);

PList stores only the pointers to the data, so you must free used memory manually, p_list_free() only frees list's internal memory, not the data it stores the pointers for. The best approach to free used memory is the p_list_foreach() routine:

PList    *list;
...
p_list_foreach (list, (PFunc) my_free_func, my_data);
p_list_free (list);

Also you can use P_INT_TO_POINTER and P_POINTER_TO_INT macros to store integers (up to 32-bit) without allocating memory for them:

PList    *list;
pint     a;
 
list = p_list_append (list, P_INT_TO_POINTER (12));
a = P_POINTER_TO_INT (list->data);

PList can store several nodes with the same pointer value, but p_list_remove() will remove only the first matching node.

If you need to add large amount of nodes at once it is better to prepend them and then reverse the list.

Definition in file plist.h.

Typedef Documentation

PList

typedef struct PList_ PList

Typedef for a list node.

Definition at line 93 of file plist.h.

Function Documentation

p_list_append()

P_LIB_API PList * p_list_append	(	PList *	list,
		ppointer	data )

Appends data to a list.

Parameters

list	PList for appending the data.
data	Data to append.

Returns

Pointer to the updated list in case of success, list otherwise.

Since

0.0.1

Before appending the first node to the list, list argument must be initialized with NULL. Otherwise behavior is unpredictable.

p_list_foreach()

P_LIB_API void p_list_foreach	(	PList *	list,
		PFunc	func,
		ppointer	user_data )

Calls a specified function for each list node.

Parameters

list	List to go through.
func	Pointer for the callback function.
user_data	User defined data, may be NULL.

Since

0.0.1

This function goes through the whole list and calls func for each node. The func will receive pointer to the node's data and user_data. You can use it to free the data:

p_list_foreach (list, (PFunc) free, NULL);
p_list_free (list);

p_list_free()

P_LIB_API void p_list_free

(

PList *

list

)

Frees list memory.

Parameters

list	List to free.

Since

0.0.1

This function frees only the list's internal memory, not the data in the pointers stored in the nodes. Don't forget to free all the data stored in the list manually.

p_list_last()

P_LIB_API PList * p_list_last

(

PList *

list

)

Gets the last node from the list.

Parameters

list	List to get the node from.

Returns

Pointer to the last list node, NULL if the list is empty.

Since

0.0.1

p_list_length()

P_LIB_API psize p_list_length

(

const PList *

list

)

Gets the number of list nodes.

Parameters

list	List to count nodes in.

Returns

Number of nodes in the list.

Since

0.0.1

Note

This function will iterate through the whole list, so don't use it in condition of the for-loop or in the code which is repeated a lot of times.

p_list_prepend()

P_LIB_API PList * p_list_prepend	(	PList *	list,
		ppointer	data )

Prepends data to a list.

Parameters

list	PList for prepending the data.
data	Data to prepend.

Returns

Pointer to the updated list in case of success, list otherwise.

Since

0.0.1

Before prepending the first node to the list, list argument must be initialized with NULL. Otherwise behavior is unpredictable.

p_list_remove()

P_LIB_API PList * p_list_remove	(	PList *	list,
		pconstpointer	data )

Removes data from a list.

Parameters

list	List to remove the data from.
data	Data to remove.

Returns

Pointer to the updated list in case of success, list otherwise.

Since

0.0.1

It searches for the first matching occurrence in the list and removes that node. Note that it removes only the pointer from the list, not the data it pointers to, so you need to free the data manually.

p_list_reverse()

P_LIB_API PList * p_list_reverse

(

PList *

list

)

Reverses the list order.

Parameters

list	PList to reverse the order.

Returns

Pointer to the top of the reversed list.

Since

0.0.1