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