1 Userspace RCU Concurrent Data Structures (CDS) API
2 by Mathieu Desnoyers and Paul E. McKenney
5 This document describes briefly the data structures contained with the
10 Doubly-linked list, which requires mutual exclusion on updates
15 Doubly-linked list, which requires mutual exclusion on updates,
16 allows RCU read traversals.
20 Doubly-linked list, with single pointer list head. Requires
21 mutual exclusion on updates and reads. Useful for implementing
22 hash tables. Downside over list.h: lookup of tail in O(n).
26 Doubly-linked list, with single pointer list head. Requires
27 mutual exclusion on updates, allows RCU read traversals. Useful
28 for implementing hash tables. Downside over rculist.h: lookup of
33 RCU queue with lock-free enqueue, lock-free dequeue. RCU used to
34 provide existance guarantees.
38 Concurrent queue with wait-free enqueue, blocking traversal.
39 This queue does _not_ use RCU.
40 (note: deprecates urcu/wfqueue.h)
44 RCU stack with lock-free push, lock-free dequeue. Various
45 synchronization techniques can be used to deal with "pop" ABA.
46 Those are detailed in the API.
47 (note: deprecates urcu/rculfstack.h)
51 Stack with wait-free enqueue, blocking dequeue. This stack does
56 Lock-Free Resizable RCU Hash Table. RCU used to provide
57 existance guarantees. Provides scalable updates, and scalable
58 RCU read-side lookups and traversals. Unique and duplicate keys
59 are supported. Provides "uniquify add" and "replace add"
60 operations, along with associated read-side traversal uniqueness
61 guarantees. Automatic hash table resize based on number of
62 elements is supported. See the API for more details.