** 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.c,v 1.2 2007/10/20 12:34:01 drh Exp $
*/

/*
** This version of the memory allocator is used only when 
** SQLITE_MEMORY_SIZE is defined.
*/
#if defined(SQLITE_MEMORY_SIZE)
................................................................................
** 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 {
  /*
  ** The alarm callback and its arguments.  The mem.mutex lock will
  ** be held while the callback is running.  Recursive calls into
  ** the memory subsystem are allowed, but no new callbacks will be
  ** issued.  The alarmBusy variable is set to prevent recursive
  ** callbacks.
  */
  sqlite3_int64 alarmThreshold;
  void (*alarmCallback)(void*, sqlite3_int64,int);
  void *alarmArg;
  int alarmBusy;
  
  /*
  ** Mutex to control access to the memory allocation subsystem.
  */
  sqlite3_mutex *mutex;
  
  /*
  ** Current allocation and high-water mark.
  */
  sqlite3_int64 nowUsed;
  sqlite3_int64 mxUsed;

  /*
  ** 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[].
  */
................................................................................
  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 unlinkChunkFromList(int i, int *pRoot){
  int next = mem.aPool[i].u.list.next;
  int prev = mem.aPool[i].u.list.prev;
  if( prev==0 ){
    *pRoot = next;
  }else{
    mem.aPool[prev].u.list.next = next;
  }
................................................................................
  mem.aPool[i].u.list.prev = 0;
}

/*
** Unlink the chunk at index i from 
** whatever list is currently a member of.
*/
static void unlinkChunk(int i){
  int size, hash;
  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 ){
    unlinkChunkFromList(i, &mem.aiSmall[size-2]);
  }else{
    hash = size % N_HASH;
    unlinkChunkFromList(i, &mem.aiHash[hash]);
  }
}

