** 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.112 2004/05/07 23:50:57 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
    }
    nextPage = get4byte(aPayload);
    if( offset<ovflSize ){
      int a = amt;
      if( a + offset > ovflSize ){
        a = ovflSize - offset;
      }
      memcpy(pBuf, &aPayload[offset], a);
      offset = 0;
      amt -= a;
      pBuf += a;
    }else{
      offset -= ovflSize;
    }
    sqlite3pager_unref(aPayload);
................................................................................
          if( d2<dist ) closest = i;
        }
      }else{
        closest = 0;
      }
      put4byte(&aData[4], n-1);
      *pPgno = get4byte(&aData[8+closest*4]);

      memcpy(&aData[8+closest*4], &aData[4+closest*n], 4);


      rc = getPage(pBt, *pPgno, ppPage);
      releasePage(pTrunk);
      if( rc==SQLITE_OK ){
        sqlite3pager_dont_rollback(*ppPage);
        rc = sqlite3pager_write((*ppPage)->aData);
      }
    }
  }else{
    /* There are no pages on the freelist, so create a new page at the
    ** end of the file */
    *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1;
................................................................................
  int *pnSize                    /* Write cell size here */
){
  int nPayload;
  const void *pSrc;
  int nSrc, n, rc;
  int spaceLeft;
  MemPage *pOvfl = 0;

  unsigned char *pPrior;
  unsigned char *pPayload;
  Btree *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;

  /* Fill in the header. */
................................................................................
  pPayload = &pCell[nHeader];
  pPrior = &pPayload[pBt->maxLocal];

  while( nPayload>0 ){
    if( spaceLeft==0 ){
      rc =  allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl);
      if( rc ){

        clearCell(pPage, pCell);
        return rc;
      }
      put4byte(pPrior, pgnoOvfl);


      pPrior = pOvfl->aData;
      put4byte(pPrior, 0);
      pPayload = &pOvfl->aData[4];
      spaceLeft = pBt->pageSize - 4;
    }
    n = nPayload;
    if( n>spaceLeft ) n = spaceLeft;
    if( n>nSrc ) n = nSrc;
    memcpy(pPayload, pSrc, n);
    nPayload -= n;
    pPayload += n;

    nSrc -= n;
    spaceLeft -= n;
    if( nSrc==0 ){
      nSrc = nData;
      pSrc = pData;
    }
    if( pOvfl && (spaceLeft==0 || nPayload==0) ){
      releasePage(pOvfl);
    }
  }

  return SQLITE_OK;
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.

** 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.113 2004/05/08 02:03:23 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
................................................................................
    }
    nextPage = get4byte(aPayload);
    if( offset<ovflSize ){
      int a = amt;
      if( a + offset > ovflSize ){
        a = ovflSize - offset;
      }
      memcpy(pBuf, &aPayload[offset+4], a);
      offset = 0;
      amt -= a;
      pBuf += a;
    }else{
      offset -= ovflSize;
    }
    sqlite3pager_unref(aPayload);
................................................................................
          if( d2<dist ) closest = i;
        }
      }else{
        closest = 0;
      }
      put4byte(&aData[4], n-1);
      *pPgno = get4byte(&aData[8+closest*4]);
      if( closest<k-1 ){
        memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
      }
      put4byte(&pTrunk->aData[4], k-1);
      rc = getPage(pBt, *pPgno, ppPage);
      releasePage(pTrunk);
      if( rc==SQLITE_OK ){
        sqlite3pager_dont_rollback((*ppPage)->aData);
        rc = sqlite3pager_write((*ppPage)->aData);
      }
    }
  }else{
    /* There are no pages on the freelist, so create a new page at the
    ** end of the file */
    *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1;
................................................................................
  int *pnSize                    /* Write cell size here */
){
  int nPayload;
  const void *pSrc;
  int nSrc, n, rc;
  int spaceLeft;
  MemPage *pOvfl = 0;
  MemPage *pToRelease = 0;
  unsigned char *pPrior;
  unsigned char *pPayload;
  Btree *pBt = pPage->pBt;
  Pgno pgnoOvfl = 0;
  int nHeader;

  /* Fill in the header. */
................................................................................
  pPayload = &pCell[nHeader];
  pPrior = &pPayload[pBt->maxLocal];

  while( nPayload>0 ){
    if( spaceLeft==0 ){
      rc =  allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl);
      if( rc ){
        releasePage(pToRelease);
        clearCell(pPage, pCell);
        return rc;
      }
      put4byte(pPrior, pgnoOvfl);
      releasePage(pToRelease);
      pToRelease = pOvfl;
      pPrior = pOvfl->aData;
      put4byte(pPrior, 0);
      pPayload = &pOvfl->aData[4];
      spaceLeft = pBt->pageSize - 4;
    }
    n = nPayload;
    if( n>spaceLeft ) n = spaceLeft;
    if( n>nSrc ) n = nSrc;
    memcpy(pPayload, pSrc, n);
    nPayload -= n;
    pPayload += n;
    pSrc += n;
    nSrc -= n;
    spaceLeft -= n;
    if( nSrc==0 ){
      nSrc = nData;
      pSrc = pData;
    }


  }

  releasePage(pToRelease);
  return SQLITE_OK;
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.28 2004/05/07 23:50:57 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  for(i=0; i<sizeof(aResult)/sizeof(aResult[0]); i++){
    sprintf(&zBuf[j]," %d", aResult[i]);
    j += strlen(&zBuf[j]);
  }
  Tcl_AppendResult(interp, &zBuf[1], 0);
  return SQLITE_OK;
}




















