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.631 2009/06/17 11:13:28 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"

            }
            put4byte(&pPrevTrunk->aData[0], iNewTrunk);
          }
        }
        pTrunk = 0;
        TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
#endif
      }else if( k>0 ){
        /* Extract a leaf from the trunk */
        int closest;
        Pgno iPage;
        unsigned char *aData = pTrunk->aData;
        rc = sqlite3PagerWrite(pTrunk->pDbPage);
        if( rc ){
          goto end_allocate_page;

  u8 *aSpace1;                 /* Space for copies of dividers cells */
  Pgno pgno;                   /* Temp var to store a page number in */

  pBt = pParent->pBt;
  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( sqlite3PagerIswriteable(pParent->pDbPage) );

#if 0
  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));
#endif

  /* At this point pParent may have at most one overflow cell. And if
  ** this overflow cell is present, it must be the cell with 
  ** index iParentIdx. This scenario comes about when this function
  ** is called (indirectly) from sqlite3BtreeDelete(). */
  assert( pParent->nOverflow==0 || pParent->nOverflow==1 );
  assert( pParent->nOverflow==0 || pParent->aOvfl[0].idx==iParentIdx );

  /* Either we found one or more cells (cntnew[0])>0) or pPage is
  ** a virtual root page.  A virtual root page is when the real root
  ** page is page 1 and we are the only child of that page.
  */
  assert( cntNew[0]>0 || (pParent->pgno==1 && pParent->nCell==0) );

  TRACE(("BALANCE: old: %d %d %d  ",
    apOld[0]->pgno, 
    nOld>=2 ? apOld[1]->pgno : 0,
    nOld>=3 ? apOld[2]->pgno : 0
  ));

  /*
  ** Allocate k new pages.  Reuse old pages where possible.
  */
  if( apOld[0]->pgno<=1 ){
    rc = SQLITE_CORRUPT;
    goto balance_cleanup;
  }

      MemPage *pT;
      t = apNew[i]->pgno;
      pT = apNew[i];
      apNew[i] = apNew[minI];
      apNew[minI] = pT;
    }
  }
  TRACE(("new: %d(%d) %d(%d) %d(%d) %d(%d) %d(%d)\n",



    apNew[0]->pgno, szNew[0],
    nNew>=2 ? apNew[1]->pgno : 0, nNew>=2 ? szNew[1] : 0,
    nNew>=3 ? apNew[2]->pgno : 0, nNew>=3 ? szNew[2] : 0,
    nNew>=4 ? apNew[3]->pgno : 0, nNew>=4 ? szNew[3] : 0,
    nNew>=5 ? apNew[4]->pgno : 0, nNew>=5 ? szNew[4] : 0));

  assert( sqlite3PagerIswriteable(pParent->pDbPage) );

    ** cause an assert() statement to fail.  */
    ptrmapCheckPages(apNew, nNew);
    ptrmapCheckPages(&pParent, 1);
#endif
  }

  assert( pParent->isInit );
  TRACE(("BALANCE: finished: old=%d new=%d cells=%d\n",
          nOld, nNew, nCell));
 
  /*
  ** Cleanup before returning.
  */
balance_cleanup:
  sqlite3ScratchFree(apCell);
  for(i=0; i<nOld; i++){

# 2009 June 17
#
# 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: tkt3918.test,v 1.1 2009/06/17 11:13:28 danielk1977 Exp $

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

do_test tkt3918.1 {
  execsql {
    PRAGMA page_size = 1024;
    PRAGMA auto_vacuum = incremental;
    CREATE TABLE t1(i, x);
  }
} {}
do_test tkt3918.2 {
  execsql {
    INSERT INTO t1 VALUES(1, randstr(1000,1000));
    INSERT INTO t1 VALUES(2, zeroblob(248*1020 + 100));
    INSERT INTO t1 VALUES(3, zeroblob(2*1020 + 100));
  }
} {}

# This set of statements sets up the free list so that the
# first free-list trunk page contains only a single leaf.
# The leaf page is also the last page in the database. The
# second free-list trunk page contains, amongst other things,
# page number 4.
do_test tkt3918.3 {
  execsql {
    DELETE FROM t1 WHERE i = 2;
    DELETE FROM t1 WHERE i = 1;
    DELETE FROM t1 WHERE i = 3;
  }
} {}

# Incrementally vacuum the database to reduce its size by a single
# page. This will remove the single leaf from the first page in
# the linked list of free-list trunk pages.
do_test tkt3918.4 {
  execsql { PRAGMA incremental_vacuum = 1 }
} {}

# Create another table. This operation will attempt to extract 
# page 4 from the database free-list. Bug 3918 caused sqlite to
# incorrectly report corruption here.
do_test tkt3918.5 {
  execsql { CREATE TABLE t2(a, b) }
} {}

finish_test