doc/cds-api.md

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