doc/cds-api.txt

   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/wfstack.h:
  32
  33         Stack with wait-free push and wait-free pop_all. Both blocking
  34         and non-blocking pop and traversal operations are provided.
  35         This stack does _not_ specifically rely on RCU.
  36         Various synchronization techniques can be used to deal with
  37         pop ABA. Those are detailed in the API.
  38
  39 urcu/wfcqueue.h:
  40
  41         Concurrent queue with wait-free enqueue. Both blocking and
  42         non-blocking dequeue, splice (move all elements from one queue
  43         to another), and traversal operations are provided.
  44         This queue does _not_ specifically rely on RCU. Mutual exclusion
  45         is used to protect dequeue, splice (from source queue) and
  46         traversal (see API for details).
  47         (note: deprecates urcu/wfqueue.h)
  48
  49 urcu/lfstack.h:
  50
  51         Stack with lock-free push, lock-free pop, wait-free pop_all,
  52         wait-free traversal. Various synchronization techniques can be
  53         used to deal with pop ABA. Those are detailed in the API.
  54         This stack does _not_ specifically rely on RCU.
  55         (note: deprecates urcu/rculfstack.h)
  56
  57 urcu/rculfqueue.h:
  58
  59         RCU queue with lock-free enqueue, lock-free dequeue.
  60         This queue relies on RCU for existence guarantees.
  61
  62 urcu/rculfhash.h:
  63
  64         Lock-Free Resizable RCU Hash Table. RCU used to provide
  65         existance guarantees. Provides scalable updates, and scalable
  66         RCU read-side lookups and traversals. Unique and duplicate keys
  67         are supported. Provides "uniquify add" and "replace add"
  68         operations, along with associated read-side traversal uniqueness
  69         guarantees. Automatic hash table resize based on number of
  70         elements is supported. See the API for more details.