r6:API:Queue

Source Files

/src/queue/queue_delete.c
/src/queue/queue_new.c
/src/queue/queue_query.c
/src/queue/queue_queue.c
/src/queue/queue_internal.h
/inc/liblfds.h

Incomplete Types

struct queue_state;

Enums

enum queue_query_type
{
  QUEUE_QUERY_ELEMENT_COUNT,
  QUEUE_QUERY_VALIDATE
};

Prototypes

int queue_new( struct queue_state **qs, atom_t number_elements );
void queue_delete( struct queue_state *qs,
                   void (*user_data_delete_function)(void *user_data, void *user_state),
                   void *user_state );

int queue_enqueue( struct queue_state *qs, void *user_data );
int queue_guaranteed_enqueue( struct queue_state *qs, void *user_data );
int queue_dequeue( struct queue_state *qs, void **user_data );

void queue_query( struct queue_state *qs, enum queue_query_type query_type, void *query_input, void *query_output );

Overview

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

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