AryaWu/sqlite
0
1/*2** 2008 February 163**4** The author disclaims copyright to this source code. In place of5** 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-length13** bitmap. Bits are numbered starting with 1.14**15** A bitmap is used to record which pages of a database file have been16** journalled during a transaction, or which pages have the "dont-write"17** property. Usually only a few pages are meet either condition.18** So the bitmap is usually sparse and has low cardinality.19** But sometimes (for example when during a DROP of a large table) most20** or all of the pages in a database can get journalled. In those cases,21** the bitmap becomes dense with high cardinality. The algorithm needs22** to handle both cases well.23**24** The size of the bitmap is fixed when the object is created.25**26** All bits are clear when the bitmap is created. Individual bits27** may be set or cleared one at a time.28**29** Test operations are about 100 times more common that set operations.30** Clear operations are exceedingly rare. There are usually between31** 5 and 500 set operations per Bitvec object, though the number of sets can32** sometimes grow into tens of thousands or larger. The size of the33** Bitvec object is the number of pages in the database file at the34** start of a transaction, and is thus usually less than a few thousand,35** but can be as large as 2 billion for a really big database.36*/37#include "sqliteInt.h"38 39/* Size of the Bitvec structure in bytes. */40#define BITVEC_SZ 51241 42/* Round the union size down to the nearest pointer boundary, since that's how43** it will be aligned within the Bitvec struct. */44#define BITVEC_USIZE \45 (((BITVEC_SZ-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(Bitvec*))46 47/* Type of the array "element" for the bitmap representation.48** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE.49** Setting this to the "natural word" size of your CPU may improve50** performance. */51#define BITVEC_TELEM u852/* Size, in bits, of the bitmap element. */53#define BITVEC_SZELEM 854/* Number of elements in a bitmap array. */55#define BITVEC_NELEM (BITVEC_USIZE/sizeof(BITVEC_TELEM))56/* Number of bits in the bitmap array. */57#define BITVEC_NBIT (BITVEC_NELEM*BITVEC_SZELEM)58 59/* Number of u32 values in hash table. */60#define BITVEC_NINT (BITVEC_USIZE/sizeof(u32))61/* Maximum number of entries in hash table before62** sub-dividing and re-hashing. */63#define BITVEC_MXHASH (BITVEC_NINT/2)64/* Hashing function for the aHash representation.65** Empirical testing showed that the *37 multiplier66** (an arbitrary prime)in the hash function provided67** no fewer collisions than the no-op *1. */68#define BITVEC_HASH(X) (((X)*1)%BITVEC_NINT)69 70#define BITVEC_NPTR ((u32)(BITVEC_USIZE/sizeof(Bitvec *)))71 72 73/*74** A bitmap is an instance of the following structure.75**76** This bitmap records the existence of zero or more bits77** with values between 1 and iSize, inclusive.78**79** There are three possible representations of the bitmap.80** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight81** bitmap. The least significant bit is bit 1.82**83** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is84** a hash table that will hold up to BITVEC_MXHASH distinct values.85**86** Otherwise, the value i is redirected into one of BITVEC_NPTR87** sub-bitmaps pointed to by Bitvec.u.apSub[]. Each subbitmap88** handles up to iDivisor separate values of i. apSub[0] holds89** values between 1 and iDivisor. apSub[1] holds values between90** iDivisor+1 and 2*iDivisor. apSub[N] holds values between91** N*iDivisor+1 and (N+1)*iDivisor. Each subbitmap is normalized92** to hold deal with values between 1 and iDivisor.93*/94struct Bitvec {95 u32 iSize; /* Maximum bit index. Max iSize is 4,294,967,296. */96 u32 nSet; /* Number of bits that are set - only valid for aHash97 ** element. Max is BITVEC_NINT. For BITVEC_SZ of 512,98 ** this would be 125. */99 u32 iDivisor; /* Number of bits handled by each apSub[] entry. */100 /* Should >=0 for apSub element. */101 /* Max iDivisor is max(u32) / BITVEC_NPTR + 1. */102 /* For a BITVEC_SZ of 512, this would be 34,359,739. */103 union {104 BITVEC_TELEM aBitmap[BITVEC_NELEM]; /* Bitmap representation */105 u32 aHash[BITVEC_NINT]; /* Hash table representation */106 Bitvec *apSub[BITVEC_NPTR]; /* Recursive representation */107 } u;108};109 110 111/*112** Create a new bitmap object able to handle bits between 0 and iSize,113** inclusive. Return a pointer to the new object. Return NULL if114** malloc fails.115*/116Bitvec *sqlite3BitvecCreate(u32 iSize){117 Bitvec *p;118 assert( sizeof(*p)==BITVEC_SZ );119 p = sqlite3MallocZero( sizeof(*p) );120 if( p ){121 p->iSize = iSize;122 }123 return p;124}125 126/*127** Check to see if the i-th bit is set. Return true or false.128** If p is NULL (if the bitmap has not been created) or if129** i is out of range, then return false.130*/131int sqlite3BitvecTestNotNull(Bitvec *p, u32 i){132 assert( p!=0 );133 i--;134 if( i>=p->iSize ) return 0;135 while( p->iDivisor ){136 u32 bin = i/p->iDivisor;137 i = i%p->iDivisor;138 p = p->u.apSub[bin];139 if (!p) {140 return 0;141 }142 }143 if( p->iSize<=BITVEC_NBIT ){144 return (p->u.aBitmap[i/BITVEC_SZELEM] & (1<<(i&(BITVEC_SZELEM-1))))!=0;145 } else{146 u32 h = BITVEC_HASH(i++);147 while( p->u.aHash[h] ){148 if( p->u.aHash[h]==i ) return 1;149 h = (h+1) % BITVEC_NINT;150 }151 return 0;152 }153}154int sqlite3BitvecTest(Bitvec *p, u32 i){155 return p!=0 && sqlite3BitvecTestNotNull(p,i);156}157 158/*159** Set the i-th bit. Return 0 on success and an error code if160** anything goes wrong.161**162** This routine might cause sub-bitmaps to be allocated. Failing163** to get the memory needed to hold the sub-bitmap is the only164** that can go wrong with an insert, assuming p and i are valid.165**166** The calling function must ensure that p is a valid Bitvec object167** and that the value for "i" is within range of the Bitvec object.168** Otherwise the behavior is undefined.169*/170int sqlite3BitvecSet(Bitvec *p, u32 i){171 u32 h;172 if( p==0 ) return SQLITE_OK;173 assert( i>0 );174 assert( i<=p->iSize );175 i--;176 while((p->iSize > BITVEC_NBIT) && p->iDivisor) {177 u32 bin = i/p->iDivisor;178 i = i%p->iDivisor;179 if( p->u.apSub[bin]==0 ){180 p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor );181 if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM_BKPT;182 }183 p = p->u.apSub[bin];184 }185 if( p->iSize<=BITVEC_NBIT ){186 p->u.aBitmap[i/BITVEC_SZELEM] |= 1 << (i&(BITVEC_SZELEM-1));187 return SQLITE_OK;188 }189 h = BITVEC_HASH(i++);190 /* if there wasn't a hash collision, and this doesn't */191 /* completely fill the hash, then just add it without */192 /* worrying about sub-dividing and re-hashing. */193 if( !p->u.aHash[h] ){194 if (p->nSet<(BITVEC_NINT-1)) {195 goto bitvec_set_end;196 } else {197 goto bitvec_set_rehash;198 }199 }200 /* there was a collision, check to see if it's already */201 /* in hash, if not, try to find a spot for it */202 do {203 if( p->u.aHash[h]==i ) return SQLITE_OK;204 h++;205 if( h>=BITVEC_NINT ) h = 0;206 } while( p->u.aHash[h] );207 /* we didn't find it in the hash. h points to the first */208 /* available free spot. check to see if this is going to */209 /* make our hash too "full". */210bitvec_set_rehash:211 if( p->nSet>=BITVEC_MXHASH ){212 unsigned int j;213 int rc;214 u32 *aiValues = sqlite3StackAllocRaw(0, sizeof(p->u.aHash));215 if( aiValues==0 ){216 return SQLITE_NOMEM_BKPT;217 }else{218 memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));219 memset(p->u.apSub, 0, sizeof(p->u.apSub));220 p->iDivisor = p->iSize/BITVEC_NPTR;221 if( (p->iSize%BITVEC_NPTR)!=0 ) p->iDivisor++;222 if( p->iDivisor<BITVEC_NBIT ) p->iDivisor = BITVEC_NBIT;223 rc = sqlite3BitvecSet(p, i);224 for(j=0; j<BITVEC_NINT; j++){225 if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]);226 }227 sqlite3StackFree(0, aiValues);228 return rc;229 }230 }231bitvec_set_end:232 p->nSet++;233 p->u.aHash[h] = i;234 return SQLITE_OK;235}236 237/*238** Clear the i-th bit.239**240** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage241** that BitvecClear can use to rebuilt its hash table.242*/243void sqlite3BitvecClear(Bitvec *p, u32 i, void *pBuf){244 if( p==0 ) return;245 assert( i>0 );246 i--;247 while( p->iDivisor ){248 u32 bin = i/p->iDivisor;249 i = i%p->iDivisor;250 p = p->u.apSub[bin];251 if (!p) {252 return;253 }254 }255 if( p->iSize<=BITVEC_NBIT ){256 p->u.aBitmap[i/BITVEC_SZELEM] &= ~(BITVEC_TELEM)(1<<(i&(BITVEC_SZELEM-1)));257 }else{258 unsigned int j;259 u32 *aiValues = pBuf;260 memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));261 memset(p->u.aHash, 0, sizeof(p->u.aHash));262 p->nSet = 0;263 for(j=0; j<BITVEC_NINT; j++){264 if( aiValues[j] && aiValues[j]!=(i+1) ){265 u32 h = BITVEC_HASH(aiValues[j]-1);266 p->nSet++;267 while( p->u.aHash[h] ){268 h++;269 if( h>=BITVEC_NINT ) h = 0;270 }271 p->u.aHash[h] = aiValues[j];272 }273 }274 }275}276 277/*278** Destroy a bitmap object. Reclaim all memory used.279*/280void sqlite3BitvecDestroy(Bitvec *p){281 if( p==0 ) return;282 if( p->iDivisor ){283 unsigned int i;284 for(i=0; i<BITVEC_NPTR; i++){285 sqlite3BitvecDestroy(p->u.apSub[i]);286 }287 }288 sqlite3_free(p);289}290 291/*292** Return the value of the iSize parameter specified when Bitvec *p293** was created.294*/295u32 sqlite3BitvecSize(Bitvec *p){296 return p->iSize;297}298 299#ifdef SQLITE_DEBUG300/*301** Show the content of a Bitvec option and its children. Indent302** everything by n spaces. Add x to each bitvec value.303**304** From a debugger such as gdb, one can type:305**306** call sqlite3ShowBitvec(p)307**308** For some Bitvec p and see a recursive view of the Bitvec's content.309*/310static void showBitvec(Bitvec *p, int n, unsigned x){311 int i;312 if( p==0 ){313 printf("NULL\n");314 return;315 }316 printf("Bitvec 0x%p iSize=%u", p, p->iSize);317 if( p->iSize<=BITVEC_NBIT ){318 printf(" bitmap\n");319 printf("%*s bits:", n, "");320 for(i=1; i<=BITVEC_NBIT; i++){321 if( sqlite3BitvecTest(p,i) ) printf(" %u", x+(unsigned)i);322 }323 printf("\n");324 }else if( p->iDivisor==0 ){325 printf(" hash with %u entries\n", p->nSet);326 printf("%*s bits:", n, "");327 for(i=0; i<BITVEC_NINT; i++){328 if( p->u.aHash[i] ) printf(" %u", x+(unsigned)p->u.aHash[i]);329 }330 printf("\n");331 }else{332 printf(" sub-bitvec with iDivisor=%u\n", p->iDivisor);333 for(i=0; i<BITVEC_NPTR; i++){334 if( p->u.apSub[i]==0 ) continue;335 printf("%*s apSub[%d]=", n, "", i);336 showBitvec(p->u.apSub[i], n+4, i*p->iDivisor);337 }338 }339}340void sqlite3ShowBitvec(Bitvec *p){341 showBitvec(p, 0, 0);342}343#endif344 345#ifndef SQLITE_UNTESTABLE346/*347** Let V[] be an array of unsigned characters sufficient to hold348** up to N bits. Let I be an integer between 0 and N. 0<=I<N.349** Then the following macros can be used to set, clear, or test350** individual bits within V.351*/352#define SETBIT(V,I) V[I>>3] |= (1<<(I&7))353#define CLEARBIT(V,I) V[I>>3] &= ~(BITVEC_TELEM)(1<<(I&7))354#define TESTBIT(V,I) (V[I>>3]&(1<<(I&7)))!=0355 356 357/*358** This routine runs an extensive test of the Bitvec code.359**360** The input is an array of integers that acts as a program361** to test the Bitvec. The integers are opcodes followed362** by 0, 1, or 3 operands, depending on the opcode. Another363** opcode follows immediately after the last operand.364**365** There are opcodes numbered starting with 0. 0 is the366** "halt" opcode and causes the test to end.367**368** 0 Halt and return the number of errors369** 1 N S X Set N bits beginning with S and incrementing by X370** 2 N S X Clear N bits beginning with S and incrementing by X371** 3 N Set N randomly chosen bits372** 4 N Clear N randomly chosen bits373** 5 N S X Set N bits from S increment X in array only, not in bitvec374** 6 Invoice sqlite3ShowBitvec() on the Bitvec object so far375** 7 X Show compile-time parameters and the hash of X 376**377** The opcodes 1 through 4 perform set and clear operations are performed378** on both a Bitvec object and on a linear array of bits obtained from malloc.379** Opcode 5 works on the linear array only, not on the Bitvec.380** Opcode 5 is used to deliberately induce a fault in order to381** confirm that error detection works. Opcodes 6 and greater are382** state output opcodes. Opcodes 6 and greater are no-ops unless383** SQLite has been compiled with SQLITE_DEBUG.384**385** At the conclusion of the test the linear array is compared386** against the Bitvec object. If there are any differences,387** an error is returned. If they are the same, zero is returned.388**389** If a memory allocation error occurs, return -1.390**391** sz is the size of the Bitvec. Or if sz is negative, make the size392** 2*(unsigned)(-sz) and disabled the linear vector check.393*/394int sqlite3BitvecBuiltinTest(int sz, int *aOp){395 Bitvec *pBitvec = 0;396 unsigned char *pV = 0;397 int rc = -1;398 int i, nx, pc, op;399 void *pTmpSpace;400 401 /* Allocate the Bitvec to be tested and a linear array of402 ** bits to act as the reference */403 if( sz<=0 ){404 pBitvec = sqlite3BitvecCreate( 2*(unsigned)(-sz) );405 pV = 0;406 }else{407 pBitvec = sqlite3BitvecCreate( sz );408 pV = sqlite3MallocZero( (7+(i64)sz)/8 + 1 );409 }410 pTmpSpace = sqlite3_malloc64(BITVEC_SZ);411 if( pBitvec==0 || pTmpSpace==0 || (pV==0 && sz>0) ) goto bitvec_end;412 413 /* NULL pBitvec tests */414 sqlite3BitvecSet(0, 1);415 sqlite3BitvecClear(0, 1, pTmpSpace);416 417 /* Run the program */418 pc = i = 0;419 while( (op = aOp[pc])!=0 ){420 if( op>=6 ){421#ifdef SQLITE_DEBUG422 if( op==6 ){423 sqlite3ShowBitvec(pBitvec);424 }else if( op==7 ){425 printf("BITVEC_SZ = %d (%d by sizeof)\n",426 BITVEC_SZ, (int)sizeof(Bitvec));427 printf("BITVEC_USIZE = %d\n", (int)BITVEC_USIZE);428 printf("BITVEC_NELEM = %d\n", (int)BITVEC_NELEM);429 printf("BITVEC_NBIT = %d\n", (int)BITVEC_NBIT);430 printf("BITVEC_NINT = %d\n", (int)BITVEC_NINT);431 printf("BITVEC_MXHASH = %d\n", (int)BITVEC_MXHASH);432 printf("BITVEC_NPTR = %d\n", (int)BITVEC_NPTR);433 }434#endif435 pc++;436 continue;437 }438 switch( op ){439 case 1:440 case 2:441 case 5: {442 nx = 4;443 i = aOp[pc+2] - 1;444 aOp[pc+2] += aOp[pc+3];445 break;446 }447 case 3:448 case 4:449 default: {450 nx = 2;451 sqlite3_randomness(sizeof(i), &i);452 break;453 }454 }455 if( (--aOp[pc+1]) > 0 ) nx = 0;456 pc += nx;457 i = (i & 0x7fffffff)%sz;458 if( (op & 1)!=0 ){459 if( pV ) SETBIT(pV, (i+1));460 if( op!=5 ){461 if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end;462 }463 }else{464 if( pV ) CLEARBIT(pV, (i+1));465 sqlite3BitvecClear(pBitvec, i+1, pTmpSpace);466 }467 }468 469 /* Test to make sure the linear array exactly matches the470 ** Bitvec object. Start with the assumption that they do471 ** match (rc==0). Change rc to non-zero if a discrepancy472 ** is found.473 */474 if( pV ){475 rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1)476 + sqlite3BitvecTest(pBitvec, 0)477 + (sqlite3BitvecSize(pBitvec) - sz);478 for(i=1; i<=sz; i++){479 if( (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){480 rc = i;481 break;482 }483 }484 }else{485 rc = 0;486 }487 488 /* Free allocated structure */489bitvec_end:490 sqlite3_free(pTmpSpace);491 sqlite3_free(pV);492 sqlite3BitvecDestroy(pBitvec);493 return rc;494}495#endif /* SQLITE_UNTESTABLE */496