/ Check-in [49f44d35]
Login

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

Overview
Comment:A small performance improvement in freeSpace() by special-casing the relatively common case of an empty freelist.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:49f44d355ff70744e4951baca2481c7c2b6c02b3
User & Date: drh 2014-08-20 18:43:44
Context
2014-08-20
23:38
Enhancements to skip-scan such that it is operable when a middle column of an index is skipped while the left-most column is constrained in the WHERE clause. check-in: bc985caa user: drh tags: trunk
18:43
A small performance improvement in freeSpace() by special-casing the relatively common case of an empty freelist. check-in: 49f44d35 user: drh tags: trunk
17:56
Reimplement the freeSpace() routine in btree.c so that it runs faster. check-in: fe4fd014 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

1326
1327
1328
1329
1330
1331
1332



1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369

1370
1371
1372
1373

1374
1375
1376
1377
1378
1379
1380
  }

  /* The list of freeblocks must be in ascending order.  Find the 
  ** spot on the list where iStart should be inserted.
  */
  hdr = pPage->hdrOffset;
  iPtr = hdr + 1;



  while( (iFreeBlk = get2byte(&data[iPtr]))>0 && iFreeBlk<iStart ){
    if( iFreeBlk<iPtr+4 ) return SQLITE_CORRUPT_BKPT;
    iPtr = iFreeBlk;
  }
  if( iFreeBlk>iLast ) return SQLITE_CORRUPT_BKPT;
  assert( iFreeBlk>iPtr || iFreeBlk==0 );

  /* At this point:
  **    iFreeBlk:   First freeblock after iStart, or zero if none
  **    iPtr:       The address of a pointer iFreeBlk
  **
  ** Check to see if iFreeBlk should be coalesced onto the end of iStart.
  */
  if( iFreeBlk && iEnd+3>=iFreeBlk ){
    nFrag = iFreeBlk - iEnd;
    if( iEnd>iFreeBlk ) return SQLITE_CORRUPT_BKPT;
    iEnd = iFreeBlk + get2byte(&data[iFreeBlk+2]);
    iSize = iEnd - iStart;
    iFreeBlk = get2byte(&data[iFreeBlk]);
  }

  /* If iPtr is another freeblock (that is, if iPtr is not the freelist pointer
  ** in the page header) then check to see if iStart should be coalesced 
  ** onto the end of iPtr.
  */
  if( iPtr>hdr+1 ){
    int iPtrEnd = iPtr + get2byte(&data[iPtr+2]);
    if( iPtrEnd+3>=iStart ){
      if( iPtrEnd>iStart ) return SQLITE_CORRUPT_BKPT;
      nFrag += iStart - iPtrEnd;
      iSize = iEnd - iPtr;
      iStart = iPtr;
    }
  }
  if( nFrag>data[hdr+7] ) return SQLITE_CORRUPT_BKPT;

  data[hdr+7] -= nFrag;

  if( iPtr==hdr+1 && iStart==get2byte(&data[hdr+5]) ){
    /* The new freeblock is at the beginning of the cell content area,
    ** so just extend the cell content area rather than create another
    ** freelist entry */

    put2byte(&data[hdr+1], iFreeBlk);
    put2byte(&data[hdr+5], iEnd);
  }else{
    /* Insert the new freeblock into the freelist */
    put2byte(&data[iPtr], iStart);
    put2byte(&data[iStart], iFreeBlk);
    put2byte(&data[iStart+2], iSize);







>
>
>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<
|
>
|



>







1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370

1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
  }

  /* The list of freeblocks must be in ascending order.  Find the 
  ** spot on the list where iStart should be inserted.
  */
  hdr = pPage->hdrOffset;
  iPtr = hdr + 1;
  if( data[iPtr+1]==0 && data[iPtr]==0 ){
    iFreeBlk = 0;  /* Shortcut for the case when the freelist is empty */
  }else{
    while( (iFreeBlk = get2byte(&data[iPtr]))>0 && iFreeBlk<iStart ){
      if( iFreeBlk<iPtr+4 ) return SQLITE_CORRUPT_BKPT;
      iPtr = iFreeBlk;
    }
    if( iFreeBlk>iLast ) return SQLITE_CORRUPT_BKPT;
    assert( iFreeBlk>iPtr || iFreeBlk==0 );
  
    /* At this point:
    **    iFreeBlk:   First freeblock after iStart, or zero if none
    **    iPtr:       The address of a pointer iFreeBlk
    **
    ** Check to see if iFreeBlk should be coalesced onto the end of iStart.
    */
    if( iFreeBlk && iEnd+3>=iFreeBlk ){
      nFrag = iFreeBlk - iEnd;
      if( iEnd>iFreeBlk ) return SQLITE_CORRUPT_BKPT;
      iEnd = iFreeBlk + get2byte(&data[iFreeBlk+2]);
      iSize = iEnd - iStart;
      iFreeBlk = get2byte(&data[iFreeBlk]);
    }
  
    /* If iPtr is another freeblock (that is, if iPtr is not the freelist pointer
    ** in the page header) then check to see if iStart should be coalesced 
    ** onto the end of iPtr.
    */
    if( iPtr>hdr+1 ){
      int iPtrEnd = iPtr + get2byte(&data[iPtr+2]);
      if( iPtrEnd+3>=iStart ){
        if( iPtrEnd>iStart ) return SQLITE_CORRUPT_BKPT;
        nFrag += iStart - iPtrEnd;
        iSize = iEnd - iPtr;
        iStart = iPtr;
      }
    }
    if( nFrag>data[hdr+7] ) return SQLITE_CORRUPT_BKPT;

    data[hdr+7] -= nFrag;
  }
  if( iStart==get2byte(&data[hdr+5]) ){
    /* The new freeblock is at the beginning of the cell content area,
    ** so just extend the cell content area rather than create another
    ** freelist entry */
    if( iPtr!=hdr+1 ) return SQLITE_CORRUPT_BKPT;
    put2byte(&data[hdr+1], iFreeBlk);
    put2byte(&data[hdr+5], iEnd);
  }else{
    /* Insert the new freeblock into the freelist */
    put2byte(&data[iPtr], iStart);
    put2byte(&data[iStart], iFreeBlk);
    put2byte(&data[iStart+2], iSize);