The Tor Browser / file revision

 // newPset: returns an empty nsIUrlClassifierPrefixSet.

 function newPset() {

   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]

             .createInstance(Ci.nsIUrlClassifierPrefixSet);

   pset.init("all");

   return pset;

 }

 // arrContains: returns true if |arr| contains the element |target|. Uses binary

 // search and requires |arr| to be sorted.

 function arrContains(arr, target) {

   let start = 0;

   let end = arr.length - 1;

   let i = 0;

   while (end > start) {

     i = start + (end - start >> 1);

     let value = arr[i];

     if (value < target)

       start = i+1;

     else if (value > target)

       end = i-1;

     else

       break;

   }

   if (start == end)

     i = start;

   return (!(i < 0 || i >= arr.length) && arr[i] == target);

 }

 // checkContents: Check whether the PrefixSet pset contains

 // the prefixes in the passed array.

 function checkContents(pset, prefixes) {

   var outcount = {}, outset = {};

   outset = pset.getPrefixes(outcount);

   let inset = prefixes;

   do_check_eq(inset.length, outset.length);

   inset.sort(function(x,y) x - y);

   for (let i = 0; i < inset.length; i++) {

     do_check_eq(inset[i], outset[i]);

   }

 }

 function wrappedProbe(pset, prefix) {

   return pset.contains(prefix);

 };

 // doRandomLookups: we use this to test for false membership with random input

 // over the range of prefixes (unsigned 32-bits integers).

 //    pset: a nsIUrlClassifierPrefixSet to test.

 //    prefixes: an array of prefixes supposed to make up the prefix set.

 //    N: number of random lookups to make.

 function doRandomLookups(pset, prefixes, N) {

   for (let i = 0; i < N; i++) {

     let randInt = prefixes[0];

     while (arrContains(prefixes, randInt))

       randInt = Math.floor(Math.random() * Math.pow(2, 32));

     do_check_false(wrappedProbe(pset, randInt));

   }

 }

 // doExpectedLookups: we use this to test expected membership.

 //    pset: a nsIUrlClassifierPrefixSet to test.

 //    prefixes:

 function doExpectedLookups(pset, prefixes, N) {

   for (let i = 0; i < N; i++) {

     prefixes.forEach(function (x) {

       dump("Checking " + x + "\n");

       do_check_true(wrappedProbe(pset, x));

     });

   }

 }

 // testBasicPset: A very basic test of the prefix set to make sure that it

 // exists and to give a basic example of its use.

 function testBasicPset() {

   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]

                .createInstance(Ci.nsIUrlClassifierPrefixSet);

   let prefixes = [2,50,100,2000,78000,1593203];

   pset.setPrefixes(prefixes, prefixes.length);

   do_check_true(wrappedProbe(pset, 100));

   do_check_false(wrappedProbe(pset, 100000));

   do_check_true(wrappedProbe(pset, 1593203));

   do_check_false(wrappedProbe(pset, 999));

   do_check_false(wrappedProbe(pset, 0));

   checkContents(pset, prefixes);

 }

 function testDuplicates() {

   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]

                .createInstance(Ci.nsIUrlClassifierPrefixSet);

   let prefixes = [1,1,2,2,2,3,3,3,3,3,3,5,6,6,7,7,9,9,9];

   pset.setPrefixes(prefixes, prefixes.length);

   do_check_true(wrappedProbe(pset, 1));

   do_check_true(wrappedProbe(pset, 2));

   do_check_true(wrappedProbe(pset, 5));

   do_check_true(wrappedProbe(pset, 9));

   do_check_false(wrappedProbe(pset, 4));

   do_check_false(wrappedProbe(pset, 8));

   checkContents(pset, prefixes);

 }

 function testSimplePset() {

   let pset = newPset();

   let prefixes = [1,2,100,400,123456789];

   pset.setPrefixes(prefixes, prefixes.length);

   doRandomLookups(pset, prefixes, 100);

   doExpectedLookups(pset, prefixes, 1);

   checkContents(pset, prefixes);

 }

 function testReSetPrefixes() {

   let pset = newPset();

   let prefixes = [1, 5, 100, 1000, 150000];

   pset.setPrefixes(prefixes, prefixes.length);

   doExpectedLookups(pset, prefixes, 1);

   let secondPrefixes = [12, 50, 300, 2000, 5000, 200000];

   pset.setPrefixes(secondPrefixes, secondPrefixes.length);

   doExpectedLookups(pset, secondPrefixes, 1);

   for (let i = 0; i < prefixes.length; i++) {

     do_check_false(wrappedProbe(pset, prefixes[i]));

   }

   checkContents(pset, secondPrefixes);

 }

 function testLargeSet() {

   let N = 1000;

   let arr = [];

   for (let i = 0; i < N; i++) {

     let randInt = Math.floor(Math.random() * Math.pow(2, 32));

     arr.push(randInt);

   }

   arr.sort(function(x,y) x - y);

   let pset = newPset();

   pset.setPrefixes(arr, arr.length);

   doExpectedLookups(pset, arr, 1);

   doRandomLookups(pset, arr, 1000);

   checkContents(pset, arr);

 }

 function testTinySet() {

   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]

                .createInstance(Ci.nsIUrlClassifierPrefixSet);

   let prefixes = [1];

   pset.setPrefixes(prefixes, prefixes.length);

   do_check_true(wrappedProbe(pset, 1));

   do_check_false(wrappedProbe(pset, 100000));

   checkContents(pset, prefixes);

   prefixes = [];

   pset.setPrefixes(prefixes, prefixes.length);

   do_check_false(wrappedProbe(pset, 1));

   checkContents(pset, prefixes);

 }

 let tests = [testBasicPset,

              testSimplePset,

              testReSetPrefixes,

              testLargeSet,

              testDuplicates,

              testTinySet];

 function run_test() {

   // None of the tests use |executeSoon| or any sort of callbacks, so we can

   // just run them in succession.

   for (let i = 0; i < tests.length; i++) {

     dump("Running " + tests[i].name + "\n");

     tests[i]();

   }

 }