| OLD | NEW |
|---|
| (Empty) |
| 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 which pages of a database file have been | |
| 16 ** 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) most | |
| 20 ** or all of the pages in a database can get journalled. In those cases, | |
| 21 ** the bitmap becomes dense with high cardinality. The algorithm needs | |
| 22 ** 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 bits | |
| 27 ** 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 between | |
| 31 ** 5 and 500 set operations per Bitvec object, though the number of sets can | |
| 32 ** sometimes grow into tens of thousands or larger. The size of the | |
| 33 ** Bitvec object is the number of pages in the database file at the | |
| 34 ** 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 ** @(#) $Id: bitvec.c,v 1.17 2009/07/25 17:33:26 drh Exp $ | |
| 38 */ | |
| 39 #include "sqliteInt.h" | |
| 40 | |
| 41 /* Size of the Bitvec structure in bytes. */ | |
| 42 #define BITVEC_SZ (sizeof(void*)*128) /* 512 on 32bit. 1024 on 64bit */ | |
| 43 | |
| 44 /* Round the union size down to the nearest pointer boundary, since that's how | |
| 45 ** it will be aligned within the Bitvec struct. */ | |
| 46 #define BITVEC_USIZE (((BITVEC_SZ-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(B
itvec*)) | |
| 47 | |
| 48 /* Type of the array "element" for the bitmap representation. | |
| 49 ** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE. | |
| 50 ** Setting this to the "natural word" size of your CPU may improve | |
| 51 ** performance. */ | |
| 52 #define BITVEC_TELEM u8 | |
| 53 /* Size, in bits, of the bitmap element. */ | |
| 54 #define BITVEC_SZELEM 8 | |
| 55 /* Number of elements in a bitmap array. */ | |
| 56 #define BITVEC_NELEM (BITVEC_USIZE/sizeof(BITVEC_TELEM)) | |
| 57 /* Number of bits in the bitmap array. */ | |
| 58 #define BITVEC_NBIT (BITVEC_NELEM*BITVEC_SZELEM) | |
| 59 | |
| 60 /* Number of u32 values in hash table. */ | |
| 61 #define BITVEC_NINT (BITVEC_USIZE/sizeof(u32)) | |
| 62 /* Maximum number of entries in hash table before | |
| 63 ** sub-dividing and re-hashing. */ | |
| 64 #define BITVEC_MXHASH (BITVEC_NINT/2) | |
| 65 /* Hashing function for the aHash representation. | |
| 66 ** Empirical testing showed that the *37 multiplier | |
| 67 ** (an arbitrary prime)in the hash function provided | |
| 68 ** no fewer collisions than the no-op *1. */ | |
| 69 #define BITVEC_HASH(X) (((X)*1)%BITVEC_NINT) | |
| 70 | |
| 71 #define BITVEC_NPTR (BITVEC_USIZE/sizeof(Bitvec *)) | |
| 72 | |
| 73 | |
| 74 /* | |
| 75 ** A bitmap is an instance of the following structure. | |
| 76 ** | |
| 77 ** This bitmap records the existance of zero or more bits | |
| 78 ** with values between 1 and iSize, inclusive. | |
| 79 ** | |
| 80 ** There are three possible representations of the bitmap. | |
| 81 ** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight | |
| 82 ** bitmap. The least significant bit is bit 1. | |
| 83 ** | |
| 84 ** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is | |
| 85 ** a hash table that will hold up to BITVEC_MXHASH distinct values. | |
| 86 ** | |
| 87 ** Otherwise, the value i is redirected into one of BITVEC_NPTR | |
| 88 ** sub-bitmaps pointed to by Bitvec.u.apSub[]. Each subbitmap | |
| 89 ** handles up to iDivisor separate values of i. apSub[0] holds | |
| 90 ** values between 1 and iDivisor. apSub[1] holds values between | |
| 91 ** iDivisor+1 and 2*iDivisor. apSub[N] holds values between | |
| 92 ** N*iDivisor+1 and (N+1)*iDivisor. Each subbitmap is normalized | |
| 93 ** to hold deal with values between 1 and iDivisor. | |
| 94 */ | |
| 95 struct Bitvec { | |
| 96 u32 iSize; /* Maximum bit index. Max iSize is 4,294,967,296. */ | |
| 97 u32 nSet; /* Number of bits that are set - only valid for aHash | |
| 98 ** element. Max is BITVEC_NINT. For BITVEC_SZ of 512, | |
| 99 ** this would be 125. */ | |
| 100 u32 iDivisor; /* Number of bits handled by each apSub[] entry. */ | |
| 101 /* Should >=0 for apSub element. */ | |
| 102 /* Max iDivisor is max(u32) / BITVEC_NPTR + 1. */ | |
| 103 /* For a BITVEC_SZ of 512, this would be 34,359,739. */ | |
| 104 union { | |
| 105 BITVEC_TELEM aBitmap[BITVEC_NELEM]; /* Bitmap representation */ | |
| 106 u32 aHash[BITVEC_NINT]; /* Hash table representation */ | |
| 107 Bitvec *apSub[BITVEC_NPTR]; /* Recursive representation */ | |
| 108 } u; | |
| 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 if | |
| 114 ** malloc fails. | |
| 115 */ | |
| 116 Bitvec *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 if | |
| 129 ** i is out of range, then return false. | |
| 130 */ | |
| 131 int sqlite3BitvecTest(Bitvec *p, u32 i){ | |
| 132 if( p==0 ) return 0; | |
| 133 if( i>p->iSize || i==0 ) return 0; | |
| 134 i--; | |
| 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 } | |
| 154 | |
| 155 /* | |
| 156 ** Set the i-th bit. Return 0 on success and an error code if | |
| 157 ** anything goes wrong. | |
| 158 ** | |
| 159 ** This routine might cause sub-bitmaps to be allocated. Failing | |
| 160 ** to get the memory needed to hold the sub-bitmap is the only | |
| 161 ** that can go wrong with an insert, assuming p and i are valid. | |
| 162 ** | |
| 163 ** The calling function must ensure that p is a valid Bitvec object | |
| 164 ** and that the value for "i" is within range of the Bitvec object. | |
| 165 ** Otherwise the behavior is undefined. | |
| 166 */ | |
| 167 int sqlite3BitvecSet(Bitvec *p, u32 i){ | |
| 168 u32 h; | |
| 169 if( p==0 ) return SQLITE_OK; | |
| 170 assert( i>0 ); | |
| 171 assert( i<=p->iSize ); | |
| 172 i--; | |
| 173 while((p->iSize > BITVEC_NBIT) && p->iDivisor) { | |
| 174 u32 bin = i/p->iDivisor; | |
| 175 i = i%p->iDivisor; | |
| 176 if( p->u.apSub[bin]==0 ){ | |
| 177 p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor ); | |
| 178 if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM; | |
| 179 } | |
| 180 p = p->u.apSub[bin]; | |
| 181 } | |
| 182 if( p->iSize<=BITVEC_NBIT ){ | |
| 183 p->u.aBitmap[i/BITVEC_SZELEM] |= 1 << (i&(BITVEC_SZELEM-1)); | |
| 184 return SQLITE_OK; | |
| 185 } | |
| 186 h = BITVEC_HASH(i++); | |
| 187 /* if there wasn't a hash collision, and this doesn't */ | |
| 188 /* completely fill the hash, then just add it without */ | |
| 189 /* worring about sub-dividing and re-hashing. */ | |
| 190 if( !p->u.aHash[h] ){ | |
| 191 if (p->nSet<(BITVEC_NINT-1)) { | |
| 192 goto bitvec_set_end; | |
| 193 } else { | |
| 194 goto bitvec_set_rehash; | |
| 195 } | |
| 196 } | |
| 197 /* there was a collision, check to see if it's already */ | |
| 198 /* in hash, if not, try to find a spot for it */ | |
| 199 do { | |
| 200 if( p->u.aHash[h]==i ) return SQLITE_OK; | |
| 201 h++; | |
| 202 if( h>=BITVEC_NINT ) h = 0; | |
| 203 } while( p->u.aHash[h] ); | |
| 204 /* we didn't find it in the hash. h points to the first */ | |
| 205 /* available free spot. check to see if this is going to */ | |
| 206 /* make our hash too "full". */ | |
| 207 bitvec_set_rehash: | |
| 208 if( p->nSet>=BITVEC_MXHASH ){ | |
| 209 unsigned int j; | |
| 210 int rc; | |
| 211 u32 *aiValues = sqlite3StackAllocRaw(0, sizeof(p->u.aHash)); | |
| 212 if( aiValues==0 ){ | |
| 213 return SQLITE_NOMEM; | |
| 214 }else{ | |
| 215 memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash)); | |
| 216 memset(p->u.apSub, 0, sizeof(p->u.apSub)); | |
| 217 p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR; | |
| 218 rc = sqlite3BitvecSet(p, i); | |
| 219 for(j=0; j<BITVEC_NINT; j++){ | |
| 220 if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]); | |
| 221 } | |
| 222 sqlite3StackFree(0, aiValues); | |
| 223 return rc; | |
| 224 } | |
| 225 } | |
| 226 bitvec_set_end: | |
| 227 p->nSet++; | |
| 228 p->u.aHash[h] = i; | |
| 229 return SQLITE_OK; | |
| 230 } | |
| 231 | |
| 232 /* | |
| 233 ** Clear the i-th bit. | |
| 234 ** | |
| 235 ** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage | |
| 236 ** that BitvecClear can use to rebuilt its hash table. | |
| 237 */ | |
| 238 void sqlite3BitvecClear(Bitvec *p, u32 i, void *pBuf){ | |
| 239 if( p==0 ) return; | |
| 240 assert( i>0 ); | |
| 241 i--; | |
| 242 while( p->iDivisor ){ | |
| 243 u32 bin = i/p->iDivisor; | |
| 244 i = i%p->iDivisor; | |
| 245 p = p->u.apSub[bin]; | |
| 246 if (!p) { | |
| 247 return; | |
| 248 } | |
| 249 } | |
| 250 if( p->iSize<=BITVEC_NBIT ){ | |
| 251 p->u.aBitmap[i/BITVEC_SZELEM] &= ~(1 << (i&(BITVEC_SZELEM-1))); | |
| 252 }else{ | |
| 253 unsigned int j; | |
| 254 u32 *aiValues = pBuf; | |
| 255 memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash)); | |
| 256 memset(p->u.aHash, 0, sizeof(p->u.aHash)); | |
| 257 p->nSet = 0; | |
| 258 for(j=0; j<BITVEC_NINT; j++){ | |
| 259 if( aiValues[j] && aiValues[j]!=(i+1) ){ | |
| 260 u32 h = BITVEC_HASH(aiValues[j]-1); | |
| 261 p->nSet++; | |
| 262 while( p->u.aHash[h] ){ | |
| 263 h++; | |
| 264 if( h>=BITVEC_NINT ) h = 0; | |
| 265 } | |
| 266 p->u.aHash[h] = aiValues[j]; | |
| 267 } | |
| 268 } | |
| 269 } | |
| 270 } | |
| 271 | |
| 272 /* | |
| 273 ** Destroy a bitmap object. Reclaim all memory used. | |
| 274 */ | |
| 275 void sqlite3BitvecDestroy(Bitvec *p){ | |
| 276 if( p==0 ) return; | |
| 277 if( p->iDivisor ){ | |
| 278 unsigned int i; | |
| 279 for(i=0; i<BITVEC_NPTR; i++){ | |
| 280 sqlite3BitvecDestroy(p->u.apSub[i]); | |
| 281 } | |
| 282 } | |
| 283 sqlite3_free(p); | |
| 284 } | |
| 285 | |
| 286 /* | |
| 287 ** Return the value of the iSize parameter specified when Bitvec *p | |
| 288 ** was created. | |
| 289 */ | |
| 290 u32 sqlite3BitvecSize(Bitvec *p){ | |
| 291 return p->iSize; | |
| 292 } | |
| 293 | |
| 294 #ifndef SQLITE_OMIT_BUILTIN_TEST | |
| 295 /* | |
| 296 ** Let V[] be an array of unsigned characters sufficient to hold | |
| 297 ** up to N bits. Let I be an integer between 0 and N. 0<=I<N. | |
| 298 ** Then the following macros can be used to set, clear, or test | |
| 299 ** individual bits within V. | |
| 300 */ | |
| 301 #define SETBIT(V,I) V[I>>3] |= (1<<(I&7)) | |
| 302 #define CLEARBIT(V,I) V[I>>3] &= ~(1<<(I&7)) | |
| 303 #define TESTBIT(V,I) (V[I>>3]&(1<<(I&7)))!=0 | |
| 304 | |
| 305 /* | |
| 306 ** This routine runs an extensive test of the Bitvec code. | |
| 307 ** | |
| 308 ** The input is an array of integers that acts as a program | |
| 309 ** to test the Bitvec. The integers are opcodes followed | |
| 310 ** by 0, 1, or 3 operands, depending on the opcode. Another | |
| 311 ** opcode follows immediately after the last operand. | |
| 312 ** | |
| 313 ** There are 6 opcodes numbered from 0 through 5. 0 is the | |
| 314 ** "halt" opcode and causes the test to end. | |
| 315 ** | |
| 316 ** 0 Halt and return the number of errors | |
| 317 ** 1 N S X Set N bits beginning with S and incrementing by X | |
| 318 ** 2 N S X Clear N bits beginning with S and incrementing by X | |
| 319 ** 3 N Set N randomly chosen bits | |
| 320 ** 4 N Clear N randomly chosen bits | |
| 321 ** 5 N S X Set N bits from S increment X in array only, not in bitvec | |
| 322 ** | |
| 323 ** The opcodes 1 through 4 perform set and clear operations are performed | |
| 324 ** on both a Bitvec object and on a linear array of bits obtained from malloc. | |
| 325 ** Opcode 5 works on the linear array only, not on the Bitvec. | |
| 326 ** Opcode 5 is used to deliberately induce a fault in order to | |
| 327 ** confirm that error detection works. | |
| 328 ** | |
| 329 ** At the conclusion of the test the linear array is compared | |
| 330 ** against the Bitvec object. If there are any differences, | |
| 331 ** an error is returned. If they are the same, zero is returned. | |
| 332 ** | |
| 333 ** If a memory allocation error occurs, return -1. | |
| 334 */ | |
| 335 int sqlite3BitvecBuiltinTest(int sz, int *aOp){ | |
| 336 Bitvec *pBitvec = 0; | |
| 337 unsigned char *pV = 0; | |
| 338 int rc = -1; | |
| 339 int i, nx, pc, op; | |
| 340 void *pTmpSpace; | |
| 341 | |
| 342 /* Allocate the Bitvec to be tested and a linear array of | |
| 343 ** bits to act as the reference */ | |
| 344 pBitvec = sqlite3BitvecCreate( sz ); | |
| 345 pV = sqlite3_malloc( (sz+7)/8 + 1 ); | |
| 346 pTmpSpace = sqlite3_malloc(BITVEC_SZ); | |
| 347 if( pBitvec==0 || pV==0 || pTmpSpace==0 ) goto bitvec_end; | |
| 348 memset(pV, 0, (sz+7)/8 + 1); | |
| 349 | |
| 350 /* NULL pBitvec tests */ | |
| 351 sqlite3BitvecSet(0, 1); | |
| 352 sqlite3BitvecClear(0, 1, pTmpSpace); | |
| 353 | |
| 354 /* Run the program */ | |
| 355 pc = 0; | |
| 356 while( (op = aOp[pc])!=0 ){ | |
| 357 switch( op ){ | |
| 358 case 1: | |
| 359 case 2: | |
| 360 case 5: { | |
| 361 nx = 4; | |
| 362 i = aOp[pc+2] - 1; | |
| 363 aOp[pc+2] += aOp[pc+3]; | |
| 364 break; | |
| 365 } | |
| 366 case 3: | |
| 367 case 4: | |
| 368 default: { | |
| 369 nx = 2; | |
| 370 sqlite3_randomness(sizeof(i), &i); | |
| 371 break; | |
| 372 } | |
| 373 } | |
| 374 if( (--aOp[pc+1]) > 0 ) nx = 0; | |
| 375 pc += nx; | |
| 376 i = (i & 0x7fffffff)%sz; | |
| 377 if( (op & 1)!=0 ){ | |
| 378 SETBIT(pV, (i+1)); | |
| 379 if( op!=5 ){ | |
| 380 if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end; | |
| 381 } | |
| 382 }else{ | |
| 383 CLEARBIT(pV, (i+1)); | |
| 384 sqlite3BitvecClear(pBitvec, i+1, pTmpSpace); | |
| 385 } | |
| 386 } | |
| 387 | |
| 388 /* Test to make sure the linear array exactly matches the | |
| 389 ** Bitvec object. Start with the assumption that they do | |
| 390 ** match (rc==0). Change rc to non-zero if a discrepancy | |
| 391 ** is found. | |
| 392 */ | |
| 393 rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1) | |
| 394 + sqlite3BitvecTest(pBitvec, 0) | |
| 395 + (sqlite3BitvecSize(pBitvec) - sz); | |
| 396 for(i=1; i<=sz; i++){ | |
| 397 if( (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){ | |
| 398 rc = i; | |
| 399 break; | |
| 400 } | |
| 401 } | |
| 402 | |
| 403 /* Free allocated structure */ | |
| 404 bitvec_end: | |
| 405 sqlite3_free(pTmpSpace); | |
| 406 sqlite3_free(pV); | |
| 407 sqlite3BitvecDestroy(pBitvec); | |
| 408 return rc; | |
| 409 } | |
| 410 #endif /* SQLITE_OMIT_BUILTIN_TEST */ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 3108030:
Move bundled copy of sqlite one level deeper to better separate it... (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/src/