/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest3_Init(Tcl_Interp *interp){
  static struct {
     char *zName;
................................................................................
     { "btree_key",                (Tcl_CmdProc*)btree_key                },
     { "btree_data",               (Tcl_CmdProc*)btree_data               },
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_dump",        (Tcl_CmdProc*)btree_cursor_dump        },
     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },

  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  return TCL_OK;
}

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the btree.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test3.c,v 1.29 2004/05/08 02:03:23 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>
................................................................................
  for(i=0; i<sizeof(aResult)/sizeof(aResult[0]); i++){
    sprintf(&zBuf[j]," %d", aResult[i]);
    j += strlen(&zBuf[j]);
  }
  Tcl_AppendResult(interp, &zBuf[1], 0);
  return SQLITE_OK;
}

/*
** The command is provided for the purpose of setting breakpoints.
** in regression test scripts.
**
** By setting a GDB breakpoint on this procedure and executing the
** btree_breakpoint command in a test script, we can stop GDB at
** the point in the script where the btree_breakpoint command is
** inserted.  This is useful for debugging.
*/
static int btree_breakpoint(
  void *NotUsed,
  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  int argc,              /* Number of arguments */
  const char **argv      /* Text of each argument */
){
  return TCL_OK;
}


/*
** Register commands with the TCL interpreter.
*/
int Sqlitetest3_Init(Tcl_Interp *interp){
  static struct {
     char *zName;
................................................................................
     { "btree_key",                (Tcl_CmdProc*)btree_key                },
     { "btree_data",               (Tcl_CmdProc*)btree_data               },
     { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
     { "btree_first",              (Tcl_CmdProc*)btree_first              },
     { "btree_last",               (Tcl_CmdProc*)btree_last               },
     { "btree_cursor_dump",        (Tcl_CmdProc*)btree_cursor_dump        },
     { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
     { "btree_breakpoint",         (Tcl_CmdProc*)btree_breakpoint         },
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  }
  Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
     TCL_LINK_INT);
  return TCL_OK;
}

#    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 script is btree database backend
#
# $Id: btree.test,v 1.17 2004/05/07 23:50:58 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
do_test btree-8.4 {
  btree_delete $::c1
} {}
do_test btree-8.4.1 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]
do_test btree-8.5 {
  set data "*** This is an even longer key"
  while {[string length $data]<2000} {append data $data}

  set ::data $data
  btree_insert $::c1 2030 $data
} {}
do_test btree-8.6 {
  btree_move_to 2030
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.7 {
  btree_data $::c1
} $::data
do_test btree-8.8 {
  btree_commit $::b1
................................................................................
} $::data
do_test btree-8.10 {
  btree_begin_transaction $::b1
  btree_delete $::c1
} {}
do_test btree-8.11 {
  lindex [btree_get_meta $::b1] 0
} {}

# Now check out keys on overflow pages.
#
do_test btree-8.12 {
  set ::keyprefix "This is a long prefix to a key "
  while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix}
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  lindex [btree_get_meta $::b1] 0
} {4}
do_test btree-8.12.1 {
  set ::c1 [btree_cursor $::b1 2 1]
  btree_insert $::c1 ${::keyprefix}1 1

  btree_data $::c1
} {1}
do_test btree-8.13 {
  btree_key $::c1
} ${keyprefix}1
do_test btree-8.14 {
  btree_insert $::c1 ${::keyprefix}2 2
  btree_insert $::c1 ${::keyprefix}3 3

  btree_key $::c1
} ${keyprefix}3
do_test btree-8.15 {
  btree_move_to $::c1 ${::keyprefix}2
  btree_data $::c1
} {2}
do_test btree-8.16 {
................................................................................
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-8.23 {
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_get_meta $::b1] 0
} {4}
do_test btree-8.24 {
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_pager_ref_dump $::b1

# Check page splitting logic
#
................................................................................
  do_test btree-9.3.$i.2 [subst {
    btree_move_to $::c1 [format %03d $i]
    string range \[btree_data $::c1\] 0 10
  }] "*** [format %03d $i] ***"
}
do_test btree-9.4.1 {
  lindex [btree_pager_stats $::b1] 1
} {3}

