code:
;; Tests of the non-robust linear algebra functions
;; Copyright (C) 2025  Rocks Mazama
;;
;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;;
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <https://www.gnu.org/licenses/>.

(ns mazama.linalg.sole-test
  (:require
   [clojure.test :refer [deftest is testing]]
   [mazama.linalg.sole :as sole]
   [mazama.linalg.utilities :as utilities]))

(def EPSILON 1/1000000)

(defn nearly==
  ""
  ([a b] (nearly== a b EPSILON))
  ([a b epsilon]
   (< (- epsilon) (- a b) epsilon)))

(defn- nullspace-vector?
  "Is the vector `v` in the nullspace of the matrix `A`?"
  [A v]
  (every? zero? (utilities/*mv A v)))

(defn- check-Ax==b [A x b]
  (let [Ax (utilities/*mm A x)]
    (is (== (:ncols Ax) (:ncols b)))
    (doseq [[x y] (map vector (:data Ax) (:data b))]
      (is (== x y)))))

(defn- check-general-solution
  [A b expected-nullspace-dimension]
  (let [x (sole/solve A b)]
    (check-Ax==b A x b)
    (is (== 3 (count (keys x))))
    (is (:ncols x))
    (is (:data x))
    (is (:nullspace x))
    (let [nullspace (:nullspace x)]
      (is (== expected-nullspace-dimension (count nullspace)))
      (is (every? #(nullspace-vector? A %) nullspace))
      (is (utilities/linearly-independent? nullspace)))))

(defn- check-unique-solution
  [A b]
  (let [x (sole/solve A b)]
    (check-Ax==b A x b)
    (is (== 2 (count (keys x))))
    (is (:ncols x))
    (is (:data x))))

(deftest sole-no-solutions
  (testing "lem.ma The Simplest Possible System (without a solution)"
    (let [A {:ncols 1 :data [0]}
          b {:ncols 1 :data [10]}]
      (is (nil? (sole/solve A b)))))

  (testing "http://sites.science.oregonstate.edu/math/home/programs/undergrad/CalculusQuestStudyGuides/vcalc/gauss/gauss.html"
    (let [A {:ncols 3 :data [ 2 -1  1
                              3  2 -4
                             -6  3 -3]}
          b {:ncols 1 :data [1 4 2]}]
      (is (nil? (sole/solve A b)))))

  (testing "https://www.cliffsnotes.com/study-guides/algebra/linear-algebra/linear-systems/gaussian-elimination"
    (let [A {:ncols 3 :data [ 1  1 -3
                              2  1 -1
                              3  2 -4]}
          b {:ncols 1 :data [4 2 7]}]
      (is (nil? (sole/solve A b))))))

(deftest sole-one-solution
  (testing "More equations than unknowns"
    (let [A {:ncols 2 :data  [4  7
                              5  8
                              6  9]}
          b {:ncols 1 :data [1 2 3]}]
      (check-unique-solution A b)))

  (testing "https://ocw.mit.edu/ans7870/18/18.013a/textbook/HTML/chapter32/section01.html"
    (let [A {:ncols 3 :data [ 2  3  1
                              3 -1 -2
                             -1 -1  1]}
          b {:ncols 1 :data [7 4 1]}]
      (check-unique-solution A b)))

  (testing "https://ocw.mit.edu/ans7870/18/18.013a/textbook/HTML/chapter32/exercise02.html"
    (let [A {:ncols 3 :data [ 1  3 -1
                              3  1 -2
                             -1 -1  1]}
          b {:ncols 1 :data [7 4 1]}]
      (check-unique-solution A b)))

  (testing "https://www.cliffsnotes.com/study-guides/algebra/linear-algebra/linear-systems/gaussian-elimination"
    (let [A {:ncols 2 :data [1  1
                             3 -2]}
          b {:ncols 1 :data [3 4]}]
      (check-unique-solution A b)))

  (testing "https://www.cliffsnotes.com/study-guides/algebra/linear-algebra/linear-systems/gaussian-elimination"
    (let [A {:ncols 3 :data (list 1 -2  1
                                  2  1 -3
                                  4 -7  1)}
          b {:ncols 1 :data (list 0 5 -1)}]
      (check-unique-solution A b)))

  (testing "https://www.cliffsnotes.com/study-guides/algebra/linear-algebra/linear-systems/gaussian-elimination"
    (let [A {:ncols 3 :data (seq [ 2 -2  0
                                   1 -1  1
                                   0  3 -2])}
          b {:ncols 1 :data [-6 1 -5]}]
      (check-unique-solution A b)))

  (testing "Example 5 from https://www.cliffsnotes.com/study-guides/algebra/linear-algebra/linear-systems/gaussian-elimination"
    (let [A {:ncols 3 :data [ 1/4  1/2  1
                                1    1  1
                                4    2  1]}
          b {:ncols 1 :data (seq [23/4 7 2])}]
      (check-unique-solution A b)))

  (testing "Some extraneous zero rows, using the previous test data"
    (let [A {:ncols 3 :data [   0    0  0
                              1/4  1/2  1
                                0    0  0
                                0    0  0
                                1    1  1
                                0    0  0
                                4    2  1
                                0    0  0
                                0    0  0]}
          b {:ncols 1 :data [0 23/4 0 0 7 0 2 0 0]}]
      (check-unique-solution A b)))

  (let [seed 1
        prng (utilities/prng-min-max seed -10 100)]
    (testing (str "random:vector:" seed)
      (let [[A _ b] (utilities/random-sole-unique-solution prng 13 1)]
        (check-unique-solution A b))))

  (let [seed 2
        prng (utilities/prng-min-max seed -5 5)]
    (testing (str "random:vector:" seed)
      (let [[A _ b] (utilities/random-sole-unique-solution prng 49 1)]
        (check-unique-solution A b))))

  (let [seed 3
        prng (utilities/prng-min-max seed -99999 99999)]
    (testing (str "random:matrix:" seed)
      (let [[A _ b] (utilities/random-sole-unique-solution prng 49 2)]
        (check-unique-solution A b)))))

(deftest sole-invert-matrix

  (testing "https://ocw.mit.edu/ans7870/18/18.013a/textbook/HTML/chapter32/section03.html"
    (let [A {:ncols 2 :data [ 1  3
                              5  6]}
          b {:ncols 2 :data [ 1  0
                              0  1]}]
      (check-unique-solution A b)))

  (testing "https://people.richland.edu/james/lecture/m116/matrices/inverses.html"
    (let [A {:ncols 3 :data [ 3  2 -5
                              1 -3  2
                              5 -1  4]}
          b {:ncols 3 :data [ 1  0  0
                              0  1  0
                              0  0  1]}]
      (check-unique-solution A b))))

(deftest sole-infinite-solutions
  (testing "lem.ma The Simplest Possible System (with infinite solutions)"
    (let [A {:ncols 1 :data [0]}
          b {:ncols 1 :data [0]}]
      (check-general-solution A b 1)))

  (testing "all zeros"
    (let [A {:ncols 2 :data [0 0
                             0 0]}
          b {:ncols 1 :data [0 0]}]
      (check-general-solution A b 2)))

  (testing "some zero columns"
    (let [A {:ncols 4 :data [1 0 2 0
                             2 0 4 0
                             3 0 3 0]}
          b {:ncols 1 :data [3 6 6]}]
      (check-general-solution A b 2)))

  (testing "Column with real and integer zeros"
    (let [A {:ncols 3 :data [  0  2  3
                             0.0  4 -1
                               0  3  0]}
          b {:ncols 1 :data [13 5 6]}]
      (check-general-solution A b 1)))

  (testing "lem.ma Our First Linear System: A Thorough Discussion"
    (let [A {:ncols 4 :data [1  0  4  7
                             0  1  5 11]}
          b {:ncols 1 :data [8 11]}]
      (check-general-solution A b 2)))

  (testing "lem.ma A Wide Linear System"
    (let [A {:ncols 5 :data [2 5 6 7 241]}
          b {:ncols 1 :data [6]}]
      (check-general-solution A b 4)))

  (testing "lem.ma A Look Ahead - An Illustration of Matrix Algebra"
    (let [A {:ncols 5 :data [1 2 3 4 5 3 7 10 13 16]}
          b {:ncols 1 :data [-4 -16]}]
      (check-general-solution A b 3)))

  (testing "https://math.colorado.edu/~nita/SystemsofLinearEquations.pdf Example 0.17 (look at the equations, not the matrices, which have errors."
    (let [A {:ncols 5 :data [2 3 1 4 -9
                             1 1 1 1 -3
                             1 1 1 2 -5
                             2 2 2 3 -8]}
          b {:ncols 1 :data [17 6 8 14]}]
      (check-general-solution A b 2)))

  (testing "https://www.math.ust.hk/~mabfchen/Math111/Week1-3.pdf Example 2.4"
    (let [A {:ncols 6 :data [ 0  0  1 -1  2  1
                              3  6  0  3 -3  2
                              1  2  0  1 -1  0
                              2  4 -2  4 -6 -5]}
          b {:ncols 1 :data [0 7 1 -4]}]
      (check-general-solution A b 3)))

  (testing "https://www.math.ucdavis.edu/~linear/linear-guest.pdf, section 2.1.4, Example 20"
    (let [A {:ncols 4 :data [ 1  0  7  0
                              0  1  3  4
                              0  0  0  0
                              0  0  0  0]}
          b {:ncols 1 :data [4 1 0 0]}]
      (check-general-solution A b 2)))

  (testing "https://math.vanderbilt.edu/sapirmv/msapir/gauss.html"
    (let [A {:ncols 7 :data [ 4  8 -2 -5  0 -23  2
                              1  2  2  5 -5  13 -2
                              2  4 -2 -5  2 -19  2
                              3  6  1  0  0  -1  0
                              4  8  1  2 -5  -1 -1]}
          b {:ncols 1 :data [37 3 21 22 30]}]
      (check-general-solution A b 3)))

  (testing "https://www.math.ust.hk/~mabfchen/Math111/Week1-3.pdf Example 2.2"
    (let [A {:ncols 4 :data [ 1 -1  1 -1
                              1 -1  1  1
                              4 -4  4  0
                             -2  2 -2  1]}
          b {:ncols 1 :data [2 0 4 -3]}]
      (check-general-solution A b 2))))

(deftest sole-rounding-errors

  (testing "https://www.dam.brown.edu/people/alcyew/handouts/linsys2.pdf"
    (let [A {:ncols 3 :data [10  -7       0
                             -3  2.09999  6
                              5  -1       5]}
          b {:ncols 1 :data [7  3.90001 6]}]
      (doseq [[x y] (map vector [0 -1 1] (:data (sole/solve A b)))]
        (is (nearly== x y)))))

  (testing "https://www.dam.brown.edu/people/alcyew/handouts/linsys2.pdf (as rationals)"
    (let [A {:ncols 3 :data [10  -7            0
                             -3  209999/100000 6
                              5  -1            5]}
          b {:ncols 1 :data [7  390001/100000 6]}]
      (is (= [0 -1 1] (:data (sole/solve A b))))))

  (testing "http://site.iugaza.edu.ps/emasry/files/2013/01/Ch9-Gauss_Elimination4.pdf"
    (let [A {:ncols 2 :data [ 2.5  6.2
                              4.8 -8.6]}
          b {:ncols 1 :data [3 5.5]}]
      (doseq [[x y] (map vector [1.168552478 0.01268045242] (:data (sole/solve A b)))]
        (is (nearly== x y)))))

  (testing "http://site.iugaza.edu.ps/emasry/files/2013/01/Ch9-Gauss_Elimination4.pdf"
    (let [A {:ncols 3 :data [ 3.0 -0.1 -0.2
                              0.1  7.0 -0.3
                              0.3 -0.2 10.0]}
          b {:ncols 1 :data [7.85 -19.3 71.4]}]
      (doseq [[x y] (map vector [3.0 -2.5 7.0] (:data (sole/solve A b)))]
        (is (nearly== x y)))))

  (testing "http://site.iugaza.edu.ps/emasry/files/2013/01/Ch9-Gauss_Elimination4.pdf (as rationals)"
    (let [A {:ncols 3 :data [ 30/10 -01/10 -02/10
                              01/10  70/10 -03/10
                              03/10 -02/10 100/10]}
          b {:ncols 1 :data [785/100 -193/10 714/10]}]
      (is (= [30/10 -25/10 70/10] (:data (sole/solve A b)))))))


code:
;; Utilities for the non-robust linear algebra functions
;; Copyright (C) 2025  Rocks Mazama
;;
;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.
;;
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with this program.  If not, see <https://www.gnu.org/licenses/>.

(ns mazama.linalg.utilities
  (:require
   [mazama.linalg.matrix :as matrix]
   [mazama.linalg.sole :as sole]))

(defn +v
  "Add two vectors, `u` and `v`.
  If the number of components differ then the result is undefined."
  ([u] u)
  ([u v] (map + u v)))

(defn *v
  "Multiply a scalar `c` and a vector `v`."
  [c v]
  (map #(* % c) v))

(defn linear-combination
  "Create a linear combination from the vectors `vs` and coefficients `cs`.
  If the number of elements or components differ then the result is undefined."
  [vs cs]
  (let [product (map *v cs vs)]
    (if (empty? product)
      []
      (reduce +v product))))

(defn dot-product
  "Compute the dot product of two vectors.
  If the number of components differ then the result is undefined."
  [u v]
  ;; Slower alternative...
  ;; (reduce + 0 (map * u v))
  (loop [u u
         v v
         result 0]
    (if (or (empty? u) (empty? v))
      result
      (recur (rest u) (rest v) (+ result (* (first u) (first v)))))))

(defn *mv
  "Multiply a matrix A and a vector `x` to form the vector Ax."
  [{:keys [ncols data]} x]
  (->> data
       (map * (cycle x))
       (partition ncols)
       (map #(reduce + %))))

(defn *mm
  "Multiply a matrix `A` by a matrix `B` to form the matrix AB."
  [A B]
  ;; Slower alternative...
  ;;  (->> B
  ;;       (matrix/columns)
  ;;       (map #(*mv A %))
  ;;       (matrix/columns->matrix))
  (let [bcolumns (matrix/columns B)]
    (loop [arows (matrix/rows A)
           bcols bcolumns
           data []]
      (cond
        (empty? arows) {:ncols (:ncols B) :data data}
        (empty? bcols) (recur (rest arows) bcolumns data)
        :else (recur arows
                     (rest bcols)
                     (conj data (dot-product (first arows) (first bcols))))))))

(defn linear-combination?
  "Is `v` a linear combination of the vectors `vs`?"
  [v vs]
  (sole/solve (matrix/columns->matrix vs) {:ncols 1 :data v}))

(defn linearly-independent?
  "Are the vectors in the collection `vs` linearly independent?"
  [vs]
  (let [A (matrix/columns->matrix vs)
        b {:ncols 1 :data (repeat (/ (count (:data A)) (:ncols A)) 0)}
        x (sole/solve A b)]
    (and x (nil? (:nullspace x)))))

(defn random-seq [prng count]
  (repeatedly count prng))

(defn prng-bound [seed bound]
  (let [frand (java.util.Random. seed)]
    (fn [] (.nextInt frand bound))))

(defn prng-min-max
  "Return a pseudo-random number generator using seed.
  Each call to the prng returns min <= value <= max."
  [seed min max]
  (let [bound (inc (- max min))
        rndm (prng-bound seed bound)]
    (fn [] (+ min (rndm)))))

(defn random-matrix
  "Return a nxm matrix using prng to generate values"
  [prng n m]
  {:ncols m :data (random-seq prng (* n m))})

(defn random-sole-unique-solution
  "Return a System of Linear Equations Ax=b that has a unique solution.
    A is an nxn matrix,
    x is an nxp matrix,
    b is an nxp matrix.
    The elements of A and x are generated by prng."
  [prng n p]
  (let [A (random-matrix prng n n)
        x (random-matrix prng n p)
        b (*mm A x)]
    (vector A x b)))


code:
build
dist
usts.egg-info
usts/__pycache__

path: .gitignore

license: mit


code:
# usts

Simple cli tool for creating status text to something like dwm-bar.

## Items

| Item              | Dependencies | Description                                          |
| :---:             | :---         | :---                                                 |
| `time`            | `datetime`   | Display current time with strftime formating.        |
| `cpu_usage`       | `psutil`     | Display percent of cpu usage.                        |
| `memory_usage`    | `psutil`     | Display memory usage (percent, available, etc...)    |
| `cryptocurrency`  | `requests`   | Display cryptocurrency from coingecko.com api.       |

## Installation

```sh
pip install usts
```

## ~/.config/usts/config.py example

```py
# import make functions from mkitems.py file
from usts.mkitems import *

# setup list of items
items = [
    make_cpu_usage(),
    make_memory_usage(),
    make_time(),
]

# Execute is action with status
#   setxroot -> setxroot -name "status"
#   stdout   -> just print status in terminal
execute = "stdout"
```

## Usage

```sh
usts
```

## Contacts

| Contact                                               | Description       |
| :---:                                                 | :---              |
| [`Matrix`](https://matrix.to/#/#librehub:matrix.org)  | Matrix server.    |
| [`Discord`](https://discord.gg/naGkzRN)               | Discord server.   |

## Donates
**Monero:** `47KkgEb3agJJjSpeW1LpVi1M8fsCfREhnBCb1yib5KQgCxwb6j47XBQAamueByrLUceRinJqveZ82UCbrGqrsY9oNuZ97xN`


code:
import usts
from setuptools import setup

with open("README.md", "r") as file_stream:
    readme = file_stream.read()

setup(
    long_description=readme,
    long_description_content_type="text/markdown",
    name="usts",
    version=usts.__version__,
    description="Simple cli tool for creating status text to something like dwm-bar.",
    url="https://notabug.org/loliconshik3/usts",
    author="loliconshik3",
    packages=["usts"],
    entry_points={"console_scripts": ["usts = usts.__main__:main"]},
)


code:
"""
Simple cli tool for creating status text to something like dwm-bar.
"""
__version__ = "0.1.0"


code:
from usts.usts import UStatus
import sys

def main():
    ustatus = UStatus()
    sys.exit(ustatus.exec())

if __name__ == "__main__":
    main()


code:
import configparser
import importlib
import sys
import os

class Config:

    def __init__(self):
        self.config = configparser.ConfigParser()

        self.home_dir           = os.path.expanduser('~')
        self.config_dir_path    = self.home_dir + "/.config/usts/"
        self.config_path        = self.config_dir_path + "config.py"

        sys.path.append(self.config_dir_path)

        self.make_config_dir()
        self.load_config()

    def is_config_exists(self):
        return os.path.exists(self.config_path)

    def make_config_dir(self):
        os.makedirs(self.config_dir_path, exist_ok=True)

    def load_config(self):
        if not self.is_config_exists(): return None, None
        pfile = importlib.import_module("config")
        return pfile.items, pfile.execute


code:
import threading
import time

class Item:

    def __init__(self, execute, periodic: float=1.0) -> None:
        self.text = ""
        self.periodic = periodic
        self.execute = execute
        self.is_exec = True

        self.thread = threading.Thread(target=self.update)

    def update(self) -> None:
        while self.is_exec:
            self.text = self.execute()
            if self.periodic == -1: return
            time.sleep(self.periodic)
        return

    def exec(self) -> None:
        self.thread.start()


code:
from .item import Item
from .utils import *

def make_str(value: str):
    execute = lambda: value
    return Item(execute, periodic=-1)

def make_time(timestrf: str="%m/%d/%Y %H:%M:%S", periodic: float=1.0) -> Item:
    try: import datetime
    except: raise ImportError("datetime module not found!")

    execute = lambda: datetime.datetime.now().strftime(timestrf)
    return Item(execute, periodic)

def make_cpu_usage(str_format: str="CPU: {data}%", periodic: float=1.0) -> Item:
    try: import psutil
    except: raise ImportError("psutil module not found!")

    execute = lambda: str_format.replace("{data}",
        str(psutil.cpu_percent())
    )

    return Item(execute, periodic)

def make_memory_usage(str_format: str="RAM: {data}",
                      data_type: str="percent", data_format: str="%",
                      periodic: float=1.0) -> Item:
    try: import psutil
    except: raise ImportError("psutil module not found!")

    str_format += data_format
    execute = lambda: str_format.replace("{data}",
        str(format_bytes(
            psutil.virtual_memory().__getattribute__(data_type),
            data_format)
        ))

    return Item(execute, periodic)

def make_cryptocurrency(str_format: str="Monero: {data}$", coin: str="monero",
                        currency: str="usd", periodic: float=60.0) -> Item:
    try: import requests
    except: raise ImportError("requests module not found!")

    request_url = f'https://api.coingecko.com/api/v3/simple/price?ids={coin}&vs_currencies={currency}'
    execute = lambda: str_format.replace("{data}",
        str(requests.get(request_url).json()[coin][currency]))

    return Item(execute, periodic)


code:
from .cfg import Config
from .mkitems import *

import datetime
import time
import os

class UStatus:

    def __init__(self, execute="stdout", update_periodic: float=1.0, separator: str=' | '):
        """
        :param execute [stdout / setxroot]  -> do actions with status:
            stdout      - just print it,
            setxroot    - setxroot -name "status"
        :param update_periodic              -> time when status is updated
        :param separator                    -> separator between items
        """
        self.is_exec            = True
        self.update_periodic    = update_periodic
        self.separator          = separator
        self.items              = self.make_items()

        self.config = Config()
        citems, cexecute = self.config.load_config()
        if not cexecute is None: execute = cexecute
        if not citems is None: self.items = citems

        self.execute = self.make_execute(execute)

    def make_execute(self, execute_str):
        execs = {
            "stdout"    : self.stdout,
            "setxroot"  : self.xsetroot,
        }
        if not execute_str in execs.keys():
            raise KeyError(f"{execute_str} not in execute list!")
        return execs[execute_str]

    def make_items(self) -> list:
        return [
            make_cpu_usage(),
            make_memory_usage(),
            make_time(),
        ]

    def make_status_string(self) -> str:
        status = ""
        if self.items is None: return status

        for item in self.items:
            status += item.text + self.separator
        return status[:-len(self.separator)]

    def stdout(self):
        status = self.make_status_string()
        print(f"\r{(len(status)+10) * ' '}", end='\r')
        print(f"\r{status}", end='\r')

    def xsetroot(self):
        status = self.make_status_string()
        try: os.system(f'xsetroot -name "{status}"')
        except Exception as e: raise e

    def wait_for_zero_time(self):
        now = datetime.datetime.now()
        wait = 1000000 - now.microsecond
        time.sleep(wait/1000000)

    def exec(self):
        self.wait_for_zero_time()
        for item in self.items:
            item.exec()
        while self.is_exec:
            self.execute()
            time.sleep(self.update_periodic)
        for item in self.items:
            item.is_exec = False


code:
def format_bytes(size, data_format):
    if not data_format in ['b', 'Kb', 'Mb', 'Gb', 'Tb']: return size
    # 2**10 = 1024
    power = 2**10
    n = 0
    power_labels = {0 : 'b', 1: 'Kb', 2: 'Mb', 3: 'Gb', 4: 'Tb'}
    while power_labels[n] != data_format:
        size /= power
        n += 1
    return round(size, 1)


code:
.*
*.o
*.lo
*.out
*.swp
*.so
*.a
tst
config.mak

repo_name: avarzille/xrcu


code:
Revision history for XRCU

0.1 19/03/2019
  - First public version

path: Changes


code:
STATIC_LIBS = libxrcu.a
SHARED_LIBS = libxrcu.so

HEADERS = xrcu.hpp stack.hpp hash_table.hpp skip_list.hpp   \
          xatomic.hpp lwlock.hpp optional.hpp queue.hpp

OBJS = xrcu.o hash_table.o stack.o lwlock.o skip_list.o queue.o
LOBJS = $(OBJS:.o=.lo)

TEST_OBJS = $(LOBJS)

-include config.mak

ALL_LIBS = $(STATIC_LIBS) $(SHARED_LIBS)

AR = $(CROSS_COMPILE)ar
RANLIB = $(CROSS_COMPILE)ranlib
CXXFLAGS += $(CXXFLAGS_AUTO)

all: $(ALL_LIBS)

check: $(TEST_OBJS)
	$(CXX) $(CXXFLAGS) tests/test.cpp $(TEST_OBJS) -o tst
	./tst

%.o: %.cpp $(HEADERS)
	$(CXX) $(CXXFLAGS) -c $< -o $@

%.lo: %.cpp $(HEADERS)
	$(CXX) $(CXXFLAGS) -fPIC -c $< -o $@

libxrcu.a: $(OBJS)
	rm -f $@
	$(AR) rc $@ $(OBJS)
	$(RANLIB) $@

libxrcu.so: $(LOBJS)
	$(CXX) -fPIC -shared $(CXXFLAGS) -o $@ $(LOBJS)

install: $(ALL_LIBS)
	mkdir -p $(includedir)/xrcu
	cp libxrcu* $(libdir)/
	cp $(HEADERS) $(includedir)/xrcu

clean:
	rm -rf *.o *.lo libxrcu.* tst

path: Makefile


code:
XRCU is a library that provides efficient lockless synchronization for
read-mostly tasks and structures.


code:
#! /bin/sh

usage () {
cat <<EOF
Usage: $0 [option]... [var=value]... [target]

In order to set environment variables (like CXX), you have to specify them as
var=value. See below for descriptions of some of them.

Default values are specified in brackets.

Configuration settings:
  --srcdir=dir            source directory [auto detected]

Installation directories:
  --prefix=prefix         main installation prefix [/usr/local]
  --libdir=dir            library files [prefix/lib]
  --includedir=dir        include files [prefix/include]

System types:
  --target=target         configure to run on target [auto detected]
  --host=host             same as target
  --build=build           build system, used to detect cross compiling

Optional features:
  --enable-debug          build with debug symbols [no]
  --enable-warnings       build with extensive warnings [yes]
  --enable-shared         build shared library [yes]
  --enable-static         build static library [no]
  --max-finalizers=N      maximum number of pending finalizers

Environment variables you may set:
  CXX                     C++ compiler [auto detected]
  CXXFLAGS                C++ compiler flags [-O2 -pipe ...]
  CROSS_COMPILE           prefix for cross compiler and tools [not set]

These variables may be set to override detections made by configure.

EOF
exit 0
}

quote () {
tr '\n' ' ' <<EOF | grep '^[-[:alnum:]_=,./:]* $' >/dev/null 2>&1 && { echo "$1" ; return 0 ; }
$1
EOF
printf %s\\n "$1" | sed -e "s/'/'\\\\''/g" -e "1s/^/'/" -e "\$s/\$/'/" -e "s#^'\([-[:alnum:]_,./:]*\)=\(.*\)\$#\1='\2#"
}

echo () { printf "%s\n" "$*" ; }

fail () { echo "$*" ; exit 1 ; }

fnmatch () { eval "case \"\$2\" in $1) return 0 ;; *) return 1 ;; esac" ; }

cmdexists () { type "$1" >/dev/null 2>&1 ; }

trycxx () { test -z "$CXX" && cmdexists "$1" && CXX=$1 ; }

stripdir () {
  while eval "fnmatch '*/' \"\${$1}\"" ; do eval "$1=\${$1%/}" ; done
}

tryflag () {
  printf "checking whether compiler accepts %s... " "$2"
  echo "typedef int x;" > "$tsrc"
  if $CXX $CXXFLAGS_TRY $2 -c -o /dev/null "$tsrc" >/dev/null 2>&1 ; then
    printf "yes\n"
    eval "$1=\"\${$1} \$2\""
    eval "$1=\${$1# }"
    return 0
  else
    printf "no\n"
    return 1
  fi
}

CXXFLAGS_EXTRA=
CXXFLAGS_AUTO=
CXXFLAGS_TRY=
srcdir=
prefix=/usr/local
libdir='$(prefix)/lib'
includedir='$(prefix)/include'
debug=no
warnings=yes
shared=yes
static=no
maxfins=1000

for arg ; do
case "$arg" in
  --help|-h) usage ;;
  --srcdir=*) srcdir=${arg#*=} ;;
  --prefix=*) prefix=${arg#*=} ;;
  --libdir=*) libdir=${arg#*=} ;;
  --includedir=*) includedir=${arg#*=} ;;
  --syslibdir=*) syslibdir=${arg#*=} ;;
  --enable-shared|--enable-shared=yes) shared=yes ;;
  --disable-shared|--enable-shared=no) shared=no ;;
  --enable-static|--enable-static=yes) static=yes ;;
  --disable-static|--enable-static=no) static=no ;;
  --enable-debug|--enable-debug=yes) debug=yes ;;
  --disable-debug|--enable-debug=no) debug=no ;;
  --enable-warnings|--enable-warnings=yes) warnings=yes ;;
  --disable-warnings|--enable-warnings=no) warnings=no ;;
  --enable-*|--disable-*|--with-*|--without-*|--*dir=*) ;;
  --host=*|--target=*) target=${arg#*=} ;;
  --build=*) build=${arg#*=} ;;
  --max-finalizers=*) maxfins=${arg#*=} ;;
  -* ) fail "$0: unknown option '$arg'" ;;
  CXX=*) CXX=${arg#*=} ;;
  CXXFLAGS=*) CXXFLAGS=${arg#*=} ;;
  LDFLAGS=*) LDFLAGS=${arg#*=} ;;
  CROSS_COMPILE=*) CROSS_COMPILE=${arg#*=} ;;
  *=*) ;;
  *) build=$arg ; target=$arg ;;
