--- name: "libatomic-stack" section: "3" platform: "linux" package: "libatomic-ops-dev" version: "7.8.2-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/libatomic-stack" --- # libatomic-stack(3) Library providing linked stack abstraction ## NAME libatomic-stack - Library providing linked stack abstraction ## SYNOPSIS **#include \** **cc ... -latomic\_ops\_gpl** Note that the AO\_stack implementation is licensed under the GPL, unlike the lower level routines. **void AO\_stack\_init(AO\_stack\_t \*list);**\ **void AO\_stack\_push\_release(AO\_stack\_t \*list, AO\_t \*new\_element);**\ **AO\_t \* AO\_stack\_pop\_acquire(volatile AO\_stack\_t \*list);** ## DESCRIPTION **libatomic-stack** defines a linked stack abstraction. Stacks may be accessed by multiple concurrent threads. The implementation is 1-lock-free, i.e. it will continue to make progress if at most one thread becomes inactive while operating on the data structure. This makes it safe to access these data structures from non-reentrant signal handlers, provided at most one non-signal-handler thread is accessing the data structure at once. This latter condition can be ensured by acquiring an ordinary lock around the non-hndler accesses to the data structure. We use a fully lock-free implementation when the underlying hardware makes that less expensive, i.e. when we have a double-wide compare-and-swap operation available. (The fully lock-free implementation uses an AO\_t- sized version count, and assumes it does not wrap during the time any given operation is active. This seems reasonably safe on 32-bit hardware, and very safe on 64-bit hardware.) If a fully lock-free implementation is used, the macro *AO\_STACK\_IS\_LOCK\_FREE* will be defined. The cleanest way to use these routines is probably to define the stack node type with an initial *AO\_t* link field, so that the conversion between the link-field pointer and the stack element pointer is just a compile-time cast. But other possibilities exist. (This would be cleaner in C++ with templates.) A stack is represented by an AO\_stack\_t structure. (This is normally 2 or 3 times the size of a pointer.) It may be statically initialized by setting it to *AO\_STACK\_INITIALIZER* , or dynamically initialized to an empty stack with *AO\_stack\_init* . There are only three operations for accessing stacks: - **AO\_stack\_init** Initalise a stack - **AO\_stack\_push\_release** Push new element onto the stack. - **AO\_stack\_pop\_acquire** Pop element off the stack. We require that the objects pushed as list elements remain addressable as long as any push or pop operation are in progress. (It is OK for an object to be "pop"ped off a stack and "deallocated" with a concurrent "pop" on the same stack still in progress, but only if "deallocation" leaves the object addressable. The second "pop" may still read the object, but the value it reads will not matter.) We require that the headers ( *AO\_stack* objects) remain allocated and valid as long as any operations on them are still in-flight. We also provide macros *AO\_REAL\_HEAD\_PTR* that converts an *AO\_stack\_t* to a pointer to the link field in the next element, and *AO\_REAL\_NEXT\_PTR* that converts a link field to a real, dereferencable, pointer to the link field in the next element. This is intended only for debugging, or to traverse the list after modification has ceased. There is otherwise no guarantee that walking a stack using this macro will produce any kind of consistent picture of the data structure. ## SEE ALSO [libatomic-ops(3)](/libatomic-ops/3.md), [libatomic-malloc(3)](/libatomic-malloc/3.md) ## AUTHOR This manual page was written by Ian Wienand \, based on comments in the source code. It was written for the Debian project (but may be used by others).