A JavaScript implementation of the non-blocking RotatingSkipList algorithm described in Dick, I. Fekete, A. Gramoli, V. (2016) "A Skip List for Multicore", to appear in Concurrency and Computation Practice and Experience 2016

RotatingSkipList.ts

/*
A JavaScript implementation of the non-blocking RotatingSkipList algorithm described in:
Dick, I. Fekete, A. Gramoli, V. (2016)
"A Skip List for Multicore", to appear in
Concurrency and Computation Practice and Experience 2016

http://poseidon.it.usyd.edu.au/~gramoli/web/doc/pubs/rotating-skiplist-preprint-2016.pdf
https://github.com/gramoli/synchrobench/blob/master/c-cpp/src/skiplists/rotating/nohotspot_ops.c
*/

type     KEY = 0; const     KEY = 0;
type     VAL = 1; const     VAL = 1;
type    PREV = 2; const    PREV = 2;
type    NEXT = 3; const    NEXT = 3;
type   LEVEL = 4; const   LEVEL = 4;
type DELETED = 5; const DELETED = 5;
type   WHEEL = 6; const   WHEEL = 6;

type SkipNode<K, V> = {
     /* KEY */ 0: K,
     /* VAL */ 1: V | SkipNode<K, V>,
    /* PREV */ 2: SkipNode<K, V>,
    /* NEXT */ 3: SkipNode<K, V>,
   /* LEVEL */ 4: number,
 /* DELETED */ 5: boolean,
               length: number,
               [k: number]: any
};

function SkipNode<K, V>(
    key: K, val: V,
    prev: SkipNode<K, V> | null,
    next: SkipNode<K, V> | null,
    level: number
): SkipNode<K, V> {
    return [
    /* KEY */ key,
    /* VAL */ val,
   /* PREV */ prev,
   /* NEXT */ next,
  /* LEVEL */ level | 0,
/* DELETED */ false
    ];
}

type Disposable = { dispose(): void, unsubscribe?: () => void };
type Scheduler = { schedule(delay: number, state: any): Disposable };
const TimeoutScheduler = { d: null,
    schedule<K, V>(this: { d: any }, delay: number, list: SkipList<K, V> ) {
        if (this.d === null) {
            const self = this, timeout = setTimeout(() => list.rebalance(this.d = null), delay);
            return this.d = { dispose() { if (self.d) clearTimeout(timeout); self.d = null; } };
        }
        return this.d;
    }
};

