SQLite4
Check-in [547b950db0]
Not logged in

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

Overview
Comment:Trim overflow pages when the corresponding record is deleted from the database.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 547b950db0f5078a3a9158ac65e8119461557cbe
User & Date: dan 2013-10-18 08:28:02
Context
2013-10-18
17:07
Add new file bt_lock.c. Currently contains stubs only. check-in: a4c634a7d6 user: dan tags: trunk
08:28
Trim overflow pages when the corresponding record is deleted from the database. check-in: 547b950db0 user: dan tags: trunk
2013-10-14
14:03
Use key-prefixes instead of full keys on interior nodes. check-in: 449433ea21 user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/bt_main.c.

856
857
858
859
860
861
862




































































































863
864
865
866
867
868
869
....
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
....
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
....
2195
2196
2197
2198
2199
2200
2201


2202

2203
2204
2205
2206
2207
2208
2209

  /* Load in overflow data */
  aOut = &pCsr->ovfl.pBuf[nLocal];
  rc = btOverflowArrayRead(pCsr->pDb, pCell, aOut, nOvfl1 + nOvfl2);

  return rc;
}





































































































int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u8 *aData;
  u8 *pCell;
  int iCell = pCsr->aiCell[pCsr->nPg-1];
  int nK;
................................................................................
    const int pgsz, BtPage *pLeft, BtPage *pRight, KeyValue *pKV
){
  int nMax;
  int nMaxPrefix = pgsz/4;

  u8 *aLeft; int nLeft;
  u8 *aRight; int nRight;
  u8 *aData;
  int i;

  aLeft = btKeyPrefix(pgsz, pLeft, 1, &nLeft);
  aRight = btKeyPrefix(pgsz, pRight, 0, &nRight);

  nMax = MIN(nLeft, nMaxPrefix);
  for(i=0; i<nMax && aLeft[i]==aRight[i]; i++);
................................................................................

  return rc;
}