esac
done

for i in srcdir prefix libdir includedir ; do
  stripdir $i
done

# See if we're building out of tree.

if test -z "$srcdir" ; then
  srcdir="${0%/configure}"
  stripdir srcdir
fi

abs_builddir="$(pwd)" || fail "$0: cannot determine working directory"
abs_srcdir="$(cd $srcdir && pwd)" || fail "$0: invalid source directory $srcdir"
test "$abs_srcdir" = "$abs_builddir" && srcdir=.
test "$srcdir" != "." -a -f Makefile -a ! -h Makefile && fail "$0: Makefile already exists in the working directory"

# Generate a temporary directory.
set -C
tdir=$(mktemp -d "$(basename $0).XXXXXXX")
set +C
trap 'rm -rf "$tdir"' EXIT INT QUIT TERM HUP

tsrc="$tdir/tx.cpp"
texe="$tdir/texe"

# For cross-compiling, set a default CROSS_COMPILE if it wasn't provided.
test "$target" && \
test "$target" != "$build" && \
test -z "$CROSS_COMPILE" && \
CROSS_COMPILE="$target-"

# Set C++ compiler.
printf "checking for C++ compiler..."
trycxx ${CROSS_COMPILE}g++
trycxx ${CROSS_COMPILE}clang++
trycxx ${CROSS_COMPILE}icc
trycxx ${CROSS_COMPILE}cxx
printf "%s\n" "$CXX"
test -n "$CXX" || { echo "$0: cannot find a C++ compiler" ; exit 1 ; }

