1 /*

     2 ** 2008 February 16

     3 **

     4 ** The author disclaims copyright to this source code.  In place of

     5 ** a legal notice, here is a blessing:

     6 **

     7 **    May you do good and not evil.

     8 **    May you find forgiveness for yourself and forgive others.

     9 **    May you share freely, never taking more than you give.

    10 **

    11 *************************************************************************

    12 ** This file implements an object that represents a fixed-length

    13 ** bitmap.  Bits are numbered starting with 1.

    14 **

    15 ** A bitmap is used to record what pages a database file have been

    16 ** journalled during a transaction.  Usually only a few pages are

    17 ** journalled.  So the bitmap is usually sparse and has low cardinality.

    18 ** But sometimes (for example when during a DROP of a large table) most

    19 ** or all of the pages get journalled.  In those cases, the bitmap becomes

    20 ** dense.  The algorithm needs to handle both cases well.

    21 **

    22 ** The size of the bitmap is fixed when the object is created.

    23 **

    24 ** All bits are clear when the bitmap is created.  Individual bits

    25 ** may be set or cleared one at a time.

    26 **

    27 ** Test operations are about 100 times more common that set operations.

    28 ** Clear operations are exceedingly rare.  There are usually between

    29 ** 5 and 500 set operations per Bitvec object, though the number of sets can

    30 ** sometimes grow into tens of thousands or larger.  The size of the

    31 ** Bitvec object is the number of pages in the database file at the

    32 ** start of a transaction, and is thus usually less than a few thousand,

    33 ** but can be as large as 2 billion for a really big database.

    34 **

    35 ** @(#) $Id: bitvec.c,v 1.6 2008/06/20 14:59:51 danielk1977 Exp $

    36 */

    37 #include "sqliteInt.h"

    38 

    39 #define BITVEC_SZ        512

    40 /* Round the union size down to the nearest pointer boundary, since that's how 

    41 ** it will be aligned within the Bitvec struct. */

    42 #define BITVEC_USIZE     (((BITVEC_SZ-12)/sizeof(Bitvec*))*sizeof(Bitvec*))

    43 #define BITVEC_NCHAR     BITVEC_USIZE

    44 #define BITVEC_NBIT      (BITVEC_NCHAR*8)

    45 #define BITVEC_NINT      (BITVEC_USIZE/4)

    46 #define BITVEC_MXHASH    (BITVEC_NINT/2)

    47 #define BITVEC_NPTR      (BITVEC_USIZE/sizeof(Bitvec *))

    48 

    49 #define BITVEC_HASH(X)   (((X)*37)%BITVEC_NINT)

    50 

    51 /*

    52 ** A bitmap is an instance of the following structure.

    53 **

    54 ** This bitmap records the existance of zero or more bits

    55 ** with values between 1 and iSize, inclusive.

    56 **

    57 ** There are three possible representations of the bitmap.

    58 ** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight

    59 ** bitmap.  The least significant bit is bit 1.

    60 **

    61 ** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is

    62 ** a hash table that will hold up to BITVEC_MXHASH distinct values.

    63 **

    64 ** Otherwise, the value i is redirected into one of BITVEC_NPTR

    65 ** sub-bitmaps pointed to by Bitvec.u.apSub[].  Each subbitmap

    66 ** handles up to iDivisor separate values of i.  apSub[0] holds

    67 ** values between 1 and iDivisor.  apSub[1] holds values between

    68 ** iDivisor+1 and 2*iDivisor.  apSub[N] holds values between

    69 ** N*iDivisor+1 and (N+1)*iDivisor.  Each subbitmap is normalized

    70 ** to hold deal with values between 1 and iDivisor.

    71 */

    72 struct Bitvec {

    73   u32 iSize;      /* Maximum bit index */

    74   u32 nSet;       /* Number of bits that are set */

    75   u32 iDivisor;   /* Number of bits handled by each apSub[] entry */

    76   union {

    77     u8 aBitmap[BITVEC_NCHAR];    /* Bitmap representation */

    78     u32 aHash[BITVEC_NINT];      /* Hash table representation */

    79     Bitvec *apSub[BITVEC_NPTR];  /* Recursive representation */

    80   } u;

    81 };

    82 

    83 /*

    84 ** Create a new bitmap object able to handle bits between 0 and iSize,

    85 ** inclusive.  Return a pointer to the new object.  Return NULL if 

    86 ** malloc fails.

    87 */

    88 Bitvec *sqlite3BitvecCreate(u32 iSize){

    89   Bitvec *p;

    90   assert( sizeof(*p)==BITVEC_SZ );

    91   p = sqlite3MallocZero( sizeof(*p) );

    92   if( p ){

    93     p->iSize = iSize;

    94   }

    95   return p;

    96 }

    97 

    98 /*

    99 ** Check to see if the i-th bit is set.  Return true or false.

   100 ** If p is NULL (if the bitmap has not been created) or if

   101 ** i is out of range, then return false.

   102 */

   103 int sqlite3BitvecTest(Bitvec *p, u32 i){

   104   if( p==0 ) return 0;

   105   if( i>p->iSize || i==0 ) return 0;

   106   if( p->iSize<=BITVEC_NBIT ){

   107     i--;

   108     return (p->u.aBitmap[i/8] & (1<<(i&7)))!=0;

   109   }

   110   if( p->iDivisor>0 ){

   111     u32 bin = (i-1)/p->iDivisor;

   112     i = (i-1)%p->iDivisor + 1;

   113     return sqlite3BitvecTest(p->u.apSub[bin], i);

   114   }else{

   115     u32 h = BITVEC_HASH(i);

   116     while( p->u.aHash[h] ){

   117       if( p->u.aHash[h]==i ) return 1;

   118       h++;

   119       if( h>=BITVEC_NINT ) h = 0;

   120     }

   121     return 0;

   122   }

   123 }

   124 

   125 /*

   126 ** Set the i-th bit.  Return 0 on success and an error code if

   127 ** anything goes wrong.

   128 */

   129 int sqlite3BitvecSet(Bitvec *p, u32 i){

   130   u32 h;

   131   assert( p!=0 );

   132   assert( i>0 );

   133   assert( i<=p->iSize );

   134   if( p->iSize<=BITVEC_NBIT ){

   135     i--;

   136     p->u.aBitmap[i/8] |= 1 << (i&7);

   137     return SQLITE_OK;

   138   }

   139   if( p->iDivisor ){

   140     u32 bin = (i-1)/p->iDivisor;

   141     i = (i-1)%p->iDivisor + 1;

   142     if( p->u.apSub[bin]==0 ){

   143       sqlite3BeginBenignMalloc();

   144       p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor );

   145       sqlite3EndBenignMalloc();

   146       if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM;

   147     }

   148     return sqlite3BitvecSet(p->u.apSub[bin], i);

   149   }

   150   h = BITVEC_HASH(i);

   151   while( p->u.aHash[h] ){

   152     if( p->u.aHash[h]==i ) return SQLITE_OK;

   153     h++;

   154     if( h==BITVEC_NINT ) h = 0;

   155   }

   156   p->nSet++;

   157   if( p->nSet>=BITVEC_MXHASH ){

   158     int j, rc;

   159     u32 aiValues[BITVEC_NINT];

   160     memcpy(aiValues, p->u.aHash, sizeof(aiValues));

   161     memset(p->u.apSub, 0, sizeof(p->u.apSub[0])*BITVEC_NPTR);

   162     p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR;

   163     rc = sqlite3BitvecSet(p, i);

   164     for(j=0; j<BITVEC_NINT; j++){

   165       if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]);

   166     }

   167     return rc;

   168   }

   169   p->u.aHash[h] = i;

   170   return SQLITE_OK;

   171 }

   172 

   173 /*

   174 ** Clear the i-th bit.  Return 0 on success and an error code if

   175 ** anything goes wrong.

   176 */

   177 void sqlite3BitvecClear(Bitvec *p, u32 i){

   178   assert( p!=0 );

   179   assert( i>0 );

   180   if( p->iSize<=BITVEC_NBIT ){

   181     i--;

   182     p->u.aBitmap[i/8] &= ~(1 << (i&7));

   183   }else if( p->iDivisor ){

   184     u32 bin = (i-1)/p->iDivisor;

   185     i = (i-1)%p->iDivisor + 1;

   186     if( p->u.apSub[bin] ){

   187       sqlite3BitvecClear(p->u.apSub[bin], i);

   188     }

   189   }else{

   190     int j;

   191     u32 aiValues[BITVEC_NINT];

   192     memcpy(aiValues, p->u.aHash, sizeof(aiValues));

   193     memset(p->u.aHash, 0, sizeof(p->u.aHash[0])*BITVEC_NINT);

   194     p->nSet = 0;

   195     for(j=0; j<BITVEC_NINT; j++){

   196       if( aiValues[j] && aiValues[j]!=i ){

   197         sqlite3BitvecSet(p, aiValues[j]);

   198       }

   199     }

   200   }

   201 }

   202 

   203 /*

   204 ** Destroy a bitmap object.  Reclaim all memory used.

   205 */

   206 void sqlite3BitvecDestroy(Bitvec *p){

   207   if( p==0 ) return;

   208   if( p->iDivisor ){

   209     int i;

   210     for(i=0; i<BITVEC_NPTR; i++){

   211       sqlite3BitvecDestroy(p->u.apSub[i]);

   212     }

   213   }

   214   sqlite3_free(p);

   215 }

   216 

   217 #ifndef SQLITE_OMIT_BUILTIN_TEST

   218 /*

   219 ** Let V[] be an array of unsigned characters sufficient to hold

   220 ** up to N bits.  Let I be an integer between 0 and N.  0<=I<N.

   221 ** Then the following macros can be used to set, clear, or test

   222 ** individual bits within V.

   223 */

   224 #define SETBIT(V,I)      V[I>>3] |= (1<<(I&7))

   225 #define CLEARBIT(V,I)    V[I>>3] &= ~(1<<(I&7))

   226 #define TESTBIT(V,I)     (V[I>>3]&(1<<(I&7)))!=0

   227 

   228 /*

   229 ** This routine runs an extensive test of the Bitvec code.

   230 **

   231 ** The input is an array of integers that acts as a program

   232 ** to test the Bitvec.  The integers are opcodes followed

   233 ** by 0, 1, or 3 operands, depending on the opcode.  Another

   234 ** opcode follows immediately after the last operand.

   235 **

   236 ** There are 6 opcodes numbered from 0 through 5.  0 is the

   237 ** "halt" opcode and causes the test to end.

   238 **

   239 **    0          Halt and return the number of errors

   240 **    1 N S X    Set N bits beginning with S and incrementing by X

   241 **    2 N S X    Clear N bits beginning with S and incrementing by X

   242 **    3 N        Set N randomly chosen bits

   243 **    4 N        Clear N randomly chosen bits

   244 **    5 N S X    Set N bits from S increment X in array only, not in bitvec

   245 **

   246 ** The opcodes 1 through 4 perform set and clear operations are performed

   247 ** on both a Bitvec object and on a linear array of bits obtained from malloc.

   248 ** Opcode 5 works on the linear array only, not on the Bitvec.

   249 ** Opcode 5 is used to deliberately induce a fault in order to

   250 ** confirm that error detection works.

   251 **

   252 ** At the conclusion of the test the linear array is compared

   253 ** against the Bitvec object.  If there are any differences,

   254 ** an error is returned.  If they are the same, zero is returned.

   255 **

   256 ** If a memory allocation error occurs, return -1.

   257 */

   258 int sqlite3BitvecBuiltinTest(int sz, int *aOp){

   259   Bitvec *pBitvec = 0;

   260   unsigned char *pV = 0;

   261   int rc = -1;

   262   int i, nx, pc, op;

   263 

   264   /* Allocate the Bitvec to be tested and a linear array of

   265   ** bits to act as the reference */

   266   pBitvec = sqlite3BitvecCreate( sz );

   267   pV = sqlite3_malloc( (sz+7)/8 + 1 );

   268   if( pBitvec==0 || pV==0 ) goto bitvec_end;

   269   memset(pV, 0, (sz+7)/8 + 1);

   270 

   271   /* Run the program */

   272   pc = 0;

   273   while( (op = aOp[pc])!=0 ){

   274     switch( op ){

   275       case 1:

   276       case 2:

   277       case 5: {

   278         nx = 4;

   279         i = aOp[pc+2] - 1;

   280         aOp[pc+2] += aOp[pc+3];

   281         break;

   282       }

   283       case 3:

   284       case 4: 

   285       default: {

   286         nx = 2;

   287         sqlite3_randomness(sizeof(i), &i);

   288         break;

   289       }

   290     }

   291     if( (--aOp[pc+1]) > 0 ) nx = 0;

   292     pc += nx;

   293     i = (i & 0x7fffffff)%sz;

   294     if( (op & 1)!=0 ){

   295       SETBIT(pV, (i+1));

   296       if( op!=5 ){

   297         if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end;

   298       }

   299     }else{

   300       CLEARBIT(pV, (i+1));

   301       sqlite3BitvecClear(pBitvec, i+1);

   302     }

   303   }

   304 

   305   /* Test to make sure the linear array exactly matches the

   306   ** Bitvec object.  Start with the assumption that they do

   307   ** match (rc==0).  Change rc to non-zero if a discrepancy

   308   ** is found.

   309   */

   310   rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1)

   311           + sqlite3BitvecTest(pBitvec, 0);

   312   for(i=1; i<=sz; i++){

   313     if(  (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){

   314       rc = i;

   315       break;

   316     }

   317   }

   318 

   319   /* Free allocated structure */

   320 bitvec_end:

   321   sqlite3_free(pV);

   322   sqlite3BitvecDestroy(pBitvec);

   323   return rc;

   324 }

   325 #endif /* SQLITE_OMIT_BUILTIN_TEST */