document concurrent data structures

Document the concurrent data structures provided by the userspace RCU
library.

Reviewed-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

diff --git a/doc/Makefile.am b/doc/Makefile.am
index bec1d7c7006eb25ccf58415366b7ab907f72b17e..27d37935b39655ac9a1933de9b89318e5a59f601 100644 (file)
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -1 +1 @@
-dist_doc_DATA = rcu-api.txt
+dist_doc_DATA = rcu-api.txt cds-api.txt

diff --git a/doc/cds-api.txt b/doc/cds-api.txt
new file mode 100644 (file)
index 0000000..7a3c6e0
--- /dev/null
+++ b/doc/cds-api.txt
@@ -0,0 +1,59 @@
+Userspace RCU Concurrent Data Structures (CDS) API
+by Mathieu Desnoyers and Paul E. McKenney
+
+
+This document describes briefly the data structures contained with the
+userspace RCU library.
+
+urcu/list.h:
+
+       Doubly-linked list, which requires mutual exclusion on updates
+       and reads.
+
+urcu/rculist.h:
+
+       Doubly-linked list, which requires mutual exclusion on updates,
+       allows RCU read traversals.
+       
+urcu/hlist.h:
+
+       Doubly-linked list, with single pointer list head. Requires
+       mutual exclusion on updates and reads. Useful for implementing
+       hash tables. Downside over list.h: lookup of tail in O(n).
+
+urcu/rcuhlist.h:
+
+       Doubly-linked list, with single pointer list head. Requires
+       mutual exclusion on updates, allows RCU read traversals. Useful
+       for implementing hash tables. Downside over rculist.h: lookup of
+       tail in O(n).
+
+urcu/rculfqueue.h:
+
+       RCU queue with lock-free enqueue, lock-free dequeue. RCU used to
+       provide existance guarantees.
+
+urcu/wfqueue.h:
+
+       Queue with wait-free enqueue, blocking dequeue. This queue does
+       _not_ use RCU.
+
+urcu/rculfstack.h:
+
+       RCU stack with lock-free push, lock-free dequeue. RCU used to
+       provide existance guarantees.
+
+urcu/wfstack.h:
+
+       Stack with wait-free enqueue, blocking dequeue. This stack does
+       _not_ use RCU.
+
+urcu/rculfhash.h:
+
+       Lock-Free Resizable RCU Hash Table. RCU used to provide
+       existance guarantees. Provides scalable updates, and scalable
+       RCU read-side lookups and traversals. Unique and duplicate keys
+       are supported. Provides "uniquify add" and "replace add"
+       operations, along with associated read-side traversal uniqueness
+       guarantees. Automatic hash table resize based on number of
+       elements is supported. See the API for more details.