Commit | Line | Data |
---|---|---|
e75bc03f MD |
1 | Userspace RCU Concurrent Data Structures (CDS) API |
2 | by Mathieu Desnoyers and Paul E. McKenney | |
3 | ||
4 | ||
5 | This document describes briefly the data structures contained with the | |
6 | userspace RCU library. | |
7 | ||
8 | urcu/list.h: | |
9 | ||
10 | Doubly-linked list, which requires mutual exclusion on updates | |
11 | and reads. | |
12 | ||
13 | urcu/rculist.h: | |
14 | ||
15 | Doubly-linked list, which requires mutual exclusion on updates, | |
16 | allows RCU read traversals. | |
17 | ||
18 | urcu/hlist.h: | |
19 | ||
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). | |
23 | ||
24 | urcu/rcuhlist.h: | |
25 | ||
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 | |
29 | tail in O(n). | |
30 | ||
e43447f9 | 31 | urcu/wfstack.h: |
e75bc03f | 32 | |
e43447f9 MD |
33 | Stack with wait-free push and wait-free pop_all. Both blocking |
34 | and non-blocking pop and traversal operations are provided. | |
35 | This stack does _not_ specifically rely on RCU. | |
36 | Various synchronization techniques can be used to deal with | |
37 | pop ABA. Those are detailed in the API. | |
e75bc03f | 38 | |
0c66dad6 | 39 | urcu/wfcqueue.h: |
e75bc03f | 40 | |
e43447f9 MD |
41 | Concurrent queue with wait-free enqueue. Both blocking and |
42 | non-blocking dequeue, splice (move all elements from one queue | |
43 | to another), and traversal operations are provided. | |
44 | This queue does _not_ specifically rely on RCU. Mutual exclusion | |
45 | is used to protect dequeue, splice (from source queue) and | |
46 | traversal (see API for details). | |
0c66dad6 | 47 | (note: deprecates urcu/wfqueue.h) |
e75bc03f | 48 | |
0c66dad6 | 49 | urcu/lfstack.h: |
e75bc03f | 50 | |
e43447f9 MD |
51 | Stack with lock-free push, lock-free pop, wait-free pop_all, |
52 | wait-free traversal. Various synchronization techniques can be | |
53 | used to deal with pop ABA. Those are detailed in the API. | |
54 | This stack does _not_ specifically rely on RCU. | |
0c66dad6 | 55 | (note: deprecates urcu/rculfstack.h) |
e75bc03f | 56 | |
e43447f9 | 57 | urcu/rculfqueue.h: |
e75bc03f | 58 | |
e43447f9 MD |
59 | RCU queue with lock-free enqueue, lock-free dequeue. |
60 | This queue relies on RCU for existence guarantees. | |
e75bc03f MD |
61 | |
62 | urcu/rculfhash.h: | |
63 | ||
64 | Lock-Free Resizable RCU Hash Table. RCU used to provide | |
65 | existance guarantees. Provides scalable updates, and scalable | |
66 | RCU read-side lookups and traversals. Unique and duplicate keys | |
67 | are supported. Provides "uniquify add" and "replace add" | |
68 | operations, along with associated read-side traversal uniqueness | |
69 | guarantees. Automatic hash table resize based on number of | |
70 | elements is supported. See the API for more details. |