class SkipList<K, V> {
    public length = 0;
    protected base = 0;
    protected levels: number;
    protected head: SkipNode<K, V>;
    protected scheduler: Scheduler | null;
    protected disposable: Disposable | null = null;
    constructor(size?: number, scheduler?: boolean | Scheduler) {
        this.head = SkipNode(<any> Number.NEGATIVE_INFINITY, null, null, null, 1);
        this.levels = Math.round(Math.log2(size !== undefined ? Math.abs(size | 0) || 65535 : 65535));
        this.scheduler = !scheduler ? null : typeof scheduler === 'boolean' ? TimeoutScheduler : scheduler;
    }
    /**
     * Get a value from the skip list
     * @param  {K} key        The search key
     * @return {TResult|null} The search key's value, or null if the key is not in the skip list
     */
    get(key: K) {
        const [node] = this.search(key, KEY);
        return !node[DELETED] && node[KEY] === key ? node[VAL] : null;
    }
    /**
     * Get a key from the skip list
     * @param  {V} key        The search value
     * @return {TResult|null} The search value's key, or null if the value is not in the skip list
     */
    key(val: V) {
        const [node] = this.search(val, VAL);
        return !node[DELETED] && node[VAL] === val ? node[KEY] : null;
    }
    /**
     * Set a value into the skip list
     * @param {Number} key The search key
     * @param {any}    val The search value
     */
    set(key: K, val: V) {
        const [node, next] = this.search(key);
        // If key matches exactly, write the new value into the node
        if (node[KEY] === key) {
            return node[VAL] = val;
        }
        this.length += 1;
        // Otherwise, splice a new node for this key into the skip list
        node[NEXT] = next ? (next[PREV] =
            SkipNode(key, val, node, next, 0)) :
            SkipNode(key, val, node, next, 0)  ;
        // Invalidate the skip list levels and return the value
        return this.rebalance(this.scheduler) && val || val;
    }
    /**
     * Delete a key from the skip list
     * @param  {Number}  key The search key
     * @return {boolean}     A boolean indicating whether the key was in the list and required removal
     */
    delete(key: K) {
        const [node] = this.search(key);
        // If key not present or is  logically deleted, return false
        if (node[DELETED] || node[KEY] !== key) { return false; }
        // Mark or reclaim the deleted nodes, and return true
        return (node[DELETED] = true) && (node[LEVEL] > 0 ?
            // nodes with index items are marked for removal and reclaimed using index height changes.
            this.rebalance(this.scheduler) :
            // If node is height 1 (i.e. they don't have index nodes above), we can safely remove and reclaim the node in-place.
            SkipList.remove(this, node[PREV], node[VAL] = node)
        ) && true || true;
    }
    /**
     * Traverse the skip list and return the node and next that match the search
     * @param  {S}       key   The search value
     * @param  { 0 | 1 } field The search field flag, either KEY = 0, or VAL = 1
     * @return {[node, next]}      The found node and next | null
     */
    search<S = K>(search: S, field?: KEY | VAL): [SkipNode<K, V>, SkipNode<K, V> | null] {
        let FIELD = field === undefined ? KEY : field;
        let node = this.head, level = node[LEVEL] - 1;
        let next: SkipNode<K, V>, { base, levels } = this;
        // find an entry-point to the node-level
        do {
            // follow level in wheels
            next = node[WHEEL - 1 + ((level + base) % levels)];
            /* if next key is smaller and there are more rows, move right */
            if (next && (next[DELETED] || <any> next[FIELD] < search)) { node = next; }
            /* if next key is larger and there are more levels, move down */
            else if (--level > base) { next = node; }
            /* otherwise we found the lowest level, now find the correct node and next */
            else {
                do {
                    // if node is physically deleted, backtrack
                    // to the first non physically deleted node
                    while (node === node[VAL]) node = node[PREV];
                    // next becomes immediate next node. if next is not
                    // logically deleted, but is physically deleted,
                    // remove the deleted nodes and retry
                    if ((next = node[NEXT]) && next[DELETED]) {
                        next = SkipList.remove(this, node, next);
                    }
                    // if we're still at the right position, return the results
                    if (!next || <any> next[FIELD] > search) {
                        return [node, next || null];
                    }
                    // otherwise continue the traversal
                    node = next;
                } while (true);
            }
        } while (true);
    }
    rebalance(scheduler?: Scheduler | null): null {
        if (scheduler && typeof scheduler.schedule === 'function') {
            if (!this.disposable) {
                this.disposable = scheduler.schedule(0, this);
            }
            return null;
        } else if (this.disposable) {
            (this.disposable.unsubscribe || this.disposable.dispose).call(this.disposable);
            this.disposable = null;
        }
        // raised - keep track of whether we raised the index level
        // threshold - keep track of whether we should lower index level
        let level, threshold, { base, head, levels } = this;
        let [raised, kept, removed] = SkipList.raiseBottomLevel(this, head, base, levels);
        // If we raised the bottom level, add a new index level
        if (1 === (level = head[LEVEL]) && raised) {
            // set index to null before we increase the level
            head[WHEEL + ((level + base) % levels)] = null;
            head[LEVEL] = ++level;
        }
        // raise the index level nodes
        // tslint:disable-next-line:whitespace
        for (let height = 1; height < level;) {
            raised = SkipList.raiseIndexLevel(head, base, levels, height);
            // if we raised index to the head level, add a new index level
            if (level === ++height && raised && level < levels) {
                // set index to null before we increase the level
                head[WHEEL + ((level + base) % levels)] = null;
                head[LEVEL] = ++level;
            }
        }
        // if needed, remove the lowest index level
        if (kept * 10 < removed && level > 1) {
            this.base = SkipList.lowerIndexLevel(head, base, levels);
        }
        return null;
    }
    /**
     * Finish physically removing a node
     * @param  {Node} prev the node before the one to remove
     * @param  {Node} node the node to finish removing
     * @return {Node|null} the next valid node, or null if no more valid nodes
     */
    protected static remove<K, V>(list: SkipList<K, V>, prev: SkipNode<K, V>, node: SkipNode<K, V>) {
        // if node is not logically deleted, return it
        if (node[VAL] !== node) { return node; }
        // if node is not the next node in the skip list, return it
        if (prev[NEXT] !== node) { return node; }
        list.length -= 1;
        // remove the node
        let next = node[NEXT];
        if (prev[NEXT] = next) {
            next[PREV] = prev;
        }
        return next || null;
    }
    /**
     * Traverse and raise the bottom skip list level. Tries to raise non-deleted
     * nodes, and finishes deletions that have been started but not completed.
     * @return {[boolean raised, int kept, int removed]}
     */
    protected static raiseBottomLevel<K, V>(list: SkipList<K, V>, head: SkipNode<K, V>, base: number, levels: number) {
        let next_head_below: SkipNode<K, V>;
        let raised = 0, kept = 0, removed = 0;
        let key, prev = head, node = head[NEXT];
        let next = node[NEXT], index = WHEEL + (base % levels);
        let above_head = head, above_prev = head, above_next = head;
        do {
            // if node logically deleted, then maybe physically delete
            if (node[DELETED]) {
                // If node is physically deleted or level > 0
                // otherwise, physically delete and increment deleted
                if (node[VAL] !== node && node[LEVEL] === 0 && 0 < ++removed) {
                    SkipList.remove(list, node[PREV], node[VAL] = node);
                }
            }
            // if not deleted, increment kept count
            // raise the level the node in the middle of three
            // consecutive non-deleted nodes of the same height
            else if (++kept &&
                    (prev[LEVEL] === 0) &&
                    (node[LEVEL] === 0) &&
                    (next[LEVEL] === 0)) {
                key = node[KEY];
                node[LEVEL] = raised = 1;
                // get the index node above for raising - inlined to avoid allocations
                if (above_next[KEY] < key) {
                    next_head_below = above_head[index];
                    do {
                        above_next = above_next[index];
                        if (above_next !== next_head_below) {
                            above_prev = above_prev[index];
                        }
                    } while (above_next && above_next[KEY] < key);
                }
                node[index] = above_next;
                above_prev[index] = node;
                above_next = above_prev = above_head = node;
            }
            prev = node;
        } while ((node = next) && (next = node[NEXT]));
        return [raised, kept, removed];
    }
    protected static raiseIndexLevel<K, V>(head: SkipNode<K, V>, base: number, levels: number, height: number) {
        let raised = 0;
        let next_head_below: SkipNode<K, V>;
        let index = WHEEL + ((height + base) % levels);
        let above = WHEEL + ((height + base - 1) % levels);
        let key, prev = head, node = head, next = head[above];
        let above_head = head, above_prev = head, above_next = head;
        while ((node = next) && (next = node[above])) {
            // skip physically deleted nodes
            while (node[VAL] === node) {
                prev[above] = next;
                node[LEVEL] -= 1; // decrement index level
                node = next;
                if (!(next = next[above])) {
                    return raised;
                }
            }
            // raise the level the node in the middle of three
            // consecutive non-deleted nodes of the same or lower height
            if (prev[LEVEL] <= height &&
                node[LEVEL] == height &&
                next[LEVEL] <= height &&
                node[DELETED] === false /* skip deleted nodes */) {
                raised = 1;
                key = node[KEY];
                // get the index node above for raising - inlined to avoid allocations
                if (above_next[KEY] < key) {
                    next_head_below = above_head[index];
                    do {
                        above_next = above_next[index];
                        if (above_next !== next_head_below) {
                            above_prev = above_prev[index];
                        }
                    } while (above_next && above_next[KEY] < key);
                }
                // fix the pointers and levels
                node[LEVEL] = height + 1;
                node[index] = above_next;
                above_prev[index] = node;
                above_next = above_prev = above_head = node;
            }
            prev = node;
        }
        return raised;
    }
    protected static lowerIndexLevel<K, V>(head: SkipNode<K, V>, base: number, levels: number) {
        let node = head, next, index = WHEEL + (base % levels);
        // if there's room to lower, decrement the level of all nodes
        if (node[LEVEL] - 2 > base) {
            do {
                next = node[index];
                if (node[LEVEL] > 0) {
                    node[LEVEL] -= 1;
                    node[index] = null;
                }
                node = next;
            } while (node);
        }
        return base + 1;
    }
}

