SQLite4
Check-in [c954958697]
Not logged in

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Further progress on b-treee backend.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:c9549586972550291b00b4cb2dfc7cd7bb27ed07
User & Date: dan 2013-09-24 20:39:25
Context
2013-09-25
18:46
Further btree updates. check-in: 6548088566 user: dan tags: trunk
2013-09-24
20:39
Further progress on b-treee backend. check-in: c954958697 user: dan tags: trunk
2013-09-19
19:19
Further btree updates. check-in: 0b68007d89 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to main.mk.

    83     83            random.o resolve.o rowset.o rtree.o select.o status.o \
    84     84            tokenize.o trigger.o \
    85     85            update.o util.o varint.o \
    86     86            vdbeapi.o vdbeaux.o vdbecodec.o vdbecursor.o \
    87     87            vdbemem.o vdbetrace.o \
    88     88            walker.o where.o utf.o
    89     89   
    90         -LIBOBJ += bt_unix.o bt_pager.o bt_main.o 
           90  +LIBOBJ += bt_unix.o bt_pager.o bt_main.o bt_varint.o kvbt.o
    91     91   
    92     92   # All of the source code files.
    93     93   #
    94     94   SRC = \
    95     95     $(TOP)/src/alter.c \
    96     96     $(TOP)/src/analyze.c \
    97     97     $(TOP)/src/attach.c \

Changes to src/bt.h.

   100    100   **   SQLITE4_OK:
   101    101   **   SQLITE4_NOTFOUND:
   102    102   **   SQLITE4_INEXACT:
   103    103   **   other:
   104    104   */
   105    105   int sqlite4BtCsrSeek(bt_cursor *pCsr, const void *pK, int nK, int eSeek);
   106    106   
          107  +/*
          108  +** TODO: Are these actually even required for SQLite4 KV stores?
          109  +*/
   107    110   int sqlite4BtCsrFirst(bt_cursor *pCsr);
   108    111   int sqlite4BtCsrLast(bt_cursor *pCsr);
   109    112   
   110    113   int sqlite4BtCsrNext(bt_cursor *pCsr);
   111    114   int sqlite4BtCsrPrev(bt_cursor *pCsr);
   112    115   
   113    116   int sqlite4BtCsrValid(bt_cursor *pCsr);

Changes to src/btInt.h.

    11     11   *************************************************************************
    12     12   **
    13     13   */
    14     14   
    15     15   #include "bt.h"
    16     16   
    17     17   typedef sqlite4_int64 i64;
           18  +typedef sqlite4_uint64 u64;
    18     19   typedef unsigned int u32;
           20  +typedef unsigned short u16;
    19     21   typedef unsigned char u8;
    20     22   
    21     23   /*************************************************************************
    22     24   ** Interface to bt_pager.c functionality.
    23     25   */
    24     26   typedef struct BtPage BtPage;
    25     27   typedef struct BtPager BtPager;
................................................................................
    45     47   int sqlite4BtPagerRevert(BtPager*, int iLevel);
    46     48   int sqlite4BtPagerRollback(BtPager*, int iLevel);
    47     49   int sqlite4BtPagerTransactionLevel(BtPager*);
    48     50   
    49     51   /*
    50     52   ** Query for the database page size. Requires an open read transaction.
    51     53   */
    52         -int sqlite4BtPagerPagesize(BtPager*, int *pnByte);
           54  +int sqlite4BtPagerPagesize(BtPager*);
    53     55   
    54     56   /* 
    55     57   ** Query for the root page number. Requires an open read transaction.
    56     58   */
    57         -int sqlite4BtPagerRootpgno(BtPager*, u32 *piRoot);
           59  +u32 sqlite4BtPagerRootpgno(BtPager*);
    58     60   
    59     61   /*
    60     62   ** Read, write and trim existing database pages.
    61     63   */
    62     64   int sqlite4BtPageGet(BtPager*, u32 pgno, BtPage **ppPage);
    63     65   int sqlite4BtPageWrite(BtPage*);
    64     66   int sqlite4BtPageTrim(BtPage*);
................................................................................
   126    128   /* Find the default VFS */
   127    129   bt_env *sqlite4BtEnvDefault(void);
   128    130   
   129    131   /*
   130    132   ** End of file system interface.
   131    133   *************************************************************************/
   132    134   
          135  +/*************************************************************************
          136  +** Interface to bt_varint.c functionality.
          137  +**
          138  +** All this is just copied from SQLite4 proper. It is a bit ridiculous.
          139  +*/
          140  +int sqlite4BtVarintPut32(u8 *, int);
          141  +int sqlite4BtVarintGet32(u8 *, int *);
          142  +int sqlite4BtVarintPut64(u8 *aData, i64 iVal);
          143  +int sqlite4BtVarintGet64(const u8 *aData, i64 *piVal);
          144  +int sqlite4BtVarintLen32(int);
          145  +int sqlite4BtVarintSize(u8 c);
          146  +/*
          147  +** End of bt_varint.c interface.
          148  +*************************************************************************/
   133    149   
          150  +#ifdef NDEBUG
          151  +# define btErrorBkpt(x) x
          152  +#else
          153  +int btErrorBkpt(int rc);
          154  +#endif
   134    155   

