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 | ||
31 | urcu/rculfqueue.h: | |
32 | ||
33 | RCU queue with lock-free enqueue, lock-free dequeue. RCU used to | |
34 | provide existance guarantees. | |
35 | ||
0c66dad6 | 36 | urcu/wfcqueue.h: |
e75bc03f | 37 | |
0c66dad6 MD |
38 | Concurrent queue with wait-free enqueue, blocking traversal. |
39 | This queue does _not_ use RCU. | |
40 | (note: deprecates urcu/wfqueue.h) | |
e75bc03f | 41 | |
0c66dad6 | 42 | urcu/lfstack.h: |
e75bc03f | 43 | |
0c66dad6 MD |
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) | |
e75bc03f MD |
48 | |
49 | urcu/wfstack.h: | |
50 | ||
51 | Stack with wait-free enqueue, blocking dequeue. This stack does | |
52 | _not_ use RCU. | |
53 | ||
54 | urcu/rculfhash.h: | |
55 | ||
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. |