printf "checking whether C++ compiler works... "
echo "typedef int x;" > "$tsrc"
if output=$($CXX $CXXFLAGS -c -o /dev/null "$tsrc" 2>&1) ; then
  printf "yes\n"
else
  printf "no; compiler output follows:\n%s\n" "$output"
  exit 1
fi

# Find out options to force errors on unknown compiler/linker flags.
tryflag CXXFLAGS_TRY -Werror=unknown-warning-option
tryflag CXXFLAGS_TRY -Werror=unused-command-line-argument
tryflag CXXFLAGS_TRY -Werror=ignored-optimization-argument

# Try to avoid executable stacks in GNU compilers.
tryflag CXXFLAGS_EXTRA -Wa,--noexecstack

# See if the compiler accepts explicit standard versioning
tryflag CXXFLAGS -std=c++11

# Enable optimizations
tryflag CXXFLAGS -O2

# Enable debugging if needed.
test "x$debug" = xyes && tryflag CXXFLAGS_AUTO -g

# Always try to use -pipe.
tryflag CXXFLAGS_AUTO -pipe

# See if we can link against pthreads with a compiler switch.
tryflag CXXFLAGS_AUTO -pthread

if test "x$warnings" = xyes ; then
  tryflag CXXFLAGS_AUTO -Wall
  tryflag CXXFLAGS_AUTO -Wno-parentheses
  tryflag CXXFLAGS_AUTO -Wno-uninitialized
  tryflag CXXFLAGS_AUTO -Wno-missing-braces
  tryflag CXXFLAGS_AUTO -Wno-unused-value
  tryflag CXXFLAGS_AUTO -Wno-unused-but-set-variable
  tryflag CXXFLAGS_AUTO -Wno-unknown-pragmas