console.clear();
alert('open the console to see the results');
console.log('queueing tests');

var runs = 10;
var count = Math.pow(10, 6);
var operations = Math.pow(10, 3);
var ops = `${nf(operations, ',')}`;

var create = `w/ ${nf(count, ',')} items:`;
var access = `${ops} random reads:`;
var insert = `${ops} random inserts:`;
var remove = `${ops} random deletes:`;
var splice = `${ops} random splices:`;
var rThenA = `${ops} random deletes, then ${ops} random reads:`;
var sThenA = `${ops} random splices, then ${ops} random reads:`;

setTimeout(() => {
    console.log(`ms displayed is average of ${nf(runs, ',')} runs`);
    console.log(`==========================`);
    console.log(`SkipList ${create} ${runMany(runs, initSkipList(count))}`);
    console.log(`${access} ${runMany(runs, initSkipList(count), accessSkipListRandom(count, operations))}`);
    console.log(`${insert} ${runMany(runs, initSkipList(count), updateSkipListRandom(count, operations))}`);
    console.log(`${remove} ${runMany(runs, initSkipList(count), removeSkipListRandom(count, operations))}`);
    console.log(`${rThenA} ${runMany(runs, initSkipList(count), removeSkipListRandom(count, operations, accessSkipListRandom(count, operations, true)))}`);
    console.log(`==========================`);
    console.log(`Object ${create} ${runMany(runs, initObject(count))}`);
    console.log(`${access} ${runMany(runs, initObject(count), accessObjectRandom(count, operations))}`);
    console.log(`${insert} ${runMany(runs, initObject(count), updateObjectRandom(count, operations))}`);
    console.log(`${remove} ${runMany(runs, initObject(count), removeObjectRandom(count, operations))}`);
    console.log(`${rThenA} ${runMany(runs, initObject(count), removeObjectRandom(count, operations, accessObjectRandom(count, operations)))}`);
    console.log(`==========================`);
    console.log(`Array ${create} ${runMany(runs, initArray(count))}`);
    console.log(`${access} ${runMany(runs, initArray(count), accessArrayRandom(count, operations))}`);
    console.log(`${insert} ${runMany(runs, initArray(count), updateArrayRandom(count, operations))}`);
    console.log(`${splice} ${runMany(runs, initArray(count), removeArrayRandom(count, operations))}`);
    console.log(`${sThenA} ${runMany(runs, initArray(count), removeArrayRandom(count, operations, accessArrayRandom(count, operations)))}`);
}, 5000);

