diff -r 5f8e5adbbed9 -r 29cda98b007e engine/sqlite/src/mem3.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/engine/sqlite/src/mem3.cpp	Thu Feb 25 14:29:19 2010 +0000
@@ -0,0 +1,623 @@
+/*
+** 2007 October 14
+**
+** 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 contains the C functions that implement a memory
+** allocation subsystem for use by SQLite. 
+**
+** This version of the memory allocation subsystem omits all
+** use of malloc().  All dynamically allocatable memory is
+** contained in a static array, mem.aPool[].  The size of this
+** fixed memory pool is SQLITE_MEMORY_SIZE bytes.
+**
+** This version of the memory allocation subsystem is used if
+** and only if SQLITE_MEMORY_SIZE is defined.
+**
+** $Id: mem3.cpp 1282 2008-11-13 09:31:33Z LarsPson $
+*/
+
+/*
+** This version of the memory allocator is used only when 
+** SQLITE_MEMORY_SIZE is defined.
+*/
+#if defined(SQLITE_MEMORY_SIZE)
+#include "sqliteInt.h"
+
+#ifdef SQLITE_MEMDEBUG
+# error  cannot define both SQLITE_MEMDEBUG and SQLITE_MEMORY_SIZE
+#endif
+
+/*
+** Maximum size (in Mem3Blocks) of a "small" chunk.
+*/
+#define MX_SMALL 10
+
+
+/*
+** Number of freelist hash slots
+*/
+#define N_HASH  61
+
+/*
+** A memory allocation (also called a "chunk") consists of two or 
+** more blocks where each block is 8 bytes.  The first 8 bytes are 
+** a header that is not returned to the user.
+**
+** A chunk is two or more blocks that is either checked out or
+** free.  The first block has format u.hdr.  u.hdr.size is the
+** size of the allocation in blocks if the allocation is free.
+** If the allocation is checked out, u.hdr.size is the negative
+** of the size.  Similarly, u.hdr.prevSize is the size of the
+** immediately previous allocation.
+**
+** We often identify a chunk by its index in mem.aPool[].  When
+** this is done, the chunk index refers to the second block of
+** the chunk.  In this way, the first chunk has an index of 1.
+** A chunk index of 0 means "no such chunk" and is the equivalent
+** of a NULL pointer.
+**
+** The second block of free chunks is of the form u.list.  The
+** two fields form a double-linked list of chunks of related sizes.
+** Pointers to the head of the list are stored in mem.aiSmall[] 
+** for smaller chunks and mem.aiHash[] for larger chunks.
+**
+** The second block of a chunk is user data if the chunk is checked 
+** out.
+*/
+typedef struct Mem3Block Mem3Block;
+struct Mem3Block {
+  union {
+    struct {
+      int prevSize;   /* Size of previous chunk in Mem3Block elements */
+      int size;       /* Size of current chunk in Mem3Block elements */
+    } hdr;
+    struct {
+      int next;       /* Index in mem.aPool[] of next free chunk */
+      int prev;       /* Index in mem.aPool[] of previous free chunk */
+    } list;
+  } u;
+};
+
+/*
+** All of the static variables used by this module are collected
+** into a single structure named "mem".  This is to keep the
+** static variables organized and to reduce namespace pollution
+** when this module is combined with other in the amalgamation.
+*/
+static struct {
+  /*
+  ** True if we are evaluating an out-of-memory callback.
+  */
+  int alarmBusy;
+  
+  /*
+  ** Mutex to control access to the memory allocation subsystem.
+  */
+  sqlite3_mutex *mutex;
+  
+  /*
+  ** The minimum amount of free space that we have seen.
+  */
+  int mnMaster;
+
+  /*
+  ** iMaster is the index of the master chunk.  Most new allocations
+  ** occur off of this chunk.  szMaster is the size (in Mem3Blocks)
+  ** of the current master.  iMaster is 0 if there is not master chunk.
+  ** The master chunk is not in either the aiHash[] or aiSmall[].
+  */
+  int iMaster;
+  int szMaster;
+
+  /*
+  ** Array of lists of free blocks according to the block size 
+  ** for smaller chunks, or a hash on the block size for larger
+  ** chunks.
+  */
+  int aiSmall[MX_SMALL-1];   /* For sizes 2 through MX_SMALL, inclusive */
+  int aiHash[N_HASH];        /* For sizes MX_SMALL+1 and larger */
+
+  /*
+  ** Memory available for allocation
+  */
+  Mem3Block aPool[SQLITE_MEMORY_SIZE/sizeof(Mem3Block)+2];
+} mem;
+
+/*
+** Unlink the chunk at mem.aPool[i] from list it is currently
+** on.  *pRoot is the list that i is a member of.
+*/
+static void memsys3UnlinkFromList(int i, int *pRoot){
+  int next = mem.aPool[i].u.list.next;
+  int prev = mem.aPool[i].u.list.prev;
+  assert( sqlite3_mutex_held(mem.mutex) );
+  if( prev==0 ){
+    *pRoot = next;
+  }else{
+    mem.aPool[prev].u.list.next = next;
+  }
+  if( next ){
+    mem.aPool[next].u.list.prev = prev;
+  }
+  mem.aPool[i].u.list.next = 0;
+  mem.aPool[i].u.list.prev = 0;
+}
+
+/*
+** Unlink the chunk at index i from 
+** whatever list is currently a member of.
+*/
+static void memsys3Unlink(int i){
+  int size, hash;
+  assert( sqlite3_mutex_held(mem.mutex) );
+  size = mem.aPool[i-1].u.hdr.size;
+  assert( size==mem.aPool[i+size-1].u.hdr.prevSize );
+  assert( size>=2 );
+  if( size <= MX_SMALL ){
+    memsys3UnlinkFromList(i, &mem.aiSmall[size-2]);
+  }else{
+    hash = size % N_HASH;
+    memsys3UnlinkFromList(i, &mem.aiHash[hash]);
+  }
+}
+
+/*
+** Link the chunk at mem.aPool[i] so that is on the list rooted
+** at *pRoot.
+*/
+static void memsys3LinkIntoList(int i, int *pRoot){
+  assert( sqlite3_mutex_held(mem.mutex) );
+  mem.aPool[i].u.list.next = *pRoot;
+  mem.aPool[i].u.list.prev = 0;
+  if( *pRoot ){
+    mem.aPool[*pRoot].u.list.prev = i;
+  }
+  *pRoot = i;
+}
+
+/*
+** Link the chunk at index i into either the appropriate
+** small chunk list, or into the large chunk hash table.
+*/
+static void memsys3Link(int i){
+  int size, hash;
+  assert( sqlite3_mutex_held(mem.mutex) );
+  size = mem.aPool[i-1].u.hdr.size;
+  assert( size==mem.aPool[i+size-1].u.hdr.prevSize );
+  assert( size>=2 );
+  if( size <= MX_SMALL ){
+    memsys3LinkIntoList(i, &mem.aiSmall[size-2]);
+  }else{
+    hash = size % N_HASH;
+    memsys3LinkIntoList(i, &mem.aiHash[hash]);
+  }
+}
+
+/*
+** Enter the mutex mem.mutex. Allocate it if it is not already allocated.
+**
+** Also:  Initialize the memory allocation subsystem the first time
+** this routine is called.
+*/
+static void memsys3Enter(void){
+  if( mem.mutex==0 ){
+    mem.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MEM);
+    mem.aPool[0].u.hdr.size = SQLITE_MEMORY_SIZE/8;
+    mem.aPool[SQLITE_MEMORY_SIZE/8].u.hdr.prevSize = SQLITE_MEMORY_SIZE/8;
+    mem.iMaster = 1;
+    mem.szMaster = SQLITE_MEMORY_SIZE/8;
+    mem.mnMaster = mem.szMaster;
+  }
+  sqlite3_mutex_enter(mem.mutex);
+}
+
+/*
+** Return the amount of memory currently checked out.
+*/
+sqlite3_int64 sqlite3_memory_used(void){
+  sqlite3_int64 n;
+  memsys3Enter();
+  n = SQLITE_MEMORY_SIZE - mem.szMaster*8;
+  sqlite3_mutex_leave(mem.mutex);  
+  return n;
+}
+
+/*
+** Return the maximum amount of memory that has ever been
+** checked out since either the beginning of this process
+** or since the most recent reset.
+*/
+sqlite3_int64 sqlite3_memory_highwater(int resetFlag){
+  sqlite3_int64 n;
+  memsys3Enter();
+  n = SQLITE_MEMORY_SIZE - mem.mnMaster*8;
+  if( resetFlag ){
+    mem.mnMaster = mem.szMaster;
+  }
+  sqlite3_mutex_leave(mem.mutex);  
+  return n;
+}
+
+/*
+** Change the alarm callback.
+**
+** This is a no-op for the static memory allocator.  The purpose
+** of the memory alarm is to support sqlite3_soft_heap_limit().
+** But with this memory allocator, the soft_heap_limit is really
+** a hard limit that is fixed at SQLITE_MEMORY_SIZE.
+*/
+int sqlite3_memory_alarm(
+  void(*xCallback)(void *pArg, sqlite3_int64 used,int N),
+  void *pArg,
+  sqlite3_int64 iThreshold
+){
+  return SQLITE_OK;
+}
+
+/*
+** Called when we are unable to satisfy an allocation of nBytes.
+*/
+static void memsys3OutOfMemory(int nByte){
+  if( !mem.alarmBusy ){
+    mem.alarmBusy = 1;
+    assert( sqlite3_mutex_held(mem.mutex) );
+    sqlite3_mutex_leave(mem.mutex);
+    sqlite3_release_memory(nByte);
+    sqlite3_mutex_enter(mem.mutex);
+    mem.alarmBusy = 0;
+  }
+}
+
+/*
+** Return the size of an outstanding allocation, in bytes.  The
+** size returned omits the 8-byte header overhead.  This only
+** works for chunks that are currently checked out.
+*/
+static int memsys3Size(void *p){
+  Mem3Block *pBlock = (Mem3Block*)p;
+  assert( pBlock[-1].u.hdr.size<0 );
+  return (-1-pBlock[-1].u.hdr.size)*8;
+}
+
+/*
+** Chunk i is a free chunk that has been unlinked.  Adjust its 
+** size parameters for check-out and return a pointer to the 
+** user portion of the chunk.
+*/
+static void *memsys3Checkout(int i, int nBlock){
+  assert( sqlite3_mutex_held(mem.mutex) );
+  assert( mem.aPool[i-1].u.hdr.size==nBlock );
+  assert( mem.aPool[i+nBlock-1].u.hdr.prevSize==nBlock );
+  mem.aPool[i-1].u.hdr.size = -nBlock;
+  mem.aPool[i+nBlock-1].u.hdr.prevSize = -nBlock;
+  return &mem.aPool[i];
+}
+
+/*
+** Carve a piece off of the end of the mem.iMaster free chunk.
+** Return a pointer to the new allocation.  Or, if the master chunk
+** is not large enough, return 0.
+*/
+static void *memsys3FromMaster(int nBlock){
+  assert( sqlite3_mutex_held(mem.mutex) );
+  assert( mem.szMaster>=nBlock );
+  if( nBlock>=mem.szMaster-1 ){
+    /* Use the entire master */
+    void *p = memsys3Checkout(mem.iMaster, mem.szMaster);
+    mem.iMaster = 0;
+    mem.szMaster = 0;
+    mem.mnMaster = 0;
+    return p;
+  }else{
+    /* Split the master block.  Return the tail. */
+    int newi;
+    newi = mem.iMaster + mem.szMaster - nBlock;
+    assert( newi > mem.iMaster+1 );
+    mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = -nBlock;
+    mem.aPool[newi-1].u.hdr.size = -nBlock;
+    mem.szMaster -= nBlock;
+    mem.aPool[newi-1].u.hdr.prevSize = mem.szMaster;
+    mem.aPool[mem.iMaster-1].u.hdr.size = mem.szMaster;
+    if( mem.szMaster < mem.mnMaster ){
+      mem.mnMaster = mem.szMaster;
+    }
+    return (void*)&mem.aPool[newi];
+  }
+}
+
+/*
+** *pRoot is the head of a list of free chunks of the same size
+** or same size hash.  In other words, *pRoot is an entry in either
+** mem.aiSmall[] or mem.aiHash[].  
+**
+** This routine examines all entries on the given list and tries
+** to coalesce each entries with adjacent free chunks.  
+**
+** If it sees a chunk that is larger than mem.iMaster, it replaces 
+** the current mem.iMaster with the new larger chunk.  In order for
+** this mem.iMaster replacement to work, the master chunk must be
+** linked into the hash tables.  That is not the normal state of
+** affairs, of course.  The calling routine must link the master
+** chunk before invoking this routine, then must unlink the (possibly
+** changed) master chunk once this routine has finished.
+*/
+static void memsys3Merge(int *pRoot){
+  int iNext, prev, size, i;
+
+  assert( sqlite3_mutex_held(mem.mutex) );
+  for(i=*pRoot; i>0; i=iNext){
+    iNext = mem.aPool[i].u.list.next;
+    size = mem.aPool[i-1].u.hdr.size;
+    assert( size>0 );
+    if( mem.aPool[i-1].u.hdr.prevSize>0 ){
+      memsys3UnlinkFromList(i, pRoot);
+      prev = i - mem.aPool[i-1].u.hdr.prevSize;
+      assert( prev>=0 );
+      if( prev==iNext ){
+        iNext = mem.aPool[prev].u.list.next;
+      }
+      memsys3Unlink(prev);
+      size = i + size - prev;
+      mem.aPool[prev-1].u.hdr.size = size;
+      mem.aPool[prev+size-1].u.hdr.prevSize = size;
+      memsys3Link(prev);
+      i = prev;
+    }
+    if( size>mem.szMaster ){
+      mem.iMaster = i;
+      mem.szMaster = size;
+    }
+  }
+}
+
+/*
+** Return a block of memory of at least nBytes in size.
+** Return NULL if unable.
+*/
+static void *memsys3Malloc(int nByte){
+  int i;
+  int nBlock;
+  int toFree;
+
+  assert( sqlite3_mutex_held(mem.mutex) );
+  assert( sizeof(Mem3Block)==8 );
+  if( nByte<=0 ){
+    nBlock = 2;
+  }else{
+    nBlock = (nByte + 15)/8;
+  }
+  assert( nBlock >= 2 );
+
+  /* STEP 1:
+  ** Look for an entry of the correct size in either the small
+  ** chunk table or in the large chunk hash table.  This is
+  ** successful most of the time (about 9 times out of 10).
+  */
+  if( nBlock <= MX_SMALL ){
+    i = mem.aiSmall[nBlock-2];
+    if( i>0 ){
+      memsys3UnlinkFromList(i, &mem.aiSmall[nBlock-2]);
+      return memsys3Checkout(i, nBlock);
+    }
+  }else{
+    int hash = nBlock % N_HASH;
+    for(i=mem.aiHash[hash]; i>0; i=mem.aPool[i].u.list.next){
+      if( mem.aPool[i-1].u.hdr.size==nBlock ){
+        memsys3UnlinkFromList(i, &mem.aiHash[hash]);
+        return memsys3Checkout(i, nBlock);
+      }
+    }
+  }
+
+  /* STEP 2:
+  ** Try to satisfy the allocation by carving a piece off of the end
+  ** of the master chunk.  This step usually works if step 1 fails.
+  */
+  if( mem.szMaster>=nBlock ){
+    return memsys3FromMaster(nBlock);
+  }
+
+
+  /* STEP 3:  
+  ** Loop through the entire memory pool.  Coalesce adjacent free
+  ** chunks.  Recompute the master chunk as the largest free chunk.
+  ** Then try again to satisfy the allocation by carving a piece off
+  ** of the end of the master chunk.  This step happens very
+  ** rarely (we hope!)
+  */
+  for(toFree=nBlock*16; toFree<SQLITE_MEMORY_SIZE*2; toFree *= 2){
+    memsys3OutOfMemory(toFree);
+    if( mem.iMaster ){
+      memsys3Link(mem.iMaster);
+      mem.iMaster = 0;
+      mem.szMaster = 0;
+    }
+    for(i=0; i<N_HASH; i++){
+      memsys3Merge(&mem.aiHash[i]);
+    }
+    for(i=0; i<MX_SMALL-1; i++){
+      memsys3Merge(&mem.aiSmall[i]);
+    }
+    if( mem.szMaster ){
+      memsys3Unlink(mem.iMaster);
+      if( mem.szMaster>=nBlock ){
+        return memsys3FromMaster(nBlock);
+      }
+    }
+  }
+
+  /* If none of the above worked, then we fail. */
+  return 0;
+}
+
+/*
+** Free an outstanding memory allocation.
+*/
+void memsys3Free(void *pOld){
+  Mem3Block *p = (Mem3Block*)pOld;
+  int i;
+  int size;
+  assert( sqlite3_mutex_held(mem.mutex) );
+  assert( p>mem.aPool && p<&mem.aPool[SQLITE_MEMORY_SIZE/8] );
+  i = p - mem.aPool;
+  size = -mem.aPool[i-1].u.hdr.size;
+  assert( size>=2 );
+  assert( mem.aPool[i+size-1].u.hdr.prevSize==-size );
+  mem.aPool[i-1].u.hdr.size = size;
+  mem.aPool[i+size-1].u.hdr.prevSize = size;
+  memsys3Link(i);
+
+  /* Try to expand the master using the newly freed chunk */
+  if( mem.iMaster ){
+    while( mem.aPool[mem.iMaster-1].u.hdr.prevSize>0 ){
+      size = mem.aPool[mem.iMaster-1].u.hdr.prevSize;
+      mem.iMaster -= size;
+      mem.szMaster += size;
+      memsys3Unlink(mem.iMaster);
+      mem.aPool[mem.iMaster-1].u.hdr.size = mem.szMaster;
+      mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = mem.szMaster;
+    }
+    while( mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.size>0 ){
+      memsys3Unlink(mem.iMaster+mem.szMaster);
+      mem.szMaster += mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.size;
+      mem.aPool[mem.iMaster-1].u.hdr.size = mem.szMaster;
+      mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = mem.szMaster;
+    }
+  }
+}
+
+/*
+** Allocate nBytes of memory
+*/
+void *sqlite3_malloc(int nBytes){
+  sqlite3_int64 *p = 0;
+  if( nBytes>0 ){
+    memsys3Enter();
+    p = memsys3Malloc(nBytes);
+    sqlite3_mutex_leave(mem.mutex);
+  }
+  return (void*)p; 
+}
+
+/*
+** Free memory.
+*/
+void sqlite3_free(void *pPrior){
+  if( pPrior==0 ){
+    return;
+  }
+  assert( mem.mutex!=0 );
+  sqlite3_mutex_enter(mem.mutex);
+  memsys3Free(pPrior);
+  sqlite3_mutex_leave(mem.mutex);  
+}
+
+/*
+** Change the size of an existing memory allocation
+*/
+void *sqlite3_realloc(void *pPrior, int nBytes){
+  int nOld;
+  void *p;
+  if( pPrior==0 ){
+    return sqlite3_malloc(nBytes);
+  }
+  if( nBytes<=0 ){
+    sqlite3_free(pPrior);
+    return 0;
+  }
+  assert( mem.mutex!=0 );
+  nOld = memsys3Size(pPrior);
+  if( nBytes<=nOld && nBytes>=nOld-128 ){
+    return pPrior;
+  }
+  sqlite3_mutex_enter(mem.mutex);
+  p = memsys3Malloc(nBytes);
+  if( p ){
+    if( nOld<nBytes ){
+      memcpy(p, pPrior, nOld);
+    }else{
+      memcpy(p, pPrior, nBytes);
+    }
+    memsys3Free(pPrior);
+  }
+  sqlite3_mutex_leave(mem.mutex);
+  return p;
+}
+
+/*
+** Open the file indicated and write a log of all unfreed memory 
+** allocations into that log.
+*/
+void sqlite3_memdebug_dump(const char *zFilename){
+#ifdef SQLITE_DEBUG
+  FILE *out;
+  int i, j, size;
+  if( zFilename==0 || zFilename[0]==0 ){
+    out = stdout;
+  }else{
+    out = fopen(zFilename, "w");
+    if( out==0 ){
+      fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
+                      zFilename);
+      return;
+    }
+  }
+  memsys3Enter();
+  fprintf(out, "CHUNKS:\n");
+  for(i=1; i<=SQLITE_MEMORY_SIZE/8; i+=size){
+    size = mem.aPool[i-1].u.hdr.size;
+    if( size>=-1 && size<=1 ){
+      fprintf(out, "%p size error\n", &mem.aPool[i]);
+      assert( 0 );
+      break;
+    }
+    if( mem.aPool[i+(size<0?-size:size)-1].u.hdr.prevSize!=size ){
+      fprintf(out, "%p tail size does not match\n", &mem.aPool[i]);
+      assert( 0 );
+      break;
+    }
+    if( size<0 ){
+      size = -size;
+      fprintf(out, "%p %6d bytes checked out\n", &mem.aPool[i], size*8-8);
+    }else{
+      fprintf(out, "%p %6d bytes free%s\n", &mem.aPool[i], size*8-8,
+                  i==mem.iMaster ? " **master**" : "");
+    }
+  }
+  for(i=0; i<MX_SMALL-1; i++){
+    if( mem.aiSmall[i]==0 ) continue;
+    fprintf(out, "small(%2d):", i);
+    for(j = mem.aiSmall[i]; j>0; j=mem.aPool[j].u.list.next){
+      fprintf(out, " %p(%d)", &mem.aPool[j], mem.aPool[j-1].u.hdr.size*8-8);
+    }
+    fprintf(out, "\n"); 
+  }
+  for(i=0; i<N_HASH; i++){
+    if( mem.aiHash[i]==0 ) continue;
+    fprintf(out, "hash(%2d):", i);
+    for(j = mem.aiHash[i]; j>0; j=mem.aPool[j].u.list.next){
+      fprintf(out, " %p(%d)", &mem.aPool[j], mem.aPool[j-1].u.hdr.size*8-8);
+    }
+    fprintf(out, "\n"); 
+  }
+  fprintf(out, "master=%d\n", mem.iMaster);
+  fprintf(out, "nowUsed=%d\n", SQLITE_MEMORY_SIZE - mem.szMaster*8);
+  fprintf(out, "mxUsed=%d\n", SQLITE_MEMORY_SIZE - mem.mnMaster*8);
+  sqlite3_mutex_leave(mem.mutex);
+  if( out==stdout ){
+    fflush(stdout);
+  }else{
+    fclose(out);
+  }
+#endif
+}
+
+
+#endif /* !SQLITE_MEMORY_SIZE */