Changes to src/bt_main.c.

     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   **
    13     13   */
    14     14   
    15     15   #include "btInt.h"
           16  +#include <string.h>
           17  +#include <assert.h>
           18  +
           19  +#define BT_MAX_DEPTH 32           /* Maximum possible depth of tree */
           20  +
           21  +/*
           22  +** Values that make up the single byte flags field at the start of
           23  +** b-tree pages. 
           24  +*/
           25  +#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */
    16     26   
    17     27   struct bt_db {
    18     28     sqlite4_env *pEnv;              /* SQLite environment */
    19     29     BtPager *pPager;                /* Underlying page-based database */
    20     30   };
    21     31   
    22     32   struct bt_cursor {
    23     33     bt_db *pDb;                     /* Database that owns this cursor */
    24     34   
    25     35     int nPg;                        /* Number of valid entries in apPage[] */
    26         -  int iCell;                      /* Current cell in apPage[nPg] */
    27         -  BtPage *apPage[32];             /* All pages from root to current leaf */
           36  +  int aiCell[BT_MAX_DEPTH];       /* Current cell of each apPage[] entry */
           37  +  BtPage *apPage[BT_MAX_DEPTH];   /* All pages from root to current leaf */
    28     38   };
           39  +
           40  +#ifndef btErrorBkpt
           41  +int btErrorBkpt(int rc){
           42  +  static int error_cnt = 0;
           43  +  error_cnt++;
           44  +  return rc;
           45  +}
           46  +#endif
           47  +
           48  +/*
           49  +** Interpret the first 4 bytes of the buffer indicated by the first parameter
           50  +** as a 32-bit unsigned big-endian integer.
           51  +*/
           52  +static u32 btGetU32(const u8 *a){
           53  +  return ((u32)a[0] << 24) + ((u32)a[1] << 16) + ((u32)a[2] << 8) + ((u32)a[3]);
           54  +}
           55  +static u16 btGetU16(const u8 *a){
           56  +  return ((u32)a[0] << 8) + (u32)a[1];
           57  +}
           58  +
           59  +static void btPutU16(u8 *a, u16 i){
           60  +  a[0] = (u8)((i>>8) & 0xFF);
           61  +  a[1] = (u8)((i>>0) & 0xFF);
           62  +}
    29     63   
    30     64   /*
    31     65   ** Allocate a new database handle.
    32     66   */
    33     67   int sqlite4BtNew(sqlite4_env *pEnv, int nExtra, bt_db **ppDb){
    34     68     bt_db *db = 0;                  /* New database object */
    35     69     BtPager *pPager = 0;            /* Pager object for this database */
................................................................................
    96    130     rc = sqlite4BtPagerRollback(db->pPager, iLevel);
    97    131     return rc;
    98    132   }
    99    133   
   100    134   int sqlite4BtTransactionLevel(bt_db *db){
   101    135     return sqlite4BtPagerTransactionLevel(db->pPager);
   102    136   }
          137  +
          138  +static void btCsrSetup(bt_db *db, bt_cursor *pCsr){
          139  +  memset(pCsr, 0, sizeof(bt_cursor));
          140  +  pCsr->pDb = db;
          141  +}
   103    142   
   104    143   int sqlite4BtCsrOpen(bt_db *db, int nExtra, bt_cursor **ppCsr){
   105    144     int rc;                         /* Return Code */
   106    145     int nByte;                      /* Total bytes of space to allocate */
   107    146     bt_cursor *pCsr;                /* New cursor object */
   108    147   
   109    148     nByte = sizeof(bt_cursor) + nExtra;
   110         -  pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
          149  +  *ppCsr = pCsr = (bt_cursor*)sqlite4_malloc(db->pEnv, nByte);
   111    150     if( pCsr==0 ){
   112         -    rc = SQLITE4_NOMEM;
          151  +    rc = btErrorBkpt(SQLITE4_NOMEM);
   113    152     }else{
   114         -    memset(pCsr, 0, nByte);
   115         -    pCsr->pDb = db;
          153  +    btCsrSetup(db, pCsr);
   116    154     }
   117    155   
   118    156     return rc;
   119    157   }
   120    158   
   121    159   int sqlite4BtCsrClose(bt_cursor *pCsr){
   122    160     return SQLITE4_OK;
   123    161   }
   124    162   
   125    163   void *sqlite4BtCsrExtra(bt_cursor *pCsr){
   126    164     return (void*)&pCsr[1];
   127    165   }
   128    166   
   129         -int sqlite4BtCsrSeek(bt_cursor *pCsr, const void *pK, int nK, int eSeek){
   130         -  return SQLITE4_OK;
   131         -}
   132         -
   133    167   static void btCsrReset(bt_cursor *pCsr){
   134    168     int i;
   135    169     for(i=0; i<pCsr->nPg; i++){
   136    170       sqlite4BtPageRelease(pCsr->apPage[i]);
   137    171     }
   138    172     pCsr->nPg = 0;
   139         -  pCsr->iCell = 0;
          173  +}
          174  +
          175  +/*
          176  +** Set pCsr->apPage[pCsr->nPg] to a reference to database page pgno.
          177  +*/
          178  +static int btCsrDescend(bt_cursor *pCsr, u32 pgno){
          179  +  int rc;
          180  +  if( pCsr->nPg>=BT_MAX_DEPTH ){
          181  +    rc = btErrorBkpt(SQLITE4_CORRUPT);
          182  +  }else{
          183  +    rc = sqlite4BtPageGet(pCsr->pDb->pPager, pgno, &pCsr->apPage[pCsr->nPg]);
          184  +    if( pCsr->nPg==0 && rc==SQLITE4_OK ){
          185  +    }
          186  +    if( rc==SQLITE4_OK ){
          187  +      pCsr->nPg++;
          188  +    }
          189  +  }
          190  +  return rc;
          191  +}
          192  +
          193  +static int btCellCount(const u8 *aData, int nData){
          194  +  return (int)btGetU16(&aData[nData-2]);
          195  +}
          196  +
          197  +static int btFreeOffset(const u8 *aData, int nData){
          198  +  return (int)btGetU16(&aData[nData-4]);
          199  +}
          200  +
          201  +static u8 btFlags(const u8 *aData, int nData){
          202  +  return aData[0];
          203  +}
          204  +
          205  +static u8 *btCellFind(u8 *aData, int nData, int iCell){
          206  +  int iOff = btGetU16(&aData[nData - 4 - iCell*2 - 2]);
          207  +  return &aData[iOff];
          208  +}
          209  +
          210  +/*
          211  +** Return a pointer to the big-endian u16 field that contains the 
          212  +** pointer to cell iCell.
          213  +*/
          214  +static u8* btCellPtrFind(u8 *aData, int nData, int iCell){
          215  +  return &aData[nData - 4 - iCell*2 - 2];
          216  +}
          217  +
          218  +
          219  +/*
          220  +** This function seeks the cursor as required for either sqlite4BtCsrFirst()
          221  +** (if parameter bLast is false) or sqlite4BtCsrLast() (if bLast is true).
          222  +*/
          223  +static int btCsrEnd(bt_cursor *pCsr, int bLast){
          224  +  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
          225  +  int rc;                         /* Return Code */
          226  +  u32 pgno;                       /* Page number for next page to load */
          227  +
          228  +  /* Reset the cursor */
          229  +  btCsrReset(pCsr);
          230  +
          231  +  /* Figure out the root page number */
          232  +  assert( pCsr->nPg==0 );
          233  +  pgno = sqlite4BtPagerRootpgno(pCsr->pDb->pPager);
          234  +
          235  +  while( rc==SQLITE4_OK ){
          236  +    /* Load page number pgno into the b-tree */
          237  +    rc = btCsrDescend(pCsr, pgno);
          238  +    if( rc==SQLITE4_OK ){
          239  +      int nByte;
          240  +      u8 *pCell;
          241  +      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
          242  +
          243  +      /* If the cursor has descended to a leaf break out of the loop. */
          244  +      pCsr->aiCell[pCsr->nPg-1] = (bLast ? btCellCount(aData, pgsz) : 0);
          245  +      if( (aData[0] & BT_PGFLAGS_INTERNAL)==0 ) break;
          246  +      
          247  +      /* Otherwise, set pgno to the left or rightmost child of the page
          248  +      ** just loaded, depending on whether the cursor is seeking to the
          249  +      ** start or end of the tree.  */
          250  +      if( bLast==0 ){
          251  +        pCell = btCellFind(aData, pgsz, 0);
          252  +        pCell += sqlite4BtVarintGet32(pCell, &nByte);
          253  +        pCell += nByte;
          254  +        sqlite4BtVarintGet32(pCell, (int *)&pgno);
          255  +      }else{
          256  +        pgno = btGetU32(&aData[1]);
          257  +      }
          258  +    }
          259  +  }
          260  +  return rc;
          261  +}
          262  +
          263  +/*
          264  +** This function compares the key passed via parameters pK and nK to the
          265  +** key stored as part of cell iCell on the database page stored in buffer
          266  +** aData (size nData bytes).
          267  +**
          268  +** If the cell key is C, and the user key K, then this function sets:
          269  +**
          270  +**     *piRes = (C - K).
          271  +**
          272  +** In other workds, *piRes is +ve, zero or -ve if C is respectively larger, 
          273  +** equal to or smaller than K.
          274  +*/
          275  +static int btCellKeyCompare(
          276  +  bt_cursor *pCsr,                /* Cursor handle */
          277  +  const u8 *aData, int nData,     /* Page data (nData is the page size) */
          278  +  int iCell,                      /* Cell to compare key from */
          279  +  const u8 *pK, int nK,           /* Key to compare to cell key */
          280  +  int *piRes                      /* OUT: Result of comparison */
          281  +){
          282  +  int rc = SQLITE4_OK;
          283  +  u8 *pCell = btCellFind((u8*)aData, nData, iCell);
          284  +  int nCellKey;                   /* Number of bytes in cell key */
          285  +  int res;
          286  +
          287  +  pCell += sqlite4BtVarintGet32(pCell, &nCellKey);
          288  +  if( nCellKey==0 ){
          289  +    /* Type (c) cell */
          290  +    assert( 0 );
          291  +  }else{
          292  +    int nCmp = ((nCellKey <= nK) ? nCellKey : nK);
          293  +    res = memcmp(pCell, pK, nCmp);
          294  +    if( res==0 ){
          295  +      res = nCellKey - nK;
          296  +    }
          297  +  }
          298  +
          299  +  *piRes = res;
          300  +  return rc;
          301  +}
          302  +
          303  +int sqlite4BtCsrSeek(
          304  +  bt_cursor *pCsr, 
          305  +  const void *pK,                 /* Key to seek for */
          306  +  int nK,                         /* Size of key pK in bytes */
          307  +  int eSeek                       /* Seek mode (a BT_SEEK_XXX constant) */
          308  +){
          309  +  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
          310  +  u32 pgno;                       /* Page number for next page to load */
          311  +  int rc = SQLITE4_OK;            /* Return Code */
          312  +
          313  +  /* Reset the cursor */
          314  +  btCsrReset(pCsr);
          315  +
          316  +  /* Figure out the root page number */
          317  +  assert( pCsr->nPg==0 );
          318  +  pgno = sqlite4BtPagerRootpgno(pCsr->pDb->pPager);
          319  +
          320  +  while( rc==SQLITE4_OK && pgno ){
          321  +    /* Load page number pgno into the b-tree */
          322  +    rc = btCsrDescend(pCsr, pgno);
          323  +    if( rc==SQLITE4_OK ){
          324  +      int nCell;                  /* Number of cells on this page */
          325  +      int iHi;                    /* pK/nK is <= than cell iHi */
          326  +      int iLo;                    /* pK/nK is > than cell (iLo-1) */
          327  +      int res;                    /* Result of comparison */
          328  +      u8 *aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
          329  +
          330  +      iLo = 0;
          331  +      iHi = nCell = btCellCount(aData, pgsz);
          332  +
          333  +      while( iHi>iLo ){
          334  +        int iTst = (iHi+iLo)/2;   /* Cell to compare to pK/nK */
          335  +        rc = btCellKeyCompare(pCsr, aData, pgsz, iTst, pK, nK, &res);
          336  +        if( rc!=SQLITE4_OK || res==0 ){
          337  +          /* Cell iTst is EQUAL to pK/nK */
          338  +          iHi = iLo = iTst;
          339  +        }else if( res<0 ){
          340  +          /* Cell iTst is SMALLER than pK/nK */
          341  +          iLo = iTst+1;
          342  +        }else{
          343  +          /* Cell iTst is LARGER than pK/nK */
          344  +          iHi = iTst;
          345  +        }
          346  +      }
          347  +      assert( rc!=SQLITE4_OK || iHi==iLo );
          348  +      pCsr->aiCell[pCsr->nPg-1] = iHi;
          349  +
          350  +      if( aData[0] & BT_PGFLAGS_INTERNAL ){
          351  +        if( iHi==nCell ){
          352  +          pgno = btGetU32(&aData[1]);
          353  +        }else{
          354  +          u8 *pCell;
          355  +          int nByte;
          356  +          pCell = btCellFind(aData, pgsz, 0);
          357  +          pCell += sqlite4BtVarintGet32(pCell, &nByte);
          358  +          pCell += nByte;
          359  +          sqlite4BtVarintGet32(pCell, (int*)&pgno);
          360  +        }
          361  +      }else{
          362  +        pgno = 0;
          363  +        if( res!=0 ){
          364  +          rc = SQLITE4_INEXACT;
          365  +        }
          366  +      }
          367  +    }
          368  +  }
          369  +
          370  +  return rc;
   140    371   }
   141    372   
   142    373   /*
   143    374   ** Position cursor pCsr to point to the smallest key in the database.
   144    375   */
   145    376   int sqlite4BtCsrFirst(bt_cursor *pCsr){
   146         -  /* Reset the cursor */
   147         -  btCsrReset(pCsr);
   148         -
   149         -  /* Load the root page into pCsr->apPage[0] */
   150         -
   151         -  return SQLITE4_OK;
          377  +  return btCsrEnd(pCsr, 0);
   152    378   }
   153    379   
   154    380   /*
   155    381   ** Position cursor pCsr to point to the largest key in the database.
   156    382   */
   157    383   int sqlite4BtCsrLast(bt_cursor *pCsr){
   158         -  return SQLITE4_OK;
          384  +  return btCsrEnd(pCsr, 1);
   159    385   }
   160    386   
          387  +/*
          388  +** Advance to the next entry in the tree.
          389  +*/
   161    390   int sqlite4BtCsrNext(bt_cursor *pCsr){
          391  +  assert( 0 );
   162    392     return SQLITE4_OK;
   163    393   }
   164    394   
   165    395   int sqlite4BtCsrPrev(bt_cursor *pCsr){
          396  +  assert( 0 );
   166    397     return SQLITE4_OK;
   167    398   }
   168    399   
   169    400   int sqlite4BtCsrValid(bt_cursor *pCsr){
          401  +  assert( 0 );
   170    402     return 0;
   171    403   }
   172    404   
   173    405   int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){
          406  +  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
          407  +  u8 *aData;
          408  +  
          409  +  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
          410  +
   174    411     return SQLITE4_OK;
   175    412   }
   176    413   
   177    414   int sqlite4BtCsrData(
   178    415     bt_cursor *pCsr,                /* Cursor handle */
   179    416     int iOffset,                    /* Offset of requested data */
   180    417     int nByte,                      /* Bytes requested (or -ve for all avail.) */
   181    418     const void **ppV,               /* OUT: Pointer to data buffer */
   182    419     int *pnV                        /* OUT: Size of data buffer in bytes */
   183    420   ){
          421  +  assert( 0 );
   184    422     return SQLITE4_OK;
   185    423   }
   186    424   
          425  +static int btInsertIntoLeaf(
          426  +  bt_cursor *pCsr, 
          427  +  const void *pK, int nK, 
          428  +  const void *pV, int nV
          429  +){
          430  +  int rc = SQLITE4_OK;
          431  +  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
          432  +  u8 *aData;                      /* Page buffer */
          433  +  int nCell;                      /* Number of cells on this page already */
          434  +  int nFree;                      /* Free space on this page in bytes */
          435  +  int nReq;                       /* Space required for type (a) cell */
          436  +  int iCell;                      /* Position to insert new key */
          437  +  int iWrite;                     /* Byte offset at which to write new cell */
          438  +  BtPage *pLeaf;
          439  +
          440  +  nReq = sqlite4BtVarintLen32(nK) + nK + sqlite4BtVarintLen32(nV) + nV + 2;
          441  +
          442  +  iCell = pCsr->aiCell[pCsr->nPg-1];
          443  +  assert( pCsr->nPg>0 );
          444  +  pLeaf = pCsr->apPage[pCsr->nPg-1];
          445  +  aData = (u8*)sqlite4BtPageData(pLeaf);
          446  +
          447  +  nCell = btCellCount(aData, pgsz);
          448  +  assert( iCell<=btCellCount(aData, pgsz) );
          449  +
          450  +  if( nCell==0 ){
          451  +    iWrite = 1;                   /* Right after "flags" byte */
          452  +    nFree = pgsz - 1 - 4;         /* Page is free aside from header & footer */
          453  +  }else{
          454  +    iWrite = btFreeOffset(aData, pgsz);
          455  +    nFree = pgsz - btFreeOffset(aData, pgsz) - (2+nCell) * 2;
          456  +  }
          457  +  if( nFree>=nReq ){
          458  +    rc = sqlite4BtPageWrite(pLeaf);
          459  +    if( rc==SQLITE4_OK ){
          460  +      aData = sqlite4BtPageData(pLeaf);
          461  +
          462  +      /* Increase cell count */
          463  +      btPutU16(&aData[pgsz-2], nCell+1);
          464  +
          465  +      /* Update the cell pointer array */
          466  +      if( iCell!=nCell ){
          467  +        u8 *aFrom = &aData[pgsz-4-iCell*2];
          468  +        memmove(aFrom, &aFrom[-2], (nCell-iCell) * 2);
          469  +      }
          470  +      btPutU16(btCellPtrFind(aData, pgsz, iCell), iWrite);
          471  +      
          472  +      /* Write the cell itself */
          473  +      iWrite += sqlite4BtVarintPut32(&aData[iWrite], nK);
          474  +      iWrite += nK;
          475  +      iWrite += sqlite4BtVarintPut32(&aData[iWrite], nV);
          476  +      iWrite += nV;
          477  +      btPutU16(&aData[pgsz-4], iWrite);
          478  +    }
          479  +  }else{
          480  +    assert( 0 );
          481  +  }
          482  +
          483  +  return rc;
          484  +}
          485  +
          486  +/*
          487  +** Insert a new key/value pair or replace an existing one.
          488  +*/
   187    489   int sqlite4BtReplace(bt_db *db, const void *pK, int nK, const void *pV, int nV){
   188         -  return SQLITE4_OK;
          490  +  int rc = SQLITE4_OK;
          491  +  bt_cursor csr;
          492  +
          493  +  btCsrSetup(db, &csr);
          494  +  rc = sqlite4BtCsrSeek(&csr, pK, nK, BT_SEEK_GE);
          495  +  if( rc==SQLITE4_OK ){
          496  +    /* The cursor currently points to an entry with key pK/nK. This call
          497  +    ** should therefore replace that entry. So delete it and then re-seek
          498  +    ** the cursor.  */
          499  +    rc = sqlite4BtDelete(&csr);
          500  +    if( rc==SQLITE4_OK ){
          501  +      rc = sqlite4BtCsrSeek(&csr, pK, nK, BT_SEEK_GE);
          502  +    }
          503  +  }
          504  +  if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT);
          505  +
          506  +  if( rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT ){
          507  +    /* Insert the new KV pair into the current leaf. */
          508  +    rc = btInsertIntoLeaf(&csr, pK, nK, pV, nV);
          509  +  }
          510  +
          511  +  return rc;
   189    512   }
   190    513   
   191    514   int sqlite4BtDelete(bt_cursor *pCsr){
          515  +  assert( 0 );
   192    516     return SQLITE4_OK;
   193    517   }
   194    518   
   195    519   int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){
   196    520     return sqlite4BtPagerSetCookie(db->pPager, iVal);
   197    521   }
   198    522   
   199    523   int sqlite4BtGetCookie(bt_db *db, unsigned int *piVal){
   200    524     return sqlite4BtPagerGetCookie(db->pPager, piVal);
   201    525   }
          526  +
          527  +#ifndef NDEBUG
          528  +static void printPage(u8 *aData, int nData){
          529  +  printf("nCell=%d\n", (int)btCellCount(aData, nData));
          530  +  printf("iFree=%d\n", (int)btFreeOffset(aData, nData));
          531  +  printf("flags=%d\n", (int)btFlags(aData, nData));
          532  +}
          533  +#endif
   202    534   