fi

case $maxfins in
  ''|*[!0-9]*) fail "--max-finalizers must be an integer" ;;
  *) ;;
esac

# generate version file
version=$(cat $srcdir/VERSION)
major=$(echo $version | cut -d. -f1)
minor=$(echo $version | cut -d. -f2)
echo "const int MAJOR = $major; const int MINOR = $minor;" > $srcdir/version.hpp

printf "creating config.mak... "

cmdline=$(quote "$0")
for i ; do cmdline="$cmdline $(quote "$i")" ; done

exec 3>&1 1>config.mak

cat << EOF
# This version of config.mak was generated by:
# $cmdline
# Any changes made here will be lost if configure is re-run
srcdir = $srcdir
prefix = $prefix
libdir = $libdir
includedir = $includedir
CXX = $CXX
CXXFLAGS = $CXXFLAGS -DXRCU_MAX_FINS=$maxfins
CXXFLAGS_AUTO = $CXXFLAGS_AUTO
CXXFLAGS_EXTRA = $CXXFLAGS_EXTRA
LDFLAGS = $LDFLAGS
CROSS_COMPILE = $CROSS_COMPILE
EOF
test "x$static" = xno && echo "STATIC_LIBS ="
test "x$shared" = xno && echo "SHARED_LIBS ="
test "x$shared" = xno && echo 'TEST_OBJS = $(OBJS)'
exec 1>&3 3>&-

