List (add-only, ordered, singly-linked)

Source Files

└---liblfds700
    ├───inc
    │   └───liblfds700
    │           lfds700_list_addonly_ordered_singlylinked.h
    └───src
        └───lfds700_addonly_ordered_singlylinked_list
                lfds700_list_addonly_ordered_singlylinked_cleanup.c
                lfds700_list_addonly_ordered_singlylinked_get.c
                lfds700_list_addonly_ordered_singlylinked_init.c
                lfds700_list_addonly_ordered_singlylinked_insert.c
                lfds700_list_addonly_ordered_singlylinked_internal.h
                lfds700_list_addonly_ordered_singlylinked_query.c

Enums

enum lfds700_list_aos_existing_key
{
  LFDS700_LIST_AOS_EXISTING_KEY_OVERWRITE,
  LFDS700_LIST_AOS_EXISTING_KEY_FAIL
};

enum lfds700_list_aos_insert_result
{
  LFDS700_LIST_AOS_INSERT_RESULT_FAILURE_EXISTING_KEY,
  LFDS700_LIST_AOS_INSERT_RESULT_SUCCESS_OVERWRITE,
  LFDS700_LIST_AOS_INSERT_RESULT_SUCCESS
};

enum lfds700_list_aos_query
{
  LFDS700_LIST_AOS_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
  LFDS700_LIST_AOS_QUERY_SINGLETHREADED_VALIDATE
};

Opaque Structures

struct lfds700_list_aos_element;
struct lfds700_list_aos_state;
struct lfds700_misc_prng_state;

Macros

#define LFDS700_LIST_AOS_GET_START( list_aos_state )
#define LFDS700_LIST_AOS_GET_NEXT( list_aos_element )
#define LFDS700_LIST_AOS_GET_START_AND_THEN_NEXT( list_aos_state, pointer_to_list_aos_element )

#define LFDS700_LIST_AOS_GET_KEY_FROM_ELEMENT( list_aos_element )
#define LFDS700_LIST_AOS_SET_KEY_IN_ELEMENT( list_aos_element, new_key )

#define LFDS700_LIST_AOS_GET_VALUE_FROM_ELEMENT( list_aos_element )
#define LFDS700_LIST_AOS_SET_VALUE_IN_ELEMENT( list_aos_element, new_value )

#define LFDS700_LIST_AOS_GET_USER_STATE_FROM_STATE( list_aos_state )

Prototypes

void lfds700_list_aos_init_valid_on_current_logical_core( struct lfds700_list_aos_state *laoss,
                                                          int (*key_compare_function)(void const *new_key, void const *existing_key),
                                                          enum lfds700_list_aos_existing_key existing_key,
                                                          void *user_state );

void lfds700_list_aos_cleanup( struct lfds700_list_aos_state *laoss,
                               void (*element_cleanup_callback)(struct lfds700_list_aos_state *laoss, struct lfds700_list_aos_element *laose) );

enum lfds700_list_aos_insert_result lfds700_list_aos_insert( struct lfds700_list_aos_state *laoss,
                                                             struct lfds700_list_aos_element *laose,
                                                             struct lfds700_list_aos_element **existing_laose,
                                                             struct lfds700_misc_prng_state *ps );

int lfds700_list_aos_get_by_key( struct lfds700_list_aos_state *laoss,
                                 void *key,
                                 struct lfds700_list_aos_element **laose );

void lfds700_list_aos_query( struct lfds700_list_aos_state *laoss,
                             enum lfds700_list_aos_query query_type,
                             void *query_input,
                             void *query_output );

Overview

This data structure implements an add-only, ordered, singly-linked 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 lfds700_list_aos_init_valid_on_current_logical_core to initialize a struct lfds700_list_aos_state, and then calls lfds700_list_aos_insert to add elements to the list and lfds700_list_aos_get_by_key to find elements in the list.

(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 LFDS700_LIST_AOS_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 lfds700_list_addonly_ordered_singlylinked.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 lfds700_list_aos_element, and this is used when calling lfds700_list_aos_insert. 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.

Lock-free Specific Behaviour

The state initialization function, lfds700_list_aos_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 LFDS700_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 struct lfds700_misc_prng_state argument is the state for a single-threaded, fast, high quality random number generator, required by the exponential backoff code. Each thread should allocate and initialize one of these structures, and then it can be used for all API calls which take this argument.

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.

Example

Coming soon. No, really! (Written 29th Dec 2015).