/ Check-in [121308fa]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Size reduction and performance improvements in btree.c and the allocateSpace() routine. Also fix an assert() in freeSpace().
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 121308fa869ad490a6924798d276c0ff32759acc
User & Date: drh 2014-08-20 13:35:45
Context
2014-08-20
14:37
Refactor local variable names in the freeSpace() routine of btree.c for improved understandability. check-in: 7e63089a user: drh tags: trunk
13:35
Size reduction and performance improvements in btree.c and the allocateSpace() routine. Also fix an assert() in freeSpace(). check-in: 121308fa user: drh tags: trunk
13:25
Add SQLITE_API macros in front of interface routines in the test_intarray.c extension. check-in: eea06617 user: drh tags: trunk
13:17
Change an assert() added by the previous commit into a testcase(). Fix a separate assert() in btree.c:freeSpace(). Closed-Leaf check-in: fe51d3aa user: drh tags: btree-speedup
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

1218
1219
1220
1221
1222
1223
1224





1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250

1251
1252
1253
1254
1255
1256
1257
....
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272


1273
1274
1275
1276
1277
1278
1279
....
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
  if( gap>top ){
    if( top==0 ){
      top = 65536;
    }else{
      return SQLITE_CORRUPT_BKPT;
    }
  }





  testcase( gap+2==top );
  testcase( gap+1==top );
  testcase( gap==top );

  if( data[hdr+7]>=60 ){
    /* Always defragment highly fragmented pages */
    rc = defragmentPage(pPage);
    if( rc ) return rc;
    top = get2byteNotZero(&data[hdr+5]);
  }else if( gap+2<=top ){
    /* Search the freelist looking for a free slot big enough to satisfy 
    ** the request. The allocation is made from the first free slot in 
    ** the list that is large enough to accommodate it.
    */
    int pc, addr;
    for(addr=hdr+1; (pc = get2byte(&data[addr]))>0; addr=pc){
      int size;            /* Size of the free slot */
      if( pc>usableSize-4 || pc<addr+4 ){
        return SQLITE_CORRUPT_BKPT;
      }
      size = get2byte(&data[pc+2]);
      if( size>=nByte ){
        int x = size - nByte;
        testcase( x==4 );
        testcase( x==3 );
        if( x<4 ){

          /* Remove the slot from the free-list. Update the number of
          ** fragmented bytes within the page. */
          memcpy(&data[addr], &data[pc], 2);
          data[hdr+7] += (u8)x;
        }else if( size+pc > usableSize ){
          return SQLITE_CORRUPT_BKPT;
        }else{
................................................................................
        }
        *pIdx = pc + x;
        return SQLITE_OK;
      }
    }
  }

  /* Check to make sure there is enough space in the gap to satisfy
  ** the allocation.  If not, defragment.
  */
  testcase( gap+2+nByte==top );
  if( gap+2+nByte>top ){


    rc = defragmentPage(pPage);
    if( rc ) return rc;
    top = get2byteNotZero(&data[hdr+5]);
    assert( gap+nByte<=top );
  }


................................................................................
  unsigned char *data = pPage->aData;

  assert( pPage->pBt!=0 );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( start>=pPage->hdrOffset+6+pPage->childPtrSize );
  assert( (start + size) <= (int)pPage->pBt->usableSize );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( size>=0 );   /* Minimum cell size is 4 */

  if( pPage->pBt->btsFlags & BTS_SECURE_DELETE ){
    /* Overwrite deleted information with zeros when the secure_delete
    ** option is enabled */
    memset(&data[start], 0, size);
  }








>
>
>
>
>



<
<
<
<
<
<
|
<
<
<
<












>







 







|
|



>
>







 







|







1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232






1233




1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
....
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
....
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
  if( gap>top ){
    if( top==0 ){
      top = 65536;
    }else{
      return SQLITE_CORRUPT_BKPT;
    }
  }

  /* If there is enough space between gap and top for one more cell pointer
  ** array entry offset, and if the freelist is not empty, then search the
  ** freelist looking for a free slot big enough to satisfy the request.
  */
  testcase( gap+2==top );
  testcase( gap+1==top );
  testcase( gap==top );






  if( gap+2<=top && (data[hdr+1] || data[hdr+2]) ){




    int pc, addr;
    for(addr=hdr+1; (pc = get2byte(&data[addr]))>0; addr=pc){
      int size;            /* Size of the free slot */
      if( pc>usableSize-4 || pc<addr+4 ){
        return SQLITE_CORRUPT_BKPT;
      }
      size = get2byte(&data[pc+2]);
      if( size>=nByte ){
        int x = size - nByte;
        testcase( x==4 );
        testcase( x==3 );
        if( x<4 ){
          if( data[hdr+7]>=60 ) goto defragment_page;
          /* Remove the slot from the free-list. Update the number of
          ** fragmented bytes within the page. */
          memcpy(&data[addr], &data[pc], 2);
          data[hdr+7] += (u8)x;
        }else if( size+pc > usableSize ){
          return SQLITE_CORRUPT_BKPT;
        }else{
................................................................................
        }
        *pIdx = pc + x;
        return SQLITE_OK;
      }
    }
  }

  /* The request could not be fulfilled using a freelist slot.  Check
  ** to see if defragmentation is necessary.
  */
  testcase( gap+2+nByte==top );
  if( gap+2+nByte>top ){
defragment_page:
    testcase( pPage->nCell==0 );
    rc = defragmentPage(pPage);
    if( rc ) return rc;
    top = get2byteNotZero(&data[hdr+5]);
    assert( gap+nByte<=top );
  }


................................................................................
  unsigned char *data = pPage->aData;

  assert( pPage->pBt!=0 );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( start>=pPage->hdrOffset+6+pPage->childPtrSize );
  assert( (start + size) <= (int)pPage->pBt->usableSize );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( size>=4 );   /* Minimum cell size is 4 */

  if( pPage->pBt->btsFlags & BTS_SECURE_DELETE ){
    /* Overwrite deleted information with zeros when the secure_delete
    ** option is enabled */
    memset(&data[start], 0, size);
  }