From d2dc87f6d52da7f018ff8228cb49552cc1cba1d6 Mon Sep 17 00:00:00 2001
From: drh <drh@noemail.net>
Date: Thu, 2 Jul 2015 19:47:08 +0000
Subject: [PATCH] When doing coverage analysis of a btree page for pragma
 integrity_check, make the first entry (that covers the header, cell index,
 and gap) implied, for a performance boost and size reduction.

FossilOrigin-Name: e53d497c2d2fbc5014b39f5624b52ce207800698
---
 manifest      | 14 +++++++-------
 manifest.uuid |  2 +-
 src/btree.c   | 20 +++++++++++++-------
 3 files changed, 21 insertions(+), 15 deletions(-)

diff --git a/manifest b/manifest
index da9a81acb6..d4f2070257 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Minor\schange\sto\smkfts5c.tcl\sso\sthat\sfts5.c\scan\sbe\sused\saccording\sto\sthe\sinstructions\sin\sloadext.html.
-D 2015-07-02T18:52:16.632
+C When\sdoing\scoverage\sanalysis\sof\sa\sbtree\spage\sfor\spragma\sintegrity_check,\nmake\sthe\sfirst\sentry\s(that\scovers\sthe\sheader,\scell\sindex,\sand\sgap)\simplied,\nfor\sa\sperformance\sboost\sand\ssize\sreduction.
+D 2015-07-02T19:47:08.924
 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f
 F Makefile.in 1f525f24e2d3a4defd0ce819c10980caeec967fe
 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23
@@ -269,7 +269,7 @@ F src/auth.c b56c78ebe40a2110fd361379f7e8162d23f92240
 F src/backup.c 4d9134dc988a87838c06056c89c0e8c4700a0452
 F src/bitvec.c d1f21d7d91690747881f03940584f4cc548c9d3d
 F src/btmutex.c 45a968cc85afed9b5e6cf55bf1f42f8d18107f79
-F src/btree.c cf3375bf706d15d3b8b7ac1fc86b0bf5603324d5
+F src/btree.c 7705ce3e17c2b0cb8d4c3d935b269270d3c2a548
 F src/btree.h 969adc948e89e449220ff0ff724c94bb2a52e9f1
 F src/btreeInt.h 2ad754dd4528baa8d0946a593cc373b890bf859e
 F src/build.c b3f15255d5b16e42dafeaa638fd4f8a47c94ed70
@@ -1364,7 +1364,7 @@ F tool/vdbe_profile.tcl 67746953071a9f8f2f668b73fe899074e2c6d8c1
 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4
 F tool/warnings.sh 48bd54594752d5be3337f12c72f28d2080cb630b
 F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f
-P ec2573487cb86664f7f056168a764c28ca8236fc
-R 8f8fb58b016bb7e374a57938c502e4cf
-U dan
-Z f04dde703cf9595bec71c1e298c8382a
+P edbcccd349090efff3f975e27451608136a429fc
+R cdbc7a7113ac1ac4a12173f49bd7408c
+U drh
+Z 652b7ed6ab7d80fc7ccd06705dfdfa60
diff --git a/manifest.uuid b/manifest.uuid
index 8110ba7c6b..77cf6612a3 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-edbcccd349090efff3f975e27451608136a429fc
\ No newline at end of file
+e53d497c2d2fbc5014b39f5624b52ce207800698
\ No newline at end of file
diff --git a/src/btree.c b/src/btree.c
index ca0dd0e596..30f24e9129 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -8955,7 +8955,7 @@ static int checkTreePage(
   u32 usableSize;          /* Usable size of the page */
   u32 contentOffset;       /* Offset to the start of the cell content area */
   u32 *heap = 0;           /* Min-heap used for checking cell coverage */
-  u32 x, prev = 0;
+  u32 x, prev = 0;         /* Next and previous entry on the min-heap */
   const char *saved_zPfx = pCheck->zPfx;
   int saved_v1 = pCheck->v1;
   int saved_v2 = pCheck->v2;
@@ -9018,7 +9018,6 @@ static int checkTreePage(
     ** as the other cell checks, so initialize the heap.  */
     heap = pCheck->heap;
     heap[0] = 0;
-    btreeHeapInsert(heap, contentOffset-1);
   }
 
   /* EVIDENCE-OF: R-02776-14802 The cell pointer array consists of K 2-byte
@@ -9099,7 +9098,6 @@ static int checkTreePage(
     if( !pPage->leaf ){
       heap = pCheck->heap;
       heap[0] = 0;
-      btreeHeapInsert(heap, contentOffset-1);
       for(i=nCell-1; i>=0; i--){
         u32 size;
         pc = get2byteAligned(&data[cellStart+i*2]);
@@ -9133,13 +9131,21 @@ static int checkTreePage(
     }
     /* Analyze the min-heap looking for overlap between cells and/or 
     ** freeblocks, and counting the number of untracked bytes in nFrag.
+    ** 
+    ** Each min-heap entry is of the form:    (start_address<<16)|end_address.
+    ** There is an implied first entry the covers the page header, the cell
+    ** pointer index, and the gap between the cell pointer index and the start
+    ** of cell content.  
+    **
+    ** The loop below pulls entries from the min-heap in order and compares
+    ** the start_address against the previous end_address.  If there is an
+    ** overlap, that means bytes are used multiple times.  If there is a gap,
+    ** that gap is added to the fragmentation count.
     */
     nFrag = 0;
-    assert( heap[0]>0 );
-    assert( (heap[1]>>16)==0 );
-    btreeHeapPull(heap,&prev);
+    prev = contentOffset - 1;   /* Implied first min-heap entry */
     while( btreeHeapPull(heap,&x) ){
-      if( (prev&0xffff)+1>(x>>16) ){
+      if( (prev&0xffff)>=(x>>16) ){
         checkAppendMsg(pCheck,
           "Multiple uses for byte %u of page %d", x>>16, iPage);
         break;
-- 
2.47.2