/ Check-in [7e63089a]
Login
Overview
Comment:Refactor local variable names in the freeSpace() routine of btree.c for improved understandability.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:7e63089a191f29aefde05e89bb612f3036cfa034
User & Date: drh 2014-08-20 14:37:09
Context
2014-08-20
17:56
Reimplement the freeSpace() routine in btree.c so that it runs faster. check-in: fe4fd014 user: drh tags: trunk
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
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300


1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
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
  assert( top+nByte <= (int)pPage->pBt->usableSize );
  *pIdx = top;
  return SQLITE_OK;
}

/*
** Return a section of the pPage->aData to the freelist.
** The first byte of the new free block is pPage->aDisk[start]
** and the size of the block is "size" bytes.
**
** Most of the effort here is involved in coalesing adjacent
** free blocks into a single big free block.
*/
static int freeSpace(MemPage *pPage, int start, int size){
  int addr, pbegin, hdr;


  int iLast;                        /* Largest possible freeblock offset */
  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);
  }

  /* Add the space back into the linked list of freeblocks.  Note that
  ** even though the freeblock list was checked by btreeInitPage(),
  ** btreeInitPage() did not detect overlapping cells or
  ** freeblocks that overlapped cells.   Nor does it detect when the
  ** cell content area exceeds the value in the page header.  If these
  ** situations arise, then subsequent insert operations might corrupt
  ** the freelist.  So we do need to check for corruption while scanning
  ** the freelist.
  */
  hdr = pPage->hdrOffset;
  addr = hdr + 1;
  iLast = pPage->pBt->usableSize - 4;
  assert( start<=iLast );
  while( (pbegin = get2byte(&data[addr]))<start && pbegin>0 ){
    if( pbegin<addr+4 ){
      return SQLITE_CORRUPT_BKPT;
    }
    addr = pbegin;
  }
  if( pbegin>iLast ){
    return SQLITE_CORRUPT_BKPT;
  }
  assert( pbegin>addr || pbegin==0 );
  put2byte(&data[addr], start);
  put2byte(&data[start], pbegin);
  put2byte(&data[start+2], size);
  pPage->nFree = pPage->nFree + (u16)size;

  /* Coalesce adjacent free blocks */
  addr = hdr + 1;
  while( (pbegin = get2byte(&data[addr]))>0 ){
    int pnext, psize, x;
    assert( pbegin>addr );

    assert( pbegin <= (int)pPage->pBt->usableSize-4 );
    pnext = get2byte(&data[pbegin]);
    psize = get2byte(&data[pbegin+2]);
    if( pbegin + psize + 3 >= pnext && pnext>0 ){
      int frag = pnext - (pbegin+psize);



      if( (frag<0) || (frag>(int)data[hdr+7]) ){
        return SQLITE_CORRUPT_BKPT;
      }
      data[hdr+7] -= (u8)frag;
      x = get2byte(&data[pnext]);
      put2byte(&data[pbegin], x);
      x = pnext + get2byte(&data[pnext+2]) - pbegin;

      put2byte(&data[pbegin+2], x);
    }else{
      addr = pbegin;

    }
  }

  /* If the cell content area begins with a freeblock, remove it. */
  if( data[hdr+1]==data[hdr+5] && data[hdr+2]==data[hdr+6] ){
    int top;
    pbegin = get2byte(&data[hdr+1]);
    memcpy(&data[hdr+1], &data[pbegin], 2);
    top = get2byte(&data[hdr+5]) + get2byte(&data[pbegin+2]);
    put2byte(&data[hdr+5], top);
  }
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  return SQLITE_OK;
}

