diff options
author | Deathamns <deathamns@gmail.com> | 2014-10-17 21:44:19 +0200 |
---|---|---|
committer | Deathamns <deathamns@gmail.com> | 2014-11-09 17:39:12 +0100 |
commit | 5b79bf353647a4dad9d4968d0f246582744f07bc (patch) | |
tree | 06f045f4dfbd188a8f1217c491b185f0d41d6d50 /src/js/liquid-dict.js | |
parent | 96c4e2e2565ffbd7d413ed7721d9610772b03859 (diff) | |
download | uBlock-5b79bf353647a4dad9d4968d0f246582744f07bc.zip uBlock-5b79bf353647a4dad9d4968d0f246582744f07bc.tar.gz uBlock-5b79bf353647a4dad9d4968d0f246582744f07bc.tar.bz2 |
Work on vendor API abstraction, and near complete Safari support
Diffstat (limited to 'src/js/liquid-dict.js')
-rw-r--r-- | src/js/liquid-dict.js | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/src/js/liquid-dict.js b/src/js/liquid-dict.js new file mode 100644 index 0000000..08744d7 --- /dev/null +++ b/src/js/liquid-dict.js @@ -0,0 +1,227 @@ +/******************************************************************************* + + µBlock - a Chromium browser extension to block requests. + Copyright (C) 2014 Raymond Hill + + 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://github.com/gorhill/uBlock +*/ + +/* jshint bitwise: false */ +/* global µBlock */ + +/******************************************************************************/ + +µBlock.LiquidDict = (function() { + +/******************************************************************************/ + +var LiquidDict = function() { + this.dict = {}; + this.count = 0; + this.bucketCount = 0; + this.frozenBucketCount = 0; + + // Somewhat arbitrary: I need to come up with hard data to know at which + // point binary search is better than indexOf. + this.cutoff = 256; +}; + +/******************************************************************************/ + +var meltBucket = function(ldict, len, bucket) { + ldict.frozenBucketCount -= 1; + var map = {}; + if ( bucket.charAt(0) === ' ' ) { + bucket.trim().split(' ').map(function(k) { + map[k] = true; + }); + } else { + var offset = 0; + while ( offset < bucket.length ) { + map[bucket.substring(offset, len)] = true; + offset += len; + } + } + return map; +}; + +/******************************************************************************/ + +var melt = function(ldict) { + var buckets = ldict.dict; + var bucket; + for ( var key in buckets ) { + bucket = buckets[key]; + if ( typeof bucket === 'string' ) { + buckets[key] = meltBucket(ldict, key.charCodeAt(0) & 0xFF, bucket); + } + } +}; + +/******************************************************************************/ + +var freezeBucket = function(ldict, bucket) { + ldict.frozenBucketCount += 1; + var words = Object.keys(bucket); + var wordLen = words[0].length; + if ( wordLen * words.length < ldict.cutoff ) { + return ' ' + words.join(' ') + ' '; + } + return words.sort().join(''); +}; + +/******************************************************************************/ + +// How the key is derived dictates the number and size of buckets. +// +// http://jsperf.com/makekey-concat-vs-join/3 +// +// Question: Why is using a prototyped function better than a standalone +// helper function? + +LiquidDict.prototype.makeKey = function(word) { + var len = word.length; + if ( len > 255 ) { + len = 255; + } + var i8 = len >>> 3; + var i4 = len >>> 2; + var i2 = len >>> 1; + + // Be sure the msb is not set, this will guarantee a valid unicode + // character (because 0xD800-0xDFFF). + return String.fromCharCode( + (word.charCodeAt( i8) & 0x01) << 14 | + (word.charCodeAt( i4 ) & 0x01) << 13 | + (word.charCodeAt( i4+i8) & 0x01) << 12 | + (word.charCodeAt(i2 ) & 0x01) << 11 | + (word.charCodeAt(i2 +i8) & 0x01) << 10 | + (word.charCodeAt(i2+i4 ) & 0x01) << 9 | + (word.charCodeAt(i2+i4+i8) & 0x01) << 8 , + len + ); +}; + +/******************************************************************************/ + +LiquidDict.prototype.test = function(word) { + var key = this.makeKey(word); + var 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 + ' ') !== -1; + } + // binary search + var len = word.length; + var left = 0; + // http://jsperf.com/or-vs-floor/3 + var right = ~~(bucket.length / len + 0.5); + var i, needle; + while ( left < right ) { + i = left + right >> 1; + 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) { + var key = this.makeKey(word); + if ( key === undefined ) { + return false; + } + var bucket = this.dict[key]; + if ( bucket === undefined ) { + this.dict[key] = bucket = {}; + this.bucketCount += 1; + bucket[word] = true; + this.count += 1; + 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 += 1; + return true; + } + return false; +}; + +/******************************************************************************/ + +LiquidDict.prototype.freeze = function() { + var buckets = this.dict; + var bucket; + for ( var key in buckets ) { + bucket = buckets[key]; + if ( typeof bucket === 'object' ) { + buckets[key] = freezeBucket(this, bucket); + } + } +}; + +/******************************************************************************/ + +LiquidDict.prototype.reset = function() { + this.dict = {}; + this.count = 0; + this.bucketCount = 0; + this.frozenBucketCount = 0; +}; + +/******************************************************************************/ + +LiquidDict.prototype.toSelfie = function() { + return { + count: this.count, + bucketCount: this.bucketCount, + frozenBucketCount: this.frozenBucketCount, + dict: this.dict + }; +}; + +/******************************************************************************/ + +LiquidDict.prototype.fromSelfie = function(selfie) { + this.count = selfie.count; + this.bucketCount = selfie.bucketCount; + this.frozenBucketCount = selfie.frozenBucketCount; + this.dict = selfie.dict; +}; + +/******************************************************************************/ + +return LiquidDict; + +/******************************************************************************/ + +})(); + +/******************************************************************************/ |