test/bitvec.test

   1 # 2008 February 18
   2 #
   3 # The author disclaims copyright to this source code.  In place of
   4 # a legal notice, here is a blessing:
   5 #
   6 #    May you do good and not evil.
   7 #    May you find forgiveness for yourself and forgive others.
   8 #    May you share freely, never taking more than you give.
   9 #
  10 #***********************************************************************
  11 #
  12 # Unit testing of the Bitvec object.
  13 #
  14 # $Id: bitvec.test,v 1.4 2009/04/01 23:49:04 drh Exp $
  15 #
  16
  17 set testdir [file dirname $argv0]
  18 source $testdir/tester.tcl
  19
  20 # The built-in test logic must be operational in order for
  21 # this test to work.
  22 ifcapable !builtin_test {
  23   finish_test
  24   return
  25 }
  26
  27 # Test that sqlite3BitvecBuiltinTest correctly reports errors
  28 # that are deliberately introduced.
  29 #
  30 do_test bitvec-1.0.1 {
  31   sqlite3BitvecBuiltinTest 400 {5 1 1 1 0}
  32 } 1
  33 do_test bitvec-1.0.2 {
  34   sqlite3BitvecBuiltinTest 400 {5 1 234 1 0}
  35 } 234
  36
  37 # Run test cases that set every bit in vectors of various sizes.
  38 # for larger cases, this should cycle the bit vector representation
  39 # from hashing into subbitmaps.  The subbitmaps should start as
  40 # hashes then change to either subbitmaps or linear maps, depending
  41 # on their size.
  42 #
  43 do_test bitvec-1.1 {
  44   sqlite3BitvecBuiltinTest 400 {1 400 1 1 0}
  45 } 0
  46 do_test bitvec-1.2 {
  47   sqlite3BitvecBuiltinTest 4000 {1 4000 1 1 0}
  48 } 0
  49 do_test bitvec-1.3 {
  50   sqlite3BitvecBuiltinTest 40000 {1 40000 1 1 0}
  51 } 0
  52 do_test bitvec-1.4 {
  53   sqlite3BitvecBuiltinTest 400000 {1 400000 1 1 0}
  54 } 0
  55
  56 # By specifying a larger increments, we spread the load around.
  57 #
  58 do_test bitvec-1.5 {
  59   sqlite3BitvecBuiltinTest 400 {1 400 1 7 0}
  60 } 0
  61 do_test bitvec-1.6 {
  62   sqlite3BitvecBuiltinTest 4000 {1 4000 1 7 0}
  63 } 0
  64 do_test bitvec-1.7 {
  65   sqlite3BitvecBuiltinTest 40000 {1 40000 1 7 0}
  66 } 0
  67 do_test bitvec-1.8 {
  68   sqlite3BitvecBuiltinTest 400000 {1 400000 1 7 0}
  69 } 0
  70
  71 # First fill up the bitmap with ones,  then go through and
  72 # clear all the bits.  This will stress the clearing mechanism.
  73 #
  74 do_test bitvec-1.9 {
  75   sqlite3BitvecBuiltinTest 400 {1 400 1 1 2 400 1 1 0}
  76 } 0
  77 do_test bitvec-1.10 {
  78   sqlite3BitvecBuiltinTest 4000 {1 4000 1 1 2 4000 1 1 0}
  79 } 0
  80 do_test bitvec-1.11 {
  81   sqlite3BitvecBuiltinTest 40000 {1 40000 1 1 2 40000 1 1 0}
  82 } 0
  83 do_test bitvec-1.12 {
  84   sqlite3BitvecBuiltinTest 400000 {1 400000 1 1 2 400000 1 1 0}
  85 } 0
  86
  87 do_test bitvec-1.13 {
  88   sqlite3BitvecBuiltinTest 400 {1 400 1 1 2 400 1 7 0}
  89 } 0
  90 do_test bitvec-1.15 {
  91   sqlite3BitvecBuiltinTest 4000 {1 4000 1 1 2 4000 1 7 0}
  92 } 0
  93 do_test bitvec-1.16 {
  94   sqlite3BitvecBuiltinTest 40000 {1 40000 1 1 2 40000 1 77 0}
  95 } 0
  96 do_test bitvec-1.17 {
  97   sqlite3BitvecBuiltinTest 400000 {1 400000 1 1 2 400000 1 777 0}
  98 } 0
  99
 100 do_test bitvec-1.18 {
 101   sqlite3BitvecBuiltinTest 400000 {1 5000 100000 1 2 400000 1 37 0}
 102 } 0
 103
 104 # Attempt to induce hash collisions.
 105 #
 106 unset -nocomplain start
 107 unset -nocomplain incr
 108 foreach start {1 2 3 4 5 6 7 8} {
 109   foreach incr {124 125} {
 110     do_test bitvec-1.20.$start.$incr {
 111       set prog [list 1 60 $::start $::incr 2 5000 1 1 0]
 112       sqlite3BitvecBuiltinTest 5000 $prog
 113     } 0
 114   }
 115 }
 116
 117 do_test bitvec-1.30.big_and_slow {
 118   sqlite3BitvecBuiltinTest 17000000 {1 17000000 1 1 2 17000000 1 1 0}
 119 } 0
 120
 121
 122 # Test setting and clearing a random subset of bits.
 123 #
 124 do_test bitvec-2.1 {
 125   sqlite3BitvecBuiltinTest 4000 {3 2000 4 2000 0}
 126 } 0
 127 do_test bitvec-2.2 {
 128   sqlite3BitvecBuiltinTest 4000 {3 1000 4 1000 3 1000 4 1000 3 1000 4 1000
 129                                  3 1000 4 1000 3 1000 4 1000 3 1000 4 1000 0}
 130 } 0
 131 do_test bitvec-2.3 {
 132   sqlite3BitvecBuiltinTest 400000 {3 10 0}
 133 } 0
 134 do_test bitvec-2.4 {
 135   sqlite3BitvecBuiltinTest 4000 {3 10 2 4000 1 1 0}
 136 } 0
 137 do_test bitvec-2.5 {
 138   sqlite3BitvecBuiltinTest 5000 {3 20 2 5000 1 1 0}
 139 } 0
 140 do_test bitvec-2.6 {
 141   sqlite3BitvecBuiltinTest 50000 {3 60 2 50000 1 1 0}
 142 } 0
 143 do_test bitvec-2.7 {
 144   sqlite3BitvecBuiltinTest 5000 {
 145           1 25 121 125
 146           1 50 121 125
 147           2 25 121 125
 148           0
 149   }
 150 } 0
 151
 152 # This procedure runs sqlite3BitvecBuiltinTest with argments "n" and
 153 # "program".  But it also causes a malloc error to occur after the
 154 # "failcnt"-th malloc.  The result should be "0" if no malloc failure
 155 # occurs or "-1" if there is a malloc failure.
 156 #
 157 proc bitvec_malloc_test {label failcnt n program} {
 158   do_test $label [subst {
 159     sqlite3_memdebug_fail $failcnt
 160     set x \[sqlite3BitvecBuiltinTest $n [list $program]\]
 161     set nFail \[sqlite3_memdebug_fail -1\]
 162     if {\$nFail==0} {
 163       set ::go 0
 164       set x -1
 165     }
 166     set x
 167   }] -1
 168 }
 169
 170 # Make sure malloc failures are handled sanily.
 171 #
 172 unset -nocomplain n
 173 unset -nocomplain go
 174 set go 1
 175 save_prng_state
 176 for {set n 0} {$go} {incr n} {
 177   restore_prng_state
 178   bitvec_malloc_test bitvec-3.1.$n $n 5000 {
 179       3 60 2 5000 1 1 3 60 2 5000 1 1 3 60 2 5000 1 1 0
 180   }
 181 }
 182 set go 1
 183 for {set n 0} {$go} {incr n} {
 184   restore_prng_state
 185   bitvec_malloc_test bitvec-3.2.$n $n 5000 {
 186       3 600 2 5000 1 1 3 600 2 5000 1 1 3 600 2 5000 1 1 0
 187   }
 188 }
 189 set go 1
 190 for {set n 1} {$go} {incr n} {
 191   bitvec_malloc_test bitvec-3.3.$n $n 50000 {1 50000 1 1 0}
 192 }
 193
 194 finish_test
 195 return