Commit | Line | Data |
---|---|---|
d001c886 MJ |
1 | <!-- |
2 | SPDX-FileCopyrightText: 2023 EfficiOS Inc. | |
3 | ||
4 | SPDX-License-Identifier: CC-BY-4.0 | |
5 | --> | |
6 | ||
dcb9c05a PP |
7 | Userspace RCU Concurrent Data Structures (CDS) API |
8 | ================================================== | |
9 | ||
10 | by Mathieu Desnoyers and Paul E. McKenney | |
11 | ||
12 | This document describes briefly the data structures contained with the | |
13 | userspace RCU library. | |
14 | ||
15 | ||
16 | Data structure files | |
17 | -------------------- | |
18 | ||
19 | ### `urcu/list.h` | |
20 | ||
21 | Doubly-linked list, which requires mutual exclusion on | |
22 | updates and reads. | |
23 | ||
24 | ||
25 | ### `urcu/rculist.h` | |
26 | ||
27 | Doubly-linked list, which requires mutual exclusion on | |
28 | updates, allows RCU read traversals. | |
29 | ||
30 | ||
31 | ### `urcu/hlist.h` | |
32 | ||
33 | Doubly-linked list, with single pointer list head. Requires | |
34 | mutual exclusion on updates and reads. Useful for implementing hash tables. | |
35 | Downside over `list.h`: lookup of tail in O(n). | |
36 | ||
37 | ||
38 | ### `urcu/rcuhlist.h` | |
39 | ||
40 | Doubly-linked list, with single pointer list head. | |
41 | Requires mutual exclusion on updates, allows RCU read traversals. Useful | |
a5a99662 | 42 | for implementing hash tables. Downside over `rculist.h`: lookup of tail in O(n). |
dcb9c05a PP |
43 | |
44 | ||
45 | ### `urcu/wfstack.h` | |
46 | ||
72886af7 | 47 | Stack with wait-free push and wait-free pop\_all. Both |
dcb9c05a PP |
48 | blocking and non-blocking pop and traversal operations are provided. This |
49 | stack does _not_ specifically rely on RCU. Various synchronization techniques | |
50 | can be used to deal with pop ABA. Those are detailed in the API. | |
51 | ||
52 | ||
53 | ### `urcu/wfcqueue.h` | |
54 | ||
55 | Concurrent queue with wait-free enqueue. Both blocking and | |
56 | non-blocking dequeue, splice (move all elements from one queue | |
57 | to another), and traversal operations are provided. | |
58 | ||
59 | This queue does _not_ specifically rely on RCU. Mutual exclusion | |
60 | is used to protect dequeue, splice (from source queue) and | |
61 | traversal (see API for details). | |
62 | ||
63 | - Note: deprecates `urcu/wfqueue.h`. | |
64 | ||
65 | ||
66 | ### `urcu/lfstack.h` | |
67 | ||
72886af7 | 68 | Stack with lock-free push, lock-free pop, wait-free pop\_all, |
dcb9c05a PP |
69 | wait-free traversal. Various synchronization techniques can be |
70 | used to deal with pop ABA. Those are detailed in the API. | |
71 | This stack does _not_ specifically rely on RCU. | |
72 | ||
73 | - Note: deprecates `urcu/rculfstack.h`. | |
74 | ||
75 | ||
76 | ### `urcu/rculfqueue.h` | |
77 | ||
78 | RCU queue with lock-free enqueue, lock-free dequeue. | |
79 | This queue relies on RCU for existence guarantees. | |
80 | ||
81 | ||
82 | ### `urcu/rculfhash.h` | |
83 | ||
84 | Lock-Free Resizable RCU Hash Table. RCU used to provide | |
f99c6e92 | 85 | existence guarantees. Provides scalable updates, and scalable |
dcb9c05a PP |
86 | RCU read-side lookups and traversals. Unique and duplicate keys |
87 | are supported. Provides "uniquify add" and "replace add" | |
88 | operations, along with associated read-side traversal uniqueness | |
89 | guarantees. Automatic hash table resize based on number of | |
90 | elements is supported. See the API for more details. |