https://github.com/michalmarczyk/ctries.clj.git
git clone 'https://github.com/michalmarczyk/ctries.clj.git'
(ql:quickload :michalmarczyk.ctries.clj)
A Clojure port of the original (Scala) implementation of Ctries – concurrently modifiable, lock-free (“global progress guaranteed”), constant-time snapshotable, HAMT-like maps.
Ctries were introduced in the following two papers:
Their design bears some similarity to Clojure's transients in that they prevent in-place modifications to a tree-based data structure from affecting instances with which it shares structure by tracking subtree ownership. The mechanism for accomplishing this in a concurrent setting involves two versions of restricted “double CAS”, of which one (GCAS) is an independently interesting contribution of the second Ctries paper.
This library was announced at Clojure eXchange 2014; the presentation can be viewed here: Ephemeral-first data structures.
There is one public namespace, ctries.clj, with a single public
function called concurrent-map:
(require '[ctries.clj :as ct])
(ct/concurrent-map)
;= #<Ctrie {}>
Ctrie objects created by concurrent-map implement the transient API
with a few idiosyncracies:
They may be modified in place; assoc!, dissoc! and conj! are
guaranteed to return the same instance when given a Ctrie.
They may be concurrently accessed and modified by an arbitrary number of threads.
They may be passed to persistent! any number of times; each such
call will produce an independent persistent snapshot.
Additionally, both the mutable Ctries produced by concurrent-map and
immutable snapshots thereof returned by persistent! support deref
(also known as @); this operation returns independent mutable
snapshots:
(def x (ct/concurrent-map :foo 1))
(def y @x)
(def z @x)
(assoc! x 1 1)
(assoc! y 2 2)
(assoc! z 3 3)
[x y z]
;= [#<Ctrie {1 1, :foo 1}> #<Ctrie {:foo 1, 2 2}> #<Ctrie {3 3, :foo 1}>]
ctries.clj releases are available from Clojars. Please follow the link to discover the current release number.
Leiningen dependency information:
[ctries.clj "${version}"]
Maven dependency information:
<dependency>
<groupId>ctries.clj</groupId>
<artifactId>ctries.clj</artifactId>
<version>${version}</version>
</dependency>
Gradle dependency information:
compile "ctries.clj:ctries.clj:${version}"
Please note that patches will only be accepted from developers who have submitted the Clojure CA and would be happy with the code they submit to ctries.clj becoming part of the Clojure project.
Copyright © 2014 Michał Marczyk
Distributed under the Apache License, Version 2.0.