doc/cds-api.md

   1 <!--
   2 SPDX-FileCopyrightText: 2023 EfficiOS Inc.
   3
   4 SPDX-License-Identifier: CC-BY-4.0
   5 -->
   6
   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
  42 for implementing hash tables. Downside over `rculist.h`: lookup of tail in O(n).
  43
  44
  45 ### `urcu/wfstack.h`
  46
  47 Stack with wait-free push and wait-free pop\_all. Both
  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
  68 Stack with lock-free push, lock-free pop, wait-free pop\_all,
  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
  85 existence guarantees. Provides scalable updates, and scalable
  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.