Harmonize pprint macro across projects
[urcu.git] / doc / cds-api.md
1 Userspace RCU Concurrent Data Structures (CDS) API
2 ==================================================
3
4 by Mathieu Desnoyers and Paul E. McKenney
5
6 This document describes briefly the data structures contained with the
7 userspace RCU library.
8
9
10 Data structure files
11 --------------------
12
13 ### `urcu/list.h`
14
15 Doubly-linked list, which requires mutual exclusion on
16 updates and reads.
17
18
19 ### `urcu/rculist.h`
20
21 Doubly-linked list, which requires mutual exclusion on
22 updates, allows RCU read traversals.
23
24
25 ### `urcu/hlist.h`
26
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).
30
31
32 ### `urcu/rcuhlist.h`
33
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).
37
38
39 ### `urcu/wfstack.h`
40
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.
45
46
47 ### `urcu/wfcqueue.h`
48
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.
52
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).
56
57 - Note: deprecates `urcu/wfqueue.h`.
58
59
60 ### `urcu/lfstack.h`
61
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.
66
67 - Note: deprecates `urcu/rculfstack.h`.
68
69
70 ### `urcu/rculfqueue.h`
71
72 RCU queue with lock-free enqueue, lock-free dequeue.
73 This queue relies on RCU for existence guarantees.
74
75
76 ### `urcu/rculfhash.h`
77
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.
This page took 0.043144 seconds and 4 git commands to generate.