implementation of LIFO with unique elements.
Actually, here is several implementations:
AkkaBasedCache
uses actor to gurantee sequential access. This is the slowest one. Logically, same can be achieved withsynchronized
. All other implementations here are CompareAndSwap based (exceptTrivialCache
), so they are completely lock-free.LinearAccessAndConstantPut
usesTrieMap
(works pretty same asConcurrentHashMap
) in combination with atomic vector clock.putIfAbscent
is used for atomic put. That's pretty fast, but getting a head takes linear time, so it's not recommended for big collections.ConstantOperations
is the fastest one for bigger data. All operations are effectively constant. It's based onTrieMap
+ConcurrentLinkedDeque
. Both are usingAtomicReference
s inside... no locks. The code is simple but synchronisation isn't trivial, so the more travis-ci builds was ran - the better.Deque
itself may contain duplicating elements for a while (it's eventually consistent), butMap
will always guarantee uniqueness and used as a primary source. So, this implementation guarantees sequential consistency (provides happens-before relationships) as usual. However, it may reorder puts between threads, which means that you may win your put to other thread (receivetrue
fromadd
), but actually another object with samehashCode
may be returned frompeek
/take()
. So, be careful with comparisons - use==
instead of reference equality (eq
).TrivialCache
issynchronized
+LinkedHashSet
implementation. It's slower than all except akka-based
P.S. T99.scala
- this is just T9 search tool. It's here because it's part of exercise.