From e75bc03fe3ded2faa5a77bd1370b994cd60b4865 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Tue, 15 May 2012 07:50:30 -0400 Subject: [PATCH] document concurrent data structures Document the concurrent data structures provided by the userspace RCU library. Reviewed-by: Paul E. McKenney Signed-off-by: Mathieu Desnoyers --- doc/Makefile.am | 2 +- doc/cds-api.txt | 59 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 60 insertions(+), 1 deletion(-) create mode 100644 doc/cds-api.txt diff --git a/doc/Makefile.am b/doc/Makefile.am index bec1d7c..27d3793 100644 --- 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 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. -- 2.34.1