/*
** Link the chunk at mem.aPool[i] so that is on the list rooted
** at *pRoot.
*/
static void linkChunkIntoList(int i, int *pRoot){
  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 linkChunk(int i){
  int size, hash;
  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 ){
    linkChunkIntoList(i, &mem.aiSmall[size-2]);
  }else{
    hash = size % N_HASH;
    linkChunkIntoList(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 enterMem(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;

  }
  sqlite3_mutex_enter(mem.mutex);
}

/*
** Return the amount of memory currently checked out.
*/
sqlite3_int64 sqlite3_memory_used(void){
  sqlite3_int64 n;
  enterMem();
  n = mem.nowUsed;
  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;
  enterMem();
  n = mem.mxUsed;
  if( resetFlag ){
    mem.mxUsed = mem.nowUsed;
  }
  sqlite3_mutex_leave(mem.mutex);  
  return n;
}

/*
** Change the alarm callback





*/
int sqlite3_memory_alarm(
  void(*xCallback)(void *pArg, sqlite3_int64 used,int N),
  void *pArg,
  sqlite3_int64 iThreshold
){
  enterMem();
  mem.alarmCallback = xCallback;
  mem.alarmArg = pArg;
  mem.alarmThreshold = iThreshold;
  sqlite3_mutex_leave(mem.mutex);
  return SQLITE_OK;
}

/*
** Trigger the alarm 
*/
static void sqlite3MemsysAlarm(int nByte){
  void (*xCallback)(void*,sqlite3_int64,int);
  sqlite3_int64 nowUsed;
  void *pArg;
  if( mem.alarmCallback==0 || mem.alarmBusy  ) return;
  mem.alarmBusy = 1;
  xCallback = mem.alarmCallback;
  nowUsed = mem.nowUsed;
  pArg = mem.alarmArg;
  sqlite3_mutex_leave(mem.mutex);
  xCallback(pArg, nowUsed, nByte);

  sqlite3_mutex_enter(mem.mutex);
  mem.alarmBusy = 0;

}

/*
** Return the size of an outstanding allocation, in bytes.  The
** size returned includes the 8-byte header overhead.  This only
** works for chunks that are currently checked out.
*/
static int internal_size(void *p){
  Mem3Block *pBlock = (Mem3Block*)p;
  assert( pBlock[-1].u.hdr.size<0 );
  return -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 *checkOutChunk(int i, int nBlock){
  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 *internal_from_master(int nBlock){
  assert( mem.szMaster>=nBlock );
  if( nBlock>=mem.szMaster-1 ){
    /* Use the entire master */
    void *p = checkOutChunk(mem.iMaster, mem.szMaster);
    mem.iMaster = 0;
    mem.szMaster = 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;



    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
................................................................................
** 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 mergeChunks(int *pRoot){
  int iNext, prev, size, i;

  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 ){
      unlinkChunkFromList(i, pRoot);
      prev = i - mem.aPool[i-1].u.hdr.prevSize;
      assert( prev>=0 );
      if( prev==iNext ){
        iNext = mem.aPool[prev].u.list.next;
      }
      unlinkChunk(prev);
      size = i + size - prev;
      mem.aPool[prev-1].u.hdr.size = size;
      mem.aPool[prev+size-1].u.hdr.prevSize = size;
      linkChunk(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 *internal_malloc(int nByte){
  int i;
  int nBlock;

  assert( sizeof(Mem3Block)==8 );
  if( nByte<=0 ){
    nBlock = 2;
  }else{
................................................................................
  ** 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 ){
      unlinkChunkFromList(i, &mem.aiSmall[nBlock-2]);
      return checkOutChunk(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 ){
        unlinkChunkFromList(i, &mem.aiHash[hash]);
        return checkOutChunk(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 internal_from_master(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!)
  */

  if( mem.iMaster ){
    linkChunk(mem.iMaster);
    mem.iMaster = 0;
    mem.szMaster = 0;
  }
  for(i=0; i<N_HASH; i++){
    mergeChunks(&mem.aiHash[i]);
  }
  for(i=0; i<MX_SMALL-1; i++){
    mergeChunks(&mem.aiSmall[i]);
  }
  if( mem.szMaster ){
    unlinkChunk(mem.iMaster);
    if( mem.szMaster>=nBlock ){
      return internal_from_master(nBlock);
    }
  }

  /* If none of the above worked, then we fail. */
  return 0;
}

/*
** Free an outstanding memory allocation.
*/
void internal_free(void *pOld){
  Mem3Block *p = (Mem3Block*)pOld;
  int i;
  int size;
  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;
  linkChunk(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;
      unlinkChunk(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 ){
      unlinkChunk(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 ){
    enterMem();
    if( mem.alarmCallback!=0 && mem.nowUsed+nBytes>=mem.alarmThreshold ){
      sqlite3MemsysAlarm(nBytes);
    }
    p = internal_malloc(nBytes);
    if( p==0 ){
      sqlite3MemsysAlarm(nBytes);
      p = internal_malloc(nBytes);
    }
    if( p ){
      mem.nowUsed += internal_size(p);
      if( mem.nowUsed>mem.mxUsed ){
        mem.mxUsed = mem.nowUsed;
      }
    }
    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);
  mem.nowUsed -= internal_size(pPrior);
  internal_free(pPrior);
  sqlite3_mutex_leave(mem.mutex);  
}

/*
** Change the size of an existing memory allocation
*/
void *sqlite3_realloc(void *pPrior, int nBytes){
................................................................................
    return sqlite3_malloc(nBytes);
  }
  if( nBytes<=0 ){
    sqlite3_free(pPrior);
    return 0;
  }
  assert( mem.mutex!=0 );
  sqlite3_mutex_enter(mem.mutex);
  nOld = internal_size(pPrior);

  if( mem.alarmCallback!=0 && mem.nowUsed+nBytes-nOld>=mem.alarmThreshold ){
    sqlite3MemsysAlarm(nBytes-nOld);
  }
  p = internal_malloc(nBytes);
  if( p==0 ){
    sqlite3MemsysAlarm(nBytes);
    p = internal_malloc(nBytes);
    if( p==0 ){
      sqlite3_mutex_leave(mem.mutex);
      return 0;
    }
  }
  if( nOld<nBytes ){
    memcpy(p, pPrior, nOld);
  }else{
    memcpy(p, pPrior, nBytes);
  }
  internal_free(pPrior);
  mem.nowUsed += internal_size(p)-nOld;
  if( mem.nowUsed>mem.mxUsed ){
    mem.mxUsed = mem.nowUsed;
  }
  sqlite3_mutex_leave(mem.mutex);
  return p;
}

/*
** Open the file indicated and write a log of all unfreed memory 
................................................................................
    out = fopen(zFilename, "w");
    if( out==0 ){
      fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
                      zFilename);
      return;
    }
  }
  enterMem();
  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;
................................................................................
    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=%lld\n", mem.nowUsed);
  fprintf(out, "mxUsed=%lld\n", mem.mxUsed);
  sqlite3_mutex_leave(mem.mutex);
  if( out==stdout ){
    fflush(stdout);
  }else{
    fclose(out);
  }
#endif
}


#endif /* !SQLITE_MEMORY_SIZE */

** 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.c,v 1.3 2007/10/20 15:41:58 drh Exp $
*/

/*
** This version of the memory allocator is used only when 
** SQLITE_MEMORY_SIZE is defined.
*/
#if defined(SQLITE_MEMORY_SIZE)
................................................................................
** 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[].
  */
................................................................................
  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;
  if( prev==0 ){
    *pRoot = next;
  }else{
    mem.aPool[prev].u.list.next = next;
  }
................................................................................
  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;
  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){
  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;
  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;



    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( 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( 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
................................................................................
** 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;

  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;

  assert( sizeof(Mem3Block)==8 );
  if( nByte<=0 ){
    nBlock = 2;
  }else{
................................................................................
  ** 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!)
  */
  memsys3OutOfMemory(nBlock*16);
  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( 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){
................................................................................
    return sqlite3_malloc(nBytes);
  }
  if( nBytes<=0 ){
    sqlite3_free(pPrior);
    return 0;
  }
  assert( mem.mutex!=0 );

  nOld = memsys3Size(pPrior);
#if 0
  if( nBytes<=nOld && nBytes>=nOld-128 ){
    return pPrior;
  }
#endif
  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 
................................................................................
    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;
................................................................................
    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 */

void sqlite3VdbeTrace(Vdbe *p, FILE *trace){
  p->trace = trace;
}
#endif

/*
** Resize the Vdbe.aOp array so that it contains at least N
** elements. If the Vdbe is in VDBE_MAGIC_RUN state, then
** the Vdbe.aOp array will be sized to contain exactly N
** elements. Vdbe.nOpAlloc is set to reflect the new size of
** the array.
**
** If an out-of-memory error occurs while resizing the array,
** Vdbe.aOp and Vdbe.nOpAlloc remain unchanged (this is so that
** any opcodes already allocated can be correctly deallocated
** along with the rest of the Vdbe).
*/
static void resizeOpArray(Vdbe *p, int N){
  int runMode = p->magic==VDBE_MAGIC_RUN;
  if( runMode || p->nOpAlloc<N ){
    VdbeOp *pNew;
    int nNew = N + 100*(!runMode);
    int oldSize = p->nOpAlloc;
    pNew = sqlite3DbRealloc(p->db, p->aOp, nNew*sizeof(Op));
    if( pNew ){
      p->nOpAlloc = nNew;
      p->aOp = pNew;
      if( nNew>oldSize ){
        memset(&p->aOp[oldSize], 0, (nNew-oldSize)*sizeof(Op));
      }
    }
  }
}

/*
** Add a new instruction to the list of instructions current in the
** VDBE.  Return the address of the new instruction.
................................................................................
int sqlite3VdbeAddOp(Vdbe *p, int op, int p1, int p2){
  int i;
  VdbeOp *pOp;

  i = p->nOp;
  assert( p->magic==VDBE_MAGIC_INIT );
  if( p->nOpAlloc<=i ){
    resizeOpArray(p, i+1);
    if( p->db->mallocFailed ){
      return 0;
    }
  }
  p->nOp++;
  pOp = &p->aOp[i];
  pOp->opcode = op;
................................................................................
/*
** Add a whole list of operations to the operation stack.  Return the
** address of the first operation added.
*/
int sqlite3VdbeAddOpList(Vdbe *p, int nOp, VdbeOpList const *aOp){
  int addr;
  assert( p->magic==VDBE_MAGIC_INIT );

  resizeOpArray(p, p->nOp + nOp);

  if( p->db->mallocFailed ){
    return 0;
  }
  addr = p->nOp;
  if( nOp>0 ){
    int i;
    VdbeOpList const *pIn = aOp;

void sqlite3VdbeTrace(Vdbe *p, FILE *trace){
  p->trace = trace;
}
#endif

/*
** Resize the Vdbe.aOp array so that it contains at least N
** elements.



**
** If an out-of-memory error occurs while resizing the array,
** Vdbe.aOp and Vdbe.nOpAlloc remain unchanged (this is so that
** any opcodes already allocated can be correctly deallocated
** along with the rest of the Vdbe).
*/
static void resizeOpArray(Vdbe *p, int N){


  VdbeOp *pNew;

  int oldSize = p->nOpAlloc;
  pNew = sqlite3DbRealloc(p->db, p->aOp, N*sizeof(Op));
  if( pNew ){
    p->nOpAlloc = N;
    p->aOp = pNew;
    if( N>oldSize ){
      memset(&p->aOp[oldSize], 0, (N-oldSize)*sizeof(Op));

    }
  }
}

/*
** Add a new instruction to the list of instructions current in the
** VDBE.  Return the address of the new instruction.
................................................................................
int sqlite3VdbeAddOp(Vdbe *p, int op, int p1, int p2){
  int i;
  VdbeOp *pOp;

  i = p->nOp;
  assert( p->magic==VDBE_MAGIC_INIT );
  if( p->nOpAlloc<=i ){
    resizeOpArray(p, p->nOpAlloc*2 + 100);
    if( p->db->mallocFailed ){
      return 0;
    }
  }
  p->nOp++;
  pOp = &p->aOp[i];
  pOp->opcode = op;
................................................................................
/*
** Add a whole list of operations to the operation stack.  Return the
** address of the first operation added.
*/
int sqlite3VdbeAddOpList(Vdbe *p, int nOp, VdbeOpList const *aOp){
  int addr;
  assert( p->magic==VDBE_MAGIC_INIT );
  if( p->nOp + nOp > p->nOpAlloc ){
    resizeOpArray(p, p->nOp*2 + nOp);
  }
  if( p->db->mallocFailed ){
    return 0;
  }
  addr = p->nOp;
  if( nOp>0 ){
    int i;
    VdbeOpList const *pIn = aOp;

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing built-in functions.
#
# $Id: func.test,v 1.69 2007/09/12 17:01:45 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Create a table to work with.
#
do_test func-0.0 {
................................................................................
  }
} {0}
do_test func-12.7 {
  execsql {
    DROP TABLE t4;
  }
} {}


# Test that the auxdata API for scalar functions works. This test uses
# a special user-defined function only available in test builds,
# test_auxdata(). Function test_auxdata() takes any number of arguments.
do_test func-13.1 {
  execsql {
    SELECT test_auxdata('hello world');

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing built-in functions.
#
# $Id: func.test,v 1.70 2007/10/20 15:41:58 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Create a table to work with.
#
do_test func-0.0 {
................................................................................
  }
} {0}
do_test func-12.7 {
  execsql {
    DROP TABLE t4;
  }
} {}


# Test that the auxdata API for scalar functions works. This test uses
# a special user-defined function only available in test builds,
# test_auxdata(). Function test_auxdata() takes any number of arguments.
do_test func-13.1 {
  execsql {
    SELECT test_auxdata('hello world');

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements some common TCL routines used for regression
# testing the SQLite library
#
# $Id: tester.tcl,v 1.92 2007/10/15 19:34:32 drh Exp $


set tcl_precision 15
set sqlite_pending_byte 0x0010000

# 
# Check the command-line arguments for a default soft-heap-limit.
................................................................................
  if {$sqlite_open_file_count} {
    puts "$sqlite_open_file_count files were left open"
    incr nErr
  }
  if {[sqlite3_memory_used]>0} {
    puts "Unfreed memory: [sqlite3_memory_used] bytes"
    incr nErr
    ifcapable memdebug {
      puts "Writing unfreed memory log to \"./memleak.txt\""
      sqlite3_memdebug_dump ./memleak.txt
    }
  } else {
    puts "All memory allocations freed - no leaks"
    ifcapable memdebug {
      sqlite3_memdebug_dump ./memusage.txt

#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements some common TCL routines used for regression
# testing the SQLite library
#
# $Id: tester.tcl,v 1.93 2007/10/20 15:41:58 drh Exp $


set tcl_precision 15
set sqlite_pending_byte 0x0010000

# 
# Check the command-line arguments for a default soft-heap-limit.
................................................................................
  if {$sqlite_open_file_count} {
    puts "$sqlite_open_file_count files were left open"
    incr nErr
  }
  if {[sqlite3_memory_used]>0} {
    puts "Unfreed memory: [sqlite3_memory_used] bytes"
    incr nErr
    ifcapable memdebug||(mem3&&debug) {
      puts "Writing unfreed memory log to \"./memleak.txt\""
      sqlite3_memdebug_dump ./memleak.txt
    }
  } else {
    puts "All memory allocations freed - no leaks"
    ifcapable memdebug {
      sqlite3_memdebug_dump ./memusage.txt