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/wfcqueue.h:

	Concurrent queue with wait-free enqueue, blocking traversal.
	This queue does _not_ use RCU.
	(note: deprecates urcu/wfqueue.h)

urcu/lfstack.h:

	RCU stack with lock-free push, lock-free dequeue. Various
	synchronization techniques can be used to deal with "pop" ABA.
	Those are detailed in the API.
	(note: deprecates urcu/rculfstack.h)

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.