michael@0: // newPset: returns an empty nsIUrlClassifierPrefixSet.
michael@0: function newPset() {
michael@0:   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
michael@0:             .createInstance(Ci.nsIUrlClassifierPrefixSet);
michael@0:   pset.init("all");
michael@0:   return pset;
michael@0: }
michael@0: 
michael@0: // arrContains: returns true if |arr| contains the element |target|. Uses binary
michael@0: // search and requires |arr| to be sorted.
michael@0: function arrContains(arr, target) {
michael@0:   let start = 0;
michael@0:   let end = arr.length - 1;
michael@0:   let i = 0;
michael@0: 
michael@0:   while (end > start) {
michael@0:     i = start + (end - start >> 1);
michael@0:     let value = arr[i];
michael@0: 
michael@0:     if (value < target)
michael@0:       start = i+1;
michael@0:     else if (value > target)
michael@0:       end = i-1;
michael@0:     else
michael@0:       break;
michael@0:   }
michael@0:   if (start == end)
michael@0:     i = start;
michael@0: 
michael@0:   return (!(i < 0 || i >= arr.length) && arr[i] == target);
michael@0: }
michael@0: 
michael@0: // checkContents: Check whether the PrefixSet pset contains
michael@0: // the prefixes in the passed array.
michael@0: function checkContents(pset, prefixes) {
michael@0:   var outcount = {}, outset = {};
michael@0:   outset = pset.getPrefixes(outcount);
michael@0:   let inset = prefixes;
michael@0:   do_check_eq(inset.length, outset.length);
michael@0:   inset.sort(function(x,y) x - y);
michael@0:   for (let i = 0; i < inset.length; i++) {
michael@0:     do_check_eq(inset[i], outset[i]);
michael@0:   }
michael@0: }
michael@0: 
michael@0: function wrappedProbe(pset, prefix) {
michael@0:   return pset.contains(prefix);
michael@0: };
michael@0: 
michael@0: // doRandomLookups: we use this to test for false membership with random input
michael@0: // over the range of prefixes (unsigned 32-bits integers).
michael@0: //    pset: a nsIUrlClassifierPrefixSet to test.
michael@0: //    prefixes: an array of prefixes supposed to make up the prefix set.
michael@0: //    N: number of random lookups to make.
michael@0: function doRandomLookups(pset, prefixes, N) {
michael@0:   for (let i = 0; i < N; i++) {
michael@0:     let randInt = prefixes[0];
michael@0:     while (arrContains(prefixes, randInt))
michael@0:       randInt = Math.floor(Math.random() * Math.pow(2, 32));
michael@0: 
michael@0:     do_check_false(wrappedProbe(pset, randInt));
michael@0:   }
michael@0: }
michael@0: 
michael@0: // doExpectedLookups: we use this to test expected membership.
michael@0: //    pset: a nsIUrlClassifierPrefixSet to test.
michael@0: //    prefixes:
michael@0: function doExpectedLookups(pset, prefixes, N) {
michael@0:   for (let i = 0; i < N; i++) {
michael@0:     prefixes.forEach(function (x) {
michael@0:       dump("Checking " + x + "\n");
michael@0:       do_check_true(wrappedProbe(pset, x));
michael@0:     });
michael@0:   }
michael@0: }
michael@0: 
michael@0: // testBasicPset: A very basic test of the prefix set to make sure that it
michael@0: // exists and to give a basic example of its use.
michael@0: function testBasicPset() {
michael@0:   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
michael@0:                .createInstance(Ci.nsIUrlClassifierPrefixSet);
michael@0:   let prefixes = [2,50,100,2000,78000,1593203];
michael@0:   pset.setPrefixes(prefixes, prefixes.length);
michael@0: 
michael@0:   do_check_true(wrappedProbe(pset, 100));
michael@0:   do_check_false(wrappedProbe(pset, 100000));
michael@0:   do_check_true(wrappedProbe(pset, 1593203));
michael@0:   do_check_false(wrappedProbe(pset, 999));
michael@0:   do_check_false(wrappedProbe(pset, 0));
michael@0: 
michael@0: 
michael@0:   checkContents(pset, prefixes);
michael@0: }
michael@0: 
michael@0: function testDuplicates() {
michael@0:   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
michael@0:                .createInstance(Ci.nsIUrlClassifierPrefixSet);
michael@0:   let prefixes = [1,1,2,2,2,3,3,3,3,3,3,5,6,6,7,7,9,9,9];
michael@0:   pset.setPrefixes(prefixes, prefixes.length);
michael@0: 
michael@0:   do_check_true(wrappedProbe(pset, 1));
michael@0:   do_check_true(wrappedProbe(pset, 2));
michael@0:   do_check_true(wrappedProbe(pset, 5));
michael@0:   do_check_true(wrappedProbe(pset, 9));
michael@0:   do_check_false(wrappedProbe(pset, 4));
michael@0:   do_check_false(wrappedProbe(pset, 8));
michael@0: 
michael@0: 
michael@0:   checkContents(pset, prefixes);
michael@0: }
michael@0: 
michael@0: function testSimplePset() {
michael@0:   let pset = newPset();
michael@0:   let prefixes = [1,2,100,400,123456789];
michael@0:   pset.setPrefixes(prefixes, prefixes.length);
michael@0: 
michael@0:   doRandomLookups(pset, prefixes, 100);
michael@0:   doExpectedLookups(pset, prefixes, 1);
michael@0: 
michael@0: 
michael@0:   checkContents(pset, prefixes);
michael@0: }
michael@0: 
michael@0: function testReSetPrefixes() {
michael@0:   let pset = newPset();
michael@0:   let prefixes = [1, 5, 100, 1000, 150000];
michael@0:   pset.setPrefixes(prefixes, prefixes.length);
michael@0: 
michael@0:   doExpectedLookups(pset, prefixes, 1);
michael@0: 
michael@0:   let secondPrefixes = [12, 50, 300, 2000, 5000, 200000];
michael@0:   pset.setPrefixes(secondPrefixes, secondPrefixes.length);
michael@0: 
michael@0:   doExpectedLookups(pset, secondPrefixes, 1);
michael@0:   for (let i = 0; i < prefixes.length; i++) {
michael@0:     do_check_false(wrappedProbe(pset, prefixes[i]));
michael@0:   }
michael@0: 
michael@0: 
michael@0:   checkContents(pset, secondPrefixes);
michael@0: }
michael@0: 
michael@0: function testLargeSet() {
michael@0:   let N = 1000;
michael@0:   let arr = [];
michael@0: 
michael@0:   for (let i = 0; i < N; i++) {
michael@0:     let randInt = Math.floor(Math.random() * Math.pow(2, 32));
michael@0:     arr.push(randInt);
michael@0:   }
michael@0: 
michael@0:   arr.sort(function(x,y) x - y);
michael@0: 
michael@0:   let pset = newPset();
michael@0:   pset.setPrefixes(arr, arr.length);
michael@0: 
michael@0:   doExpectedLookups(pset, arr, 1);
michael@0:   doRandomLookups(pset, arr, 1000);
michael@0: 
michael@0:   checkContents(pset, arr);
michael@0: }
michael@0: 
michael@0: function testTinySet() {
michael@0:   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
michael@0:                .createInstance(Ci.nsIUrlClassifierPrefixSet);
michael@0:   let prefixes = [1];
michael@0:   pset.setPrefixes(prefixes, prefixes.length);
michael@0: 
michael@0:   do_check_true(wrappedProbe(pset, 1));
michael@0:   do_check_false(wrappedProbe(pset, 100000));
michael@0:   checkContents(pset, prefixes);
michael@0: 
michael@0:   prefixes = [];
michael@0:   pset.setPrefixes(prefixes, prefixes.length);
michael@0:   do_check_false(wrappedProbe(pset, 1));
michael@0:   checkContents(pset, prefixes);
michael@0: }
michael@0: 
michael@0: let tests = [testBasicPset,
michael@0:              testSimplePset,
michael@0:              testReSetPrefixes,
michael@0:              testLargeSet,
michael@0:              testDuplicates,
michael@0:              testTinySet];
michael@0: 
michael@0: function run_test() {
michael@0:   // None of the tests use |executeSoon| or any sort of callbacks, so we can
michael@0:   // just run them in succession.
michael@0:   for (let i = 0; i < tests.length; i++) {
michael@0:     dump("Running " + tests[i].name + "\n");
michael@0:     tests[i]();
michael@0:   }
michael@0: }