SQLite

/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $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.