ematrix/lib/LiquidDict.jsm

/*******************************************************************************

    ηMatrix - a browser extension to black/white list requests.
    Copyright (C) 2014-2019 Raymond Hill
    Copyright (C) 2019-2020-2021 Alessio Vanni

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see {http://www.gnu.org/licenses/}.

    Home: https://gitlab.com/vannilla/ematrix
    uMatrix Home: https://github.com/gorhill/uMatrix
*/

'use strict';

var EXPORTED_SYMBOLS = ['LiquidDict'];

var LiquidDict = function () {
    this.dict = {};
    this.count = 0;
    this.duplicateCount = 0;
    this.bucketCount = 0;
    this.frozenCount = 0;
    this.cutoff = 500;
};

function meltBucket(dict, len, bucket) {
    let map = {};

    --dict.frozenCount;

    if (bucket.charAt(0) === ' ') {
	bucket.trim().split(' ').map(function (e) {
	    map[e] = true;
	});
    } else {
	for (let i=0; i<bucket.length; i+=len) {
	    map[bucket.substring(i, len)] = true;
	}
    }

    return map;
}

function melt(dict) {
    let buckets = dict.dict;
    for (let key in buckets) {
	let bucket = buckets[key];
	if (typeof bucket === 'string') {
	    buckets[key] = meltBucket(dict, key.charCodeAt(0) & 0xFF, bucket);
	}
    }
}

function freezeBucket(dict, bucket) {
    let words = Object.keys(bucket);
    let wlen = words[0].length;

    ++dict.frozenCount;

    if (wlen * words.length < dict.cutoff) {
	return ' ' + words.join(' ') + ' ';
    }

    return words.sort().join('');
}

LiquidDict.prototype.makeKey = function (word) {
    let len = word.length;
    if (len > 255) {
	len = 255;
    }

    let i = len >> 2;
    return String.fromCharCode((word.charCodeAt(0) & 0x03) << 14
			       | (word.charCodeAt(i) & 0x03) << 12
			       | (word.charCodeAt(i+i) & 0x03) << 10
			       | (word.charCodeAt(i+i+i) & 0x03) << 8
			       | len);
};

LiquidDict.prototype.test = function (word) {
    let key = this.makeKey(word);
    let bucket = this.dict[key];

    if (bucket === undefined) {
	return false;
    }

    if (typeof bucket === 'object') {
	return bucket[word] !== undefined;
    }

    if (bucket.charAt(0) === ' ') {
	return bucket.indexOf(' ' + word + ' ') >= 0;
    }

    let len = word.length;
    let left = 0;
    let right = ~~(bucket.length / len + 0.5);

    while (left < right) {
	let i = left + right >> 1;
	let needle = bucket.substr(len * i, len);

	if (word < needle) {
	    right = i;
	} else if (word > needle) {
	    left = i + 1;
	} else {
	    return true;
	}
    }

    return false;
};

LiquidDict.prototype.add = function (word) {
    let key = this.makeKey(word);
    if (key === undefined) {
	return false;
    }

    let bucket = this.dict[key];
    if (bucket === undefined) {
	this.dict[key] = bucket = {};
	++this.bucketCount;
	bucket[word] = true;
	++this.count;

	return true;
    } else if (typeof bucket === 'string') {
	this.dict[key] = bucket = meltBucket(this, word.len, bucket);
    }

    if (bucket[word] === undefined) {
	bucket[word] = true;
	++this.count;

	return true;
    }

    ++this.duplicateCount;

    return false;
};

LiquidDict.prototype.freeze = function () {
    let buckets = this.dict;

    for (let key in buckets) {
	let bucket = buckets[key];
	if (typeof bucket === 'object') {
	    buckets[key] = freezeBucket(this, bucket);
	}
    }
};

LiquidDict.prototype.reset = function () {
    this.dict = {};
    this.count = 0;
    this.duplicateCount = 0;
    this.bucketCount = 0;
    this.frozenBucketCount = 0;
}