test "$srcdir" = "." || ln -sf $srcdir/Makefile .

printf "done\n"

path: configure


code:
<?xml version="1.0" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<title>XRCU Documentation</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />

NAME

ABOUT THIS DOCUMENT

ABOUT LOCK FREE ALGORITHMS AND STRUCTURES

ABOUT RCU

API design

RCU API

RCU critical section management

RCU finalizable objects

Miscellaneous functions

Implementation details

Interlude: optionals

Optional API

Implementation details

Stacks

Stack API

Implementation details

Skip lists

Skip list API

Implementation details

Hash tables

Hash table API

Implementation details

BUGS

AUTHORS

NAME

XRCU is a library that provides efficient lock-less synchronization for read-mostly tasks and structures

ABOUT THIS DOCUMENT

This file is meant to document the XRCU library, including internal details and the rationale behind the decisions taken.

This document assumes that the reader is at least somewhat familiar with such concepts as multi-threading, lock-free algorithms and data structures, and read-copy-update (RCU).

ABOUT LOCK FREE ALGORITHMS AND STRUCTURES

The term lock free is used to refer to several different things depending on the author, but the basic idea is that an algorithm or structure is lock free if multiple threads can operate on it without the end result being dependent on said threads' scheduling. That is, it doesn't matter if the involved threads are suspended or preempted; progress is guaranteed.

The usually mentioned advantage of lock freedom is performance. When you are using lock free algorithms, you naturally avoid using things like mutexes, which can have a non-negligible performance impact. On the other hand, other people point out that lock free algorithms are typically harder to understand, that debugging is notoriously difficult, and that the benefits generally do not compensate for these complexities.

The reason why this library was developed is to give other programmers another option when designing high performant, low latency systems. We do not claim that lock freedom is a silver bullet when it comes to making programs faster. On the other hand, it's also hard to argue that lock contention tends to be a real bottleneck, and several projects have moved towards lock free structures given the performance benefits they bring (see for example, many kernels).

ABOUT RCU

There is a big problem with using lock free algorithms in programming languages that feature manual memory management, and it has to do with memory reclamation. Since lock freedom implies that multiple threads may operate on a given structure concurrently, it is possible to find ourselves in a situation in which a thread is reading some data, while another one is deleting that same piece of data, potentially freeing the memory associated to it.

As such, lock freedom needs an additional twist in languages like C and C++. We need an additional subsystem that allows us to synchronize reclamation without using heavyweight methods like mutexes (we are developing a lock-free library, after all).

This is where RCU comes in. RCU, short for read-copy-update, is a mechanism that allows multiple threads to read from memory, while postponing reclamations until it is safe to do so (i.e: until no readers are operating on said memory). RCU typically assumes that updates are performed using atomic instructions, and isn't concerned with them (At least, that's the case in this library).

There are several different ways to implement RCU, and the one chosen in this library will be detailed later. For now, it's important to point out that RCU typically makes reading from shared memory a very cheap operation, while imposing more overhead on updates. Thus, it's more suited for tasks in which reads are more frequent than modifications.

It should be noted that RCU is not the only way to manage memory reclamations in a multi-threaded environment, but as its name implies, XRCU chose it because it was deemed the best option. Since our lock-free structures rely on RCU to work properly, we'll describe the RCU interface that this library exposes first.

API design

All public interfaces (functions, types, methods, etc) reside in the namespace xrcu. It's the explicit intent of the authors to mantain compatibility with every interface that was ever exposed. Any breaking changes should be done in different interfaces (either by adding new functions, or by overloading).

The implementation of some template types require additional, internal details, and those usually reside in a namespace appropriately named detail (Said namespace is inside xrcu). It goes without saying that users should not rely on those internal details, and that the authors may freely break compatibility with them.

XRCU uses some thread-specific data in order to function properly. There may be some systems that have issues when dynamically loading libraries that use thread-specific data (I believe Windows Vista was among them). Consult with your working environment's manual to verify that if you notice any problem.

Finally, it should be mentioned that XRCU requires no initializatio or cleanup at a library level to function properly. Once the library is installed, you can freely use its API without any further action needed.

Note that XRCU may expose more functions or types that are specified in this document. This is usually done to avoid code bloat. Anything that isn't included in this file should be treated as private and subject to change.

RCU API

  #include <xrcu/xrcu.hpp>

The following section documents the RCU API that is exposed in XRCU. It's used internally quite a bit by other parts of the library, yet it's very useful by itself when implementing other concurrent algorithms or data structures.

RCU critical section management

RCU is based on the concept of critical sections, code fragments that are executed under the guarantee that no reclamation can take place. This allows the user to safely read from shared memory, knowing that it will be valid during the critical section. Writes have to be synchronized independently of RCU, however.

Naturally, RCU critical sections don't prevent all memory reclamation, they only affect the destruction of objects that are derived from a type defined in XRCU, called finalizable. If you wish to use the RCU API, all you need to do is make your types derive from finalizable and use its API, and you'll be set. Any other memory management function, like malloc and friends is unaffected by RCU as implemented in this library.

Critical sections are managed through the following API:

void enter_cs (void);

Makes the calling thread enter a critical section. Critical sections can be safely nested without problem. As long as we are in one, finalizable objects cannot be reclaimed.

void exit_cs (void);

Exits a critical section. This is generally called after the calling thread is done reading from shared memory, and wants to signal that reclamations should be re-allowed. The effects of calling exit_cs when the calling thread is not in a critical section are undefined.

bool in_cs (void);

