cmin.js

/*
 * Copyright (c) 2021 RethinkDNS and its authors.
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 * The MIT License (MIT)
 *
 * Copyright (c) 2013 Mikola Lysenko
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

//forked with minor changes from https://github.com/mikolalysenko/count-min-sketch

"use strict";

var defaultHash = require("k-hash");

function CountMinSketch(width, depth, hashFunc, scratch, table) {
  this.width = width;
  this.depth = depth;
  this.hashFunc = hashFunc;
  this.scratch = scratch || new Uint32Array(depth);
  this.table = table || new Uint8Array(width * depth);
}

var proto = CountMinSketch.prototype;

proto.toJSON = function () {
  return {
    width: this.width,
    depth: this.depth,
    table: Array.prototype.slice.call(this.table),
  };
};

proto.fromJSON = function (data) {
  if (typeof data == "string") {
    data = JSON.parse(data);
  }
  if (!(data.width && data.depth && data.table)) {
    throw new Error("Cannot reconstruct the filter with a partial object");
  }
  var n = data.width * data.depth;
  var table = this.table;
  if (table.length > n) {
    table = table.subarray(0, n);
  } else if (table.length < n) {
    table = new Uint32Array(n);
  }
  var input_table = data.table;
  for (var i = 0; i < n; ++i) {
    table[i] = input_table[i];
  }
  if (this.scratch.length > data.depth) {
    this.scratch = this.scratch.subarray(0, data.depth);
  } else if (this.scratch.length < data.depth) {
    this.scratch = new Uint32Array(data.depth);
  }
  this.width = data.width | 0;
  this.depth = data.depth | 0;
  this.table = table;
  return this;
};

proto.update = function (key, v) {
  var scratch = this.scratch;
  var d = this.depth;
  var w = this.width;
  var tab = this.table;
  var ptr = 0;
  this.hashFunc(key, scratch);
  for (var i = 0; i < d; ++i) {
    tab[ptr + (scratch[i] % w)] += v;
    ptr += w;
  }
};

proto.query = function (key) {
  var scratch = this.scratch;
  var d = this.depth;
  var w = this.width;
  var tab = this.table;
  var ptr = w;
  this.hashFunc(key, scratch);
  var r = tab[scratch[0] % w];
  for (var i = 1; i < d; ++i) {
    r = Math.min(r, tab[ptr + (scratch[i] % w)]);
    ptr += w;
  }
  return r;
};

function createCountMinSketch(accuracy, probIncorrect, hashFunc) {
  accuracy = accuracy || 0.1;
  probIncorrect = probIncorrect || 0.0001;
  hashFunc = hashFunc || defaultHash;
  var width = Math.ceil(Math.E / accuracy) | 0;
  var depth = Math.ceil(-Math.log(probIncorrect)) | 0;
  return new CountMinSketch(width, depth, hashFunc);
}

function loadCountMinSketch(accuracy, probIncorrect, scratch, table, hashFunc) {
  accuracy = accuracy || 0.1;
  probIncorrect = probIncorrect || 0.0001;
  hashFunc = hashFunc || defaultHash;
  var width = Math.ceil(Math.E / accuracy) | 0;
  var depth = Math.ceil(-Math.log(probIncorrect)) | 0;
  return new CountMinSketch(width, depth, hashFunc, scratch, table);
}

module.exports.createCountMinSketch = createCountMinSketch;
module.exports.loadCountMinSketch = loadCountMinSketch;