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 Queue with wait-free enqueue, blocking dequeue. This queue does
43 RCU stack with lock-free push, lock-free dequeue. RCU used to
44 provide existance guarantees.
48 Stack with wait-free enqueue, blocking dequeue. This stack does
53 Lock-Free Resizable RCU Hash Table. RCU used to provide
54 existance guarantees. Provides scalable updates, and scalable
55 RCU read-side lookups and traversals. Unique and duplicate keys
56 are supported. Provides "uniquify add" and "replace add"
57 operations, along with associated read-side traversal uniqueness
58 guarantees. Automatic hash table resize based on number of
59 elements is supported. See the API for more details.