diff -r 000000000000 -r 08ec8eefde2f persistentstorage/sql/SQLite/bitvec.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/persistentstorage/sql/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; ju.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; jiDivisor ){ + int i; + for(i=0; iu.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>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 */