# Treiber stack
A **Treiber stack** (R.K. Treiber, 1986) is the simplest lock-free data structure built entirely on [[cas|compare-and-swap]]: a singly-linked stack where push and pop both work by CASing the head pointer, retrying if another thread got there first. It's usually the first lock-free structure taught, since it's a direct, minimal demonstration of the CAS-retry-loop pattern that shows up everywhere in lock-free programming, including in the more complex [[lock-free-queue|Michael-Scott queue]].

```c
struct node {
    void                   *data;
    _Atomic(struct node *)  next;
};

_Atomic(struct node *) head = NULL;

void push(void *data) {
    struct node *n = malloc(sizeof *n);
    n->data = data;
    struct node *old_head;
    do {
        old_head = atomic_load(&head);
        n->next = old_head;
    } while (!atomic_compare_exchange_weak(&head, &old_head, n));
}

void *pop(void) {
    struct node *old_head;
    struct node *new_head;
    do {
        old_head = atomic_load(&head);
        if (old_head == NULL) return NULL;        // empty stack
        new_head = atomic_load(&old_head->next);
    } while (!atomic_compare_exchange_weak(&head, &old_head, new_head));
    void *data = old_head->data;
    free(old_head);   // unsafe without reclamation - see below
    return data;
}
```

## Why it's simpler than a lock-free queue

A stack only ever needs to touch one end, the head, so both push and pop are a single CAS loop with no helping mechanism required. Compare this to the [[lock-free-queue|Michael-Scott queue]], where enqueue and dequeue touch head and tail separately and sometimes need to help a stalled thread finish updating `tail`. The Treiber stack's simplicity is exactly why it's the standard first example: it shows the CAS-retry pattern with none of the extra bookkeeping a two-ended structure needs.

## The same reclamation problem

The `free(old_head)` in `pop` has the identical hazard as in the Michael-Scott queue: if the freed node is reused and pushed again before every concurrent `pop` has finished dereferencing it, a stale CAS can succeed against a coincidentally-matching address (the [[aba-problem|ABA problem]]). Production implementations need [[hazard-pointer|hazard pointers]] or [[rcu|epoch-based reclamation]] rather than an immediate `free`, exactly as with any other CAS-based lock-free structure.