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.217 2004/11/13 13:19:56 danielk1977 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.

  u8 *apDiv[NB];               /* Divider cells in pParent */
  int cntNew[NB+2];            /* Index in aCell[] of cell after i-th page */
  int szNew[NB+2];             /* Combined size of cells place on i-th page */
  u8 **apCell;                 /* All cells begin balanced */
  int *szCell;                 /* Local size of all cells in apCell[] */
  u8 *aCopy[NB];               /* Space for holding data of apCopy[] */
  u8 *aSpace;                  /* Space to hold copies of dividers cells */
  BtCursor *pCur;

  /* 
  ** Find the parent page.
  */
  assert( pPage->isInit );
  assert( sqlite3pager_iswriteable(pPage->aData) );
  pBt = pPage->pBt;

      if( rc ) goto balance_cleanup;
      apNew[i] = pNew;
    }
    nNew++;
    zeroPage(pNew, pageFlags);
  }











  /*
  ** Put the new pages in accending order.  This helps to
  ** keep entries in the disk file in order so that a scan
  ** of the table is a linear scan through the file.  That
  ** in turn helps the operating system to deliver pages
  ** from the disk more rapidly.
  **

    nOld>=3 ? pgnoOld[2] : 0,
    pgnoNew[0], szNew[0],
    nNew>=2 ? pgnoNew[1] : 0, nNew>=2 ? szNew[1] : 0,
    nNew>=3 ? pgnoNew[2] : 0, nNew>=3 ? szNew[2] : 0,
    nNew>=4 ? pgnoNew[3] : 0, nNew>=4 ? szNew[3] : 0,
    nNew>=5 ? pgnoNew[4] : 0, nNew>=5 ? szNew[4] : 0));

#if 0
  /* The following block shows how cells migrated during the balance op. */
  if( sqlite3_btree_trace ){
    char zBuf[200];
    char *zCsr = zBuf;
    int a, b, c=0, d=0;
    *zCsr = '\0';
    for(a=0; a<nOld; a++){
      int nOldCells = apCopy[a]->nCell+apCopy[a]->nOverflow;
      for(b=0; b<(nOldCells+((a!=nOld-1&&!leafData)?1:0)); b++){
        int x = 0;
        Pgno iNewPage;
        Pgno iOldPage;
        int iNewIndex;
        int iOldIndex;

        if( b<nOldCells ){
          iOldPage = pgnoOld[a];
          iOldIndex = b;
        }else{
          iOldPage = pParent->pgno;
          iOldIndex = idxDiv[a];
        }

        while( cntNew[x]<=c ) x++;
        if( x>0 && c==cntNew[x-1] && !leafData ){
          iNewPage = pParent->pgno;
          iNewIndex = nxDiv + a;
        }else{
          assert( x<nNew );
          iNewPage = pgnoNew[x];
          iNewIndex = c-(x>0?cntNew[x-1]:0)-(leafData?0:1);
        }

        if( (&zBuf[sizeof(zBuf)])-zCsr > 100 && 
            (1 || iOldPage!=iNewPage || iOldIndex!=iNewIndex) ){
          zCsr += sprintf(zCsr, " %d.%d->%d.%d", iOldPage, iOldIndex,
              iNewPage, iNewIndex);
        }
        c++;
        if( (d==0 && strlen(zBuf)>35) || strlen(zBuf)>60 ){
          TRACE(("%s%s\n", d==0?"BALANCE: Cell migration:":"", zBuf));
          zCsr = zBuf;
          d = 1;
        }
      }
    }
    assert( c==nCell );
    if( zCsr!=zBuf ){
      TRACE(("%s%s\n", d==0?"BALANCE: Cell migration":"", zBuf));
    }
  }
