diff -r 000000000000 -r 08ec8eefde2f persistentstorage/sql/SQLite/mem6.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/persistentstorage/sql/SQLite/mem6.c	Fri Jan 22 11:06:30 2010 +0200
@@ -0,0 +1,496 @@
+/*
+** 2008 July 24
+**
+** 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 an alternative memory allocation system for SQLite.
+** This system is implemented as a wrapper around the system provided
+** by the operating system - vanilla malloc(), realloc() and free().
+**
+** This system differentiates between requests for "small" allocations 
+** (by default those of 128 bytes or less) and "large" allocations (all
+** others). The 256 byte threshhold is configurable at runtime.
+**
+** All requests for large allocations are passed through to the 
+** default system.
+**
+** Requests for small allocations are met by allocating space within
+** one or more larger "chunks" of memory obtained from the default
+** memory allocation system. Chunks of memory are usually 64KB or 
+** larger. The algorithm used to manage space within each chunk is
+** the same as that used by mem5.c. 
+**
+** This strategy is designed to prevent the default memory allocation
+** system (usually the system malloc) from suffering from heap 
+** fragmentation. On some systems, heap fragmentation can cause a 
+** significant real-time slowdown.
+**
+** $Id: mem6.c,v 1.7 2008/07/28 19:34:53 drh Exp $
+*/
+
+#ifdef SQLITE_ENABLE_MEMSYS6
+
+#include "sqliteInt.h"
+
+/*
+** Maximum size of any "small" allocation is ((1<<LOGMAX)*Mem6Chunk.nAtom).
+** Mem6Chunk.nAtom is always at least 8, so this is not a practical
+** limitation
+*/
+#define LOGMAX 30
+
+/*
+** Default value for the "small" allocation size threshold.
+*/
+#define SMALL_MALLOC_DEFAULT_THRESHOLD 256
+
+/*
+** Minimum size for a memory chunk.
+*/
+#define MIN_CHUNKSIZE (1<<16)
+
+#define LOG2_MINALLOC 4
+
+
+typedef struct Mem6Chunk Mem6Chunk;
+typedef struct Mem6Link Mem6Link;
+
+/*
+** A minimum allocation is an instance of the following structure.
+** Larger allocations are an array of these structures where the
+** size of the array is a power of 2.
+*/
+struct Mem6Link {
+  int next;       /* Index of next free chunk */
+  int prev;       /* Index of previous free chunk */
+};
+
+/*
+** Masks used for mem5.aCtrl[] elements.
+*/
+#define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block relative to POW2_MIN */
+#define CTRL_FREE     0x20    /* True if not checked out */
+
+struct Mem6Chunk {
+  Mem6Chunk *pNext;
+
+  /*
+  ** Lists of free blocks of various sizes.
+  */
+  int aiFreelist[LOGMAX+1];
+
+  int nCheckedOut; /* Number of currently outstanding allocations */
+
+  /*
+  ** Space for tracking which blocks are checked out and the size
+  ** of each block. One byte per block.
+  */
+  u8 *aCtrl;
+
+  /*
+  ** Memory available for allocation
+  */
+  int nAtom;       /* Smallest possible allocation in bytes */
+  int nBlock;      /* Number of nAtom sized blocks in zPool */
+  u8 *zPool;       /* Pointer to memory chunk from which allocations are made */
+};
+
+#define MEM6LINK(idx) ((Mem6Link *)(&pChunk->zPool[(idx)*pChunk->nAtom]))
+
+struct Mem6Global {
+  int nMinAlloc;                  /* Minimum allowed allocation size */
+  int nThreshold;                 /* Allocs larger than this go to malloc() */
+  int nLogThreshold;              /* log2 of (nThreshold/nMinAlloc) */
+  sqlite3_mutex *mutex;
+  Mem6Chunk *pChunk;              /* Singly linked list of all memory chunks */
+} mem6;
+
+/*
+** Unlink the chunk at pChunk->aPool[i] from list it is currently
+** on.  It should be found on pChunk->aiFreelist[iLogsize].
+*/
+static void memsys6Unlink(Mem6Chunk *pChunk, int i, int iLogsize){
+  int next, prev;
+  assert( i>=0 && i<pChunk->nBlock );
+  assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );
+  assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
+
+  next = MEM6LINK(i)->next;
+  prev = MEM6LINK(i)->prev;
+  if( prev<0 ){
+    pChunk->aiFreelist[iLogsize] = next;
+  }else{
+    MEM6LINK(prev)->next = next;
+  }
+  if( next>=0 ){
+    MEM6LINK(next)->prev = prev;
+  }
+}
+
+/*
+** Link the chunk at mem5.aPool[i] so that is on the iLogsize
+** free list.
+*/
+static void memsys6Link(Mem6Chunk *pChunk, int i, int iLogsize){
+  int x;
+  assert( i>=0 && i<pChunk->nBlock );
+  assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );
+  assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
+
+  x = MEM6LINK(i)->next = pChunk->aiFreelist[iLogsize];
+  MEM6LINK(i)->prev = -1;
+  if( x>=0 ){
+    assert( x<pChunk->nBlock );
+    MEM6LINK(x)->prev = i;
+  }
+  pChunk->aiFreelist[iLogsize] = i;
+}
+
+
+/*
+** Find the first entry on the freelist iLogsize.  Unlink that
+** entry and return its index. 
+*/
+static int memsys6UnlinkFirst(Mem6Chunk *pChunk, int iLogsize){
+  int i;
+  int iFirst;
+
+  assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );
+  i = iFirst = pChunk->aiFreelist[iLogsize];
+  assert( iFirst>=0 );
+  memsys6Unlink(pChunk, iFirst, iLogsize);
+  return iFirst;
+}
+
+static int roundupLog2(int n){
+  static const char LogTable256[256] = {
+    0,                                                    /* 1 */
+    1,                                                    /* 2 */
+    2, 2,                                                 /* 3..4 */
+    3, 3, 3, 3,                                           /* 5..8 */
+    4, 4, 4, 4, 4, 4, 4, 4,                               /* 9..16 */
+    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,       /* 17..32 */
+    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,       /* 33..64 */
+    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,       /* 65..128 */
+    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+    8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,       /* 129..256 */
+  };
+
+  assert(n<=(1<<16) && n>0);
+  if( n<=256 ) return LogTable256[n-1];
+  return LogTable256[(n>>8) - ((n&0xFF)?0:1)] + 8;
+}
+
+/*
+** Allocate and return a block of (pChunk->nAtom << iLogsize) bytes from chunk
+** pChunk. If the allocation request cannot be satisfied, return 0.
+*/
+static void *chunkMalloc(Mem6Chunk *pChunk, int iLogsize){
+  int i;           /* Index of a mem5.aPool[] slot */
+  int iBin;        /* Index into mem5.aiFreelist[] */
+
+  /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
+  ** block.  If not, then split a block of the next larger power of
+  ** two in order to create a new free block of size iLogsize.
+  */
+  for(iBin=iLogsize; pChunk->aiFreelist[iBin]<0 && iBin<=mem6.nLogThreshold; iBin++){}
+  if( iBin>mem6.nLogThreshold ) return 0;
+  i = memsys6UnlinkFirst(pChunk, iBin);
+  while( iBin>iLogsize ){
+    int newSize;
+    iBin--;
+    newSize = 1 << iBin;
+    pChunk->aCtrl[i+newSize] = CTRL_FREE | iBin;
+    memsys6Link(pChunk, i+newSize, iBin);
+  }
+  pChunk->aCtrl[i] = iLogsize;
+
+  /* Return a pointer to the allocated memory. */
+  pChunk->nCheckedOut++;
+  return (void*)&pChunk->zPool[i*pChunk->nAtom];
+}
+
+/*
+** Free the allocation pointed to by p, which is guaranteed to be non-zero
+** and a part of chunk object pChunk.
+*/
+static void chunkFree(Mem6Chunk *pChunk, void *pOld){
+  u32 size, iLogsize;
+  int iBlock;             
+
+  /* Set iBlock to the index of the block pointed to by pOld in 
+  ** the array of pChunk->nAtom byte blocks pointed to by pChunk->zPool.
+  */
+  iBlock = ((u8 *)pOld-pChunk->zPool)/pChunk->nAtom;
+
+  /* Check that the pointer pOld points to a valid, non-free block. */
+  assert( iBlock>=0 && iBlock<pChunk->nBlock );
+  assert( ((u8 *)pOld-pChunk->zPool)%pChunk->nAtom==0 );
+  assert( (pChunk->aCtrl[iBlock] & CTRL_FREE)==0 );
+
+  iLogsize = pChunk->aCtrl[iBlock] & CTRL_LOGSIZE;
+  size = 1<<iLogsize;
+  assert( iBlock+size-1<pChunk->nBlock );
+
+  pChunk->aCtrl[iBlock] |= CTRL_FREE;
+  pChunk->aCtrl[iBlock+size-1] |= CTRL_FREE;
+
+  pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize;
+  while( iLogsize<mem6.nLogThreshold ){
+    int iBuddy;
+    if( (iBlock>>iLogsize) & 1 ){
+      iBuddy = iBlock - size;
+    }else{
+      iBuddy = iBlock + size;
+    }
+    assert( iBuddy>=0 );
+    if( (iBuddy+(1<<iLogsize))>pChunk->nBlock ) break;
+    if( pChunk->aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
+    memsys6Unlink(pChunk, iBuddy, iLogsize);
+    iLogsize++;
+    if( iBuddy<iBlock ){
+      pChunk->aCtrl[iBuddy] = CTRL_FREE | iLogsize;
+      pChunk->aCtrl[iBlock] = 0;
+      iBlock = iBuddy;
+    }else{
+      pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize;
+      pChunk->aCtrl[iBuddy] = 0;
+    }
+    size *= 2;
+  }
+  pChunk->nCheckedOut--;
+  memsys6Link(pChunk, iBlock, iLogsize);
+}
+
+/*
+** Return the actual size of the block pointed to by p, which is guaranteed
+** to have been allocated from chunk pChunk.
+*/
+static int chunkSize(Mem6Chunk *pChunk, void *p){
+  int iSize = 0;
+  if( p ){
+    int i = ((u8 *)p-pChunk->zPool)/pChunk->nAtom;
+    assert( i>=0 && i<pChunk->nBlock );
+    iSize = pChunk->nAtom * (1 << (pChunk->aCtrl[i]&CTRL_LOGSIZE));
+  }
+  return iSize;
+}
+
+/*
+** Return true if there are currently no outstanding allocations.
+*/
+static int chunkIsEmpty(Mem6Chunk *pChunk){
+  return (pChunk->nCheckedOut==0);
+}
+
+/*
+** Initialize the buffer zChunk, which is nChunk bytes in size, as
+** an Mem6Chunk object. Return a copy of the zChunk pointer.
+*/
+static Mem6Chunk *chunkInit(u8 *zChunk, int nChunk, int nMinAlloc){
+  int ii;
+  int iOffset;
+  Mem6Chunk *pChunk = (Mem6Chunk *)zChunk;
+
+  assert( nChunk>sizeof(Mem6Chunk) );
+  assert( nMinAlloc>sizeof(Mem6Link) );
+
+  memset(pChunk, 0, sizeof(Mem6Chunk));
+  pChunk->nAtom = nMinAlloc;
+  pChunk->nBlock = ((nChunk-sizeof(Mem6Chunk)) / (pChunk->nAtom+sizeof(u8)));
+
+  pChunk->zPool = (u8 *)&pChunk[1];
+  pChunk->aCtrl = &pChunk->zPool[pChunk->nBlock*pChunk->nAtom];
+
+  for(ii=0; ii<=mem6.nLogThreshold; ii++){
+    pChunk->aiFreelist[ii] = -1;
+  }
+
+  iOffset = 0;
+  for(ii=mem6.nLogThreshold; ii>=0; ii--){
+    int nAlloc = (1<<ii);
+    while( (iOffset+nAlloc)<=pChunk->nBlock ){
+      pChunk->aCtrl[iOffset] = ii | CTRL_FREE;
+      memsys6Link(pChunk, iOffset, ii);
+      iOffset += nAlloc;
+    }
+  }
+
+  return pChunk;
+}
+
+
+static void mem6Enter(void){
+  sqlite3_mutex_enter(mem6.mutex);
+}
+
+static void mem6Leave(void){
+  sqlite3_mutex_leave(mem6.mutex);
+}
+
+/*
+** Based on the number and size of the currently allocated chunks, return
+** the size of the next chunk to allocate, in bytes.
+*/
+static int nextChunkSize(void){
+  int iTotal = MIN_CHUNKSIZE;
+  Mem6Chunk *p;
+  for(p=mem6.pChunk; p; p=p->pNext){
+    iTotal = iTotal*2;
+  }
+  return iTotal;
+}
+
+static void freeChunk(Mem6Chunk *pChunk){
+  Mem6Chunk **pp = &mem6.pChunk;
+  for( pp=&mem6.pChunk; *pp!=pChunk; pp = &(*pp)->pNext );
+  *pp = (*pp)->pNext;
+  free(pChunk);
+}
+
+static void *memsys6Malloc(int nByte){
+  Mem6Chunk *pChunk;
+  void *p = 0;
+  int nTotal = nByte+8;
+  int iOffset = 0;
+
+  if( nTotal>mem6.nThreshold ){
+    p = malloc(nTotal);
+  }else{
+    int iLogsize = 0;
+    if( nTotal>(1<<LOG2_MINALLOC) ){
+      iLogsize = roundupLog2(nTotal) - LOG2_MINALLOC;
+    }
+    mem6Enter();
+    for(pChunk=mem6.pChunk; pChunk; pChunk=pChunk->pNext){
+      p = chunkMalloc(pChunk, iLogsize);
+      if( p ){
+        break;
+      }
+    }
+    if( !p ){
+      int iSize = nextChunkSize();
+      p = malloc(iSize);
+      if( p ){
+        pChunk = chunkInit((u8 *)p, iSize, mem6.nMinAlloc);
+        pChunk->pNext = mem6.pChunk;
+        mem6.pChunk = pChunk;
+        p = chunkMalloc(pChunk, iLogsize);
+        assert(p);
+      }
+    }
+    iOffset = ((u8*)p - (u8*)pChunk);
+    mem6Leave();
+  }
+
+  if( !p ){
+    return 0;
+  }
+  ((u32 *)p)[0] = iOffset;
+  ((u32 *)p)[1] = nByte;
+  return &((u32 *)p)[2];
+}
+
+static int memsys6Size(void *pPrior){
+  if( pPrior==0 ) return 0;
+  return ((u32*)pPrior)[-1];
+}
+
+static void memsys6Free(void *pPrior){
+  int iSlot;
+  void *p = &((u32 *)pPrior)[-2];
+  iSlot = ((u32 *)p)[0];
+  if( iSlot ){
+    Mem6Chunk *pChunk;
+    mem6Enter();
+    pChunk = (Mem6Chunk *)(&((u8 *)p)[-1 * iSlot]);
+    chunkFree(pChunk, p);
+    if( chunkIsEmpty(pChunk) ){
+      freeChunk(pChunk);
+    }
+    mem6Leave();
+  }else{
+    free(p);
+  }
+}
+
+static void *memsys6Realloc(void *p, int nByte){
+  void *p2;
+
+  if( p && nByte<=memsys6Size(p) ){
+    p2 = p;
+  }else{
+    p2 = memsys6Malloc(nByte);
+    if( p && p2 ){
+      memcpy(p2, p, memsys6Size(p));
+      memsys6Free(p);
+    }
+  }
+
+  return p2;
+}
+
+static int memsys6Roundup(int n){
+  if( n>mem6.nThreshold ){
+    return n;
+  }else{
+    return (1<<roundupLog2(n));
+  }
+}
+
+static int memsys6Init(void *pCtx){
+  u8 bMemstat = sqlite3Config.bMemstat;
+  mem6.nMinAlloc = (1 << LOG2_MINALLOC);
+  mem6.pChunk = 0;
+  mem6.nThreshold = sqlite3Config.nSmall;
+  if( mem6.nThreshold<=0 ){
+    mem6.nThreshold = SMALL_MALLOC_DEFAULT_THRESHOLD;
+  }
+  mem6.nLogThreshold = roundupLog2(mem6.nThreshold) - LOG2_MINALLOC;
+  if( !bMemstat ){
+    mem6.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
+  }
+  return SQLITE_OK;
+}
+
+static void memsys6Shutdown(void *pCtx){
+  memset(&mem6, 0, sizeof(mem6));
+}
+
+/*
+** This routine is the only routine in this file with external 
+** linkage. It returns a pointer to a static sqlite3_mem_methods
+** struct populated with the memsys6 methods.
+*/
+const sqlite3_mem_methods *sqlite3MemGetMemsys6(void){
+  static const sqlite3_mem_methods memsys6Methods = {
+     memsys6Malloc,
+     memsys6Free,
+     memsys6Realloc,
+     memsys6Size,
+     memsys6Roundup,
+     memsys6Init,
+     memsys6Shutdown,
+     0
+  };
+  return &memsys6Methods;
+}
+
+#endif