persistentstorage/sql/SQLite/bitvec.c
changeset 0 08ec8eefde2f
equal deleted inserted replaced
-1:000000000000 0:08ec8eefde2f
       
     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 */