Home | History | Annotate | Line # | Download | only in doc 
      1 <!--
      2 SPDX-FileCopyrightText: 2023 EfficiOS Inc.
      3 
      4 SPDX-License-Identifier: CC-BY-4.0
      5 -->
      6 
      7 Userspace RCU Concurrent Data Structures (CDS) API
      8 ==================================================
      9 
     10 by Mathieu Desnoyers and Paul E. McKenney
     11 
     12 This document describes briefly the data structures contained with the
     13 userspace RCU library.
     14 
     15 
     16 Data structure files
     17 --------------------
     18 
     19 ### `urcu/list.h`
     20 
     21 Doubly-linked list, which requires mutual exclusion on
     22 updates and reads.
     23 
     24 
     25 ### `urcu/rculist.h`
     26 
     27 Doubly-linked list, which requires mutual exclusion on
     28 updates, allows RCU read traversals.
     29 
     30 
     31 ### `urcu/hlist.h`
     32 
     33 Doubly-linked list, with single pointer list head. Requires
     34 mutual exclusion on updates and reads. Useful for implementing hash tables.
     35 Downside over `list.h`: lookup of tail in O(n).
     36 
     37 
     38 ### `urcu/rcuhlist.h`
     39 
     40 Doubly-linked list, with single pointer list head.
     41 Requires mutual exclusion on updates, allows RCU read traversals. Useful
     42 for implementing hash tables. Downside over `rculist.h`: lookup of tail in O(n).
     43 
     44 
     45 ### `urcu/wfstack.h`
     46 
     47 Stack with wait-free push and wait-free pop\_all. Both
     48 blocking and non-blocking pop and traversal operations are provided. This
     49 stack does _not_ specifically rely on RCU. Various synchronization techniques
     50 can be used to deal with pop ABA. Those are detailed in the API.
     51 
     52 
     53 ### `urcu/wfcqueue.h`
     54 
     55 Concurrent queue with wait-free enqueue. Both blocking and
     56 non-blocking dequeue, splice (move all elements from one queue
     57 to another), and traversal operations are provided.
     58 
     59 This queue does _not_ specifically rely on RCU. Mutual exclusion
     60 is used to protect dequeue, splice (from source queue) and
     61 traversal (see API for details).
     62 
     63   - Note: deprecates `urcu/wfqueue.h`.
     64 
     65 
     66 ### `urcu/lfstack.h`
     67 
     68 Stack with lock-free push, lock-free pop, wait-free pop\_all,
     69 wait-free traversal. Various synchronization techniques can be
     70 used to deal with pop ABA. Those are detailed in the API.
     71 This stack does _not_ specifically rely on RCU.
     72 
     73   - Note: deprecates `urcu/rculfstack.h`.
     74 
     75 
     76 ### `urcu/rculfqueue.h`
     77 
     78 RCU queue with lock-free enqueue, lock-free dequeue.
     79 This queue relies on RCU for existence guarantees.
     80 
     81 
     82 ### `urcu/rculfhash.h`
     83 
     84 Lock-Free Resizable RCU Hash Table. RCU used to provide
     85 existence guarantees. Provides scalable updates, and scalable
     86 RCU read-side lookups and traversals. Unique and duplicate keys
     87 are supported. Provides "uniquify add" and "replace add"
     88 operations, along with associated read-side traversal uniqueness
     89 guarantees. Automatic hash table resize based on number of
     90 elements is supported. See the API for more details.
     91