[lttng-dev] [RFC PATCH urcu] document concurrent data structures

[Mathieu Desnoyers]

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

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
---
diff --git a/doc/cds-api.txt b/doc/cds-api.txt
new file mode 100644
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.

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com