r6.0.0:lfds600_queue

Source Files

/liblfds600/src/lfds600_queue/lfds600_queue_delete.c
/liblfds600/src/lfds600_queue/lfds600_queue_new.c
/liblfds600/src/lfds600_queue/lfds600_queue_query.c
/liblfds600/src/lfds600_queue/lfds600_queue_queue.c
/liblfds600/src/lfds600_queue/lfds600_queue_internal.h
/liblfds600/inc/liblfds600.h

Incomplete Types

struct lfds600_queue_state;

Enums

enum lfds600_queue_query_type
{
  LFDS600_QUEUE_QUERY_ELEMENT_COUNT,
  LFDS600_QUEUE_QUERY_VALIDATE
};

Prototypes

int lfds600_queue_new( struct lfds600_queue_state **qs, lfds600_atom_t number_elements );
void lfds600_queue_delete( struct lfds600_queue_state *qs,
                           void (*user_data_delete_function)(void *user_data, void *user_state),
                           void *user_state );

int lfds600_queue_enqueue( struct lfds600_queue_state *qs, void *user_data );
int lfds600_queue_guaranteed_enqueue( struct lfds600_queue_state *qs, void *user_data );
int lfds600_queue_dequeue( struct lfds600_queue_state *qs, void **user_data );

void lfds600_queue_query( struct lfds600_queue_state *qs, enum lfds600_queue_query_type query_type, void *query_input, void *query_output );

Overview

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

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