/*







|
|




|
|
>
>
|
|



|
|

|




|












|

|
|
|


|

|


|
|
|
|
|


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


|
|
|
<
>
|

<
>






|
|
|







1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
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
1385
  assert( top+nByte <= (int)pPage->pBt->usableSize );
  *pIdx = top;
  return SQLITE_OK;
}

/*
** Return a section of the pPage->aData to the freelist.
** The first byte of the new free block is pPage->aData[iStart]
** and the size of the block is iSize bytes.
**
** Most of the effort here is involved in coalesing adjacent
** free blocks into a single big free block.
*/
static int freeSpace(MemPage *pPage, int iStart, int iSize){
  int iPtr;                  /* Address of pointer to next freeblock */
  int iFreeBlk;              /* Address of the next freeblock */
  int hdr;                   /* Page header size.  0 or 100 */
  int iLast;                 /* Largest possible freeblock offset */
  unsigned char *data = pPage->aData;   /* Page content */

  assert( pPage->pBt!=0 );
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  assert( iStart>=pPage->hdrOffset+6+pPage->childPtrSize );
  assert( (iStart + iSize) <= (int)pPage->pBt->usableSize );
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  assert( iSize>=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[iStart], 0, iSize);
  }

  /* Add the space back into the linked list of freeblocks.  Note that
  ** even though the freeblock list was checked by btreeInitPage(),
  ** btreeInitPage() did not detect overlapping cells or
  ** freeblocks that overlapped cells.   Nor does it detect when the
  ** cell content area exceeds the value in the page header.  If these
  ** situations arise, then subsequent insert operations might corrupt
  ** the freelist.  So we do need to check for corruption while scanning
  ** the freelist.
  */
  hdr = pPage->hdrOffset;
  iPtr = hdr + 1;
  iLast = pPage->pBt->usableSize - 4;
  assert( iStart<=iLast );
  while( (iFreeBlk = get2byte(&data[iPtr]))<iStart && iFreeBlk>0 ){
    if( iFreeBlk<iPtr+4 ){
      return SQLITE_CORRUPT_BKPT;
    }
    iPtr = iFreeBlk;
  }
  if( iFreeBlk>iLast ){
    return SQLITE_CORRUPT_BKPT;
  }
  assert( iFreeBlk>iPtr || iFreeBlk==0 );
  put2byte(&data[iPtr], iStart);
  put2byte(&data[iStart], iFreeBlk);
  put2byte(&data[iStart+2], iSize);
  pPage->nFree = pPage->nFree + (u16)iSize;

  /* Coalesce adjacent free blocks */
  iPtr = hdr + 1;
  while( (iFreeBlk = get2byte(&data[iPtr]))>0 ){
    int iNextBlk;      /* Next freeblock after iFreeBlk */
    int szFreeBlk;     /* Size of iFreeBlk */
    assert( iFreeBlk>iPtr );
    assert( iFreeBlk <= (int)pPage->pBt->usableSize-4 );
    iNextBlk = get2byte(&data[iFreeBlk]);
    szFreeBlk = get2byte(&data[iFreeBlk+2]);

    if( iFreeBlk + szFreeBlk + 3 >= iNextBlk && iNextBlk>0 ){
      int nFrag;     /* Fragment bytes in between iFreeBlk and iNextBlk */
      int x;         /* Temp value */
      nFrag = iNextBlk - (iFreeBlk+szFreeBlk);
      if( (nFrag<0) || (nFrag>(int)data[hdr+7]) ){
        return SQLITE_CORRUPT_BKPT;
      }
      data[hdr+7] -= (u8)nFrag;
      x = get2byte(&data[iNextBlk]);
      put2byte(&data[iFreeBlk], x);

      x = iNextBlk + get2byte(&data[iNextBlk+2]) - iFreeBlk;
      put2byte(&data[iFreeBlk+2], x);
    }else{

      iPtr = iFreeBlk;
    }
  }

  /* If the cell content area begins with a freeblock, remove it. */
  if( data[hdr+1]==data[hdr+5] && data[hdr+2]==data[hdr+6] ){
    int top;
    iFreeBlk = get2byte(&data[hdr+1]);
    memcpy(&data[hdr+1], &data[iFreeBlk], 2);
    top = get2byte(&data[hdr+5]) + get2byte(&data[iFreeBlk+2]);
    put2byte(&data[hdr+5], top);
  }
  assert( sqlite3PagerIswriteable(pPage->pDbPage) );
  return SQLITE_OK;
}

/*