/ Check-in [ef27e7a0]
Login

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

Overview
Comment:Improve the strict enforcement of cell sizes in balancing from check-in [12713f320b2c1def] so that it also works with table-btrees in addition to index-btrees.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:ef27e7a08728aa7447ae19812803ac5c4a9d80c97541014bd292485792005a3e
User & Date: drh 2019-02-01 14:50:43
Context
2019-02-01
14:54
New test cases added to test/fuzzdata8.db. check-in: e5924939 user: drh tags: trunk
14:50
Improve the strict enforcement of cell sizes in balancing from check-in [12713f320b2c1def] so that it also works with table-btrees in addition to index-btrees. check-in: ef27e7a0 user: drh tags: trunk
14:40
Fix an assert() in fts5 that could fail if the database is corrupt. check-in: 55f06aa3 user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to src/btree.c.

6724
6725
6726
6727
6728
6729
6730
6731
6732
6733
6734
6735
6736
6737
6738



6739
6740
6741
6742

6743
6744
6745
6746
6747







6748
6749
6750
6751
6752
6753
6754
....
7654
7655
7656
7657
7658
7659
7660
7661
7662
7663



7664
7665
7666

7667
7668
7669
7670
7671
7672
7673
**             -----------
**            /     |     \
**           /      |      \
**  ---------   ---------   ---------
**  |Child-1|   |Child-2|   |Child-3|
**  ---------   ---------   ---------
**
** The order of cells is in the array is:
**
**       1.  All cells from Child-1 in order
**       2.  The first divider cell from Parent
**       3.  All cells from Child-2 in order
**       4.  The second divider cell from Parent
**       5.  All cells from Child-3 in order
**



** The apEnd[] array holds pointer to the end of page for Child-1, the
** Parent, Child-2, the Parent (again), and Child-3.  The ixNx[] array
** holds the number of cells contained in each of these 5 stages, and
** all stages to the left.  Hence:

**    ixNx[0] = Number of cells in Child-1.
**    ixNx[1] = Number of cells in Child-1 plus 1 for first divider.
**    ixNx[2] = Number of cells in Child-1 and Child-2 + 1 for 1st divider.
**    ixNx[3] = Number of cells in Child-1 and Child-2 + both divider cells
**    ixNx[4] = Total number of cells.







*/
typedef struct CellArray CellArray;
struct CellArray {
  int nCell;              /* Number of cells in apCell[] */
  MemPage *pRef;          /* Reference page */
  u8 **apCell;            /* All cells begin balanced */
  u16 *szCell;            /* Local size of all cells in apCell[] */
................................................................................
  **    szNew[i]: Spaced used on the i-th sibling page.
  **   cntNew[i]: Index in b.apCell[] and b.szCell[] for the first cell to
  **              the right of the i-th sibling page.
  ** usableSpace: Number of bytes of space available on each sibling.
  ** 
  */
  usableSpace = pBt->usableSize - 12 + leafCorrection;
  for(i=0; i<nOld; i++){
    MemPage *p = apOld[i];
    b.apEnd[i*2] = p->aDataEnd;



    b.apEnd[i*2+1] = pParent->aDataEnd;
    b.ixNx[i*2] = cntOld[i];
    b.ixNx[i*2+1] = cntOld[i]+1;

    szNew[i] = usableSpace - p->nFree;
    for(j=0; j<p->nOverflow; j++){
      szNew[i] += 2 + p->xCellSize(p, p->apOvfl[j]);
    }
    cntNew[i] = cntOld[i];
  }
  k = nOld;







|







>
>
>
|
|
|
|
>





>
>
>
>
>
>
>







 







|

|
>
>
>
|
<
|
>







6724
6725
6726
6727
6728
6729
6730
6731
6732
6733
6734
6735
6736
6737
6738
6739
6740
6741
6742
6743
6744
6745
6746
6747
6748
6749
6750
6751
6752
6753
6754
6755
6756
6757
6758
6759
6760
6761
6762
6763
6764
6765
....
7665
7666
7667
7668
7669
7670
7671
7672
7673
7674
7675
7676
7677
7678

7679
7680
7681
7682
7683
7684
7685
7686
7687
**             -----------
**            /     |     \
**           /      |      \
**  ---------   ---------   ---------
**  |Child-1|   |Child-2|   |Child-3|
**  ---------   ---------   ---------
**
** The order of cells is in the array is for an index btree is:
**
**       1.  All cells from Child-1 in order
**       2.  The first divider cell from Parent
**       3.  All cells from Child-2 in order
**       4.  The second divider cell from Parent
**       5.  All cells from Child-3 in order
**
** For a table-btree (with rowids) the items 2 and 4 are empty because
** content exists only in leaves and there are no divider cells.
**
** For an index btree, the apEnd[] array holds pointer to the end of page
** for Child-1, the Parent, Child-2, the Parent (again), and Child-3,
** respectively. The ixNx[] array holds the number of cells contained in
** each of these 5 stages, and all stages to the left.  Hence:
**
**    ixNx[0] = Number of cells in Child-1.
**    ixNx[1] = Number of cells in Child-1 plus 1 for first divider.
**    ixNx[2] = Number of cells in Child-1 and Child-2 + 1 for 1st divider.
**    ixNx[3] = Number of cells in Child-1 and Child-2 + both divider cells
**    ixNx[4] = Total number of cells.
**
** For a table-btree, the concept is similar, except only apEnd[0]..apEnd[2]
** are used and they point to the leaf pages only, and the ixNx value are:
**
**    ixNx[0] = Number of cells in Child-1.
**    ixNx[1] = Number of cells in Child-1 and Child-2 + 1 for 1st divider.
**    ixNx[2] = Number of cells in Child-1 and Child-2 + both divider cells
*/
typedef struct CellArray CellArray;
struct CellArray {
  int nCell;              /* Number of cells in apCell[] */
  MemPage *pRef;          /* Reference page */
  u8 **apCell;            /* All cells begin balanced */
  u16 *szCell;            /* Local size of all cells in apCell[] */
................................................................................
  **    szNew[i]: Spaced used on the i-th sibling page.
  **   cntNew[i]: Index in b.apCell[] and b.szCell[] for the first cell to
  **              the right of the i-th sibling page.
  ** usableSpace: Number of bytes of space available on each sibling.
  ** 
  */
  usableSpace = pBt->usableSize - 12 + leafCorrection;
  for(i=k=0; i<nOld; i++, k++){
    MemPage *p = apOld[i];
    b.apEnd[k] = p->aDataEnd;
    b.ixNx[k] = cntOld[i];
    if( !leafData ){
      k++;
      b.apEnd[k] = pParent->aDataEnd;

      b.ixNx[k] = cntOld[i]+1;
    }
    szNew[i] = usableSpace - p->nFree;
    for(j=0; j<p->nOverflow; j++){
      szNew[i] += 2 + p->xCellSize(p, p->apOvfl[j]);
    }
    cntNew[i] = cntOld[i];
  }
  k = nOld;