Userspace RCU Concurrent Data Structures (CDS) API
==================================================
by Mathieu Desnoyers and Paul E. McKenney
This document describes briefly the data structures contained with the
userspace RCU library.
Data structure files
--------------------
### `urcu/list.h`
Doubly-linked list, which requires mutual exclusion on
updates and reads.
### `urcu/rculist.h`
Doubly-linked list, which requires mutual exclusion on
updates, allows RCU read traversals.
### `urcu/hlist.h`
Doubly-linked list, with single pointer list head. Requires
mutual exclusion on updates and reads. Useful for implementing hash tables.
Downside over `list.h`: lookup of tail in O(n).
### `urcu/rcuhlist.h`
Doubly-linked list, with single pointer list head.
Requires mutual exclusion on updates, allows RCU read traversals. Useful
for implementing hash tables. Downside over `rculist.h`: lookup of tail in O(n).
### `urcu/wfstack.h`
Stack with wait-free push and wait-free pop\_all. Both
blocking and non-blocking pop and traversal operations are provided. This
stack does _not_ specifically rely on RCU. Various synchronization techniques
can be used to deal with pop ABA. Those are detailed in the API.
### `urcu/wfcqueue.h`
Concurrent queue with wait-free enqueue. Both blocking and
non-blocking dequeue, splice (move all elements from one queue
to another), and traversal operations are provided.
This queue does _not_ specifically rely on RCU. Mutual exclusion
is used to protect dequeue, splice (from source queue) and
traversal (see API for details).
- Note: deprecates `urcu/wfqueue.h`.
### `urcu/lfstack.h`
Stack with lock-free push, lock-free pop, wait-free pop\_all,
wait-free traversal. Various synchronization techniques can be
used to deal with pop ABA. Those are detailed in the API.
This stack does _not_ specifically rely on RCU.
- Note: deprecates `urcu/rculfstack.h`.
### `urcu/rculfqueue.h`
RCU queue with lock-free enqueue, lock-free dequeue.
This queue relies on RCU for existence guarantees.
### `urcu/rculfhash.h`
Lock-Free Resizable RCU Hash Table. RCU used to provide
existence guarantees. Provides scalable updates, and scalable
RCU read-side lookups and traversals. Unique and duplicate keys
are supported. Provides "uniquify add" and "replace add"
operations, along with associated read-side traversal uniqueness
guarantees. Automatic hash table resize based on number of
elements is supported. See the API for more details.