Changes to src/bt_pager.c.

   100    100     if( p->hash.nEntry>=p->hash.nHash/2 ){
   101    101       int i;
   102    102       int nNew = (p->hash.nHash ? p->hash.nHash*2 : 256);
   103    103       BtPage **aNew;
   104    104       BtPage **aOld = p->hash.aHash;
   105    105   
   106    106       aNew = (BtPage **)sqlite4_malloc(p->pEnv, nNew*sizeof(BtPage*));
   107         -    if( aNew==0 ) return SQLITE4_NOMEM;
          107  +    if( aNew==0 ) return btErrorBkpt(SQLITE4_NOMEM);
   108    108       memset(aNew, 0, nNew*sizeof(BtPage*));
   109    109       for(i=0; i<p->hash.nHash; i++){
   110    110         while( aOld[i] ){
   111    111           BtPage *pShift = aOld[i];
   112    112           aOld[i] = pShift->pNextHash;
   113    113           h = hashkey(nNew, pPg->pgno);
   114    114           pShift->pNextHash = aNew[h];
................................................................................
   142    142   }
   143    143   
   144    144   /*
   145    145   ** Search the hash table for a page with page number pgno. If found, return
   146    146   ** a pointer to the BtPage object. Otherwise, return NULL.
   147    147   */
   148    148   static BtPage *btHashSearch(BtPager *p, u32 pgno){
   149         -  int h = hashkey(p->hash.nHash, pgno);
   150         -  BtPage *pRet;
   151         -  for(pRet=p->hash.aHash[h]; pRet && pRet->pgno!=pgno; pRet=pRet->pNextHash);
          149  +  BtPage *pRet = 0;
          150  +  if( p->hash.nHash ){
          151  +    int h = hashkey(p->hash.nHash, pgno);
          152  +    for(pRet=p->hash.aHash[h]; pRet && pRet->pgno!=pgno; pRet=pRet->pNextHash);
          153  +  }
   152    154     return pRet;
   153    155   }
   154    156   
   155    157   /*
   156    158   ** Remove all entries from the hash-table. And free any allocations made
   157    159   ** by earlier calls to btHashAdd().
   158    160   */
................................................................................
   169    171   */
   170    172   int sqlite4BtPagerNew(sqlite4_env *pEnv, int nExtra, BtPager **pp){
   171    173     BtPager *p;
   172    174     int nByte;
   173    175   
   174    176     nByte = sizeof(BtPager) + nExtra;
   175    177     p = (BtPager*)sqlite4_malloc(pEnv, nByte);
   176         -  if( !p ) return SQLITE4_NOMEM; 
          178  +  if( !p ) return btErrorBkpt(SQLITE4_NOMEM); 
   177    179     memset(p, 0, nByte);
   178    180   
   179    181     p->pEnv = pEnv;
   180    182     p->pVfs = sqlite4BtEnvDefault();
   181    183     *pp = p;
   182    184     return SQLITE4_OK;
   183    185   }
................................................................................
   243    245     if( rc==SQLITE4_OK && nByte>0 ){
   244    246       rc = p->pVfs->xRead(p->pFd, 0, &p->dbhdr, sizeof(p->dbhdr));
   245    247     }else{
   246    248       memset(&p->dbhdr, 0, sizeof(p->dbhdr));
   247    249       p->dbhdr.pgsz = BT_DEFAULT_PGSZ;
   248    250     }
   249    251   
          252  +  if( rc==SQLITE4_OK ){
          253  +    /* If the read transaction was successfully opened, the transaction 
          254  +    ** level is now 1.  */
          255  +    p->iTransactionLevel = 1;
          256  +  }
   250    257     return rc;
   251    258   }
   252    259   
   253    260   /*
   254    261   ** Commit the current write transaction to disk.
   255    262   */
   256    263   static int btCommitTransaction(BtPager *p){
................................................................................
   295    302       memset(pRet, 0, sizeof(BtPage));
   296    303       pRet->aData = aData;
   297    304       pRet->pPager = p;
   298    305       rc = SQLITE4_OK;
   299    306     }else{
   300    307       sqlite4_free(p->pEnv, pRet);
   301    308       sqlite4_free(p->pEnv, aData);
   302         -    rc = SQLITE4_NOMEM;
          309  +    rc = btErrorBkpt(SQLITE4_NOMEM);
   303    310       pRet = 0;
   304    311     }
   305    312   
   306    313     *ppPg = pRet;
   307    314     return rc;
   308    315   }
   309    316   
