Resolver Data Structures

struct SkipList:
    struct Node
        n Node*  +  n  Version  +  a StringRef value
        created with a random level (< MaxLevels)
        getNext(int i), setNext(int i, Node* n)  for getting/setting the i'th Node*
        getMaxVersion(i), setMaxVersion(int i, Version v) for getting/setting the i'th Version
        calcVersionForLevel(int level): find max version at the level, between getNext(level-1) and getNext(level).

    struct Finger: 0 is lowest level, where every node is connected. We usually starts at a high level, searching for a node that is larger than the value, and then moves to a lower level. Continue this process until level 0. I.e., the finger points the value's position in the SkipList.
         Node* finger[MaxLevels]  // valid for levels >= level
         Node* x  // set to the header in Finger(Node* header, StringRef) constructor
         Node* alreadyChecked
         StringRef value

         advance(): move the finger to either next node at the same level (because this level's value is less than finger's value) or to the next level (because this level's value >= finger's value, i.e., the finger's value can be inserted before this level's node). the (level-1) Node* as "next", if "next" is checked or next->value >= value, then mark "next" as "alreadyChecked", go high a level (i.e., level--), set finger[level] = x and return true; otherwise, x = next and return false (next->value < value case). We want to advance to a level such that its value is larger.
         nextLevel(): keep calling advance() until it moves the next level (level--).
         found(): return the first Node* has the same value as the Finger, or nullptr.

    header: (MaxLevels -1) Node*

    insert(Finger f, Version version): create a random level node "x", and insert "x" at "f" -- "f" points to "x", which points to "f's previous values" (level 0 to level): copy f's first level pointers to "x"; set f's first level pointers to "x". Recalculate version for 1 to level in "f" and "x". Update "f's version" for level+1 and up.
    insert(StringRef value, Version version): use "header" to initialize a Finger. Move finger at all levels to be after the "value", and then call insert(f, version) to really insert the value into the SkipList.

    remove(Finger start, Finger end): removes the range (start, end] by setting start's pointers to end's pointers, and destroy any level 0 nodes in the range.