1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/components/url-classifier/tests/unit/test_prefixset.js Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,193 @@
1.4 +// newPset: returns an empty nsIUrlClassifierPrefixSet.
1.5 +function newPset() {
1.6 + let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
1.7 + .createInstance(Ci.nsIUrlClassifierPrefixSet);
1.8 + pset.init("all");
1.9 + return pset;
1.10 +}
1.11 +
1.12 +// arrContains: returns true if |arr| contains the element |target|. Uses binary
1.13 +// search and requires |arr| to be sorted.
1.14 +function arrContains(arr, target) {
1.15 + let start = 0;
1.16 + let end = arr.length - 1;
1.17 + let i = 0;
1.18 +
1.19 + while (end > start) {
1.20 + i = start + (end - start >> 1);
1.21 + let value = arr[i];
1.22 +
1.23 + if (value < target)
1.24 + start = i+1;
1.25 + else if (value > target)
1.26 + end = i-1;
1.27 + else
1.28 + break;
1.29 + }
1.30 + if (start == end)
1.31 + i = start;
1.32 +
1.33 + return (!(i < 0 || i >= arr.length) && arr[i] == target);
1.34 +}
1.35 +
1.36 +// checkContents: Check whether the PrefixSet pset contains
1.37 +// the prefixes in the passed array.
1.38 +function checkContents(pset, prefixes) {
1.39 + var outcount = {}, outset = {};
1.40 + outset = pset.getPrefixes(outcount);
1.41 + let inset = prefixes;
1.42 + do_check_eq(inset.length, outset.length);
1.43 + inset.sort(function(x,y) x - y);
1.44 + for (let i = 0; i < inset.length; i++) {
1.45 + do_check_eq(inset[i], outset[i]);
1.46 + }
1.47 +}
1.48 +
1.49 +function wrappedProbe(pset, prefix) {
1.50 + return pset.contains(prefix);
1.51 +};
1.52 +
1.53 +// doRandomLookups: we use this to test for false membership with random input
1.54 +// over the range of prefixes (unsigned 32-bits integers).
1.55 +// pset: a nsIUrlClassifierPrefixSet to test.
1.56 +// prefixes: an array of prefixes supposed to make up the prefix set.
1.57 +// N: number of random lookups to make.
1.58 +function doRandomLookups(pset, prefixes, N) {
1.59 + for (let i = 0; i < N; i++) {
1.60 + let randInt = prefixes[0];
1.61 + while (arrContains(prefixes, randInt))
1.62 + randInt = Math.floor(Math.random() * Math.pow(2, 32));
1.63 +
1.64 + do_check_false(wrappedProbe(pset, randInt));
1.65 + }
1.66 +}
1.67 +
1.68 +// doExpectedLookups: we use this to test expected membership.
1.69 +// pset: a nsIUrlClassifierPrefixSet to test.
1.70 +// prefixes:
1.71 +function doExpectedLookups(pset, prefixes, N) {
1.72 + for (let i = 0; i < N; i++) {
1.73 + prefixes.forEach(function (x) {
1.74 + dump("Checking " + x + "\n");
1.75 + do_check_true(wrappedProbe(pset, x));
1.76 + });
1.77 + }
1.78 +}
1.79 +
1.80 +// testBasicPset: A very basic test of the prefix set to make sure that it
1.81 +// exists and to give a basic example of its use.
1.82 +function testBasicPset() {
1.83 + let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
1.84 + .createInstance(Ci.nsIUrlClassifierPrefixSet);
1.85 + let prefixes = [2,50,100,2000,78000,1593203];
1.86 + pset.setPrefixes(prefixes, prefixes.length);
1.87 +
1.88 + do_check_true(wrappedProbe(pset, 100));
1.89 + do_check_false(wrappedProbe(pset, 100000));
1.90 + do_check_true(wrappedProbe(pset, 1593203));
1.91 + do_check_false(wrappedProbe(pset, 999));
1.92 + do_check_false(wrappedProbe(pset, 0));
1.93 +
1.94 +
1.95 + checkContents(pset, prefixes);
1.96 +}
1.97 +
1.98 +function testDuplicates() {
1.99 + let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
1.100 + .createInstance(Ci.nsIUrlClassifierPrefixSet);
1.101 + let prefixes = [1,1,2,2,2,3,3,3,3,3,3,5,6,6,7,7,9,9,9];
1.102 + pset.setPrefixes(prefixes, prefixes.length);
1.103 +
1.104 + do_check_true(wrappedProbe(pset, 1));
1.105 + do_check_true(wrappedProbe(pset, 2));
1.106 + do_check_true(wrappedProbe(pset, 5));
1.107 + do_check_true(wrappedProbe(pset, 9));
1.108 + do_check_false(wrappedProbe(pset, 4));
1.109 + do_check_false(wrappedProbe(pset, 8));
1.110 +
1.111 +
1.112 + checkContents(pset, prefixes);
1.113 +}
1.114 +
1.115 +function testSimplePset() {
1.116 + let pset = newPset();
1.117 + let prefixes = [1,2,100,400,123456789];
1.118 + pset.setPrefixes(prefixes, prefixes.length);
1.119 +
1.120 + doRandomLookups(pset, prefixes, 100);
1.121 + doExpectedLookups(pset, prefixes, 1);
1.122 +
1.123 +
1.124 + checkContents(pset, prefixes);
1.125 +}
1.126 +
1.127 +function testReSetPrefixes() {
1.128 + let pset = newPset();
1.129 + let prefixes = [1, 5, 100, 1000, 150000];
1.130 + pset.setPrefixes(prefixes, prefixes.length);
1.131 +
1.132 + doExpectedLookups(pset, prefixes, 1);
1.133 +
1.134 + let secondPrefixes = [12, 50, 300, 2000, 5000, 200000];
1.135 + pset.setPrefixes(secondPrefixes, secondPrefixes.length);
1.136 +
1.137 + doExpectedLookups(pset, secondPrefixes, 1);
1.138 + for (let i = 0; i < prefixes.length; i++) {
1.139 + do_check_false(wrappedProbe(pset, prefixes[i]));
1.140 + }
1.141 +
1.142 +
1.143 + checkContents(pset, secondPrefixes);
1.144 +}
1.145 +
1.146 +function testLargeSet() {
1.147 + let N = 1000;
1.148 + let arr = [];
1.149 +
1.150 + for (let i = 0; i < N; i++) {
1.151 + let randInt = Math.floor(Math.random() * Math.pow(2, 32));
1.152 + arr.push(randInt);
1.153 + }
1.154 +
1.155 + arr.sort(function(x,y) x - y);
1.156 +
1.157 + let pset = newPset();
1.158 + pset.setPrefixes(arr, arr.length);
1.159 +
1.160 + doExpectedLookups(pset, arr, 1);
1.161 + doRandomLookups(pset, arr, 1000);
1.162 +
1.163 + checkContents(pset, arr);
1.164 +}
1.165 +
1.166 +function testTinySet() {
1.167 + let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
1.168 + .createInstance(Ci.nsIUrlClassifierPrefixSet);
1.169 + let prefixes = [1];
1.170 + pset.setPrefixes(prefixes, prefixes.length);
1.171 +
1.172 + do_check_true(wrappedProbe(pset, 1));
1.173 + do_check_false(wrappedProbe(pset, 100000));
1.174 + checkContents(pset, prefixes);
1.175 +
1.176 + prefixes = [];
1.177 + pset.setPrefixes(prefixes, prefixes.length);
1.178 + do_check_false(wrappedProbe(pset, 1));
1.179 + checkContents(pset, prefixes);
1.180 +}
1.181 +
1.182 +let tests = [testBasicPset,
1.183 + testSimplePset,
1.184 + testReSetPrefixes,
1.185 + testLargeSet,
1.186 + testDuplicates,
1.187 + testTinySet];
1.188 +
1.189 +function run_test() {
1.190 + // None of the tests use |executeSoon| or any sort of callbacks, so we can
1.191 + // just run them in succession.
1.192 + for (let i = 0; i < tests.length; i++) {
1.193 + dump("Running " + tests[i].name + "\n");
1.194 + tests[i]();
1.195 + }
1.196 +}
