r6.1.1:lfds611_queue

Source Files

/liblfds611/src/lfds611_queue/lfds611_queue_delete.c
/liblfds611/src/lfds611_queue/lfds611_queue_new.c
/liblfds611/src/lfds611_queue/lfds611_queue_query.c
/liblfds611/src/lfds611_queue/lfds611_queue_queue.c
/liblfds611/src/lfds611_queue/lfds611_queue_internal.h
/liblfds611/inc/liblfds611.h

Incomplete Types

struct lfds611_queue_state;

Enums

enum lfds611_queue_query_type
{
  LFDS611_QUEUE_QUERY_ELEMENT_COUNT,
  LFDS611_QUEUE_QUERY_VALIDATE
};

Prototypes

int lfds611_queue_new( struct lfds611_queue_state **qs, lfds611_atom_t number_elements );
void lfds611_queue_use( struct lfds611_queue_state *qs );
void lfds611_queue_delete( struct lfds611_queue_state *qs,
                           void (*user_data_delete_function)(void *user_data, void *user_state),
                           void *user_state );

int lfds611_queue_enqueue( struct lfds611_queue_state *qs, void *user_data );
int lfds611_queue_guaranteed_enqueue( struct lfds611_queue_state *qs, void *user_data );
int lfds611_queue_dequeue( struct lfds611_queue_state *qs, void **user_data );

void lfds611_queue_query( struct lfds611_queue_state *qs, enum lfds611_queue_query_type query_type, void *query_input, void *query_output );

Overview

This API implements a queue. A new queue is instantiated by the lfds611_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 lfds611_queue_enqueue and lfds611_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 lfds611_queue_delete.

The function lfds611_queue_enqueue only fails when there are no elements available in the queue. In this case, the function lfds611_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 lfds611_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".