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