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/wfqueue.h:
  37
  38         Queue with wait-free enqueue, blocking dequeue. This queue does
  39         _not_ use RCU.
  40
  41 urcu/rculfstack.h:
  42
  43         RCU stack with lock-free push, lock-free dequeue. RCU used to
  44         provide existance guarantees.
  45
  46 urcu/wfstack.h:
  47
  48         Stack with wait-free enqueue, blocking dequeue. This stack does
  49         _not_ use RCU.
  50
  51 urcu/rculfhash.h:
  52
  53         Lock-Free Resizable RCU Hash Table. RCU used to provide
  54         existance guarantees. Provides scalable updates, and scalable
  55         RCU read-side lookups and traversals. Unique and duplicate keys
  56         are supported. Provides "uniquify add" and "replace add"
  57         operations, along with associated read-side traversal uniqueness
  58         guarantees. Automatic hash table resize based on number of
  59         elements is supported. See the API for more details.