#endif

  /* If there are other cursors that refer to one of the pages involved
  ** in the balancing, then adjust these cursors so that they still
  ** point to the same cells.
  */
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    int nCellCnt = 0;
    int iCell = -1;
    Pgno pgno = pCur->pPage->pgno;

    /* If the cursor is not valid, do not do anything with it. */
    if( !pCur->isValid ) continue;

    for(i=0; iCell<0 && i<nOld; i++){
      if( pgno==apCopy[i]->pgno ){
        iCell = nCellCnt + pCur->idx;
        break;
      }
      nCellCnt += (apCopy[i]->nCell + apCopy[i]->nOverflow) + (leafData?0:1);
    }

    if( pgno==pParent->pgno ){
      assert( !leafData );
      assert( iCell==-1 );
      if( pCur->idx>=nxDiv && pCur->idx<(nxDiv+nOld-1) ){
        for(i=0; i<=(pCur->idx-nxDiv); i++){
          iCell += (apCopy[i]->nCell + apCopy[i]->nOverflow + 1);
        }
      }
      if( pCur->idx>=(nxDiv+nOld) ){
        TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur, pgno, pCur->idx, pgno, pCur->idx+(nNew-nOld)));
        pCur->idx += (nNew-nOld);
        pCur->info.nSize = 0;
      }
    }

    if( iCell>=0 ){
      int idxNew;
      Pgno pgnoNew;
      int x = 0;

      while( cntNew[x]<=iCell ) x++;
      if( x>0 && !leafData && cntNew[x-1]==iCell ){
        /* The cell that pCur points to is a divider cell in pParent. */
        pgnoNew = pParent->pgno;
        idxNew = nxDiv + x-1;
      }else{
        /* The cell that pCur points to is on page apNew[x]. */
        idxNew = iCell-(x>0?cntNew[x-1]:0)-((leafData||x==0)?0:1);
        pgnoNew = apNew[x]->pgno;
      }

      TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
          pCur, pgno, pCur->idx, pgnoNew, idxNew));

      pCur->idx = idxNew;
      releasePage(pCur->pPage);
      rc = getPage(pBt, pgnoNew, &pCur->pPage);
      assert( rc==SQLITE_OK );
      pCur->info.nSize = 0;
    }
  }

  /* Free any old pages that were not reused as new pages.
  */
  for(i=nNew; i<nOld; i++){
    rc = freePage(apOld[i]);
    if( rc ) goto balance_cleanup;
    releasePage(apOld[i]);
    apOld[i] = 0;
  }

  /*
  ** Evenly distribute the data in apCell[] across the new pages.
  ** Insert divider cells into pParent as necessary.
  */
  j = 0;
  for(i=0; i<nNew; i++){

  Pgno pgnoChild;     /* Page number of the new child page */
  Btree *pBt;         /* The BTree */
  int usableSize;     /* Total usable size of a page */
  u8 *data;           /* Content of the parent page */
  u8 *cdata;          /* Content of the child page */
  int hdr;            /* Offset to page header in parent */
  int brk;            /* Offset to content of first cell in parent */
  BtCursor *pCur;

  assert( pPage->pParent==0 );
  assert( pPage->nOverflow>0 );
  pBt = pPage->pBt;
  rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno, 0);
  if( rc ) return rc;
  assert( sqlite3pager_iswriteable(pChild->aData) );

  if( pChild->nOverflow ){
    pChild->nFree = 0;
  }
  assert( pChild->nCell==pPage->nCell );
  zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
  put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
  TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));

  /* If there were cursors pointing at this page, point them at the new
  ** page instead. Decrement the reference count for the old page and
  ** increment it for the new one.
  */
  for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
    if( pCur->pPage==pPage ){
      TRACE(("BALANCE: Cursor %p migrates from %d,%d to %d,%d\n", 
          pCur, pPage->pgno, pCur->idx, pChild->pgno, pCur->idx));
      releasePage(pCur->pPage);
      rc = getPage(pBt, pChild->pgno,  &pCur->pPage);
      assert( rc==SQLITE_OK );
    }
  }

  rc = balance_nonroot(pChild);
  releasePage(pChild);
  return rc;
}

