How does AtomicStampedReference work, and how do you read and update it correctly?

## What it is `AtomicStampedReference<V>` (in `java.util.concurrent.atomic`) is an atomic holder for **two** things at once: an object **reference** of type `V` and an `int` **stamp**. The stamp is just an integer you control — conventionally a **version counter** you increment on every update. The point is that CAS operates on the *pair*, so two updates that leave the reference equal but advance the stamp are distinguishable. This is how it defeats the **ABA problem** (a value going A→B→A slipping past a value-only CAS). ## Constructing ```java AtomicStampedReference<Node> ref = new AtomicStampedReference<>(initialNode, 0); ``` The second argument is the initial stamp (commonly 0). ## Reading atomically The subtlety: you must read the reference and its stamp **together**, or another thread could change one between your two reads. The API solves this with an out-parameter: ```java int[] stampHolder = new int[1]; Node current = ref.get(stampHolder); // returns the reference... int stamp = stampHolder[0]; // ...and fills in the matching stamp ``` `get(int[] stampHolder)` returns the reference and writes the current stamp into `stampHolder[0]` as one consistent snapshot. There are also `getReference()` and `getStamp()`, but calling them separately is **not** an atomic snapshot — between the two calls another thread may update, so prefer `get(int[])` when you need both consistently. ## Updating atomically ```java boolean success = ref.compareAndSet( current, // expected reference next, // new reference stamp, // expected stamp stamp + 1); // new stamp (advance the version) ``` `compareAndSet` succeeds **only if both** the current reference `==` the expected reference **and** the current stamp equals the expected stamp. On success it installs the new reference and new stamp together. By convention `newStamp = expectedStamp + 1`, so every successful update advances the version. This is exactly what makes A→B→A detectable: the second 'A' carries a stamp two greater than the one you read, so your CAS (which still expects the old stamp) fails. There is also `attemptStamp(expectedRef, newStamp)` to change just the stamp while the reference is unchanged, and `set(newRef, newStamp)` for an unconditional write. ## The retry-loop idiom Like all CAS code you wrap it in a read-compute-CAS loop: ```java int[] holder = new int[1]; while (true) { Node curHead = ref.get(holder); int stamp = holder[0]; Node newHead = compute(curHead); if (ref.compareAndSet(curHead, newHead, stamp, stamp + 1)) break; // CAS failed: someone changed the reference and/or the stamp -> loop } ``` ## How it works inside, and the cost The JVM cannot atomically swap two separate words (reference + int) with one ordinary CAS. So `AtomicStampedReference` boxes the pair into a tiny **immutable holder object** — internally a `Pair<V>` carrying the reference and stamp — and stores a single `volatile` reference to that holder. A `compareAndSet` then CAS-swaps the holder reference. Consequence: each *successful, value-changing* update allocates a new holder object, adding minor allocation/GC pressure. (An optimization avoids allocating when nothing actually changes.) For most code this overhead is negligible compared to the correctness it buys. ## Stamp wraparound The stamp is a 32-bit `int`, so it can in theory overflow after ~4 billion updates and wrap to a value seen long ago, re-opening a tiny ABA window. In practice this is astronomically unlikely to coincide with a paused thread holding that exact old stamp, but it is the theoretical limit of the technique; truly paranoid designs use a wider tag. ## When to reach for it Use `AtomicStampedReference` when you build lock-free structures over a reference that can legitimately return to a prior value (lock-free stacks/queues, free lists, optimistic state machines) and ABA would corrupt them. If you only need a single 'is it marked/deleted' bit, `AtomicMarkableReference` is lighter; if the value carries its whole meaning (a counter), you need no stamp at all.