1 Userspace RCU Concurrent Data Structures (CDS) API
2 ==================================================
4 by Mathieu Desnoyers and Paul E. McKenney
6 This document describes briefly the data structures contained with the
15 Doubly-linked list, which requires mutual exclusion on
21 Doubly-linked list, which requires mutual exclusion on
22 updates, allows RCU read traversals.
27 Doubly-linked list, with single pointer list head. Requires
28 mutual exclusion on updates and reads. Useful for implementing hash tables.
29 Downside over `list.h`: lookup of tail in O(n).
34 Doubly-linked list, with single pointer list head.
35 Requires mutual exclusion on updates, allows RCU read traversals. Useful
36 for implementing hash tables. Downside over rculist.h: lookup of tail in O(n).
41 Stack with wait-free push and wait-free pop_all. Both
42 blocking and non-blocking pop and traversal operations are provided. This
43 stack does _not_ specifically rely on RCU. Various synchronization techniques
44 can be used to deal with pop ABA. Those are detailed in the API.
49 Concurrent queue with wait-free enqueue. Both blocking and
50 non-blocking dequeue, splice (move all elements from one queue
51 to another), and traversal operations are provided.
53 This queue does _not_ specifically rely on RCU. Mutual exclusion
54 is used to protect dequeue, splice (from source queue) and
55 traversal (see API for details).
57 - Note: deprecates `urcu/wfqueue.h`.
62 Stack with lock-free push, lock-free pop, wait-free pop_all,
63 wait-free traversal. Various synchronization techniques can be
64 used to deal with pop ABA. Those are detailed in the API.
65 This stack does _not_ specifically rely on RCU.
67 - Note: deprecates `urcu/rculfstack.h`.
70 ### `urcu/rculfqueue.h`
72 RCU queue with lock-free enqueue, lock-free dequeue.
73 This queue relies on RCU for existence guarantees.
76 ### `urcu/rculfhash.h`
78 Lock-Free Resizable RCU Hash Table. RCU used to provide
79 existance guarantees. Provides scalable updates, and scalable
80 RCU read-side lookups and traversals. Unique and duplicate keys
81 are supported. Provides "uniquify add" and "replace add"
82 operations, along with associated read-side traversal uniqueness
83 guarantees. Automatic hash table resize based on number of
84 elements is supported. See the API for more details.