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 | ||
36 | urcu/wfqueue.h: | |
37 | ||
38 | Queue with wait-free enqueue, blocking dequeue. This queue does | |
39 | _not_ use RCU. | |
40 | ||
41 | urcu/rculfstack.h: | |
42 | ||
43 | RCU stack with lock-free push, lock-free dequeue. RCU used to | |
44 | provide existance guarantees. | |
45 | ||
46 | urcu/wfstack.h: | |
47 | ||
48 | Stack with wait-free enqueue, blocking dequeue. This stack does | |
49 | _not_ use RCU. | |
50 | ||
51 | urcu/rculfhash.h: | |
52 | ||
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. |