/*** 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.c,v 1.7 2007/11/29 18:36:49 drh Exp $*//*** 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 */