r6.1.0:lfds610_queue

Source Files

/liblfds610/src/lfds610_queue/lfds610_queue_delete.c
/liblfds610/src/lfds610_queue/lfds610_queue_new.c
/liblfds610/src/lfds610_queue/lfds610_queue_query.c
/liblfds610/src/lfds610_queue/lfds610_queue_queue.c
/liblfds610/src/lfds610_queue/lfds610_queue_internal.h
/liblfds610/inc/liblfds610.h

Incomplete Types

struct lfds610_queue_state;

Enums

enum lfds610_queue_query_type
{
  LFDS610_QUEUE_QUERY_ELEMENT_COUNT,
  LFDS610_QUEUE_QUERY_VALIDATE
};

Prototypes

int lfds610_queue_new( struct lfds610_queue_state **qs, lfds610_atom_t number_elements );
void lfds610_queue_use( struct lfds610_queue_state *qs );
void lfds610_queue_delete( struct lfds610_queue_state *qs,
                           void (*user_data_delete_function)(void *user_data, void *user_state),
                           void *user_state );

int lfds610_queue_enqueue( struct lfds610_queue_state *qs, void *user_data );
int lfds610_queue_guaranteed_enqueue( struct lfds610_queue_state *qs, void *user_data );
int lfds610_queue_dequeue( struct lfds610_queue_state *qs, void **user_data );

void lfds610_queue_query( struct lfds610_queue_state *qs, enum lfds610_queue_query_type query_type, void *query_input, void *query_output );

Overview

This API implements a queue. A new queue is instantiated by the lfds610_queue_new function, where the argument number_elements is the maximum number of elements which can be enqueued in the queue at any one time. The caller then uses the queue by enqueuing and dequeuing, via the lfds610_queue_enqueue and lfds610_queue_dequeue functions, respectively. An enqueue or dequeue operation will enqueue or deqeueue a void pointer of user data. 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 queue is deleted using lfds610_queue_delete.

The function lfds610_queue_enqueue only fails when there are no elements available in the queue. In this case, the function lfds610_queue_guaranteed_enqueue can be called. This allocates a single new element and then enqueues that element. This permanently increases the maximum number of elements in the queue by one. This function only fails when malloc fails.

Lock-free Specific Behaviour

The maximum number of elements in the queue must be specified when the queue is created and these elements are allocated in full when the queue is created. It is possible after the queue is created to increase the number of elements in the queue, by using the function lfds610_queue_guaranteed_enqueue, but it is never possible to decrease the number of elements in the queue; the queue can only grow.

Algorithm

This queue implements Maged M. Michael and Michael L. Scott's queue algorithm, from their 1996 paper, "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms".