Skip to content

Latest commit

 

History

History
90 lines (55 loc) · 2.52 KB

cds-api.md

File metadata and controls

90 lines (55 loc) · 2.52 KB
Raw

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.

Data structure files

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 existence 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.