Returns true if the calling thread is in a critical section; false otherwise.

bool sync (void);

Waits until all threads are outside pre-existing critical sections, and returns true afterwards. If a deadlock is detected (because the calling thread is in a critical section, for example), this function returns false immediately without waiting.

struct cs_guard

This type is defined such that its constructor calls enter_cs, and its destructor calls exit_cs; it has no internal state. As its name implies, it's useful as a guard to manage entering and exiting a critical section in a way that is exception safe. A few types in this library are derived from cs_guard, such as iterators, since they need to examine potentially many elements from a container without their memory being reclaimed.

RCU finalizable objects

As it was mentioned before, XRCU defines a type called finalizable that is specifically designed to make its destruction safe (i.e: Only once all threads are outside a critical section). This type defines the following interface:

  struct finalizable
    {
      virtual void safe_destroy ();
      virtual ~finalizable ();
    };

Under most circumstances, it's enough for a user-defined type to derive from finalizable and leave it at that. However, the above 2 methods are provided as virtual for customization's sake. When a finalizable object is reclaimed by the RCU subsystem, it will call the safe_destroy method. The default implementation simply calls the object's destructor and frees the memory associated to it. If, for whatever reason, a user wants to override this behaviour, they may do so by extending either of those methods.

In addition, the following API is available when dealing with finalizables:

void finalize (finalizable *F);

Adds the object F to the calling thread's list of pending finalizable objects. Each thread has a limit on the number of pending finalizables. Once that limit is reached, they are scheduled for reclamation, and will be collected once it's safe to do so.

Only a single call to finalize is allowed on a particular object. If this function is called more than once on the same object (Either by the same thread, or another), the behaviour is undefined.

bool flush_finalizers (void);

Schedule all the calling thread's accumulated finalizable objects for reclamation immediately. Returns true if successful, false if a deadlock was detected. Note that this call may block until all threads are outside a critical section (Much as a call to sync would).

Once a thread exits, an implicit call to this function is made.

Miscellaneous functions

These functions don't really belong anywhere else, but they are included in this file for convenience's sake:

    struct atfork
      {
        void (*prepare) (void);
        void (*parent) (void);
        void (*child) (void);
      };

atfork atfork_data ();

Returns a structure that implements the needed callbacks for XRCU to mantain a consistent state across calls to fork. The returned callbacks should be passed to pthread_atfork (or similar). XRCU itself does not install these callbacks, because most calls to fork are followed immediately after exec, and because multi-threaded programs that call fork are rare.

void library_version (int& major, int& minor);

Returns the library version as a pair of major, minor. Useful to assert that a program is using the correct version (at runtime).

Implementation details

There are many ways to implement RCU. In this library, it was fundamental that RCU be implemented in a portable, simple way, even if it meant slightly more overhead. As such, things like signals and OS-specific syscalls were out.

In the end, for XRCU, we decided to use a global registry that uses a stamp to monitor which threads are in critical sections. By using C++ thread_local objects, we avoid the need for explicit registration, so that when a thread first uses the RCU API, it is added automatically to the global registry.

In order to enter a critical section, all a thread has to do is read a global counter, usually bump it by some small value, and then store that value with release semantics in its thread-specific data. Exiting a critical section is almost entirely symmetric (We decrement the thread-specific value), but with a small caveat that will be explained below.

When an object is finalized, it's prepended to a singly-linked list that is also kept in thread-specific storage. Once a certain number of them have been accumulated (specified by the constant XRCU_MAX_FINS), they are scheduled to be reclaimed. However, if the calling thread is inside a critical section at that point, a special flag is set instead, that tells the thread to immediately flush its finalizable objects once it's outside the critical section.

In this implementation, the most expensive operation is undoubtedly sync. It works by locking the global registry, then checking if any thread is in a critical section, and sleeping for short periods of time in case there are. The overhead associated to sync is the main reason why critical sections should be short, and also why finalizable objects are accumulated instead of being reclaimed right away.

Interlude: optionals

    #include <xrcu/optional.hpp>

Before moving on to the topic of containers, we need to take a look at an auxiliary structure implemented to make things easier and more convenient for users. This is the optional type.

An optional is a template type that can hold either an object of type T, or be in an uninitialized state. In other words, the value may or may not be present. Unlike the usage of a pointer which may be null, an optional never performs dynamic memory allocation, as the space required to hold the value is always there, even if it's not being used.

Optional types have been standardized in C++17, and are present in many other libraries as well. However, since XRCU aims to work with the base minimum of C++11 compliant compilers, and because it's designed not to depend on other libraries or frameworks, it contains its own (lightweight) implementation.

Optional API

An optional is defined as such:

    template <class T>
    struct optional
      {
      };

And its public interface is the following:

optional ();

Default constructor. Initializes the optional without a value.

optional (const T& value);

Initializes the optional to contain value.

optional (const optional<T>& other);

Copy constructor. If other has a value, then it initializes the optional to contain that same value. Otherwise, the optional will contain no value.

optional (T&& value);

Move constructor. Initializes the optional by taking ownership of value.

optional (optional<T>&& other);

Move constructor. If other has a value, then the optional is initialized by taken ownership of it. Otherwise, the optional will have no value.

T& operator* ();

const T& operator* () const;

Returns a (possibly const) reference to the optional's value. The results are undefined if the optional does not contain one.

T* operator-> ();

const T* operator-> () const;

Returns a (possibly const) pointer to the optional's value. The results are undefined if the optional does not contain one.

bool has_value () const;

Returns true if the optional has a value.

void reset () const;

If the optional contains a value, call its destructor and make the optional contain no value afterwards. Otherwise, there are no effects.

optional& operator= (const optional<T>& other);

If other has a value, assigns it to the optional. Otherwise, calls reset on the optional and leaves it without a value. Returns *this.

optional& operator= (const T& value);

Assigns value to the optional. Returns *this.

optional& operator= (optional<T>&& other);

If other has a value, assigns it to the optional by moving it. Otherwise, calls reset on the optional and leaves it without a value. Returns *this.

optional& operator= (T&& value);

Assigns value to the optional by moving it. Returns *this.

~optional ();

Destroys the value associated to the optional, if it had any.

Implementation details

Optionals are rather simple: They are implemented by using a union that supresses the constructor of the template type, and a flag that marks whether the optional has a value or not.

Optionals are very useful when performing lookups in mapped containers, since they allow us to bypass the need of additional output parameters to determine if a search was successful in an atomic way.

Stacks

  #include <xrcu/stack.hpp>

Stacks are the simplest of the lock-free data structures: They represent a basic LIFO stack on which you can push and pop items, one at a time. Although their functionality is a bit more limited than other structures, they are still very useful to implement things like atomic free lists.

In XRCU, stacks meet the requirements for the C++ concept of Container.

Stack API

Stacks are templated types, that can be instantiated with a type T:

  template <class T>
  struct stack
    {
      struct iterator
        {
        };

      struct const_iterator
        {
        };
    };

In C++'s parlance, a stack iterator is a forward iterator, and it may be used in any function that accepts them.

A stack iterator is a cs_guard, which means that an implicit critical section is entered when one is created, and is extended until its destruction.

The following describes the public interface for stack<T>

stack ();

Default constructor. Initializes a stack to be empty.

template <class Integer> stack (Integer n, T value);

Initializes a stack to contain n times value.

template <class Iter> stack (Iter first, Iter last);

Initializes a stack with the values in the range [first, last)

stack (std::initializer_list<T> lst);

Initializes a stack with the values in lst.

stack (const stack<T>& other);

Copy constructor. Initializes a stack with the values in other.

stack (stack<T>&& other);

Move constructor. Takes ownership of the values in other.

void push (const T& value);

Pushes value to the top of the stack.

template <class Iter> void push (Iter first, Iter last)

Pushes the values in the range [first, last) to the stack.

template <class Integer> void push (Integer n, T value)

Pushes n times value to the stack.

template<class ...Args> void emplace (Args&& ...args)

Same as push, only it constructs a new item by calling the move constructor with args....

optional<T> pop ();

