vsync / stack / quack.h

Lockfree concurrent stack/queue (Treiber stack)

Groups: Linearizable, Lock-free

It’s a queue! It’s a stack! No, it’s a quack!

Quack is a concurrent stack that can be accessed as queue. It is also known as Treiber stack. The producers call quack_push() to add new elements to the stack. The consumers call quack_popall() to return a singled-linked list in LIFO order (as a stack). The caller can change the order to FIFO order by calling quack_reverse(). The caller is reposible for iterating over the elements of the list.

Example quack

typedef struct {
     quack_node_t n; // embed quack_node in your data structure
     int value;
} node_t;

quack_t stack;
node_t *mynode;

// to push into the stack
quack_push(&stack, &mynode->n);

// to pop from and iterate in FIFO order
quack_node_t *n = quack_reverse(quack_popall(&stack));
for (; n != NULL; n = n->next) {
    node_t *nn = (node_t*) n;
    // use node
}

Reference

Treiber, R.K., 1986. Systems programming: Coping with parallelism.

---

Macros

Macro	Description
QUACK_INIT	Initializer of quack.

Macro QUACK_INIT

QUACK_INIT()

Initializer of quack.

---

Functions

Function	Description
quack_init	Initializes quack.
quack_push	Pushes node into the quack.
quack_is_empty	Checks if quack is empty.
quack_popall	Pops all elements from the quack in LIFO order.
quack_reverse	Reverse order of elements taken from the quack (from LIFO to FIFO or vice-versa).

Function quack_init

static void quack_init(quack_t *s)

Initializes quack.

Parameters:

• q: quack data structure

Function quack_push

static void quack_push(quack_t *q, quack_node_t *n)

Pushes node into the quack.

Parameters:

• q: quack data structure
• n: node element

Function quack_is_empty

static vbool_t quack_is_empty(quack_t *const q)

Checks if quack is empty.

Parameters:

• q: quack data structure

Returns: true if there is an element in quack, false otherwise.

Function quack_popall

static quack_node_t* quack_popall(quack_t *q)

Pops all elements from the quack in LIFO order.

The user is responsible for iterating over the elements (accessible with next pointer).

Parameters:

• q: quack data structure

Returns: head of quack

Function quack_reverse

static quack_node_t* quack_reverse(quack_node_t *n)

Reverse order of elements taken from the quack (from LIFO to FIFO or vice-versa).

Parameters:

• n: head or tail of quack

Returns: tail or head of quack

---