[userspace-rcu.git] / doc / cds-api.txt

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

	Stack with wait-free push and wait-free pop_all. Both blocking
	and non-blocking pop and traversal operations are provided.
	This stack does _not_ specifically rely on RCU.
	Various synchronization techniques can be used to deal with
	pop ABA. Those are detailed in the API.

urcu/wfcqueue.h:

	Concurrent queue with wait-free enqueue. Both blocking and
	non-blocking dequeue, splice (move all elements from one queue
	to another), and traversal operations are provided.
	This queue does _not_ specifically rely on RCU. Mutual exclusion
	is used to protect dequeue, splice (from source queue) and
	traversal (see API for details).
	(note: deprecates urcu/wfqueue.h)

urcu/lfstack.h:

	Stack with lock-free push, lock-free pop, wait-free pop_all,
	wait-free traversal. Various synchronization techniques can be
	used to deal with pop ABA. Those are detailed in the API.
	This stack does _not_ specifically rely on RCU.
	(note: deprecates urcu/rculfstack.h)

urcu/rculfqueue.h:

	RCU queue with lock-free enqueue, lock-free dequeue.
	This queue relies on RCU for existence guarantees.

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.
Commit	Line	Data
e75bc03f MD	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
e43447f9	31	urcu/wfstack.h:
e75bc03f	32
e43447f9 MD	33	Stack with wait-free push and wait-free pop_all. Both blocking
	34	and non-blocking pop and traversal operations are provided.
	35	This stack does _not_ specifically rely on RCU.
	36	Various synchronization techniques can be used to deal with
	37	pop ABA. Those are detailed in the API.
e75bc03f	38
0c66dad6	39	urcu/wfcqueue.h:
e75bc03f	40
e43447f9 MD	41	Concurrent queue with wait-free enqueue. Both blocking and
	42	non-blocking dequeue, splice (move all elements from one queue
	43	to another), and traversal operations are provided.
	44	This queue does _not_ specifically rely on RCU. Mutual exclusion
	45	is used to protect dequeue, splice (from source queue) and
	46	traversal (see API for details).
0c66dad6	47	(note: deprecates urcu/wfqueue.h)
e75bc03f	48
0c66dad6	49	urcu/lfstack.h:
e75bc03f	50
e43447f9 MD	51	Stack with lock-free push, lock-free pop, wait-free pop_all,
	52	wait-free traversal. Various synchronization techniques can be
	53	used to deal with pop ABA. Those are detailed in the API.
	54	This stack does _not_ specifically rely on RCU.
0c66dad6	55	(note: deprecates urcu/rculfstack.h)
e75bc03f	56
e43447f9	57	urcu/rculfqueue.h:
e75bc03f	58
e43447f9 MD	59	RCU queue with lock-free enqueue, lock-free dequeue.
e43447f9 MD	60	This queue relies on RCU for existence guarantees.
e75bc03f MD	61
	62	urcu/rculfhash.h:
	63
	64	Lock-Free Resizable RCU Hash Table. RCU used to provide
	65	existance guarantees. Provides scalable updates, and scalable
	66	RCU read-side lookups and traversals. Unique and duplicate keys
	67	are supported. Provides "uniquify add" and "replace add"
	68	operations, along with associated read-side traversal uniqueness
	69	guarantees. Automatic hash table resize based on number of
	70	elements is supported. See the API for more details.