** 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.
**
*************************************************************************
** $Id: btree.c,v 1.583 2009/04/01 09:41:54 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

................................................................................
  if( cbrk-addr!=pPage->nFree ){
    return SQLITE_CORRUPT_BKPT;
  }
  return SQLITE_OK;
}

/*
** Allocate nByte bytes of space on a page.


**
** Return the index into pPage->aData[] of the first byte of
** the new allocation.  The caller guarantees that there is enough
** space.  This routine will never fail.


**
** If the page contains nBytes of free space but does not contain
** nBytes of contiguous free space, then this routine automatically
** calls defragmentPage() to consolidate all free space before 
** allocating the new chunk.



*/
static int allocateSpace(MemPage *pPage, int nByte){
  int addr, pc, hdr;
  int size;
  int nFrag;



  int top;
  int nCell;
  int cellOffset;
  unsigned char *data;
  
  data = pPage->aData;
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( pPage->pBt );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( nByte>=0 );  /* Minimum cell size is 4 */
  assert( pPage->nFree>=nByte );
  assert( pPage->nOverflow==0 );
  pPage->nFree -= (u16)nByte;

  hdr = pPage->hdrOffset;







  nFrag = data[hdr+7];
  if( nFrag<60 ){


    /* Search the freelist looking for a slot big enough to satisfy the
    ** space request. */
    addr = hdr+1;




    while( (pc = get2byte(&data[addr]))>0 ){
      size = get2byte(&data[pc+2]);
      if( size>=nByte ){
        int x = size - nByte;
        if( size<nByte+4 ){



          memcpy(&data[addr], &data[pc], 2);
          data[hdr+7] = (u8)(nFrag + x);
          return pc;
        }else{


          put2byte(&data[pc+2], x);

          return pc + x;
        }
      }
      addr = pc;
    }
  }

  /* Allocate memory from the gap in between the cell pointer array
  ** and the cell content area.
  */
  top = get2byte(&data[hdr+5]);
  nCell = get2byte(&data[hdr+3]);
  cellOffset = pPage->cellOffset;
  if( nFrag>=60 || cellOffset + 2*nCell > top - nByte ){
    defragmentPage(pPage);
    top = get2byte(&data[hdr+5]);
  }
  top -= nByte;
  assert( cellOffset + 2*nCell <= top );
  put2byte(&data[hdr+5], top);
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  return top;
}

/*
** Return a section of the pPage->aData to the freelist.
** The first byte of the new free block is pPage->aDisk[start]
** and the size of the block is "size" bytes.

** 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.
**
*************************************************************************
** $Id: btree.c,v 1.584 2009/04/01 16:25:33 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

................................................................................
  if( cbrk-addr!=pPage->nFree ){
    return SQLITE_CORRUPT_BKPT;
  }
  return SQLITE_OK;
}

/*
** Allocate nByte bytes of space from within the B-Tree page passed
** as the first argument. Return the index into pPage->aData[] of the 
** first byte of allocated space. 
**

** The caller guarantees that the space between the end of the cell-offset 

** array and the start of the cell-content area is at least nByte bytes
** in size. So this routine can never fail.
**


** If there are already 60 or more bytes of fragments within the page,
** the page is defragmented before returning. If this were not done there
** is a chance that the number of fragmented bytes could eventually 
** overflow the single-byte field of the page-header in which this value
** is stored.
*/
static int allocateSpace(MemPage *pPage, int nByte){



  const int hdr = pPage->hdrOffset;    /* Local cache of pPage->hdrOffset */
  u8 * const data = pPage->aData;      /* Local cache of pPage->aData */
  int nFrag;                           /* Number of fragmented bytes on pPage */
  int top;



  

  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( pPage->pBt );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( nByte>=0 );  /* Minimum cell size is 4 */
  assert( pPage->nFree>=nByte );
  assert( pPage->nOverflow==0 );


  /* Assert that the space between the cell-offset array and the 
  ** cell-content area is greater than nByte bytes.
  */
  assert( nByte <= (
      get2byte(&data[hdr+5])-(hdr+8+(pPage->leaf?0:4)+2*get2byte(&data[hdr+3]))
  ));

  pPage->nFree -= (u16)nByte;
  nFrag = data[hdr+7];
  if( nFrag>=60 ){
    defragmentPage(pPage);
  }else{
    /* Search the freelist looking for a free slot big enough to satisfy 


    ** the request. The allocation is made from the first free slot in 
    ** the list that is large enough to accomadate it.
    */
    int pc, addr;
    for(addr=hdr+1; (pc = get2byte(&data[addr]))>0; addr=pc){
      int size = get2byte(&data[pc+2]);     /* Size of free slot */
      if( size>=nByte ){
        int x = size - nByte;

        if( x<4 ){
	  /* Remove the slot from the free-list. Update the number of
	  ** fragmented bytes within the page. */
          memcpy(&data[addr], &data[pc], 2);
          data[hdr+7] = (u8)(nFrag + x);

        }else{
	  /* The slot remains on the free-list. Reduce its size to account
	  ** for the portion used by the new allocation. */
          put2byte(&data[pc+2], x);
        }
        return pc + x;
      }


    }
  }

  /* Allocate memory from the gap in between the cell pointer array
  ** and the cell content area.
  */
  top = get2byte(&data[hdr+5]) - nByte;








  put2byte(&data[hdr+5], top);

  return top;
}

/*
** Return a section of the pPage->aData to the freelist.
** The first byte of the new free block is pPage->aDisk[start]
** and the size of the block is "size" bytes.