# Check the page joining logic.
#
#btree_page_dump $::b1 2
#btree_pager_ref_dump $::b1
do_test btree-9.4.2 {
  btree_move_to $::c1 005
................................................................................

# Create a tree of depth two.  That is, there is a single divider entry
# on the root pages and two leaf pages.  Then delete the divider entry
# see what happens.
#
do_test btree-10.1 {
  btree_begin_transaction $::b1
  btree_drop_table $::b1 2
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-10.2 {
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-10.3 {

#    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 script is btree database backend
#
# $Id: btree.test,v 1.18 2004/05/08 02:03:23 drh Exp $


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

# Basic functionality.  Open and close a database.
#
................................................................................
do_test btree-8.4 {
  btree_delete $::c1
} {}
do_test btree-8.4.1 {
  lindex [btree_get_meta $::b1] 0
} [expr {int(([string length $::data]-238+1019)/1020)}]
do_test btree-8.5 {
  set data "*** This is an even longer key "
  while {[string length $data]<2000} {append data $data}
  append data END
  set ::data $data
  btree_insert $::c1 2030 $data
} {}
do_test btree-8.6 {
  btree_move_to $::c1 2030
  string length [btree_data $::c1]
} [string length $::data]
do_test btree-8.7 {
  btree_data $::c1
} $::data
do_test btree-8.8 {
  btree_commit $::b1
................................................................................
} $::data
do_test btree-8.10 {
  btree_begin_transaction $::b1
  btree_delete $::c1
} {}
do_test btree-8.11 {
  lindex [btree_get_meta $::b1] 0
} {4}

# Now check out keys on overflow pages.
#
do_test btree-8.12 {
  set ::keyprefix "This is a long prefix to a key "
  while {[string length $::keyprefix]<256} {append ::keyprefix $::keyprefix}
  btree_close_cursor $::c1
  btree_clear_table $::b1 2
  lindex [btree_get_meta $::b1] 0
} {4}
do_test btree-8.12.1 {
  set ::c1 [btree_cursor $::b1 2 1]
  btree_insert $::c1 ${::keyprefix}1 1
  btree_first $::c1
  btree_data $::c1
} {1}
do_test btree-8.13 {
  btree_key $::c1
} ${keyprefix}1
do_test btree-8.14 {
  btree_insert $::c1 ${::keyprefix}2 2
  btree_insert $::c1 ${::keyprefix}3 3
  btree_last $::c1
  btree_key $::c1
} ${keyprefix}3
do_test btree-8.15 {
  btree_move_to $::c1 ${::keyprefix}2
  btree_data $::c1
} {2}
do_test btree-8.16 {
................................................................................
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-8.23 {
  btree_close_cursor $::c1
  btree_drop_table $::b1 2
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_get_meta $::b1] 0
} {5}
do_test btree-8.24 {
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_pager_ref_dump $::b1

# Check page splitting logic
#
................................................................................
  do_test btree-9.3.$i.2 [subst {
    btree_move_to $::c1 [format %03d $i]
    string range \[btree_data $::c1\] 0 10
  }] "*** [format %03d $i] ***"
}
do_test btree-9.4.1 {
  lindex [btree_pager_stats $::b1] 1
} {2}

# Check the page joining logic.
#
#btree_page_dump $::b1 2
#btree_pager_ref_dump $::b1
do_test btree-9.4.2 {
  btree_move_to $::c1 005
................................................................................

# Create a tree of depth two.  That is, there is a single divider entry
# on the root pages and two leaf pages.  Then delete the divider entry
# see what happens.
#
do_test btree-10.1 {
  btree_begin_transaction $::b1
  btree_clear_table $::b1 2
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-10.2 {
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
do_test btree-10.3 {