function initSkipList(count) {
    return function() {
        var list = new SkipList(undefined, true);
        for (let i = -1, node = (<any> list).head; ++i < count;) {
            node[NEXT] = SkipNode(i, i * 10, node, null, 0);
            node = node[NEXT];
        }
        list.rebalance();
        return list;
    }
}

function accessSkipListRandom(count, times, nullsOk?) {
    return function(list) {
        for (let i = -1; ++i < times;) {
            let x = count * Math.random() | 0;
            let y = list.get(x);
            if (y !== x * 10) {
                if (!nullsOk || y !== null) {
                    throw new Error(`expected ${y} to be ${x * 10}`);
                }
            }
        }
    }
}

function updateSkipListRandom(count, times) {
    return function (list) {
        for (let i = -1; ++i < times;) {
            let x = count * Math.random() | 0;
            list.set(x, x * 10);
        }
    }
}

function removeSkipListRandom(count, times, nextFn?) {
    return function(list) {
        for (let i = -1, n = count; ++i < times;) {
            list.delete(--n * Math.random() | 0);
        }
        nextFn && nextFn(list);
    }
}

function initObject(count) {
    return function() {
        var obj = Object.create(null);
        for (let i = -1; ++i < count;) {
            obj['key_' + i] = i * 10;
        }
        return obj;
    }
}

function accessObjectRandom(count, times) {
    let x;
    return function(obj) {
        for (let i = -1; ++i < times;) {
            x = obj['key_' + (count * Math.random() | 0)];
        }
    }
}

function updateObjectRandom(count, times) {
    return function (obj) {
        for (let i = -1; ++i < times;) {
            let x = count * Math.random() | 0;
            obj['key_' + x] = x * 10;
        }
    }
}

function removeObjectRandom(count, times, nextFn?) {
    return function(obj) {
        for (let i = -1, n = count; ++i < times;) {
            delete obj['key_' + (--n * Math.random() | 0)];
        }
        nextFn && nextFn(obj);
    }
}


function initArray(count) {
    return function() {
        var arr = new Array(count);
        for (let i = -1; ++i < count;) {
            arr[i] = i * 10;
        }
        return arr;
    }
}

function accessArrayRandom(count, times) {
    let x;
    return function(arr) {
        for (let i = -1; ++i < times;) {
            x = arr[count * Math.random() | 0];
        }
    }
}

function updateArrayRandom(count, times) {
    return function (arr) {
        for (let i = -1; ++i < times;) {
            let x = count * Math.random() | 0;
            arr[x] = x * 10;
        }
    }
}

function removeArrayRandom(count, times, nextFn?) {
    return function(arr) {
        for (let i = -1, n = count; ++i < times;) {
            arr.splice(--n * Math.random() | 0, 1);
        }
        nextFn && nextFn(arr);
    }
}

function runMany(runs, setupFn, testFn?) {
    let t = 0, i = 0, times = [],
        testArg, runTest = testFn || setupFn;
    if (testFn) testArg = setupFn();
    do {
        t = performance.now();
        runTest(testArg);
        times.push(performance.now() - t);
    } while (++i < runs);
    let sum = times.reduce((xs, x) => xs + x, 0);
    let avg = sum / times.length;
    let sig = Math.pow(10, 2);
    return `${nf(Math.round(avg * sig) / sig, ',')}ms`;
}

function nf(_number, _sep) {
    let number = typeof _number != 'undefined' && _number > 0 ? '' + _number : "";
    let dot = number.indexOf('.');
    let int = ~dot ? number.slice(0, dot) : number;
    let dec = ~dot ? number.slice(dot) : '';
    int = int.replace(new RegExp("^(\\d{" + (int.length%3? int.length%3:0) + "})(\\d{3})", "g"), "$1 $2").replace(/(\d{3})+?/gi, "$1 ").trim();
    if(typeof _sep !== 'undefined' && _sep !== ' ') {
        int = int.replace(/\s/g, _sep);
    }
    return int + dec;
}