object
HASkipList
Type Members
-
final
class
Branch[S <: Sys[S], A, B] extends HeadOrBranch[S, A, B] with Node[S, A, B]
-
-
sealed
trait
Leaf[S <: Sys[S], A, E] extends Node[S, A, E]
-
sealed
trait
Map[S <: Sys[S], A, B] extends SkipList.Map[S, A, B]
-
sealed
trait
Node[S <: Sys[S], A, E] extends AnyRef
-
sealed
trait
Set[S <: Sys[S], A] extends SkipList.Set[S, A]
Value Members
-
final
def
!=(arg0: Any): Boolean
-
final
def
##(): Int
-
final
def
==(arg0: Any): Boolean
-
-
object
Map
-
object
Set
-
final
def
asInstanceOf[T0]: T0
-
def
clone(): AnyRef
-
def
debugFindLevel[S <: Sys[S], A](list: SkipList[S, A, _], key: A)(implicit tx: HASkipList.debugFindLevel.S.Tx): Int
-
final
def
eq(arg0: AnyRef): Boolean
-
def
equals(arg0: Any): Boolean
-
def
finalize(): Unit
-
final
def
getClass(): Class[_]
-
def
hashCode(): Int
-
final
def
isInstanceOf[T0]: Boolean
-
final
def
ne(arg0: AnyRef): Boolean
-
final
def
notify(): Unit
-
final
def
notifyAll(): Unit
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
-
def
toString(): String
-
final
def
wait(): Unit
-
final
def
wait(arg0: Long, arg1: Int): Unit
-
final
def
wait(arg0: Long): Unit
A transactional version of the deterministic k-(2k+1) top-down operated skip list as described in T. Papadakis, Skip Lists and Probabilistic Analysis of Algorithms. Ch. 4 (Deterministic Skip Lists), pp. 55--78. Waterloo (CA) 1993
It uses the horizontal array technique with a parameter for k (minimum gap size). It uses a modified top-down removal algorithm that avoids the need for a second pass as in the original algorithm, and is careful about object creations, so that it will be able to persist the data structure without any unnecessary reads or writes to the store.
Three implementation notes: (1) We treat the nodes as immutable at the moment, storing them directly in the S#Val child pointers of their parents. While this currently seems to have a performance advantage (?), we could try to avoid this by using S#Refs for the child pointers, making the nodes become mutable. We could avoid copying the arrays for each insertion or deletion, at the cost of more space, but maybe better performance.
(2) The special treatment of
isRightkind of sucks. Since now that information is also persisted, we might just have two types of branches and leaves, and avoid passing around this flag.(3) Since there is a bug with the top-down one-pass removal, we might end up removing the creation of instances of virtual branches altogether again when replacing the current algorithm by a two-pass one.
TODO: nodes or at least leaves should be horizontally connected for a faster iterator and fast pair (interval) search