Index: third_party/sqlite/sqlite-src-3080704/src/bitvec.c |
diff --git a/third_party/sqlite/sqlite-src-3080704/src/bitvec.c b/third_party/sqlite/sqlite-src-3080704/src/bitvec.c |
deleted file mode 100644 |
index 52184aa964ce1898f35d1b3d87871c2d0ef4c53d..0000000000000000000000000000000000000000 |
--- a/third_party/sqlite/sqlite-src-3080704/src/bitvec.c |
+++ /dev/null |
@@ -1,407 +0,0 @@ |
-/* |
-** 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 which pages of a database file have been |
-** journalled during a transaction, or which pages have the "dont-write" |
-** property. Usually only a few pages are meet either condition. |
-** 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 in a database can get journalled. In those cases, |
-** the bitmap becomes dense with high cardinality. 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. |
-*/ |
-#include "sqliteInt.h" |
- |
-/* Size of the Bitvec structure in bytes. */ |
-#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-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(Bitvec*)) |
- |
-/* Type of the array "element" for the bitmap representation. |
-** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE. |
-** Setting this to the "natural word" size of your CPU may improve |
-** performance. */ |
-#define BITVEC_TELEM u8 |
-/* Size, in bits, of the bitmap element. */ |
-#define BITVEC_SZELEM 8 |
-/* Number of elements in a bitmap array. */ |
-#define BITVEC_NELEM (BITVEC_USIZE/sizeof(BITVEC_TELEM)) |
-/* Number of bits in the bitmap array. */ |
-#define BITVEC_NBIT (BITVEC_NELEM*BITVEC_SZELEM) |
- |
-/* Number of u32 values in hash table. */ |
-#define BITVEC_NINT (BITVEC_USIZE/sizeof(u32)) |
-/* Maximum number of entries in hash table before |
-** sub-dividing and re-hashing. */ |
-#define BITVEC_MXHASH (BITVEC_NINT/2) |
-/* Hashing function for the aHash representation. |
-** Empirical testing showed that the *37 multiplier |
-** (an arbitrary prime)in the hash function provided |
-** no fewer collisions than the no-op *1. */ |
-#define BITVEC_HASH(X) (((X)*1)%BITVEC_NINT) |
- |
-#define BITVEC_NPTR (BITVEC_USIZE/sizeof(Bitvec *)) |
- |
- |
-/* |
-** A bitmap is an instance of the following structure. |
-** |
-** This bitmap records the existence 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. Max iSize is 4,294,967,296. */ |
- u32 nSet; /* Number of bits that are set - only valid for aHash |
- ** element. Max is BITVEC_NINT. For BITVEC_SZ of 512, |
- ** this would be 125. */ |
- u32 iDivisor; /* Number of bits handled by each apSub[] entry. */ |
- /* Should >=0 for apSub element. */ |
- /* Max iDivisor is max(u32) / BITVEC_NPTR + 1. */ |
- /* For a BITVEC_SZ of 512, this would be 34,359,739. */ |
- union { |
- BITVEC_TELEM aBitmap[BITVEC_NELEM]; /* 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; |
- i--; |
- while( p->iDivisor ){ |
- u32 bin = i/p->iDivisor; |
- i = i%p->iDivisor; |
- p = p->u.apSub[bin]; |
- if (!p) { |
- return 0; |
- } |
- } |
- if( p->iSize<=BITVEC_NBIT ){ |
- return (p->u.aBitmap[i/BITVEC_SZELEM] & (1<<(i&(BITVEC_SZELEM-1))))!=0; |
- } else{ |
- u32 h = BITVEC_HASH(i++); |
- while( p->u.aHash[h] ){ |
- if( p->u.aHash[h]==i ) return 1; |
- h = (h+1) % BITVEC_NINT; |
- } |
- return 0; |
- } |
-} |
- |
-/* |
-** Set the i-th bit. Return 0 on success and an error code if |
-** anything goes wrong. |
-** |
-** This routine might cause sub-bitmaps to be allocated. Failing |
-** to get the memory needed to hold the sub-bitmap is the only |
-** that can go wrong with an insert, assuming p and i are valid. |
-** |
-** The calling function must ensure that p is a valid Bitvec object |
-** and that the value for "i" is within range of the Bitvec object. |
-** Otherwise the behavior is undefined. |
-*/ |
-int sqlite3BitvecSet(Bitvec *p, u32 i){ |
- u32 h; |
- if( p==0 ) return SQLITE_OK; |
- assert( i>0 ); |
- assert( i<=p->iSize ); |
- i--; |
- while((p->iSize > BITVEC_NBIT) && p->iDivisor) { |
- u32 bin = i/p->iDivisor; |
- i = i%p->iDivisor; |
- if( p->u.apSub[bin]==0 ){ |
- p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor ); |
- if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM; |
- } |
- p = p->u.apSub[bin]; |
- } |
- if( p->iSize<=BITVEC_NBIT ){ |
- p->u.aBitmap[i/BITVEC_SZELEM] |= 1 << (i&(BITVEC_SZELEM-1)); |
- return SQLITE_OK; |
- } |
- h = BITVEC_HASH(i++); |
- /* if there wasn't a hash collision, and this doesn't */ |
- /* completely fill the hash, then just add it without */ |
- /* worring about sub-dividing and re-hashing. */ |
- if( !p->u.aHash[h] ){ |
- if (p->nSet<(BITVEC_NINT-1)) { |
- goto bitvec_set_end; |
- } else { |
- goto bitvec_set_rehash; |
- } |
- } |
- /* there was a collision, check to see if it's already */ |
- /* in hash, if not, try to find a spot for it */ |
- do { |
- if( p->u.aHash[h]==i ) return SQLITE_OK; |
- h++; |
- if( h>=BITVEC_NINT ) h = 0; |
- } while( p->u.aHash[h] ); |
- /* we didn't find it in the hash. h points to the first */ |
- /* available free spot. check to see if this is going to */ |
- /* make our hash too "full". */ |
-bitvec_set_rehash: |
- if( p->nSet>=BITVEC_MXHASH ){ |
- unsigned int j; |
- int rc; |
- u32 *aiValues = sqlite3StackAllocRaw(0, sizeof(p->u.aHash)); |
- if( aiValues==0 ){ |
- return SQLITE_NOMEM; |
- }else{ |
- memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash)); |
- memset(p->u.apSub, 0, sizeof(p->u.apSub)); |
- 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]); |
- } |
- sqlite3StackFree(0, aiValues); |
- return rc; |
- } |
- } |
-bitvec_set_end: |
- p->nSet++; |
- p->u.aHash[h] = i; |
- return SQLITE_OK; |
-} |
- |
-/* |
-** Clear the i-th bit. |
-** |
-** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage |
-** that BitvecClear can use to rebuilt its hash table. |
-*/ |
-void sqlite3BitvecClear(Bitvec *p, u32 i, void *pBuf){ |
- if( p==0 ) return; |
- assert( i>0 ); |
- i--; |
- while( p->iDivisor ){ |
- u32 bin = i/p->iDivisor; |
- i = i%p->iDivisor; |
- p = p->u.apSub[bin]; |
- if (!p) { |
- return; |
- } |
- } |
- if( p->iSize<=BITVEC_NBIT ){ |
- p->u.aBitmap[i/BITVEC_SZELEM] &= ~(1 << (i&(BITVEC_SZELEM-1))); |
- }else{ |
- unsigned int j; |
- u32 *aiValues = pBuf; |
- memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash)); |
- memset(p->u.aHash, 0, sizeof(p->u.aHash)); |
- p->nSet = 0; |
- for(j=0; j<BITVEC_NINT; j++){ |
- if( aiValues[j] && aiValues[j]!=(i+1) ){ |
- u32 h = BITVEC_HASH(aiValues[j]-1); |
- p->nSet++; |
- while( p->u.aHash[h] ){ |
- h++; |
- if( h>=BITVEC_NINT ) h = 0; |
- } |
- p->u.aHash[h] = aiValues[j]; |
- } |
- } |
- } |
-} |
- |
-/* |
-** Destroy a bitmap object. Reclaim all memory used. |
-*/ |
-void sqlite3BitvecDestroy(Bitvec *p){ |
- if( p==0 ) return; |
- if( p->iDivisor ){ |
- unsigned int i; |
- for(i=0; i<BITVEC_NPTR; i++){ |
- sqlite3BitvecDestroy(p->u.apSub[i]); |
- } |
- } |
- sqlite3_free(p); |
-} |
- |
-/* |
-** Return the value of the iSize parameter specified when Bitvec *p |
-** was created. |
-*/ |
-u32 sqlite3BitvecSize(Bitvec *p){ |
- return p->iSize; |
-} |
- |
-#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; |
- void *pTmpSpace; |
- |
- /* Allocate the Bitvec to be tested and a linear array of |
- ** bits to act as the reference */ |
- pBitvec = sqlite3BitvecCreate( sz ); |
- pV = sqlite3MallocZero( (sz+7)/8 + 1 ); |
- pTmpSpace = sqlite3_malloc(BITVEC_SZ); |
- if( pBitvec==0 || pV==0 || pTmpSpace==0 ) goto bitvec_end; |
- |
- /* NULL pBitvec tests */ |
- sqlite3BitvecSet(0, 1); |
- sqlite3BitvecClear(0, 1, pTmpSpace); |
- |
- /* 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, pTmpSpace); |
- } |
- } |
- |
- /* 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) |
- + (sqlite3BitvecSize(pBitvec) - sz); |
- for(i=1; i<=sz; i++){ |
- if( (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){ |
- rc = i; |
- break; |
- } |
- } |
- |
- /* Free allocated structure */ |
-bitvec_end: |
- sqlite3_free(pTmpSpace); |
- sqlite3_free(pV); |
- sqlite3BitvecDestroy(pBitvec); |
- return rc; |
-} |
-#endif /* SQLITE_OMIT_BUILTIN_TEST */ |