1 files changed, 175 insertions, 0 deletions
diff --git a/lib/LiquidDict.jsm b/lib/LiquidDict.jsm
new file mode 100644
index 0000000..65de9c5
--- /dev/null
+++ b/lib/LiquidDict.jsm
@@ -0,0 +1,175 @@
+/*******************************************************************************
+
+    ηMatrix - a browser extension to black/white list requests.
+    Copyright (C) 2014-2019 Raymond Hill
+    Copyright (C) 2019 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;
+}