Move bundled copy of sqlite one level deeper to better separate it...

third_party/sqlite/src/bitvec.c

Index: third_party/sqlite/src/bitvec.c
===================================================================
--- third_party/sqlite/src/bitvec.c	(revision 56608)
+++ third_party/sqlite/src/bitvec.c	(working copy)
@@ -1,410 +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.
-**
-** @(#) $Id: bitvec.c,v 1.17 2009/07/25 17:33:26 drh Exp $
-*/
-#include "sqliteInt.h"
-
-/* Size of the Bitvec structure in bytes. */
-#define BITVEC_SZ        (sizeof(void*)*128)  /* 512 on 32bit.  1024 on 64bit */
-
-/* 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 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.  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 = sqlite3_malloc( (sz+7)/8 + 1 );
-  pTmpSpace = sqlite3_malloc(BITVEC_SZ);
-  if( pBitvec==0 || pV==0 || pTmpSpace==0  ) goto bitvec_end;
-  memset(pV, 0, (sz+7)/8 + 1);
-
-  /* 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 */