static int btDeleteFromPage(bt_cursor *pCsr, int nDel){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  int rc = SQLITE4_OK;            /* Return code */
  BtPage *pLeaf;                  /* Leaf page */

  pLeaf = pCsr->apPage[pCsr->nPg-1];
  rc = sqlite4BtPageWrite(pLeaf);
  if( rc==SQLITE4_OK ){
    int i;                        /* Used to iterate through cells to delete */
    u8 *aData;                    /* Page buffer */
    int nCell;                    /* Number of cells initially on this page */
    int iDel;                     /* Index of cell to delete */
    int nFreed = 0;               /* Total bytes of space freed */

    iDel = pCsr->aiCell[pCsr->nPg-1];
    aData = (u8*)sqlite4BtPageData(pLeaf);
    nCell = btCellCount(aData, pgsz);

    for(i=iDel; i<(iDel+nDel); i++){
      int nByte;
      btCellFindSize(aData, pgsz, i, &nByte);
      nFreed += nByte + 2;
    }
................................................................................

  btCheckPageRefs(db);
  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  int rc;


  rc =  btDeleteFromPage(pCsr, 1);

  if( rc==SQLITE4_OK ){
    rc = btBalanceIfUnderfull(pCsr);
  }
  return rc;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







<







 







|

|
|








|







 







>
>
|
>







856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
....
1788
1789
1790
1791
1792
1793
1794

1795
1796
1797
1798
1799
1800
1801
....
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
....
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311

  /* Load in overflow data */
  aOut = &pCsr->ovfl.pBuf[nLocal];
  rc = btOverflowArrayRead(pCsr->pDb, pCell, aOut, nOvfl1 + nOvfl2);

  return rc;
}

/*
** Helper function for btOverflowDelete(). 
**
** TODO: This uses recursion. Which is almost certainly not a problem 
** here, but makes some people nervous, so should probably be changed.
*/
static int btOverflowTrimtree(
  const int pgsz, 
  BtPager *pPager, 
  u32 pgno, 
  int nDepth
){
  int rc = SQLITE4_OK;

  assert( nDepth<=8 );
  if( nDepth==0 ){
    sqlite4BtPageTrimPgno(pPager, pgno);
  }else{
    const int nPgPtr = pgsz / 4;
    BtPage *pPg;
    u8 *aData;
    int i;

    rc = sqlite4BtPageGet(pPager, pgno, &pPg);
    if( rc!=SQLITE4_OK ) return rc;
    aData = sqlite4BtPageData(pPg);

    for(i=0; rc==SQLITE4_OK && i<nPgPtr; i++){
      u32 child = btGetU32(&aData[i*4]);
      if( child==0 ) break;
      rc = btOverflowTrimtree(pgsz, pPager, child, nDepth-1);
    }

    sqlite4BtPageRelease(pPg);
  }
  
  return rc;
}

/*
** Cursor pCsr currently points to a leaf page cell. If the leaf page
** cell contains an overflow array, all overflow pages are trimmed here.
**
** SQLITE4_OK is returned if no error occurs, or an SQLite4 error code
** otherwise.
*/
static int btOverflowDelete(bt_cursor *pCsr){
  BtPager *pPager = pCsr->pDb->pPager;
  const int pgsz = sqlite4BtPagerPagesize(pPager);
  u8 *aData;
  u8 *pCell;
  u8 *pOvfl = 0;
  int iCell = pCsr->aiCell[pCsr->nPg-1];
  int n;
  int rc = SQLITE4_OK;
  int e = 0;
  
  aData = (u8*)sqlite4BtPageData(pCsr->apPage[pCsr->nPg-1]);
  assert( btCellCount(aData, pgsz)>iCell );
  pCell = btCellFind(aData, pgsz, iCell);
  pCell += sqlite4BtVarintGet32(pCell, &n);

  if( n==0 ){
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pCell += n;
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pCell += sqlite4BtVarintGet32(pCell, &n);
    pOvfl = pCell;
  }else{
    pCell += n;
    pCell += sqlite4BtVarintGet32(pCell, &n);
    if( n==0 ){
      pCell += sqlite4BtVarintGet32(pCell, &n);
      pCell += n;
      pCell += sqlite4BtVarintGet32(pCell, &n);
      pOvfl = pCell;
    }
  }

  if( pOvfl ){
    int i;
    int nDirect = (int)(pOvfl[0] & 0x0F);
    int nDepth = (int)(pOvfl[0]>>4);

    /* Trim the "direct" pages. */
    for(i=0; rc==SQLITE4_OK && i<(nDirect + (nDepth==0)); i++){
      u32 pgno = btGetU32(&pOvfl[1 + i*4]);
      rc = sqlite4BtPageTrimPgno(pPager, pgno);
    }

    /* Now trim the pages that make up the overflow tree. */
    if( nDepth>0 ){
      u32 rootpgno = btGetU32(&pOvfl[1 + nDirect*4]);
      rc = btOverflowTrimtree(pgsz, pPager, rootpgno, nDepth);
    }
  }

  return rc;
}

int sqlite4BtCsrKey(bt_cursor *pCsr, const void **ppK, int *pnK){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  u8 *aData;
  u8 *pCell;
  int iCell = pCsr->aiCell[pCsr->nPg-1];
  int nK;
................................................................................
    const int pgsz, BtPage *pLeft, BtPage *pRight, KeyValue *pKV
){
  int nMax;
  int nMaxPrefix = pgsz/4;

  u8 *aLeft; int nLeft;
  u8 *aRight; int nRight;

  int i;

  aLeft = btKeyPrefix(pgsz, pLeft, 1, &nLeft);
  aRight = btKeyPrefix(pgsz, pRight, 0, &nRight);

  nMax = MIN(nLeft, nMaxPrefix);
  for(i=0; i<nMax && aLeft[i]==aRight[i]; i++);
................................................................................

  return rc;
}

static int btDeleteFromPage(bt_cursor *pCsr, int nDel){
  const int pgsz = sqlite4BtPagerPagesize(pCsr->pDb->pPager);
  int rc = SQLITE4_OK;            /* Return code */
  BtPage *pPg;                    /* Page to delete entries from */

  pPg = pCsr->apPage[pCsr->nPg-1];
  rc = sqlite4BtPageWrite(pPg);
  if( rc==SQLITE4_OK ){
    int i;                        /* Used to iterate through cells to delete */
    u8 *aData;                    /* Page buffer */
    int nCell;                    /* Number of cells initially on this page */
    int iDel;                     /* Index of cell to delete */
    int nFreed = 0;               /* Total bytes of space freed */

    iDel = pCsr->aiCell[pCsr->nPg-1];
    aData = (u8*)sqlite4BtPageData(pPg);
    nCell = btCellCount(aData, pgsz);

    for(i=iDel; i<(iDel+nDel); i++){
      int nByte;
      btCellFindSize(aData, pgsz, i, &nByte);
      nFreed += nByte + 2;
    }
................................................................................

  btCheckPageRefs(db);
  return rc;
}

int sqlite4BtDelete(bt_cursor *pCsr){
  int rc;
  rc = btOverflowDelete(pCsr);
  if( rc==SQLITE4_OK ){
    rc =  btDeleteFromPage(pCsr, 1);
  }
  if( rc==SQLITE4_OK ){
    rc = btBalanceIfUnderfull(pCsr);
  }
  return rc;
}

int sqlite4BtSetCookie(bt_db *db, unsigned int iVal){