Skip to content

Ctries implemented in Clojure, see Prokopec, Bronson, Bagwell, Odersky

Notifications You must be signed in to change notification settings

michalmarczyk/ctries.clj

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

ctries.clj

Clojars Project

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.

Usage

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:

  1. They may be modified in place; assoc!, dissoc! and conj! are guaranteed to return the same instance when given a Ctrie.

  2. They may be concurrently accessed and modified by an arbitrary number of threads.

  3. 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}>]

Releases and dependency information

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}"

Developer information

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.

Licence

Copyright © 2014 Michał Marczyk

Distributed under the Apache License, Version 2.0.

About

Ctries implemented in Clojure, see Prokopec, Bronson, Bagwell, Odersky

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published