third-party/triemap/README.md

   1 About
   2 =============================
   3
   4 This is a Java port of a concurrent trie hash map implementation from the Scala collections library. It is almost a line-by-line
   5 conversion from Scala to Java.
   6
   7 Idea + implementation techniques can be found in these reports written by Aleksandar Prokopec:
   8    * http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf - this is a nice introduction to Ctries, along with a correctness proof
   9    * http://lamp.epfl.ch/~prokopec/ctries-snapshot.pdf - a more up-to-date writeup which describes the snapshot operation
  10
  11 The original Scala implementation can be found here and is a part of scala.collection.concurrent:
  12    *   [Scala implementation](https://github.com/scala/scala/blob/930c85d6c96507d798d1847ea078eebf93dc0acb/src/library/scala/collection/concurrent/TrieMap.scala)
  13
  14 Some of the tests and implementation details were borrowed from this project:
  15    *  https://github.com/flegall/concurrent-hash-trie
  16
  17 Implementation status :
  18    *   The given implementation is complete and implements all features of the original Scala implementation including support for
  19    snapshots.
  20    *   Wherever necessary, code was adapted to be more easily usable in Java, e.g. it returns Objects instead of Option<V> as
  21    many methods of Scala's collections do.
  22    *   This class implements all the ConcurrentMap & Iterator methods and passes all the tests. Can be used as a drop-in replacement
  23        for usual Java maps, including ConcurrentHashMap.
  24
  25
  26 What is a concurrent trie hash map also known as ctrie?
  27 ========================================================
  28 ctrie is a lock-Free Concurrent Hash Array Mapped Trie.
  29
  30 A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie.
  31
  32 It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations
  33 and is memory-efficient.
  34
  35 It supports O(1), atomic, lock-free snapshots which are used to implement linearizable lock-free size, iterator and clear operations.
  36 The cost of evaluating the (lazy) snapshot is distributed across subsequent updates, thus making snapshot evaluation horizontally scalable.
  37
  38 The original Scala-based implementation of the Ctrie is a part of the Scala standard library since the version 2.10.
  39
  40 More info about Ctries:
  41
  42 - http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf - this is a nice introduction to Ctries, along with a correctness proof
  43 - http://lamp.epfl.ch/~prokopec/ctries-snapshot.pdf - a more up-to-date writeup (more coherent with the current version of the code) which describes the snapshot operation
  44
  45
  46 License
  47 ===============================
  48
  49 This library is licensed under the Apache 2.0 license.
  50
  51
  52 Usage
  53 ===============================
  54
  55 Usage of this library is very simple. Simply import the class com.romix.scala.collection.concurrent.TrieMap and use it as a usual Map.
  56
  57     import com.romix.scala.collection.concurrent.TrieMap;
  58
  59     Map myMap = new TrieMap <Object, Object> ();
  60     myMap.put("key", "value");
  61
  62
  63 Building the library
  64 ===============================
  65
  66 Use a usual `mvn clean install`
  67
  68 Using the library with Maven projects
  69 =====================================
  70 The prebuilt binaries of the library are available from Maven central. Please use the following dependency in your POM files:
  71
  72                 <dependency>
  73                         <groupId>com.github.romix</groupId>
  74                         <artifactId>java-concurrent-hash-trie-map</artifactId>
  75                         <version>0.2.1</version>
  76                 </dependency>
  77
  78
  79 External dependencies
  80 =====================================
  81 This library is self-contained. It does not depend on any additional libraries. In particular, it does not require the rather big Scala's
  82 standard library to be used.
  83