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

[Paul E. McKenney]

On Mon, May 14, 2012 at 11:36:04PM -0400, Mathieu Desnoyers wrote:
> Document the concurrent data structures provided by the userspace RCU
> library.

Looks good to me!

Reviewed-by: Paul E. McKenney <paulmck at linux.vnet.ibm.com>

> 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
> 
> _______________________________________________
> rp mailing list
> rp at svcs.cs.pdx.edu
> http://svcs.cs.pdx.edu/mailman/listinfo/rp
>