/*
** Decide if the page pPage needs to be balanced.  If balancing is

*/
static int checkReadLocks(Btree *pBt, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;
  for(p=pBt->pCursor; p; p=p->pNext){
    if( p->pgnoRoot!=pgnoRoot || p==pExclude ) continue;
    if( p->wrFlag==0 ) return SQLITE_LOCKED;
    if( p->pPage->pgno!=p->pgnoRoot ){
/*      moveToRoot(p); */
    }
  }
  return SQLITE_OK;
}

/*
** Insert a new record into the BTree.  The key is given by (pKey,nKey)

  int rc;
  int loc;
  int szNew;
  MemPage *pPage;
  Btree *pBt = pCur->pBt;
  unsigned char *oldCell;
  unsigned char *newCell = 0;
  BtCursor *pCur2;

  if( pCur->status ){
    return pCur->status;  /* A rollback destroyed this cursor */
  }
  if( pBt->inTrans!=TRANS_WRITE ){
    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;

    assert( pPage->leaf );
    pCur->idx++;
    pCur->info.nSize = 0;
  }else{
    assert( pPage->leaf );
  }
  rc = insertCell(pPage, pCur->idx, newCell, szNew, 0);
  pCur->isValid = 1;

  /* If there are other cursors pointing at this page with a BtCursor.idx
  ** field greater than or equal to 'i', then the cell they refer to
  ** has been modified or moved within the page. Fix the cursor.
  */
  for(pCur2=pPage->pBt->pCursor; pCur2; pCur2 = pCur2->pNext){
    if( pCur2->pPage==pPage ){
      if( pCur2->idx>=pCur->idx && pCur!=pCur2 && loc!=0 ){
	/* The cell pointed to by pCur2 was shifted one to the right on it's
	** page by this Insert(). 
        */
        TRACE(("INSERT: Cursor %p migrates from %d,%d to %d,%d\n", 
            pCur2, pPage->pgno, pCur2->idx, pPage->pgno, pCur2->idx+1));
        pCur2->idx++;
      }
      pCur2->info.nSize = 0;
    }
  }

  if( rc!=SQLITE_OK ) goto end_insert;
  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  if( rc==SQLITE_OK ){
  /*  moveToRoot(pCur); */
  }
end_insert:
  sqliteFree(newCell);
  return rc;
}

