plibsys
Classes | Typedefs | Functions
plist.h File Reference

Singly linked list. More...

#include <pmacros.h>
#include <ptypes.h>
Include dependency graph for plist.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

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

Typedefs

typedef typedefP_BEGIN_DECLS struct PList_ PList
 Typedef for a list node. More...
 

Functions

P_LIB_API PListp_list_append (PList *list, ppointer data) P_GNUC_WARN_UNUSED_RESULT
 Appends data to a list. More...
 
P_LIB_API PListp_list_remove (PList *list, ppointer data) P_GNUC_WARN_UNUSED_RESULT
 Removes data from a list. More...
 
P_LIB_API void p_list_foreach (PList *list, PFunc func, ppointer user_data)
 Calls a specified function for each list node. More...
 
P_LIB_API void p_list_free (PList *list)
 Frees list memory. More...
 
P_LIB_API PListp_list_last (PList *list)
 Gets the last node from the list. More...
 
P_LIB_API psize p_list_length (const PList *list)
 Gets the number of list nodes. More...
 
P_LIB_API PListp_list_prepend (PList *list, ppointer data) P_GNUC_WARN_UNUSED_RESULT
 Prepends data to a list. More...
 
P_LIB_API PListp_list_reverse (PList *list) P_GNUC_WARN_UNUSED_RESULT
 Reverses the list order. More...
 

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.

Typedef Documentation

◆ PList

typedef typedefP_BEGIN_DECLS struct PList_ PList

Typedef for a list node.

Function Documentation

◆ p_list_append()

P_LIB_API PList* p_list_append ( PList list,
ppointer  data 
)

Appends data to a list.

Parameters
listPList for appending the data.
dataData 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
listList to go through.
funcPointer for the callback function.
user_dataUser 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
listList 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
listList 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
listList 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
listPList for prepending the data.
dataData 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,
ppointer  data 
)

Removes data from a list.

Parameters
listList to remove the data from.
dataData 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
listPList to reverse the order.
Returns
Pointer to the top of the reversed list.
Since
0.0.1