woadwarrior / bloom
Simple sha256 hash based counting bloom filter implementations in Python and Javascript. Filters built with the python module can be serialized to JSON and loaded from the javascript implementation.
Clone this repository (size: 19.7 KB): HTTPS / SSH
$ hg clone http://bitbucket.org/woadwarrior/bloom/
| commit 3: | 11c29351165d |
| parent 2: | 805d9a52a443 |
| branch: | default |
Added jsUnity based unittests.
Changed (Δ7.8 KB):
raw changeset »
.hgignore (1 lines added, 0 lines removed)
js/bloom.html (49 lines added, 0 lines removed)
js/bloom.js (17 lines added, 20 lines removed)
js/jsunity-0.1.js (239 lines added, 0 lines removed)
Up to file-list js/bloom.html:
7 |
7 |
<h1>Javascript bloom filter</h1> |
8 |
8 |
<script type="text/javascript" src="sha256.js"></script> |
9 |
9 |
<script type="text/javascript" src="bloom.js"></script> |
10 |
<script type="text/javascript" src="jsunity-0.1.js"></script> |
|
11 |
<script type="text/javascript"> |
|
12 |
(function() { |
|
13 |
function bloomTestSuite() { |
|
14 |
function testUnrle() { |
|
15 |
var rle_data = [["A", 17], ["B", 8], "CCCCCC", ["D", 10], "EEEEEEEkjlfdkfkf", ["1", 8], "233333344444445555555"]; |
|
16 |
data = 'AAAAAAAAAAAAAAAAABBBBBBBBCCCCCCDDDDDDDDDDEEEEEEEkjlfdkfkf11111111233333344444445555555'; |
|
17 |
var decoded = BloomFilter.unrle(rle_data); |
|
18 |
assertEquals(decoded,data); |
|
19 |
} |
|
20 |
||
21 |
function testBloom() { |
|
22 |
var data = {"filter": [["0", 153], "10000100001", ["0", 35], "1", ["0", 34], "10000001", ["0", 238]], "k": 3, "m": 480}; |
|
23 |
BloomFilter.prototype.sha256 = sha256_digest; |
|
24 |
var bf = new BloomFilter( data ); |
|
25 |
var i=0; |
|
26 |
assertEquals(bf.empty(),false); |
|
27 |
bf.add('Jeethu Rao'); |
|
28 |
assertEquals(bf.hasKey('Jeethu Rao'),true); |
|
29 |
bf.remove('Jeethu Rao'); |
|
30 |
assertEquals(bf.hasKey('Jeethu Rao'),false); |
|
31 |
var data1 = {'filter':'','k':3,'m':400}; |
|
32 |
var bf1 = new BloomFilter( data1 ); |
|
33 |
assertEquals(bf1.empty(),true); |
|
34 |
var l = ['Jeethu Rao','Pria Chander','Thilak Raj Rao','Lakshminarayana Kamath']; |
|
35 |
for(i=0;i<l.length;i++) { |
|
36 |
bf1.add(l[i]); |
|
37 |
} |
|
38 |
assertEquals(bf1.empty(),false); |
|
39 |
for(i=0;i<l.length;i++) { |
|
40 |
assertEquals(bf1.hasKey(l[i]),true); |
|
41 |
} |
|
42 |
for(i=0;i<l.length;i++) { |
|
43 |
bf1.remove(l[i]); |
|
44 |
} |
|
45 |
for(i=0;i<l.length;i++) { |
|
46 |
assertEquals(bf1.hasKey(l[i]),false); |
|
47 |
} |
|
48 |
assertEquals(bf1.empty(),true); |
|
49 |
} |
|
50 |
} |
|
51 |
jsUnity.log = function (s) { |
|
52 |
var node = document.createElement('div'); |
|
53 |
node.innerHTML = s; |
|
54 |
document.body.appendChild(node); |
|
55 |
}; |
|
56 |
var results = jsUnity.run(bloomTestSuite); |
|
57 |
})(); |
|
58 |
</script> |
|
10 |
59 |
</body> |
11 |
60 |
</html> |
51 |
51 |
} |
52 |
52 |
var filter = []; |
53 |
53 |
var i; |
54 |
if(d.hasOwnProperty('filter') |
|
54 |
if(d.hasOwnProperty('filter')&&d.filter) { |
|
55 |
55 |
var min_value = d.hasOwnProperty('min_val') ? d.min_val : 0; |
56 |
56 |
var data = unrle(d.filter); |
57 |
57 |
var data_len = data.length; |
77 |
77 |
throw "Error, incorrect filter len: " + data_len.toString(); |
78 |
78 |
} |
79 |
79 |
} else { |
80 |
for(i=0;i< |
|
80 |
for(i=0;i<this.m;i++) { |
|
81 |
81 |
filter.push(0); |
82 |
82 |
} |
83 |
83 |
} |
90 |
90 |
this.n_bytes = Math.ceil(n_bits/8.0); |
91 |
91 |
}; |
92 |
92 |
|
93 |
|
|
93 |
// BloomFilter.prototype.sha256 = ???; |
|
94 |
94 |
|
95 |
95 |
BloomFilter.prototype.hexToInt = function( s ) { |
96 |
96 |
var v = 0; |
166 |
166 |
return this._remove( hash, 0 ); |
167 |
167 |
}; |
168 |
168 |
|
169 |
function _filter_sum( that ) { |
|
170 |
var s=0,filter=that.filter; |
|
171 |
for(var i=0,j=that.m;i<j;i++) { |
|
172 |
if(filter[i]) { |
|
173 |
s+=1; |
|
174 |
} |
|
175 |
} |
|
176 |
return s; |
|
177 |
}; |
|
178 |
||
169 |
179 |
BloomFilter.prototype.empty = function() { |
180 |
return _filter_sum(this)==0; |
|
170 |
181 |
}; |
171 |
182 |
|
172 |
183 |
BloomFilter.prototype.full = function() { |
184 |
return _filter_sum(this)==this.m; |
|
173 |
185 |
}; |
174 |
186 |
|
175 |
function test_bloom() { |
|
176 |
var data = {"filter": [["0", 153], "10000100001", ["0", 35], "1", ["0", 34], "10000001", ["0", 238]], "k": 3, "m": 480}; |
|
177 |
var bf = new BloomFilter( data ); |
|
178 |
console.log(bf.hash("Hello World")); |
|
179 |
console.log(bf.hash("Jeethu Rao")); |
|
180 |
bf.add('Jeethu Rao'); |
|
181 |
bf.remove('Jeethu Rao'); |
|
182 |
} |
|
187 |
BloomFilter.unrle = unrle; |
|
183 |
188 |
|
184 |
function test_unrle() { |
|
185 |
var rle_data = [["A", 17], ["B", 8], "CCCCCC", ["D", 10], "EEEEEEEkjlfdkfkf", ["1", 8], "233333344444445555555"]; |
|
186 |
data = 'AAAAAAAAAAAAAAAAABBBBBBBBCCCCCCDDDDDDDDDDEEEEEEEkjlfdkfkf11111111233333344444445555555'; |
|
187 |
var decoded = unrle(rle_data); |
|
188 |
return decoded==data; |
|
189 |
} |
|
190 |
console.log("Test"); |
|
191 |
console.log(test_unrle()); |
|
192 |
|
|
189 |
window.BloomFilter = BloomFilter; |
|
193 |
190 |
})(); |
Up to file-list js/jsunity-0.1.js:
1 |
//<% |
|
2 |
/** |
|
3 |
* jsUnity Universal JavaScript Testing Framework v0.1 |
|
4 |
* http://code.google.com/p/jsunity/ |
|
5 |
* |
|
6 |
* Copyright (c) 2009 Ates Goral |
|
7 |
* Licensed under the MIT license. |
|
8 |
* http://www.opensource.org/licenses/mit-license.php |
|
9 |
*/ |
|
10 |
||
11 |
/** |
|
12 |
* Assert that the given Boolean expression evaluates to <code>true</code> |
|
13 |
* |
|
14 |
* @param expr The Boolean expression |
|
15 |
*/ |
|
16 |
function assertTrue(expr) { |
|
17 |
if (!expr) { |
|
18 |
throw "Expression does not evaluate to true"; |
|
19 |
} |
|
20 |
} |
|
21 |
||
22 |
/** |
|
23 |
* Assert that the given Boolean expression evaluates to <code>false</code> |
|
24 |
* |
|
25 |
* @param expr The Boolean expression |
|
26 |
*/ |
|
27 |
function assertFalse(expr) { |
|
28 |
if (expr) { |
|
29 |
throw "Condition does not evaluate to false"; |
|
30 |
} |
|
31 |
} |
|
32 |
||
33 |
/** |
|
34 |
* Assert that the given value matches what's expected |
|
35 |
* |
|
36 |
* @param expected The expected value |
|
37 |
* @param actual The actual given value |
|
38 |
*/ |
|
39 |
function assertEquals(expected, actual) { |
|
40 |
if (expected !== actual) { |
|
41 |
throw "Actual value does not match what's expected: [expected] " |
|
42 |
+ expected + ", [actual] " + actual; |
|
43 |
} |
|
44 |
} |
|
45 |
||
46 |
/** |
|
47 |
* Assert that the given value doesn't match the given unexpected value |
|
48 |
* |
|
49 |
* @param unexpected The unexpected value |
|
50 |
* @param actual The actual given value |
|
51 |
*/ |
|
52 |
function assertNotEquals(unexpected, actual) { |
|
53 |
if (unexpected === actual) { |
|
54 |
throw "Actual value matches the unexpected value: " + actual; |
|
55 |
} |
|
56 |
} |
|
57 |
||
58 |
/** |
|
59 |
* Assert that the given object is <code>null</code> |
|
60 |
* |
|
61 |
* @param object The given object |
|
62 |
*/ |
|
63 |
function assertNull(object) { |
|
64 |
if (object !== null) { |
|
65 |
throw "Object is not null"; |
|
66 |
} |
|
67 |
} |
|
68 |
||
69 |
/** |
|
70 |
* Assert that the given object is not <code>null</code> |
|
71 |
* |
|
72 |
* @param object The given object |
|
73 |
*/ |
|
74 |
function assertNotNull(object) { |
|
75 |
if (object === null) { |
|
76 |
throw "Object is null"; |
|
77 |
} |
|
78 |
} |
|
79 |
||
80 |
/** |
|
81 |
* Assert that the given object is <code>undefined</code> |
|
82 |
* |
|
83 |
* @param object The given object |
|
84 |
*/ |
|
85 |
function assertUndefined(value) { |
|
86 |
if (value !== undefined) { |
|
87 |
throw "Value is not undefined"; |
|
88 |
} |
|
89 |
} |
|
90 |
||
91 |
/** |
|
92 |
* Assert that the given object is not <code>undefined</code> |
|
93 |
* |
|
94 |
* @param object The given object |
|
95 |
*/ |
|
96 |
function assertNotUndefined(value) { |
|
97 |
if (value === undefined) { |
|
98 |
throw "Value is undefined"; |
|
99 |
} |
|
100 |
} |
|
101 |
||
102 |
/** |
|
103 |
* Assert that the given object is <code>NaN</code> |
|
104 |
* |
|
105 |
* @param object The given object |
|
106 |
*/ |
|
107 |
function assertNaN(value) { |
|
108 |
if (!isNaN(value)) { |
|
109 |
throw "Value is not NaN"; |
|
110 |
} |
|
111 |
} |
|
112 |
||
113 |
/** |
|
114 |
* Assert that the given object is not <code>NaN</code> |
|
115 |
* |
|
116 |
* @param object The given object |
|
117 |
*/ |
|
118 |
function assertNotNaN(value) { |
|
119 |
if (isNaN(value)) { |
|
120 |
throw "Value is NaN"; |
|
121 |
} |
|
122 |
} |
|
123 |
||
124 |
/** |
|
125 |
* Fail the test by throwing an exception |
|
126 |
*/ |
|
127 |
function fail() { |
|
128 |
throw "Test failed"; |
|
129 |
} |
|
130 |
||
131 |
(function () { |
|
132 |
function parseSuiteFunction(suite) { |
|
133 |
var tokens = /^function\s+.+?\{((?:[^}]*}?)+)}$/.exec( |
|
134 |
suite.toString().split(/[\r\n]/).join(" ")); |
|
135 |
||
136 |
if (!tokens) { |
|
137 |
throw "Invalid function."; |
|
138 |
} |
|
139 |
||
140 |
var runnerBody = tokens[1]; |
|
141 |
||
142 |
var ret = { |
|
143 |
runner: new Function("f", runnerBody + "eval(f).call();"), |
|
144 |
//name: "", |
|
145 |
tests: [] |
|
146 |
}; |
|
147 |
||
148 |
var fns = runnerBody.match(/function\s+[^(]+/g); |
|
149 |
||
150 |
if (fns) { |
|
151 |
for (var i = 0; i < fns.length; i++) { |
|
152 |
var tokens = /\s(.+)$/.exec(fns[i]); |
|
153 |
||
154 |
if (tokens) { |
|
155 |
var name = tokens[1]; |
|
156 |
||
157 |
if (/^test/.test(name)) { |
|
158 |
ret.tests.push(name); |
|
159 |
} else if (/^setUp|tearDown$/.test(name)) { |
|
160 |
ret[name] = true; |
|
161 |
} |
|
162 |
} |
|
163 |
} |
|
164 |
} |
|
165 |
||
166 |
return ret; |
|
167 |
} |
|
168 |
||
169 |
function parseSuite(suite) { |
|
170 |
if (suite instanceof Function) { |
|
171 |
// functions inside function |
|
172 |
return parseSuiteFunction(suite); |
|
173 |
} else if (suite instanceof Array) { |
|
174 |
// array of test function names |
|
175 |
throw "Not implemented"; |
|
176 |
} else if (suite instanceof Object) { |
|
177 |
// functions as properties |
|
178 |
throw "Not implemented"; |
|
179 |
} else if (typeof suite === "string") { |
|
180 |
// source code of functions |
|
181 |
throw "Not implemented"; |
|
182 |
} else { |
|
183 |
throw "Must be a function, array, object or string."; |
|
184 |
} |
|
185 |
} |
|
186 |
||
187 |
jsUnity = { |
|
188 |
log: function () {}, |
|
189 |
||
190 |
error: function (s) { this.log("[ERROR] " + s); }, |
|
191 |
||
192 |
run: function (s) { |
|
193 |
try { |
|
194 |
var suite = parseSuite(s); |
|
195 |
} catch (e) { |
|
196 |
this.error("Invalid test suite: " + e); |
|
197 |
return false; |
|
198 |
} |
|
199 |
||
200 |
var total = suite.tests.length; |
|
201 |
var passed = 0; |
|
202 |
||
203 |
this.log(total + " tests found"); |
|
204 |
||
205 |
for (var i = 0; i < total; i++) { |
|
206 |
var test = suite.tests[i]; |
|
207 |
||
208 |
try { |
|
209 |
if (suite.setUp) { |
|
210 |
suite.runner("setUp"); |
|
211 |
} |
|
212 |
suite.runner(test); // suite.run(i)? |
|
213 |
if (suite.tearDown) { |
|
214 |
suite.runner("tearDown"); |
|
215 |
} |
|
216 |
passed++; |
|
217 |
this.log("[PASSED] " + test); |
|
218 |
} catch (e) { |
|
219 |
if (suite.tearDown) { |
|
220 |
suite.runner("tearDown"); |
|
221 |
} |
|
222 |
this.log("[FAILED] " + test + ": " + e); |
|
223 |
} |
|
224 |
} |
|
225 |
||
226 |
var failed = total - passed; |
|
227 |
||
228 |
this.log(passed + " tests passed"); |
|
229 |
this.log(failed + " tests failed"); |
|
230 |
||
231 |
return { |
|
232 |
total: total, |
|
233 |
passed: passed, |
|
234 |
failed: failed |
|
235 |
} |
|
236 |
} |
|
237 |
}; |
|
238 |
})(); |
|
239 |
//%> |