Queue (bounded, single consumer, single producer)

Source Files

└---liblfds700
    ├───inc
    │   └───liblfds700
    │           lfds700_queue_bounded_singleconsumer_singleproducer.h
    └───src
        └───lfds700_queue_bounded_singleconsumer_singleproducer
                lfds700_queue_bounded_singleconsumer_singleproducer_cleanup.c
                lfds700_queue_bounded_singleconsumer_singleproducer_dequeue.c
                lfds700_queue_bounded_singleconsumer_singleproducer_enqueue.c
                lfds700_queue_bounded_singleconsumer_singleproducer_init.c
                lfds700_queue_bounded_singleconsumer_singleproducer_internal.h
                lfds700_queue_bounded_singleconsumer_singleproducer_query.c

Enums

enum lfds700_queue_bss_query
{
  LFDS700_QUEUE_BSS_QUERY_GET_POTENTIALLY_INACCURATE_COUNT,
  LFDS700_QUEUE_BSS_QUERY_VALIDATE
};

Opaque Structures

struct lfds700_queue_bss_element;
struct lfds700_queue_bss_state;

Macros

#define LFDS700_QUEUE_BSS_GET_USER_STATE_FROM_STATE( queue_bbs_state )

Prototypes

void lfds700_queue_bss_init_valid_on_current_logical_core( struct lfds700_queue_bss_state *qbsss, 
                                                           struct lfds700_queue_bss_element *element_array,
                                                           lfds700_uint_t number_elements,
                                                           void *user_state );

void lfds700_queue_bss_cleanup( struct lfds700_queue_bss_state *qbsss,
                                void (*element_cleanup_callback)(struct lfds700_queue_bss_state *qbsss, void *key, void *value) );

int lfds700_queue_bss_enqueue( struct lfds700_queue_bss_state *qbsss,
                               void *key,
                               void *value );

int lfds700_queue_bss_dequeue( struct lfds700_queue_bss_state *qbsss,
                               void **key,
                               void **value );

void lfds700_queue_bss_query( struct lfds700_queue_bss_state *qbsss,
                              enum lfds700_queue_bss_query query_type,
                              void *query_input,
                              void *query_output );

Overview

This API implements a single producer, single consumer, bounded queue, where bounded means the maximum number of elements is set at init time and cannot later be changed.

The user passes to lfds700_queue_bss_init an array of struct lfds700_queue_bss_element which forms the store used for the queue. The caller is responsible for all memory allocation and deallocation.

The user is able to enqueue and dequeue a key and a value, both of which are void pointers. The key is not used in any way, and is available simply for convenience when moving key/value data pairs around a system.

Enqueuing only fails if the queue is full. Dequeuing only fails if the queue is empty.

The queue state structure is publicly visible so the caller can declare on the stack, use sizeof for memory allocation, and insert into his own structures.

Lock-free Specific Behaviour

The queue supports the concurrent operation of one reader thread and one writer thread. The reading thread can be any thread which runs on the same logical core that the first read occurred upon, and the same is true for the writing thread - any thread can write, so long as it is one thread at a time, and all the threads are running on the same logical core as the logical core used for the first write.

It may seem to work if this is not adhered to, but it's pure chance. Don't do it, it'll all end in tears.

(Note that the OS may in its wisdom move threads around, to other logical cores; this is okay - when this happes, the OS does extra magic to make sure everything continues to work as it should. In fact, this API could offer similar functions, to handover/pickup ownership of the read/write thread, but it's not been done).

It is not guaranteed that by the time lfds700_queue_bss_enqueue returns that the newly enqueued element will be dequeueable. There can be a delay, which in theory could be infinite, but in practise is typically on the order of tens of microseconds. The order of reads will however always match the order of writes - so it really is a queue (FIFO), not a random in-out mixer (RIRO :-)

White Paper

There is no white paper for this data structure. It is generally well-known and indeed is present in the Linux kernel.

Example

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