15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2008 February 16 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The author disclaims copyright to this source code. In place of 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** a legal notice, here is a blessing: 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you do good and not evil. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you find forgiveness for yourself and forgive others. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you share freely, never taking more than you give. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)************************************************************************* 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This file implements an object that represents a fixed-length 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** bitmap. Bits are numbered starting with 1. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** A bitmap is used to record which pages of a database file have been 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** journalled during a transaction, or which pages have the "dont-write" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** property. Usually only a few pages are meet either condition. 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** So the bitmap is usually sparse and has low cardinality. 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** But sometimes (for example when during a DROP of a large table) most 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** or all of the pages in a database can get journalled. In those cases, 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** the bitmap becomes dense with high cardinality. The algorithm needs 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** to handle both cases well. 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The size of the bitmap is fixed when the object is created. 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** All bits are clear when the bitmap is created. Individual bits 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** may be set or cleared one at a time. 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Test operations are about 100 times more common that set operations. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Clear operations are exceedingly rare. There are usually between 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 5 and 500 set operations per Bitvec object, though the number of sets can 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** sometimes grow into tens of thousands or larger. The size of the 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Bitvec object is the number of pages in the database file at the 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** start of a transaction, and is thus usually less than a few thousand, 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** but can be as large as 2 billion for a really big database. 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sqliteInt.h" 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Size of the Bitvec structure in bytes. */ 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_SZ 512 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Round the union size down to the nearest pointer boundary, since that's how 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** it will be aligned within the Bitvec struct. */ 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_USIZE (((BITVEC_SZ-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(Bitvec*)) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Type of the array "element" for the bitmap representation. 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE. 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Setting this to the "natural word" size of your CPU may improve 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** performance. */ 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_TELEM u8 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Size, in bits, of the bitmap element. */ 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_SZELEM 8 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Number of elements in a bitmap array. */ 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_NELEM (BITVEC_USIZE/sizeof(BITVEC_TELEM)) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Number of bits in the bitmap array. */ 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_NBIT (BITVEC_NELEM*BITVEC_SZELEM) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Number of u32 values in hash table. */ 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_NINT (BITVEC_USIZE/sizeof(u32)) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Maximum number of entries in hash table before 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** sub-dividing and re-hashing. */ 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_MXHASH (BITVEC_NINT/2) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Hashing function for the aHash representation. 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Empirical testing showed that the *37 multiplier 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** (an arbitrary prime)in the hash function provided 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** no fewer collisions than the no-op *1. */ 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_HASH(X) (((X)*1)%BITVEC_NINT) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BITVEC_NPTR (BITVEC_USIZE/sizeof(Bitvec *)) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** A bitmap is an instance of the following structure. 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This bitmap records the existance of zero or more bits 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** with values between 1 and iSize, inclusive. 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** There are three possible representations of the bitmap. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** bitmap. The least significant bit is bit 1. 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** a hash table that will hold up to BITVEC_MXHASH distinct values. 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Otherwise, the value i is redirected into one of BITVEC_NPTR 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** sub-bitmaps pointed to by Bitvec.u.apSub[]. Each subbitmap 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** handles up to iDivisor separate values of i. apSub[0] holds 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** values between 1 and iDivisor. apSub[1] holds values between 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** iDivisor+1 and 2*iDivisor. apSub[N] holds values between 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** N*iDivisor+1 and (N+1)*iDivisor. Each subbitmap is normalized 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** to hold deal with values between 1 and iDivisor. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct Bitvec { 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 iSize; /* Maximum bit index. Max iSize is 4,294,967,296. */ 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 nSet; /* Number of bits that are set - only valid for aHash 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** element. Max is BITVEC_NINT. For BITVEC_SZ of 512, 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** this would be 125. */ 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 iDivisor; /* Number of bits handled by each apSub[] entry. */ 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Should >=0 for apSub element. */ 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Max iDivisor is max(u32) / BITVEC_NPTR + 1. */ 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* For a BITVEC_SZ of 512, this would be 34,359,739. */ 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) union { 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BITVEC_TELEM aBitmap[BITVEC_NELEM]; /* Bitmap representation */ 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 aHash[BITVEC_NINT]; /* Hash table representation */ 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bitvec *apSub[BITVEC_NPTR]; /* Recursive representation */ 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } u; 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Create a new bitmap object able to handle bits between 0 and iSize, 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** inclusive. Return a pointer to the new object. Return NULL if 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** malloc fails. 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Bitvec *sqlite3BitvecCreate(u32 iSize){ 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bitvec *p; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( sizeof(*p)==BITVEC_SZ ); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = sqlite3MallocZero( sizeof(*p) ); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p ){ 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->iSize = iSize; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Check to see if the i-th bit is set. Return true or false. 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If p is NULL (if the bitmap has not been created) or if 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** i is out of range, then return false. 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int sqlite3BitvecTest(Bitvec *p, u32 i){ 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p==0 ) return 0; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( i>p->iSize || i==0 ) return 0; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i--; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( p->iDivisor ){ 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 bin = i/p->iDivisor; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = i%p->iDivisor; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = p->u.apSub[bin]; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!p) { 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->iSize<=BITVEC_NBIT ){ 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (p->u.aBitmap[i/BITVEC_SZELEM] & (1<<(i&(BITVEC_SZELEM-1))))!=0; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else{ 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 h = BITVEC_HASH(i++); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( p->u.aHash[h] ){ 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->u.aHash[h]==i ) return 1; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h = (h+1) % BITVEC_NINT; 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Set the i-th bit. Return 0 on success and an error code if 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** anything goes wrong. 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This routine might cause sub-bitmaps to be allocated. Failing 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** to get the memory needed to hold the sub-bitmap is the only 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** that can go wrong with an insert, assuming p and i are valid. 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The calling function must ensure that p is a valid Bitvec object 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** and that the value for "i" is within range of the Bitvec object. 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Otherwise the behavior is undefined. 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int sqlite3BitvecSet(Bitvec *p, u32 i){ 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 h; 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p==0 ) return SQLITE_OK; 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( i>0 ); 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( i<=p->iSize ); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i--; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while((p->iSize > BITVEC_NBIT) && p->iDivisor) { 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 bin = i/p->iDivisor; 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = i%p->iDivisor; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->u.apSub[bin]==0 ){ 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor ); 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = p->u.apSub[bin]; 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->iSize<=BITVEC_NBIT ){ 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->u.aBitmap[i/BITVEC_SZELEM] |= 1 << (i&(BITVEC_SZELEM-1)); 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SQLITE_OK; 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h = BITVEC_HASH(i++); 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* if there wasn't a hash collision, and this doesn't */ 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* completely fill the hash, then just add it without */ 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* worring about sub-dividing and re-hashing. */ 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( !p->u.aHash[h] ){ 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (p->nSet<(BITVEC_NINT-1)) { 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto bitvec_set_end; 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) goto bitvec_set_rehash; 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* there was a collision, check to see if it's already */ 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* in hash, if not, try to find a spot for it */ 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->u.aHash[h]==i ) return SQLITE_OK; 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h++; 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( h>=BITVEC_NINT ) h = 0; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while( p->u.aHash[h] ); 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* we didn't find it in the hash. h points to the first */ 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* available free spot. check to see if this is going to */ 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* make our hash too "full". */ 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bitvec_set_rehash: 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->nSet>=BITVEC_MXHASH ){ 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int j; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int rc; 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 *aiValues = sqlite3StackAllocRaw(0, sizeof(p->u.aHash)); 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( aiValues==0 ){ 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SQLITE_NOMEM; 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash)); 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(p->u.apSub, 0, sizeof(p->u.apSub)); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR; 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rc = sqlite3BitvecSet(p, i); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(j=0; j<BITVEC_NINT; j++){ 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]); 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3StackFree(0, aiValues); 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return rc; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bitvec_set_end: 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->nSet++; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->u.aHash[h] = i; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SQLITE_OK; 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Clear the i-th bit. 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** that BitvecClear can use to rebuilt its hash table. 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void sqlite3BitvecClear(Bitvec *p, u32 i, void *pBuf){ 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p==0 ) return; 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( i>0 ); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i--; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( p->iDivisor ){ 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 bin = i/p->iDivisor; 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = i%p->iDivisor; 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = p->u.apSub[bin]; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!p) { 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->iSize<=BITVEC_NBIT ){ 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->u.aBitmap[i/BITVEC_SZELEM] &= ~(1 << (i&(BITVEC_SZELEM-1))); 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int j; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 *aiValues = pBuf; 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash)); 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(p->u.aHash, 0, sizeof(p->u.aHash)); 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->nSet = 0; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(j=0; j<BITVEC_NINT; j++){ 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( aiValues[j] && aiValues[j]!=(i+1) ){ 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 h = BITVEC_HASH(aiValues[j]-1); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->nSet++; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( p->u.aHash[h] ){ 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h++; 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( h>=BITVEC_NINT ) h = 0; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->u.aHash[h] = aiValues[j]; 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Destroy a bitmap object. Reclaim all memory used. 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void sqlite3BitvecDestroy(Bitvec *p){ 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p==0 ) return; 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->iDivisor ){ 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int i; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0; i<BITVEC_NPTR; i++){ 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3BitvecDestroy(p->u.apSub[i]); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_free(p); 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Return the value of the iSize parameter specified when Bitvec *p 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** was created. 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)u32 sqlite3BitvecSize(Bitvec *p){ 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p->iSize; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef SQLITE_OMIT_BUILTIN_TEST 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Let V[] be an array of unsigned characters sufficient to hold 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** up to N bits. Let I be an integer between 0 and N. 0<=I<N. 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Then the following macros can be used to set, clear, or test 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** individual bits within V. 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define SETBIT(V,I) V[I>>3] |= (1<<(I&7)) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define CLEARBIT(V,I) V[I>>3] &= ~(1<<(I&7)) 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define TESTBIT(V,I) (V[I>>3]&(1<<(I&7)))!=0 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This routine runs an extensive test of the Bitvec code. 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The input is an array of integers that acts as a program 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** to test the Bitvec. The integers are opcodes followed 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** by 0, 1, or 3 operands, depending on the opcode. Another 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** opcode follows immediately after the last operand. 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** There are 6 opcodes numbered from 0 through 5. 0 is the 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** "halt" opcode and causes the test to end. 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 0 Halt and return the number of errors 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 1 N S X Set N bits beginning with S and incrementing by X 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2 N S X Clear N bits beginning with S and incrementing by X 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3 N Set N randomly chosen bits 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 4 N Clear N randomly chosen bits 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 5 N S X Set N bits from S increment X in array only, not in bitvec 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The opcodes 1 through 4 perform set and clear operations are performed 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** on both a Bitvec object and on a linear array of bits obtained from malloc. 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Opcode 5 works on the linear array only, not on the Bitvec. 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Opcode 5 is used to deliberately induce a fault in order to 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** confirm that error detection works. 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** At the conclusion of the test the linear array is compared 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** against the Bitvec object. If there are any differences, 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** an error is returned. If they are the same, zero is returned. 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If a memory allocation error occurs, return -1. 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int sqlite3BitvecBuiltinTest(int sz, int *aOp){ 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Bitvec *pBitvec = 0; 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned char *pV = 0; 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int rc = -1; 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i, nx, pc, op; 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *pTmpSpace; 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Allocate the Bitvec to be tested and a linear array of 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** bits to act as the reference */ 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pBitvec = sqlite3BitvecCreate( sz ); 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pV = sqlite3_malloc( (sz+7)/8 + 1 ); 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pTmpSpace = sqlite3_malloc(BITVEC_SZ); 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pBitvec==0 || pV==0 || pTmpSpace==0 ) goto bitvec_end; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(pV, 0, (sz+7)/8 + 1); 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* NULL pBitvec tests */ 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3BitvecSet(0, 1); 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3BitvecClear(0, 1, pTmpSpace); 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Run the program */ 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pc = 0; 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( (op = aOp[pc])!=0 ){ 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch( op ){ 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case 1: 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case 2: 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case 5: { 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nx = 4; 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = aOp[pc+2] - 1; 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aOp[pc+2] += aOp[pc+3]; 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case 3: 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case 4: 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: { 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nx = 2; 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_randomness(sizeof(i), &i); 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( (--aOp[pc+1]) > 0 ) nx = 0; 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pc += nx; 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = (i & 0x7fffffff)%sz; 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( (op & 1)!=0 ){ 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SETBIT(pV, (i+1)); 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( op!=5 ){ 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end; 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CLEARBIT(pV, (i+1)); 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3BitvecClear(pBitvec, i+1, pTmpSpace); 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Test to make sure the linear array exactly matches the 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** Bitvec object. Start with the assumption that they do 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** match (rc==0). Change rc to non-zero if a discrepancy 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** is found. 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1) 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) + sqlite3BitvecTest(pBitvec, 0) 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) + (sqlite3BitvecSize(pBitvec) - sz); 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=1; i<=sz; i++){ 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){ 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rc = i; 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Free allocated structure */ 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bitvec_end: 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_free(pTmpSpace); 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_free(pV); 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3BitvecDestroy(pBitvec); 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return rc; 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* SQLITE_OMIT_BUILTIN_TEST */ 409