r6:API:SList

Source Files

/src/slist/slist_delete.c
/src/slist/slist_get_and_set.c
/src/slist/slist_link.c
/src/slist/slist_new.c
/src/slist/slist_internal.h
/inc/liblfds.h

Incomplete Types

struct slist_state;
struct slist_element;

Prototypes

int slist_new( struct slist_state **ss,
               void (*user_data_delete_function)(void *user_data, void *user_state),
               void *user_state );
void slist_delete( struct slist_state *ss );

struct slist_element *slist_new_head( struct slist_state *ss, void *user_data );
struct slist_element *slist_new_next( struct slist_element *se, void *user_data );

void slist_delete_element( struct slist_state *ss, struct slist_element *se );
void slist_delete_all_elements( struct slist_state *ss );

int slist_get_user_data_from_element( struct slist_element *se, void **user_data );
int slist_set_user_data_in_element( struct slist_element *se, void *user_data );

struct slist_element *slist_get_head( struct slist_state *ss, struct slist_element **se );
struct slist_element *slist_get_next( struct slist_element *se, struct slist_element *next_se );
struct slist_element *slist_get_head_and_then_next( struct slist_state *ss, struct slist_element **se );

Overview

This API implements a singly linked list which does not support genuine delete, but only logical delete; when an element is deleted by the slist_delete_element function, it is logically deleted - all operations on the list will be as if the element was truly deleted - but not physically deleted, so it remains in the list and is not deallocated. (It is safe to call slist_get_next on a logically deleted element). Elements are only actually freed when the list is deleted or when the slist_delete_all_elements function is called and this latter function is not thread safe.

This API implements a singly linked list. A new list is instantiated by the slist_new function. The caller then uses the list by adding or deleting elements, or by traversing the list, via the slist_new_head, slist_new_next and slist_delete_element functions for adding and deleting and the slist_get_head, slist_get_next and slist_get_head_and_then_next functions for traversing. An add or delete will add or delete a single list element. Each traverse function returns a pointer to a list element. A list element contains a single void pointer of user data, which is read and written using the functions slist_get_user_data_from_element and slist_get_user_data_from_element, respectively. These void pointers are expected to point to user allocated state although of course they can be used directly to store a single value. Finally, the list is deleted using slist_delete.

Lock-free Specific Behaviour

It is not possible to actually delete individual elements, only to logically delete them. As such the list can only grow. The slist can be cleared, which does delete all elements.

Algorithm

The singly linked list algorithm is sufficiently obvious that I've implemented it from scratch. Valois (1995) describes a lock-free singly linked list which supports true delete. I will be implementing this, but it will take time and I need a singly linked list now (add-only being adequate), which is why this list is now available. Implementing Valois' list will I believe cause API changes since he uses cursors.