List (add-only, singly-linked, unordered)
Source Files
└───liblfds711
├───inc
│ └───liblfds711
│ lfds711_list_addonly_singlylinked_unordered.h
└───src
└───lfds711_list_addonly_singlylinked_unordered
lfds711_list_addonly_singlylinked_unordered_cleanup.c
lfds711_list_addonly_singlylinked_unordered_get.c
lfds711_list_addonly_singlylinked_unordered_init.c
lfds711_list_addonly_singlylinked_unordered_insert.c
lfds711_list_addonly_singlylinked_unordered_internal.h
lfds711_list_addonly_singlylinked_unordered_query.c
Enums
enum lfds711_list_asu_position; enum lfds711_list_asu_query;
Opaque Structures
struct lfds711_list_asu_element; struct lfds711_list_asu_state;
Macros
#define LFDS711_LIST_ASU_GET_START( list_asu_state ) #define LFDS711_LIST_ASU_GET_NEXT( list_asu_element ) #define LFDS711_LIST_ASU_GET_START_AND_THEN_NEXT( list_asu_state, pointer_to_list_asu_element ) #define LFDS711_LIST_ASU_GET_KEY_FROM_ELEMENT( list_asu_element ) #define LFDS711_LIST_ASU_SET_KEY_IN_ELEMENT( list_asu_element, new_key ) #define LFDS711_LIST_ASU_GET_VALUE_FROM_ELEMENT( list_asu_element ) #define LFDS711_LIST_ASU_SET_VALUE_IN_ELEMENT( list_asu_element, new_value ) #define LFDS711_LIST_ASU_GET_USER_STATE_FROM_STATE( list_asu_state )
Prototypes
void lfds711_list_asu_init_valid_on_current_logical_core( struct lfds711_list_asu_state *lasus, void *user_state ); void lfds711_list_asu_cleanup( struct lfds711_list_asu_state *lasus, void (*element_cleanup_callback)(struct lfds711_list_asu_state *lasus, struct lfds711_list_asu_element *lasue); void lfds711_list_asu_insert_at_position( struct lfds711_list_asu_state *lasus, struct lfds711_list_asu_element *lasue, struct lfds711_list_asu_element *lasue_predecessor, enum lfds711_list_asu_position position ); void lfds711_list_asu_insert_at_start( struct lfds711_list_asu_state *lasus, struct lfds711_list_asu_element *lasue ); void lfds711_list_asu_insert_at_end( struct lfds711_list_asu_state *lasus, struct lfds711_list_asu_element *lasue ; void lfds711_list_asu_insert_after( struct lfds711_list_asu_state *lasus, struct lfds711_list_asu_element *lasue, struct lfds711_list_asu_element *lasue_predecessor ); int lfds711_list_asu_get_by_key( struct lfds711_list_asu_state *lasus, int (*key_compare_function)(void const *new_key, void const *existing_key), void *key, struct lfds711_list_asu_element **lasue ); void lfds711_list_asu_query( struct lfds711_list_asu_state *lasus, enum lfds711_list_asu_query query_type, void *query_input, void *query_output );
Overview
This data structure implements an add-only, singly-linked, unordered list. It supports any number of concurrent users, and internally implements exponential backoff to help deal with high load and so improve scalability.
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.
General usage is that the user calls lfds711_list_asu_init_valid_on_current_logical_core to initialize a struct lfds711_list_asu_state, and then calls the lfds711_list_aos_insert* functions to add elements to the list and uses the various macros, such as LFDS711_LIST_ASU_GET_START and LFDS711_LIST_ASU_GET_NEXT to iterate over the list. A convenience function is provided, lfds711_list_aos_get_by_key, to search by key, but remember the list is unordered.
(See the section below, on lock-free specific behaviour, for an explanation of the unusual init function name.)
A list element provides the ability to store a key and a value, both of which are of type void *. The key is used for list ordering. The key and value are get and set by macros, such as LFDS711_LIST_ASU_SET_VALUE_IN_ELEMENT. The key can only be set in elements before they are added to a tree. The value can be set at any time, in elements both inside and outside of the list.
The state and element structures are both public, present in the lfds711_list_addonly_singlylinked_unordered.h header file, so that users can embed them in their own structures (and where necessary pass them to sizeof). Expected use is that user structures which are to enter lists contain within themselves a struct lfds711_list_aos_element, and this is used when calling lfds711_list_aos_insert* functions. This approach permits zero run-time allocation of store and also ensures the stack element is normally in the same memory page as the user data it refers to.
The list maintains, as best it can, a pointer to the last element, so linking to the end of the list is typically efficient. Note we say here "as best it can" and "typically"; the pointer to the last element is not updated atomically with the linking of a new end element, so it is possible for the end pointer to be out of place. When any code comes to use the end pointer, it moves the end pointer to the correct position before using it. (To be more precise, such code loops, attempting to move the end point to the correct position before using it, where the attempt to use it will fail if more elements have in the meantime been added to the end of the list).
Lock-free Specific Behaviour
The state initialization function, lfds711_list_asu_init_valid_on_current_logical_core, as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE, which will do that which its name suggests.
The SET macro for the key in an element can only be correctly used on elements which are outside of a list. The SET macro for the value in an element can be used at any time, on any element. By correctly is it meant to say that the GET macros will actually read the data written by the SET macros, and not some other data. I don't have to tell you how much chaos will ensure if different logical cores are reading different keys for the same element...
If shared memory is used for allocations, the virtual addresses must be the same across different processes.
White Paper
There is no white paper for this data structure; it is native to liblfds.
License
Standard liblfds license - there is no license. You are free to use this code in any way. Go forth and create wealth!
If however for legal reasons a licence is required, the license of your choice will be granted, and license for convenience is hereby granted up front for a range of popular licenses : the MIT license, the BSD license, the Apache license, the GPL and LPGL (all versions thereof) and the Creative Commons licenses (all of them). Additionally, this library (which is to say, the source code, build files, documentation, everything) is placed in the public domain.
Example
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "liblfds711.h"
struct test_data
{
struct lfds711_list_asu_element
lasue;
char
name[64];
};
int main()
{
struct test_data
*first_td,
*middle_td,
*last_td,
*td;
struct lfds711_list_asu_element
*lasue;
struct lfds711_list_asu_state
lasus;
lfds711_list_asu_init_valid_on_current_logical_core( &lasus, NULL );
// TRD : insert a few elements
first_td = malloc( sizeof(struct test_data) );
stcpy( first_td->name, "First element" );
LFDS711_LIST_ASU_SET_VALUE_IN_ELEMENT( first_td->lasue, first_td );
lfds711_list_asu_insert_at_start( &lasus, &first_td->lasue );
last_id = malloc( sizeof(struct test_data) );
stcpy( last_td->name, "Last element" );
LFDS711_LIST_ASU_SET_VALUE_IN_ELEMENT( last_td->lasue, last_td );
lfds711_list_asu_insert_at_end( &lasus, &last_td->lasue );
middle_td = malloc( sizeof(struct test_data) );
stcpy( middle_td->name, "Middle element" );
LFDS711_LIST_ASU_SET_VALUE_IN_ELEMENT( middle_td->lasue, middle_td );
lfds711_list_asu_insert_after_element( &lasus, &middle_td->lasue, &first_td->lasue );
// TRD : iterate over the list
lasue = NULL;
while( LFDS711_LIST_ASU_GET_START_AND_THEN_NEXT(&lasus,lasue) )
{
td = LFDS711_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
printf( "element name = %s\n", td->name );
}
lfds711_list_asu_cleanup( &lasus, NULL );
free( first_td );
free( middle_td );
free( last_td );
return( EXIT_SUCCESS );
}