Removes the item at the top of the stack, and returns an optional with that value. If the stack is empty, the method returns an optional with no value.

optional<T> top ();

Fetches the current item at the top of the stack, and returns an optional with it as its value. If the stack is empty, returns an optional with no value.

size_type size () const;

Returns the current size of the stack.

size_type max_size () const;

Returns the maximum allowed size for the stack.

bool empty () const;

Returns true if the stack is empty (equivalent to size () == 0).

void swap (stack<T>& other);

Swaps the contents of the stack with other, but only if other is not the same object.

stack<T>& operator= (const stack<T>& other);

Assigns the contents of other to the stack and returns *this.

stack<T>& operator= (stack<T>&& other);

Move assignment. Takes ownership of the elements in other. Returns *this.

bool operator== (const stack<T>& other) const;

Compares the elements of the stack with the ones in other. Returns true if they are all equal.

bool operator!= (const stack<T>& other) const;

Compares the elements of the stack with the ones in other. Returns true if any two of them are not equal.

bool operator< (const stack<T>& other) const;

bool operator> (const stack<T>& other) const;

bool operator<= (const stack<T>& other) const;

bool operator>= (const stack<T>& other) const;

Lexicographically compares the elements of the stack with the ones in other, in a way that is equivalent to calling std::lexicographical_compare.

void clear ();

Removes every element from the stack.

template <class T1, class T2> void assign (T1 x, T2 y);

Assigns to the stack the elements described by (x, y). They could be an iterator range, or a pair of (integer, value), as is the case with the stack's constructor.

void assign (std::initializer_list<T> lst);

Assigns to the stack the items in lst.

iterator begin ();

const_iterator cbegin () const;

Returns an iterator to the first element of the stack.

iterator end ();

const_iterator cend () const;

Returns an iterator one past the last element of the stack.

iterator::iterator ();

Default constructor for stack iterators. Leaves the object in an invalid state. Dereferencing or incrementing such an iterator has undefined behavior.

iterator::iterator (const iterator& other);

Copy constructor. Initializes the iterator to be equal to other.

T& iterator::operator* ();

const T& const_iterator::operator* () const;

Returns a (possibly const) reference to the iterator's underlying object.

T* iterator::operator-> ();

const T* const_iterator::operator-> () const;

Returns a (possibly const) pointer to the iterator's underlying object.

iterator& iterator::operator++ ();

Pre-increment operator. Moves the iterator forward, and returns it. If the iterator was at the end of the stack, the results are undefined.

iterator iterator::operator++ (int);

Post-increment operator. Moves the iterator forward, and returns an iterator equal to what it was before incrementing. If the iterator was at the end of the stack, the results are undefined.

bool iterator::operator== (const iterator& other);

bool iterator::operator!= (const iterator& other);

Tests for iterator (in)equality.

Implementation details

There really isn't much to say about the internal details of the stack. It's probably the easiest lock free structure to implement. As with most other implementations, the one in XRCU simply consists of an atomic pointer to the top node. The use of RCU prevents the biggest issue with this design, that is, the ABA problem.

The only noteworthy thing to point out is that the swap method is safe to call from multiple threads as well. In order to achive this, the library uses a special sentinel bit, that is temporarily set as the head node when a swap is undergoing. During a swap, push and pop cannot proceed, since they check against that the special bit is not set before modifying the stack.

Note that because stack iterators are implicit critical sections, and because of stacks' implementation, iterating a stack will always be safe, even in the presence of operations like push and pop. The only way for an iterator to be invalidated is it's at the beggining of the stack, and a call to pop is made. Even then, dereferencing the iterator is valid, but advancing it will end prematurely, since the object was unlinked from the stack.

Skip lists

    #include <xrcu/skip_list.hpp>

A skip list is an associative container that holds a sorted set of unique objects of a particular type. In addition to the Key type, skip lists are instantiated with a comparator type that allows them to determine ordering.

In XRCU, skip lists meet the requirements for the C++ concept of Container, and AssociativeContainer.

Skip list API

Skip lists are templated types, defined in the following way:

    template <class T, class Cmp = std::less<T> >
    struct skip_list
      {
        struct iterator
          {
          };

        struct const_iterator
          {
          };
      };

The template parameter T refers to the key type, whereas Cmp is the comparator type, which defaults to std::less. Under most circumstances, that is usually enough, but users may instantiate with any other type that defines the operator() which returns a boolean.

As shown above, skip list has iterators, but they are non-const in all cases, for practicality reasons. Much like with stacks, skip list iterators are forward iterators, and an implicit cs_guard.

The following describes the public interface for skip_list<T, Cmp>

skip_list (Cmp c = Cmp (), unsigned int depth = ...);

Initializes the skip list with comparator c, which defaults to a default constructed value. Also takes a parameter indicating the maximum depth a skip list node may have, which defaults to an implementation-specified value. Users shouldn't need to change the latter, but it can be useful when tuning the application for performance. As a general rule, a higher value implies more memory usage, but better performance.

template <class Iter> skip_list (Iter first, Iter last, Cmp c = Cmp (), unsigned int depth = ...);

Initializes the skip list to the values in [first, last). The comparator and depth parameters are the same as explained above.

skip_list (std::initializer_list<T> lst, Cmp c = Cmp (), unsigned int depth = ...);

Initializes the skip list to the values in lst. The comparator and depth parameters are the same as explained above.

skip_list (const skip_list<T, Cmp>& other);

Copy constructor. Initializes the skip list to hold the values in other.

skip_list (skip_list<T, Cmp>&& other);

Move constructor. Takes ownership of the values in other.

optional<T> find (const T& key) const;

Searches for an element equivalent to key in the skip list, and returns an optional with it as its value. If the key couldn't be found, the returned optional has no value.

bool contains (const T& key) const;

Returns true if key is present in the skip list.

bool insert (const T& key) const;

Inserts key in the skip list. Returns true if the key wasn't present previous to this call.

bool erase (const T& key) const;

Erases key from the skip list. Returns true if the key was present previous to this call.

optional<T> remove (const T& key);

Erases key from the skip list and returns an optional with that element as its value, if the key was present. Otherwise, the returned optional has no value.

iterator begin ();

const_iterator cbegin () const;

Returns an iterator to the first element of the skip list.

iterator end ();

const_iterator cend () const;

Returns an iterator one past the last element of the skip list.

size_t size () const;

Returns the current size of the skip list.

size_t max_size () const;

Returns the maximum allowed size for a skip list.

bool empty () const;

Returns true if the skip list is empty (i.e: its size is 0).

template <class Iter> void assign (Iter first, Iter last);

Assigns to the skip list the elements in [first, last).

void assign (std::initializer_list<T> lst);

Assigns to the skip list the elements in lst.

skip_list& operator= (const skip_list<T, Cmp>& other);

Assigns the elements in other to the skip list. Returns *this.

skip_list& operator= (skip_list<T, Cmp>&& other);

Move assignment. Takes ownership of the elements in other. Returns *this.

void swap (skip_list<T, Cmp>& other);

Swaps the contents of the skip list with other, but only if other is a different object.

void clear ();

Removes every element from the skip list.

Implementation details

In XRCU, skip lists are implemented as described in any piece of literature that talks about them. Basically, every skip list of depth D has a head node that can be linked with up to other D nodes. When performing a lookup for an element, we start at the head node, and move horizontally until the current element is equal or greater. If it's equal, we the lookup succeeded. Otherwise, we move vertically to the next node, until we either find the element, or we exhausted every node.

Insertions first perform a lookup, and if the search failed, we create a new node with the specified value as its key. The number of linked nodes it will have is determined in a semi-random way, but it must never exceed the maximum depth of the skip list. After the node is created, we try to atomically link it with its computed predecesors and successors (Returned in the same lookup call we did before). If we succeed, the node is considered part of the skip list; otherwise, we free it and retry.

Erasing an element proceeds in a similar fashion, only we check that the lookup did not fail, and then atomically relink the node's predecessors with the node's own successors, thereby removing the key from the skip list.

