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