Skip to content

Instantly share code, notes, and snippets.

@BastienClement

BastienClement/blocklist.js

Created June 9, 2014 18:02
Show Gist options
  • Save BastienClement/2ab427bdbfbfe00a9ab5 to your computer and use it in GitHub Desktop.
Save BastienClement/2ab427bdbfbfe00a9ab5 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Bastien Clément created this gist Jun 9, 2014.
    346 changes: 346 additions & 0 deletions blocklist.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,346 @@
    var ip = require('ip');

    console.time("load");
    var list = require("./bt_level1.js").map(function(block) {
    try {
    block.start = ip.toLong(block.start);
    block.end = ip.toLong(block.end);
    } catch(e) {
    console.log(e, block);
    process.exit(0);
    }
    return block;
    });
    console.timeEnd("load");
    console.log("entries: " + list.length);

    function BlockTree(start, end, reason) {
    this.block = { start: start, end: end, reason: reason };
    this.max = end;
    this.depth = 1;
    this.left = null;
    this.right = null;
    }

    BlockTree.prototype.balance = function() {
    var ldepth = this.left ? this.left.depth : 0;
    var rdepth = this.right ? this.right.depth : 0;

    if (ldepth > rdepth + 1) {
    var lldepth = this.left.left ? this.left.left.depth : 0;
    var lrdepth = this.left.right ? this.left.right.depth : 0;
    if (lldepth < lrdepth) this.left.rotateRR();
    this.rotateLL();
    } else if (ldepth + 1 < rdepth) {
    var rrdepth = this.right.right ? this.right.right.depth : 0;
    var rldepth = this.right.left ? this.right.left.depth : 0;
    if (rldepth > rrdepth) this.right.rotateLL();
    this.rotateRR();
    }
    }

    BlockTree.prototype.rotateLL = function() {
    var _block = this.block;
    var _right = this.right;

    this.block = this.left.block;
    this.right = this.left;
    this.left = this.left.left;

    this.right.left = this.right.right;
    this.right.right = _right;
    this.right.block = _block;

    this.right.update();
    this.update();
    };

    BlockTree.prototype.rotateRR = function() {
    var _block = this.block;
    var _left = this.left;

    this.block = this.right.block;
    this.end = this.right.end;
    this.left = this.right;
    this.right = this.right.right;

    this.left.right = this.left.left;
    this.left.left = _left;
    this.left.block = _block;

    this.left.update();
    this.update();
    };

    BlockTree.prototype.update = function() {
    this.depth = 1;
    if (this.left) this.depth = this.left.depth + 1;
    if (this.right && this.depth <= this.right.depth) this.depth = this.right.depth + 1;
    this.max = Math.max(this.block.end, this.left ? this.left.max : 0, this.right ? this.right.max : 0);
    };

    BlockTree.prototype.add = function(start, end, reason) {
    var d = start - this.block.start;
    var update = false;

    if (d == 0 && this.block.end < end) {
    this.block.end = end;
    this.block.reason = reason;
    update = true;
    } else if (d < 0) {
    if (this.left) {
    update = this.left.add(start, end, reason);
    if (update) this.balance();
    } else {
    this.left = new BlockTree(start, end, reason);
    update = true;
    }
    } else if (d > 0) {
    if (this.right) {
    update = this.right.add(start, end, reason);
    if (update) this.balance();
    } else {
    this.right = new BlockTree(start, end, reason);
    update = true;
    }
    }

    if (update) this.update();
    return update;
    };

    BlockTree.prototype.search = function(addr) {
    var node = this;
    while (node && !(addr >= node.block.start && addr <= node.block.end)) {
    if (node.left && node.left.max >= addr) node = node.left;
    else node = node.right;
    }
    return node ? node.block : null;
    }

    // #### BIN ####
    function bin_lookup(addr) {
    var min = 0;
    var max = list.length - 1;
    while(min <= max) {
    var mid = Math.floor((min + max) / 2);
    var range = list[mid];
    if(range.start <= addr && range.end >= addr) return range;
    else if(range.start > addr) max = mid - 1;
    else min = mid + 1;
    }
    return null;
    }

    // #### INSERT ####

    console.time("insert");

    var tree = new BlockTree(list[0].start, list[0].end, list[0].reason);

    for(var i = 1, l = list.length; i < l; ++i) {
    tree.add(list[i].start, list[i].end, list[i].reason);
    }

    console.timeEnd("insert");

    var miss = [];
    var hit = [];
    var miss_bin = [];
    var hit_bin = [];

    while(miss.length < 500000 || hit.length < 500000) {
    var ip = Math.round(Math.random()*range+min);

    var start = process.hrtime();
    var block = tree.search(ip);
    var diff = process.hrtime(start);
    var time = (diff[0] * 1e9 + diff[1]) / 1000;

    (block ? hit : miss).push(time);

    start = process.hrtime();
    var block2 = bin_lookup(ip);
    diff = process.hrtime(start);
    time = (diff[0] * 1e9 + diff[1]) / 1000;

    (block2 ? hit_bin : miss_bin).push(time);

    /*if(!!block2 !== !!block) {
    console.log("Lookup error:", ip);
    console.log("Tree:", block);
    console.log("Binary:", block2);
    return;
    }*/
    }

    function round(n) {
    var str = String(Math.round(n * 1000) / 1000);
    if (str.length > 6) return str.slice(0, 6 - str.length);
    return str;
    }

    function compute_data(set, drop_pct) {
    set.sort();

    var len = set.length;

    if(drop_pct) {
    var drop = len * drop_pct;
    set = set.slice(drop, -drop);
    len = set.length;
    }

    var min = Infinity;
    var max = -Infinity;
    var sum = 0;

    for(var i = 0; i < len; ++i) {
    var n = set[i];
    if(n < min) min = n;
    if(n > max) max = n;
    sum += n;
    }

    var avg = sum / len;

    var mid = (len - 1) / 2;
    var mean = (set[Math.floor(mid)] + set[Math.ceil(mid)]) / 2;

    var dev = 0;

    for(var i = 0; i < len; ++i) {
    var n = set[i] - avg;
    dev += n * n;
    }

    var std_dev = Math.sqrt(dev / (len - 1));

    return [len, round(min), round(avg), round(mean), round(max), round(std_dev)];
    }

    console.log("\n(time unit is μs)");

    console.log("\nFull tree data:");
    var miss_data = compute_data(miss, 0);
    var hit_data = compute_data(hit, 0);

    console.log("\tCount\tMin\tAvg\tMedian\tMax\tσ");
    console.log("Miss:\t"
    + miss_data[0] + "\t"
    + miss_data[1] + "\t"
    + miss_data[2] + "\t"
    + miss_data[3] + "\t"
    + miss_data[4] + "\t"
    + miss_data[5]);

    console.log("Hit:\t"
    + hit_data[0] + "\t"
    + hit_data[1] + "\t"
    + hit_data[2] + "\t"
    + hit_data[3] + "\t"
    + hit_data[4] + "\t"
    + hit_data[5]);

    console.log("\nFull binary search:");
    var miss_bin_data = compute_data(miss_bin, 0);
    var hit_bin_data = compute_data(hit_bin, 0);

    console.log("\tCount\tMin\tAvg\tMedian\tMax\tσ");
    console.log("Miss:\t"
    + miss_bin_data[0] + "\t"
    + miss_bin_data[1] + "\t"
    + miss_bin_data[2] + "\t"
    + miss_bin_data[3] + "\t"
    + miss_bin_data[4] + "\t"
    + miss_bin_data[5]);

    console.log("Hit:\t"
    + hit_bin_data[0] + "\t"
    + hit_bin_data[1] + "\t"
    + hit_bin_data[2] + "\t"
    + hit_bin_data[3] + "\t"
    + hit_bin_data[4] + "\t"
    + hit_bin_data[5]);

    console.log("\n90% tree data:");
    var miss_data = compute_data(miss, 0.05);
    var hit_data = compute_data(hit, 0.05);

    console.log("\tCount\tMin\tAvg\tMedian\tMax\tσ");
    console.log("Miss:\t"
    + miss_data[0] + "\t"
    + miss_data[1] + "\t"
    + miss_data[2] + "\t"
    + miss_data[3] + "\t"
    + miss_data[4] + "\t"
    + miss_data[5]);

    console.log("Hit:\t"
    + hit_data[0] + "\t"
    + hit_data[1] + "\t"
    + hit_data[2] + "\t"
    + hit_data[3] + "\t"
    + hit_data[4] + "\t"
    + hit_data[5]);

    console.log("\n90% binary search:");
    var miss_bin_data = compute_data(miss_bin, 0.05);
    var hit_bin_data = compute_data(hit_bin, 0.05);

    console.log("\tCount\tMin\tAvg\tMedian\tMax\tσ");
    console.log("Miss:\t"
    + miss_bin_data[0] + "\t"
    + miss_bin_data[1] + "\t"
    + miss_bin_data[2] + "\t"
    + miss_bin_data[3] + "\t"
    + miss_bin_data[4] + "\t"
    + miss_bin_data[5]);

    console.log("Hit:\t"
    + hit_bin_data[0] + "\t"
    + hit_bin_data[1] + "\t"
    + hit_bin_data[2] + "\t"
    + hit_bin_data[3] + "\t"
    + hit_bin_data[4] + "\t"
    + hit_bin_data[5]);

    return;

    module.exports = function(blocklist) {
    var tree = null;
    var that = {};

    that.add = function(start, end, reason) {
    if (!start) return;
    if (typeof start === 'object') {
    end = start.end;
    reason = start.reason;
    start = start.start;
    }

    if (typeof start !== 'number') start = ip.toLong(start);

    if (!end) end = start;
    if (typeof end !== 'number') end = ip.toLong(end);

    if (start < 0 || end > 4294967295 || end < start) throw new Error("Invalid block range");

    if (tree) tree.add(start, end, reason);
    else tree = new BlockTree(start, end, reason);
    }

    that.search = function(addr) {
    if (!tree) return null;
    if (typeof addr !== 'number') addr = ip.toLong(addr);
    return tree.search(addr);
    }

    if (Array.isArray(blocklist)) {
    blocklist.forEach(function(block) {
    that.add(block);
    });
    }

    return that;
    };