-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.
-
-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
- existance 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.