Skip lists mantain an atomic word to store the length. However, this is used slightly differently as one would think, because the lowest bit is used as an ad-hoc lock bit in order to serialize concurrent calls to swap.

Hash tables

    #include <xrcu/hash_table.hpp>

Hash tables are associative containers that map unique keys to values. Ordering is unspecified for both keys and values. In addition to the key and value types, hash tables are instantiated with a hashing type and an equality type; callables that compute a hash value for a given key, and one that tests for equality, given two keys, respectively.

Additionally, hash tables mantain a load factor that determines when a full rehash is performed. A rehash implies moving all the key-value pairs into a new location to reduce the overhead of most operations.

In XRCU, hash tables meet the requirements for the C++ concept of Container and UnorderedAssociativeContainer.

Hash table API

As mentioned above, hash tables are template types, defined like this:

    template <class Key, class Val,
              class Equal = std::equal<Key>,
              class Hash = std::hash<Key> >
    struct hash_table
      {
        struct iterator
          {
          };

        struct const_iterator
          {
          };
      };

The template parameters should be pretty self explanatory: They refer to the key, value, equality and hashing types, in that order. The Equal type has to operate on two keys and return a boolean value that determines their equality, whereas the Hash type has to operate on keys and return unsigned integers. Both are allowed to throw exceptions, although it is not really wise to do so.

Much like with skip lists, hash table iterators are always constant, and also an implicit cs_guard.

The following describes public interface for hash tables:

hash_table (size_t size = 0, float lf = 0.85, Equal e = Equal (), Hash h = Hash ())

Initializes the hash table to hold size elements, with a load factor of lf, using the equality predicate e and the hasher h. The load factor must be in the range [0.4, 0.9]; if it's not, then it will silently be set to the default of 0.85.

template <class It> hash_table (It first, It last, float lf = 0.85, Equal e = Equal (), Hash h = Hash ())

Initializes the hash table with the values between (first, last]. The elements in that range must have two public members defined: first and second, referring to the key and value of each element, respectively, and in a similar fashion to what std::pair does. The other parameters work as with the previous constructor.

hash_table (std::initializer_list<std::pair<Key, Val> >, float lf = 0.85, Equal e = Equal (), Hash h = Hash ())

Initializes the hash table with the values in lst. The rest of the parameters work as with the previous constructors.

hash_table (const hash_table<Key, Val, Hash, Equal>& other);

Copy constructor. Initializes the hash table with the values in other.

hash_table (hash_table<Key, Val, Hash, Equal>&& other);

Move constructor. Takes ownership of the values in other.

size_t size () const;

Returns the hash table size.

size_t max_size () const;

Returns the maximum allowed size for a hash table.

bool empty () const;

Returns true if the hash table is empty.

optional<Val> find (const Key& key) const;

Val find (const Key& key, const Val& defl) const;

Look for key in the hash table. If it's found, returns the value associated to it. If it's not found, returns an empty optional in the first version, or defl in the second one.

bool contains (const Key& key) const;

Returns true if the key is present in the hash table.

bool insert (const Key& key, const Val& val);

Associates key with val in the hash table. Returns true if the value was not present. Otherwise, the former value is replaced.

template <class Fn, class ...Args> bool update (const Key& key, Fn f, Args... args);

Updates the value associated to key by calling f with it and the rest of the arguments. In other words, if val is the value associated to key, calls f (val, args...) and updates the value with the result. If no value was present for key, the function is called with a default constructed value instead (as if by calling Val ()).

Note that the function takes a reference to the value, and so it's possible to modify it in place. Additionally, if the function returns the very same object that was passed (i.e: the same reference that it received), there won't be any updates made. The function can also return a freshly made object, and update will work the same. The function may be called more than once if the atomic updates fail.

Returns true if key was present in the hash table before the call.

bool erase (const Key& key);

Erases key from the hash table. Returns true if key was present before the call.

optional<Val> remove (const Key& key);

Removes key from the hash table and returns the value that was associated to if, if it was present.

void clear ();

Removes every element from the hash table.

template <class Iter> void assign (Iter first, Iter last);

Assigns the elements in [first, last) to the hash table. The same restrictions as the range constructor apply here.

void assign (std::initializer_list<std::pair<Key, Val>> lst);

Assigns the elements in lst to the hash table.

hash_table<Key, Val>& operator= (const hash_table<Key, Val>& other);

Assigns the elements in other to the hash table. Returns *this.

hash_table<Key, Val>& operator= (hash_table<Key, Val>&& other);

Move assignment. Takes ownership of the elements in other. Returns *this.

void swap (hash_table<Key, Val>& other);

Swaps the contents of the hash table with other, but only if other is a different object.

iterator begin ();

const_iterator cbegin () const;

Returns an iterator to the first element of the hash table.

iterator end ();

const_iterator cend () const;

Returns an iterator one past the last element of the hash table.

iterator::iterator ();

Default constructor for hash table iterators. Leaves the object in an invalid state. Dereferencing or incrementing such an iterator has undefined behavior.

iterator::iterator (const iterator& other);

Copy constructor. Initializes the iterator to be equal to other.

Key iterator::key () const;

Returns the key for the iterator.

Val iterator::value () const;

Returns the value for the iterator.

std::pair<Key, Val> iterator::operator* () const;

Returns an std::pair constructed with the key and value of the iterator.

iterator& iterator::operator++ ();

Pre-increment operator. Moves the iterator forward and returns it. If the iterator was at the end, the results are undefined.

iterator iterator::operator++ (int);

Post-increment operator. Moves the iterator forward, and returns an iterator equal to what it was before incrementing. If the iterator was at the end, the results are undefined.

bool iterator::operator== (const iterator& other);

bool iterator::operator!= (const iterator& other);

Test for iterator (in)equality.

Implementation details

Hash tables are somewhat complex, because the atomicity requirements force us to do some rather convoluted things. To start off, a hash table is essentially a vector of consecutive key and value pairs, with some special values indicating free and deleted entries. However, since we can only operate atomically on integers, we wrap any other type that is not integral into a dynamically allocated pointer. This is done based on the template instantiation and is figured out at compile time.

When a lookup is performed, the passed key is hashed with the table's own internal hasher and a hash code is computed. Using this code, we produce an index into the vector and then we iterate over it, looking for a key that matches, or until we find a free entry, in which case the lookup fails.

Insertions are a bit more complicated. We start by performing a lookup, as described above, and then determine what to do based on the result: If the lookup came up empty, then we need to insert both the key and the value; otherwise, we only need to update the value.

If only the value needs to be updated (because the key is already present), then the insertion simply consists of atomically swapping the old value with the new one, and, if succesful, finalizing the old value as well.

If we need to insert the key as well, first we decrement an internal counter that keeps track of how many additional elements we can insert before a rehash is triggered. If the counter has already reached zero, then we have to rehash before inserting the key and value. If no rehash is needed, or after it's done, both the key and value are updated atomically (Some platforms allow us to do it in a single step, otherwise the operations are done sequentially).

At this point, we have to pause to make a sort of confession: Hash tables as implemented in XRCU are not entirely lock free, because rehashing actually takes an internal lock (I know, you're crushed). This not because of any intrinsical limitation, but rather, to make things easier. Since rehashes are probably the least common of the operations, we figured it wasn't that big of a deal anyways.

Going back to rehashes, these are the most expensive operations. As mentioned, they start off by acquiring an internal lock, and then they iterate over the full vector, marking the value indexes with a special bit that signals that the table is being rehashed. When this bit is set, insertions and erasures are forbidden (They both check for this bit before proceeding).

Erasures are pretty simple in comparison. They obviously perform a lookup on the key, and if it didn't come up empty, they atomically swap out the value for the special empty constant. Afterwards, they can mutate the key entry without atomicity (Because erased entries cannot be reused).

BUGS

All implemented containers use standard operators new and delete to perform memory (de)allocations. There's no way to specify custom allocators yet, although it's planned in the future.

AUTHORS

Agustina Arzille (avarzille@riseup.net) and Luciano Lo Giudice (lmlogiudice@gmail.com)