r6.1.0:lfds610_slist

Source Files

/liblfds610/src/lfds610_slist/lfds610_slist_delete.c
/liblfds610/src/lfds610_slist/lfds610_slist_get_and_set.c
/liblfds610/src/lfds610_slist/lfds610_slist_link.c
/liblfds610/src/lfds610_slist/lfds610_slist_new.c
/liblfds610/src/lfds610_slist/lfds610_slist_internal.h
/liblfds610/inc/liblfds610.h

Incomplete Types

struct lfds610_slist_state;
struct lfds610_slist_element;

Prototypes

int lfds610_slist_new( struct lfds610_slist_state **ss,
                       void (*user_data_delete_function)(void *user_data, void *user_state),
                       void *user_state );
void lfds610_slist_use( struct lfds610_slist_state *ss );
void lfds610_slist_delete( struct lfds610_slist_state *ss );

struct lfds610_slist_element *lfds610_slist_new_head( struct lfds610_slist_state *ss, void *user_data );
struct lfds610_slist_element *lfds610_slist_new_next( struct lfds610_slist_element *se, void *user_data );

int lfds610_slist_logically_delete_element( struct lfds610_slist_state *ss, struct lfds610_slist_element *se );
void lfds610_slist_single_threaded_physically_delete_all_elements( struct lfds610_slist_state *ss );

int lfds610_slist_get_user_data_from_element( struct lfds610_slist_element *se, void **user_data );
int lfds610_slist_set_user_data_in_element( struct lfds610_slist_element *se, void *user_data );

struct lfds610_slist_element *lfds610_slist_get_head( struct lfds610_slist_state *ss, struct lfds610_slist_element **se );
struct lfds610_slist_element *lfds610_slist_get_next( struct lfds610_slist_element *se, struct lfds610_slist_element *next_se );
struct lfds610_slist_element *lfds610_slist_get_head_and_then_next( struct lfds610_slist_state *ss, struct lfds610_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 lfds610_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 lfds610_slist_get_next on a logically deleted element). Elements are only actually freed when the list is deleted or when the lfds610_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 lfds610_slist_new function. The caller then uses the list by adding or deleting elements, or by traversing the list, via the lfds610_slist_new_head, lfds610_slist_new_next and lfds610_slist_delete_element functions for adding and deleting and the lfds610_slist_get_head, lfds610_slist_get_next and lfds610_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 lfds610_slist_get_user_data_from_element and lfds610_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 lfds610_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.