Queue (bounded, single consumer, single producer)

Source Files

└───liblfds711
    ├───inc
    │   └───liblfds711
    │           lfds711_queue_bounded_singleproducer_singleconsumer.h
    └───src
        └───lfds711_queue_bounded_singleproducer_singleconsumer
                lfds711_queue_bounded_singleproducer_singleconsumer_cleanup.c
                lfds711_queue_bounded_singleproducer_singleconsumer_dequeue.c
                lfds711_queue_bounded_singleproducer_singleconsumer_enqueue.c
                lfds711_queue_bounded_singleproducer_singleconsumer_init.c
                lfds711_queue_bounded_singleproducer_singleconsumer_internal.h
                lfds711_queue_bounded_singleproducer_singleconsumer_query.c

Enums

enum lfds711_queue_bss_query;

Opaque Structures

struct lfds711_queue_bss_element;
struct lfds711_queue_bss_state;

Macros

#define LFDS711_QUEUE_BSS_GET_USER_STATE_FROM_STATE( queue_bbs_state )

Prototypes

void lfds711_queue_bss_init_valid_on_current_logical_core( struct lfds711_queue_bss_state *qbsss, 
                                                           struct lfds711_queue_bss_element *element_array,
                                                           lfds711_uint_t number_elements,
                                                           void *user_state );

void lfds711_queue_bss_cleanup( struct lfds711_queue_bss_state *qbsss,
                                void (*element_cleanup_callback)(struct lfds711_queue_bss_state *qbsss, void *key, void *value) );

int lfds711_queue_bss_enqueue( struct lfds711_queue_bss_state *qbsss,
                               void *key,
                               void *value );

int lfds711_queue_bss_dequeue( struct lfds711_queue_bss_state *qbsss,
                               void **key,
                               void **value );

void lfds711_queue_bss_query( struct lfds711_queue_bss_state *qbsss,
                              enum lfds711_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 lfds711_queue_bss_init an array of struct lfds711_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 lfds711_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.

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 <string.h>
#include "liblfds711.h"

struct test_data
{
  char
    name[64];
};

int main()
{
  struct lfds711_queue_bss_element
    qbsse[10];

  struct lfds711_queue_bss_state
    qbsss;

  struct test_data
    td,
    *temp_td;

  lfds711_queue_bss_init_valid_on_current_logical_core( &qbsss, qbsse, 10, NULL );

  strcpy( td.name, "Bob The Skutter" );

  lfds711_queue_bss_enqueue( *qbsss, NULL, &td );

  lfds711_queue_bss_dequeue( &qbsss, NULL, &temp_td );

  printf( "skutter name = %s\n", temp_td->name );

  lfds711_queue_bss_cleanup( &qbsss, NULL );

  return( EXIT_SUCCESS );
}