/*

    szNext = cellSizePtr(leafCur.pPage, pNext);
    assert( MX_CELL_SIZE(pBt)>=szNext+4 );
    tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
    if( tempCell==0 ) return SQLITE_NOMEM;
    rc = insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);
    if( rc!=SQLITE_OK ) return rc;
    put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
    pCur->isValid = 0;
    rc = balance(pPage);
    sqliteFree(tempCell);
    if( rc ) return rc;
    dropCell(leafCur.pPage, leafCur.idx, szNext);
    rc = balance(leafCur.pPage);
    releaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
    dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
    pCur->isValid = 0;
    rc = balance(pPage);
  }
  moveToRoot(pCur);
  return rc;
}

/*

# 2004 Jun 4	
#
# 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 implements regression tests for SQLite library.  The
# focus of this script is btree database backend.
#
# $Id: btree8.test,v 1.1 2004/11/13 13:19:56 danielk1977 Exp $

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

# Use the SQL interface to create a couple of btree tables, one using
# the flags for an SQL table, the other an SQL index.
# 
do_test btree8-1.0 {
  execsql {
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b);
    CREATE INDEX i1 ON t1(b);
  }
} {}
set tnum [execsql {SELECT rootpage FROM sqlite_master where type = 'table'}]
set inum [execsql {SELECT rootpage FROM sqlite_master where type = 'index'}]
db close

# Open the database at the btree level and begin a transaction
do_test btree8-1.1 {
  set ::bt [btree_open test.db 100 0]
  btree_begin_transaction $::bt
  expr 0
} {0}

# For each element in the list $keys, insert an entry into the SQL table
# with the corresponding key value. Check that the cursor used to insert
# the key is left pointing to it after the insert. Then save this cursor
# in the list $csr_list.
#
set keys [list 3178 4886 719 1690 443 4113 1618 310 1320 2028]
set csr_list [list]
set testnum 2
foreach key $keys {
  do_test btree-8-1.$testnum {
    set csr [btree_cursor $::bt $::tnum 1]
    btree_insert $csr $key [string repeat a 10]
    lappend csr_list $csr
    btree_key $csr
  } $key
  incr testnum 
}
btree_commit $::bt

# set btree_trace 1

# Now write more entries to the table (and overwriting the ones that exist).
# After each write, check that the cursors created above still point to the
# same entries.
btree_begin_transaction $::bt
set ::write_csr [btree_cursor $::bt $::tnum 1]
for {set i $testnum} {$i < 5000 && $nErr==0 } {incr i} {
  set datalen [expr int(rand()*20.0)]

  do_test btree8-1.$i.1 {
    btree_insert $::write_csr $i [string repeat x $datalen]
  } {}

  set testnum 1
  foreach csr $csr_list key $keys {
    incr testnum
    do_test btree8-1.$i.$testnum {
      btree_key $::csr
    } $key
  }
}
btree_close_cursor $::write_csr
btree_commit $::bt
if {$::nErr>0} { puts $::csr_list }
foreach csr $csr_list {
  btree_close_cursor $csr
}
set csr_list [list]

# Transform the number $num into a string of length $len by repeating the
# string representation of the number as many times as necessary. Repeats
# are seperated by a '.' character. Eg:
#
# [num_to_string 456 10] -> "456.456.45"
#
proc num_to_string {num len} {
  return [string range [string repeat "$num." $len] 0 [expr $len-1]]
}

foreach key $keys {
  lappend skeys [num_to_string $key 20]
}

# For each element in the list $skeys, insert an entry into the SQL index
# with the corresponding key value. Check that the cursor used to insert
# the key is left pointing to it after the insert. Then save this cursor
# in the list $csr_list.
#
btree_begin_transaction $::bt
set testnum 0
foreach key $skeys {
  incr testnum 
  do_test btree-8-2.$testnum {
    set csr [btree_cursor $::bt $::inum 1]
    btree_insert $csr $key ""
    lappend csr_list $csr
    btree_key $csr
  } $key
}
btree_commit $::bt

# set btree_trace 1

# Now write more entries to the index (and overwrite the ones that exist).
# After each write, check that the cursors created above still point to the
# same entries.
btree_begin_transaction $::bt
set ::write_csr [btree_cursor $::bt $::inum 1]
for {set i $testnum} {$i < 5000 && $nErr==0 } {incr i} {
  set skey [num_to_string $i 20]

  do_test btree8-2.$i.1 {
    btree_insert $::write_csr $skey ""
  } {}

  set testnum 1
  foreach csr $csr_list key $skeys {
    incr testnum
    do_test btree8-2.$i.$testnum {
      btree_key $::csr
    } $key
  }
}
btree_close_cursor $::write_csr
btree_commit $::bt
if {$::nErr>0} { puts $::csr_list }
foreach csr $csr_list {
  btree_close_cursor $csr
}
set csr_list [list]

finish_test

# 2001 September 15
#
# 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 runs all tests.
#
# $Id: quick.test,v 1.33 2004/11/13 13:19:56 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl
rename finish_test really_finish_test
proc finish_test {} {}
set ISQUICK 1

  crash.test
  malloc.test
  memleak.test
  misuse.test
  quick.test
  utf16.test
  autovacuum_crash.test
  btree8.test
}

if {[sqlite3 -has-codec]} {
  # lappend EXCLUDE \
  #  conflict.test
}