................................................................................
   379    386       }
   380    387       p->iTransactionLevel = iLevel;
   381    388     }
   382    389     return rc;
   383    390   }
   384    391   
   385    392   int sqlite4BtPagerRollback(BtPager *p, int iLevel){
   386         -  int rc;
          393  +  int rc = SQLITE4_OK;
   387    394   
   388    395     assert( p->pFd );
   389    396     if( p->iTransactionLevel>=iLevel ){
   390    397       assert( iLevel<=1 );          /* TODO: Fix this! */
   391         -    rc = btRollbackTransaction(p);
          398  +    if( p->iTransactionLevel>=2 ){
          399  +      rc = btRollbackTransaction(p);
          400  +    }
   392    401       p->iTransactionLevel = iLevel;
   393    402     }
   394    403   
   395    404     return rc;
   396    405   }
   397    406   
   398    407   int sqlite4BtPagerRevert(BtPager *p, int iLevel){
................................................................................
   413    422   int sqlite4BtPagerTransactionLevel(BtPager *p){
   414    423     return p->iTransactionLevel;
   415    424   }
   416    425   
   417    426   /*
   418    427   ** Query for the database page size. Requires an open read transaction.
   419    428   */
   420         -int sqlite4BtPagerPagesize(BtPager *p, int *pnByte){
          429  +int sqlite4BtPagerPagesize(BtPager *p){
   421    430     assert( p->iTransactionLevel>=1 && p->pFd );
   422         -  *pnByte = (int)p->dbhdr.pgsz;
   423         -  return SQLITE4_OK;
          431  +  return (int)p->dbhdr.pgsz;
   424    432   }
          433  +
   425    434   
   426    435   /* 
   427    436   ** Query for the root page number. Requires an open read transaction.
   428    437   */
   429         -int sqlite4BtPagerRootpgno(BtPager *p, u32 *piRoot){
          438  +u32 sqlite4BtPagerRootpgno(BtPager *p){
   430    439     assert( p->iTransactionLevel>=1 && p->pFd );
   431         -  *piRoot = 2;
   432         -  return SQLITE4_OK;
          440  +  return 2;
   433    441   }
   434    442   
   435    443   /*
   436    444   ** Read, write and trim existing database pages.
   437    445   */
   438    446   int sqlite4BtPageGet(BtPager *p, u32 pgno, BtPage **ppPg){
   439    447     int rc = SQLITE4_OK;            /* Return code */

Changes to src/bt_unix.c.

    39     39   #include "btInt.h"
    40     40   
    41     41   /* There is no fdatasync() call on Android */
    42     42   #ifdef __ANDROID__
    43     43   # define fdatasync(x) fsync(x)
    44     44   #endif
    45     45   
    46         -/*
    47         -** The malloc/free functions used for allocations made within this file.
    48         -** There are relatively few such allocations.
    49         -*/
    50         -static void *btMalloc(size_t n){ 
    51         -  return malloc(n); 
    52         -}
    53         -static void btFree(void *p){ 
    54         -  free(p); 
    55         -}
    56         -static void *btRealloc(void *p, size_t n){ 
    57         -  return realloc(p, n); 
    58         -}
    59         -static void *btReallocOrFree(void *p, size_t n){
    60         -  void *pNew = realloc(p, n); 
    61         -  if( pNew==0 ) free(p);
    62         -  return pNew;
    63         -}
    64         -
    65         -#ifdef NDEBUG
    66         -# define btErrorBkpt(x) x
    67         -#else
    68         -static int btErrorBkpt(int rc){
    69         -  return rc;
    70         -}
    71         -#endif
    72         -
    73     46   /*
    74     47   ** An open file is an instance of the following object
    75     48   */
    76     49   typedef struct PosixFile PosixFile;
    77     50   struct PosixFile {
    78     51     sqlite4_env *pSqlEnv;
    79     52     bt_env *pEnv;                   /* The run-time environment */
................................................................................
    83     56     int nShm;                       /* Number of entries in array apShm[] */
    84     57     void **apShm;                   /* Array of 32K shared memory segments */
    85     58   };
    86     59   
    87     60   static char *posixShmFile(PosixFile *p){
    88     61     char *zShm;
    89     62     int nName = strlen(p->zName);
    90         -  zShm = (char*)btMalloc(nName+4+1);
           63  +  zShm = (char*)sqlite4_malloc(p->pSqlEnv, nName+4+1);
    91     64     if( zShm ){
    92     65       memcpy(zShm, p->zName, nName);
    93     66       memcpy(&zShm[nName], "-shm", 5);
    94     67     }
    95     68     return zShm;
    96     69   }
    97     70   
................................................................................
   356    329       struct stat sStat;
   357    330   
   358    331       /* If the shared-memory file has not been opened, open it now. */
   359    332       if( p->shmfd<=0 ){
   360    333         char *zShm = posixShmFile(p);
   361    334         if( !zShm ) return btErrorBkpt(SQLITE4_NOMEM);
   362    335         p->shmfd = open(zShm, O_RDWR|O_CREAT, 0644);
   363         -      btFree(zShm);
          336  +      sqlite4_free(p->pSqlEnv, zShm);
   364    337         if( p->shmfd<0 ){ 
   365    338           return btErrorBkpt(SQLITE4_IOERR);
   366    339         }
   367    340       }
   368    341   
   369    342       /* If the shared-memory file is not large enough to contain the 
   370    343       ** requested chunk, cause it to grow.  */
................................................................................
   373    346       }
   374    347       if( sStat.st_size<nReq ){
   375    348         if( ftruncate(p->shmfd, nReq) ){
   376    349           return btErrorBkpt(SQLITE4_IOERR);
   377    350         }
   378    351       }
   379    352   
   380         -    apNew = (void**)btRealloc(p->apShm, sizeof(void *) * nNew);
          353  +    apNew = (void**)sqlite4_realloc(p->pSqlEnv, p->apShm, sizeof(void*) * nNew);
   381    354       if( !apNew ) return btErrorBkpt(SQLITE4_NOMEM);
   382    355       for(i=p->nShm; i<nNew; i++){
   383    356         apNew[i] = 0;
   384    357       }
   385    358       p->apShm = apNew;
   386    359       p->nShm = nNew;
   387    360     }
................................................................................
   411    384         }
   412    385       }
   413    386       close(p->shmfd);
   414    387       p->shmfd = 0;
   415    388       if( bDelete ){
   416    389         char *zShm = posixShmFile(p);
   417    390         if( zShm ) unlink(zShm);
   418         -      btFree(zShm);
          391  +      sqlite4_free(p->pSqlEnv, zShm);
   419    392       }
   420    393     }
   421    394     return SQLITE4_OK;
   422    395   }
   423    396   
   424    397   
   425    398   static int btPosixOsClose(bt_file *pFile){
   426    399      PosixFile *p = (PosixFile *)pFile;
   427    400      btPosixOsShmUnmap(pFile, 0);
   428    401      close(p->fd);
   429         -   btFree(p->apShm);
   430         -   btFree(p);
          402  +   sqlite4_free(p->pSqlEnv, p->apShm);
          403  +   sqlite4_free(p->pSqlEnv, p);
   431    404      return SQLITE4_OK;
   432    405   }
   433    406   
   434    407   bt_env *sqlite4BtEnvDefault(void){
   435    408     static bt_env posix_env = {
   436    409       0,                            /* pVfsCtx */
   437    410       btPosixOsFullpath,            /* xFullpath */

Changes to src/env.c.

    20     20   */
    21     21   static KVFactory memFactory = {
    22     22      0,
    23     23      "temp",
    24     24      sqlite4KVStoreOpenMem,
    25     25      1
    26     26   };
    27         -KVFactory sqlite4BuiltinFactory = {
           27  +static KVFactory btFactory = {
    28     28      &memFactory,
           29  +   "bt",
           30  +   sqlite4OpenBtree,
           31  +   1
           32  +};
           33  +KVFactory sqlite4BuiltinFactory = {
           34  +   &btFactory,
    29     35      "main",
    30     36      sqlite4KVStoreOpenLsm,
    31     37      1
    32     38   };
    33     39   
    34     40   /*
    35     41   ** The following singleton contains the global configuration for

Changes to src/kv.c.

    91     91     const char *zStorageName;
    92     92     KVFactory *pMkr;
    93     93     sqlite4_kvfactory xFactory;
    94     94   
    95     95     if( (flags & SQLITE4_KVOPEN_TEMPORARY)!=0 || zUri==0 || zUri[0]==0 ){
    96     96       zStorageName = "temp";
    97     97     }else{
    98         -    zStorageName = sqlite4_uri_parameter(zName, "kv");
           98  +    zStorageName = sqlite4_uri_parameter(zUri, "kv");
    99     99       if( zStorageName==0 ){
   100    100         if( memcmp(":memory:", zUri, 8)==0 ){
   101    101           zStorageName = "temp";
   102    102         }else{
   103    103           zStorageName = "main";
   104    104         }
   105    105       }

Changes to src/kv.h.

   154    154   /* Typedefs of datatypes */
   155    155   typedef struct sqlite4_kvstore KVStore;
   156    156   typedef struct sqlite4_kv_methods KVStoreMethods;
   157    157   typedef struct sqlite4_kvcursor KVCursor;
   158    158   typedef unsigned char KVByteArray;
   159    159   typedef sqlite4_kvsize KVSize;
   160    160   
          161  +int sqlite4OpenBtree(sqlite4_env*, KVStore**, const char *, unsigned);
   161    162   int sqlite4KVStoreOpenMem(sqlite4_env*, KVStore**, const char *, unsigned);
   162    163   int sqlite4KVStoreOpenLsm(sqlite4_env*, KVStore**, const char *, unsigned);
   163    164   int sqlite4KVStoreOpen(
   164    165     sqlite4*,
   165    166     const char *zLabel, 
   166    167     const char *zUri,
   167    168     KVStore**,

Changes to src/kvbt.c.

   158    158   */
   159    159   static int btSeek(
   160    160     KVCursor *pKVCursor, 
   161    161     const KVByteArray *aKey,
   162    162     KVSize nKey,
   163    163     int dir
   164    164   ){
   165         -  int rc;
   166    165     KVBtCsr *pCsr = (KVBtCsr *)pKVCursor;
   167    166   
   168    167     assert( dir==0 || dir==1 || dir==-1 || dir==-2 );
   169    168     assert( BT_SEEK_EQ==0 && BT_SEEK_GE==1 && BT_SEEK_LE==-1 );
   170    169     assert( BT_SEEK_LEFAST==-2 );
   171    170   
   172    171     return sqlite4BtCsrSeek(pCsr->pCsr, (void *)aKey, nKey, dir);
................................................................................
   178    177   ** Though the entry is "deleted", it still continues to exist as a
   179    178   ** phantom.  Subsequent xNext or xPrev calls will work, as will
   180    179   ** calls to xKey and xData, thought the result from xKey and xData
   181    180   ** are undefined.
   182    181   */
   183    182   static int btDelete(KVCursor *pKVCursor){
   184    183     KVBtCsr *pBtcsr = (KVBtCsr *)pKVCursor;
   185         -  return sqlite4BtDelete(pBtcsr);
          184  +  return sqlite4BtDelete(pBtcsr->pCsr);
   186    185   }
   187    186   
   188    187   /*
   189    188   ** Return the key of the node the cursor is pointing to.
   190    189   */
   191    190   static int btKey(
   192    191     KVCursor *pKVCursor,         /* The cursor whose key is desired */
................................................................................
   272    271       btGetMeta,                    /* xGetMeta */
   273    272       btPutMeta,                    /* xPutMeta */
   274    273       btGetMethod                   /* xGetMethod */
   275    274     };
   276    275   
   277    276     KVBt *pNew = 0;
   278    277     bt_db *pDb = 0;
          278  +  int rc;
   279    279   
   280         -  rc = sqlite4BtNew(ENV, sizeof(KVBt), &pDb);
          280  +  rc = sqlite4BtNew(pEnv, sizeof(KVBt), &pDb);
   281    281     if( rc==SQLITE4_OK ){
   282    282       pNew = (KVBt*)sqlite4BtExtra(pDb);
   283    283       pNew->base.pStoreVfunc = &bt_methods;
   284    284       pNew->base.pEnv = pEnv;
   285    285       pNew->pDb = pDb;
   286    286       rc = sqlite4BtOpen(pDb, zFilename);
   287    287     }

Added test/simple3.test.

            1  +# 2013 September 24
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# The tests in this file were used while developing the SQLite 4 code. 
           12  +#
           13  +set testdir [file dirname $argv0]
           14  +source $testdir/tester.tcl
           15  +set testprefix simple3
           16  +
           17  +db close
           18  +forcedelete test.db
           19  +
           20  +do_test 1.0 {
           21  +  sqlite4 db file:test.db?kv=bt
           22  +  db close
           23  +} {}
           24  +
           25  +do_test 1.1 { sqlite4 db file:test.db?kv=bt } {}
           26  +execsql { PRAGMA trace = 1 }
           27  +do_execsql_test 1.2 { CREATE TABLE t1(a, b) } 
           28  +
           29  +finish_test

Changes to www/bt.wiki.

   493    493   
   494    494   <p><b>Page Header</b>
   495    495   
   496    496   <p>Page headers are similar to those in SQLite3: 
   497    497   
   498    498   <ul>
   499    499     <li> 1 byte - flags.
   500         -  <li> 2 bytes - Number of cells on this page.
   501         -  <li> 2 bytes - Offset of first byte after last cell.
   502    500     <li> Internal nodes only: 4 bytes - Page number of rightmost child node.
   503    501   </ul>
   504    502   
   505    503   <p><b>Page Footer</b>
   506    504   
          505  +<p> Starting from the end of the page, the fields in the page footer are:
          506  +
          507  +<ul>
          508  +  <li> 2 bytes - Number of cells on this page.
          509  +  <li> 2 bytes - Offset of first byte after last cell.
          510  +  <li> 2 bytes for each cell - the offset to the start of the cell.
          511  +</ul>
   507    512   
   508    513   <h4 id=cell_formats>2.2.3.8. Cell Formats</h4>
   509    514   
   510    515   <p><b>B-Tree Nodes</b>
   511    516   
   512    517   <p>Cell format:
   513    518