sl@0: /*
sl@0: ** 2008 February 16
sl@0: **
sl@0: ** The author disclaims copyright to this source code.  In place of
sl@0: ** a legal notice, here is a blessing:
sl@0: **
sl@0: **    May you do good and not evil.
sl@0: **    May you find forgiveness for yourself and forgive others.
sl@0: **    May you share freely, never taking more than you give.
sl@0: **
sl@0: *************************************************************************
sl@0: ** This file implements an object that represents a fixed-length
sl@0: ** bitmap.  Bits are numbered starting with 1.
sl@0: **
sl@0: ** A bitmap is used to record what pages a database file have been
sl@0: ** journalled during a transaction.  Usually only a few pages are
sl@0: ** journalled.  So the bitmap is usually sparse and has low cardinality.
sl@0: ** But sometimes (for example when during a DROP of a large table) most
sl@0: ** or all of the pages get journalled.  In those cases, the bitmap becomes
sl@0: ** dense.  The algorithm needs to handle both cases well.
sl@0: **
sl@0: ** The size of the bitmap is fixed when the object is created.
sl@0: **
sl@0: ** All bits are clear when the bitmap is created.  Individual bits
sl@0: ** may be set or cleared one at a time.
sl@0: **
sl@0: ** Test operations are about 100 times more common that set operations.
sl@0: ** Clear operations are exceedingly rare.  There are usually between
sl@0: ** 5 and 500 set operations per Bitvec object, though the number of sets can
sl@0: ** sometimes grow into tens of thousands or larger.  The size of the
sl@0: ** Bitvec object is the number of pages in the database file at the
sl@0: ** start of a transaction, and is thus usually less than a few thousand,
sl@0: ** but can be as large as 2 billion for a really big database.
sl@0: **
sl@0: ** @(#) $Id: bitvec.c,v 1.6 2008/06/20 14:59:51 danielk1977 Exp $
sl@0: */
sl@0: #include "sqliteInt.h"
sl@0: 
sl@0: #define BITVEC_SZ        512
sl@0: /* Round the union size down to the nearest pointer boundary, since that's how 
sl@0: ** it will be aligned within the Bitvec struct. */
sl@0: #define BITVEC_USIZE     (((BITVEC_SZ-12)/sizeof(Bitvec*))*sizeof(Bitvec*))
sl@0: #define BITVEC_NCHAR     BITVEC_USIZE
sl@0: #define BITVEC_NBIT      (BITVEC_NCHAR*8)
sl@0: #define BITVEC_NINT      (BITVEC_USIZE/4)
sl@0: #define BITVEC_MXHASH    (BITVEC_NINT/2)
sl@0: #define BITVEC_NPTR      (BITVEC_USIZE/sizeof(Bitvec *))
sl@0: 
sl@0: #define BITVEC_HASH(X)   (((X)*37)%BITVEC_NINT)
sl@0: 
sl@0: /*
sl@0: ** A bitmap is an instance of the following structure.
sl@0: **
sl@0: ** This bitmap records the existance of zero or more bits
sl@0: ** with values between 1 and iSize, inclusive.
sl@0: **
sl@0: ** There are three possible representations of the bitmap.
sl@0: ** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight
sl@0: ** bitmap.  The least significant bit is bit 1.
sl@0: **
sl@0: ** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is
sl@0: ** a hash table that will hold up to BITVEC_MXHASH distinct values.
sl@0: **
sl@0: ** Otherwise, the value i is redirected into one of BITVEC_NPTR
sl@0: ** sub-bitmaps pointed to by Bitvec.u.apSub[].  Each subbitmap
sl@0: ** handles up to iDivisor separate values of i.  apSub[0] holds
sl@0: ** values between 1 and iDivisor.  apSub[1] holds values between
sl@0: ** iDivisor+1 and 2*iDivisor.  apSub[N] holds values between
sl@0: ** N*iDivisor+1 and (N+1)*iDivisor.  Each subbitmap is normalized
sl@0: ** to hold deal with values between 1 and iDivisor.
sl@0: */
sl@0: struct Bitvec {
sl@0:   u32 iSize;      /* Maximum bit index */
sl@0:   u32 nSet;       /* Number of bits that are set */
sl@0:   u32 iDivisor;   /* Number of bits handled by each apSub[] entry */
sl@0:   union {
sl@0:     u8 aBitmap[BITVEC_NCHAR];    /* Bitmap representation */
sl@0:     u32 aHash[BITVEC_NINT];      /* Hash table representation */
sl@0:     Bitvec *apSub[BITVEC_NPTR];  /* Recursive representation */
sl@0:   } u;
sl@0: };
sl@0: 
sl@0: /*
sl@0: ** Create a new bitmap object able to handle bits between 0 and iSize,
sl@0: ** inclusive.  Return a pointer to the new object.  Return NULL if 
sl@0: ** malloc fails.
sl@0: */
sl@0: Bitvec *sqlite3BitvecCreate(u32 iSize){
sl@0:   Bitvec *p;
sl@0:   assert( sizeof(*p)==BITVEC_SZ );
sl@0:   p = sqlite3MallocZero( sizeof(*p) );
sl@0:   if( p ){
sl@0:     p->iSize = iSize;
sl@0:   }
sl@0:   return p;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Check to see if the i-th bit is set.  Return true or false.
sl@0: ** If p is NULL (if the bitmap has not been created) or if
sl@0: ** i is out of range, then return false.
sl@0: */
sl@0: int sqlite3BitvecTest(Bitvec *p, u32 i){
sl@0:   if( p==0 ) return 0;
sl@0:   if( i>p->iSize || i==0 ) return 0;
sl@0:   if( p->iSize<=BITVEC_NBIT ){
sl@0:     i--;
sl@0:     return (p->u.aBitmap[i/8] & (1<<(i&7)))!=0;
sl@0:   }
sl@0:   if( p->iDivisor>0 ){
sl@0:     u32 bin = (i-1)/p->iDivisor;
sl@0:     i = (i-1)%p->iDivisor + 1;
sl@0:     return sqlite3BitvecTest(p->u.apSub[bin], i);
sl@0:   }else{
sl@0:     u32 h = BITVEC_HASH(i);
sl@0:     while( p->u.aHash[h] ){
sl@0:       if( p->u.aHash[h]==i ) return 1;
sl@0:       h++;
sl@0:       if( h>=BITVEC_NINT ) h = 0;
sl@0:     }
sl@0:     return 0;
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Set the i-th bit.  Return 0 on success and an error code if
sl@0: ** anything goes wrong.
sl@0: */
sl@0: int sqlite3BitvecSet(Bitvec *p, u32 i){
sl@0:   u32 h;
sl@0:   assert( p!=0 );
sl@0:   assert( i>0 );
sl@0:   assert( i<=p->iSize );
sl@0:   if( p->iSize<=BITVEC_NBIT ){
sl@0:     i--;
sl@0:     p->u.aBitmap[i/8] |= 1 << (i&7);
sl@0:     return SQLITE_OK;
sl@0:   }
sl@0:   if( p->iDivisor ){
sl@0:     u32 bin = (i-1)/p->iDivisor;
sl@0:     i = (i-1)%p->iDivisor + 1;
sl@0:     if( p->u.apSub[bin]==0 ){
sl@0:       sqlite3BeginBenignMalloc();
sl@0:       p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor );
sl@0:       sqlite3EndBenignMalloc();
sl@0:       if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM;
sl@0:     }
sl@0:     return sqlite3BitvecSet(p->u.apSub[bin], i);
sl@0:   }
sl@0:   h = BITVEC_HASH(i);
sl@0:   while( p->u.aHash[h] ){
sl@0:     if( p->u.aHash[h]==i ) return SQLITE_OK;
sl@0:     h++;
sl@0:     if( h==BITVEC_NINT ) h = 0;
sl@0:   }
sl@0:   p->nSet++;
sl@0:   if( p->nSet>=BITVEC_MXHASH ){
sl@0:     int j, rc;
sl@0:     u32 aiValues[BITVEC_NINT];
sl@0:     memcpy(aiValues, p->u.aHash, sizeof(aiValues));
sl@0:     memset(p->u.apSub, 0, sizeof(p->u.apSub[0])*BITVEC_NPTR);
sl@0:     p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR;
sl@0:     rc = sqlite3BitvecSet(p, i);
sl@0:     for(j=0; j<BITVEC_NINT; j++){
sl@0:       if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]);
sl@0:     }
sl@0:     return rc;
sl@0:   }
sl@0:   p->u.aHash[h] = i;
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Clear the i-th bit.  Return 0 on success and an error code if
sl@0: ** anything goes wrong.
sl@0: */
sl@0: void sqlite3BitvecClear(Bitvec *p, u32 i){
sl@0:   assert( p!=0 );
sl@0:   assert( i>0 );
sl@0:   if( p->iSize<=BITVEC_NBIT ){
sl@0:     i--;
sl@0:     p->u.aBitmap[i/8] &= ~(1 << (i&7));
sl@0:   }else if( p->iDivisor ){
sl@0:     u32 bin = (i-1)/p->iDivisor;
sl@0:     i = (i-1)%p->iDivisor + 1;
sl@0:     if( p->u.apSub[bin] ){
sl@0:       sqlite3BitvecClear(p->u.apSub[bin], i);
sl@0:     }
sl@0:   }else{
sl@0:     int j;
sl@0:     u32 aiValues[BITVEC_NINT];
sl@0:     memcpy(aiValues, p->u.aHash, sizeof(aiValues));
sl@0:     memset(p->u.aHash, 0, sizeof(p->u.aHash[0])*BITVEC_NINT);
sl@0:     p->nSet = 0;
sl@0:     for(j=0; j<BITVEC_NINT; j++){
sl@0:       if( aiValues[j] && aiValues[j]!=i ){
sl@0:         sqlite3BitvecSet(p, aiValues[j]);
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Destroy a bitmap object.  Reclaim all memory used.
sl@0: */
sl@0: void sqlite3BitvecDestroy(Bitvec *p){
sl@0:   if( p==0 ) return;
sl@0:   if( p->iDivisor ){
sl@0:     int i;
sl@0:     for(i=0; i<BITVEC_NPTR; i++){
sl@0:       sqlite3BitvecDestroy(p->u.apSub[i]);
sl@0:     }
sl@0:   }
sl@0:   sqlite3_free(p);
sl@0: }
sl@0: 
sl@0: #ifndef SQLITE_OMIT_BUILTIN_TEST
sl@0: /*
sl@0: ** Let V[] be an array of unsigned characters sufficient to hold
sl@0: ** up to N bits.  Let I be an integer between 0 and N.  0<=I<N.
sl@0: ** Then the following macros can be used to set, clear, or test
sl@0: ** individual bits within V.
sl@0: */
sl@0: #define SETBIT(V,I)      V[I>>3] |= (1<<(I&7))
sl@0: #define CLEARBIT(V,I)    V[I>>3] &= ~(1<<(I&7))
sl@0: #define TESTBIT(V,I)     (V[I>>3]&(1<<(I&7)))!=0
sl@0: 
sl@0: /*
sl@0: ** This routine runs an extensive test of the Bitvec code.
sl@0: **
sl@0: ** The input is an array of integers that acts as a program
sl@0: ** to test the Bitvec.  The integers are opcodes followed
sl@0: ** by 0, 1, or 3 operands, depending on the opcode.  Another
sl@0: ** opcode follows immediately after the last operand.
sl@0: **
sl@0: ** There are 6 opcodes numbered from 0 through 5.  0 is the
sl@0: ** "halt" opcode and causes the test to end.
sl@0: **
sl@0: **    0          Halt and return the number of errors
sl@0: **    1 N S X    Set N bits beginning with S and incrementing by X
sl@0: **    2 N S X    Clear N bits beginning with S and incrementing by X
sl@0: **    3 N        Set N randomly chosen bits
sl@0: **    4 N        Clear N randomly chosen bits
sl@0: **    5 N S X    Set N bits from S increment X in array only, not in bitvec
sl@0: **
sl@0: ** The opcodes 1 through 4 perform set and clear operations are performed
sl@0: ** on both a Bitvec object and on a linear array of bits obtained from malloc.
sl@0: ** Opcode 5 works on the linear array only, not on the Bitvec.
sl@0: ** Opcode 5 is used to deliberately induce a fault in order to
sl@0: ** confirm that error detection works.
sl@0: **
sl@0: ** At the conclusion of the test the linear array is compared
sl@0: ** against the Bitvec object.  If there are any differences,
sl@0: ** an error is returned.  If they are the same, zero is returned.
sl@0: **
sl@0: ** If a memory allocation error occurs, return -1.
sl@0: */
sl@0: int sqlite3BitvecBuiltinTest(int sz, int *aOp){
sl@0:   Bitvec *pBitvec = 0;
sl@0:   unsigned char *pV = 0;
sl@0:   int rc = -1;
sl@0:   int i, nx, pc, op;
sl@0: 
sl@0:   /* Allocate the Bitvec to be tested and a linear array of
sl@0:   ** bits to act as the reference */
sl@0:   pBitvec = sqlite3BitvecCreate( sz );
sl@0:   pV = sqlite3_malloc( (sz+7)/8 + 1 );
sl@0:   if( pBitvec==0 || pV==0 ) goto bitvec_end;
sl@0:   memset(pV, 0, (sz+7)/8 + 1);
sl@0: 
sl@0:   /* Run the program */
sl@0:   pc = 0;
sl@0:   while( (op = aOp[pc])!=0 ){
sl@0:     switch( op ){
sl@0:       case 1:
sl@0:       case 2:
sl@0:       case 5: {
sl@0:         nx = 4;
sl@0:         i = aOp[pc+2] - 1;
sl@0:         aOp[pc+2] += aOp[pc+3];
sl@0:         break;
sl@0:       }
sl@0:       case 3:
sl@0:       case 4: 
sl@0:       default: {
sl@0:         nx = 2;
sl@0:         sqlite3_randomness(sizeof(i), &i);
sl@0:         break;
sl@0:       }
sl@0:     }
sl@0:     if( (--aOp[pc+1]) > 0 ) nx = 0;
sl@0:     pc += nx;
sl@0:     i = (i & 0x7fffffff)%sz;
sl@0:     if( (op & 1)!=0 ){
sl@0:       SETBIT(pV, (i+1));
sl@0:       if( op!=5 ){
sl@0:         if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end;
sl@0:       }
sl@0:     }else{
sl@0:       CLEARBIT(pV, (i+1));
sl@0:       sqlite3BitvecClear(pBitvec, i+1);
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   /* Test to make sure the linear array exactly matches the
sl@0:   ** Bitvec object.  Start with the assumption that they do
sl@0:   ** match (rc==0).  Change rc to non-zero if a discrepancy
sl@0:   ** is found.
sl@0:   */
sl@0:   rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1)
sl@0:           + sqlite3BitvecTest(pBitvec, 0);
sl@0:   for(i=1; i<=sz; i++){
sl@0:     if(  (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){
sl@0:       rc = i;
sl@0:       break;
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   /* Free allocated structure */
sl@0: bitvec_end:
sl@0:   sqlite3_free(pV);
sl@0:   sqlite3BitvecDestroy(pBitvec);
sl@0:   return rc;
sl@0: }
sl@0: #endif /* SQLITE_OMIT_BUILTIN_TEST */