third_party/sqlite/sqlite-src-3080704/src/pcache.c

   1 /*
   2 ** 2008 August 05
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** This file implements that page cache.
  13 */
  14 #include "sqliteInt.h"
  15
  16 /*
  17 ** A complete page cache is an instance of this structure.
  18 */
  19 struct PCache {
  20   PgHdr *pDirty, *pDirtyTail;         /* List of dirty pages in LRU order */
  21   PgHdr *pSynced;                     /* Last synced page in dirty page list */
  22   int nRef;                           /* Number of referenced pages */
  23   int szCache;                        /* Configured cache size */
  24   int szPage;                         /* Size of every page in this cache */
  25   int szExtra;                        /* Size of extra space for each page */
  26   u8 bPurgeable;                      /* True if pages are on backing store */
  27   u8 eCreate;                         /* eCreate value for for xFetch() */
  28   int (*xStress)(void*,PgHdr*);       /* Call to try make a page clean */
  29   void *pStress;                      /* Argument to xStress */
  30   sqlite3_pcache *pCache;             /* Pluggable cache module */
  31   PgHdr *pPage1;                      /* Reference to page 1 */
  32 };
  33
  34 /*
  35 ** Some of the assert() macros in this code are too expensive to run
  36 ** even during normal debugging.  Use them only rarely on long-running
  37 ** tests.  Enable the expensive asserts using the
  38 ** -DSQLITE_ENABLE_EXPENSIVE_ASSERT=1 compile-time option.
  39 */
  40 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  41 # define expensive_assert(X)  assert(X)
  42 #else
  43 # define expensive_assert(X)
  44 #endif
  45
  46 /********************************** Linked List Management ********************/
  47
  48 /* Allowed values for second argument to pcacheManageDirtyList() */
  49 #define PCACHE_DIRTYLIST_REMOVE   1    /* Remove pPage from dirty list */
  50 #define PCACHE_DIRTYLIST_ADD      2    /* Add pPage to the dirty list */
  51 #define PCACHE_DIRTYLIST_FRONT    3    /* Move pPage to the front of the list */
  52
  53 /*
  54 ** Manage pPage's participation on the dirty list.  Bits of the addRemove
  55 ** argument determines what operation to do.  The 0x01 bit means first
  56 ** remove pPage from the dirty list.  The 0x02 means add pPage back to
  57 ** the dirty list.  Doing both moves pPage to the front of the dirty list.
  58 */
  59 static void pcacheManageDirtyList(PgHdr *pPage, u8 addRemove){
  60   PCache *p = pPage->pCache;
  61
  62   if( addRemove & PCACHE_DIRTYLIST_REMOVE ){
  63     assert( pPage->pDirtyNext || pPage==p->pDirtyTail );
  64     assert( pPage->pDirtyPrev || pPage==p->pDirty );
  65
  66     /* Update the PCache1.pSynced variable if necessary. */
  67     if( p->pSynced==pPage ){
  68       PgHdr *pSynced = pPage->pDirtyPrev;
  69       while( pSynced && (pSynced->flags&PGHDR_NEED_SYNC) ){
  70         pSynced = pSynced->pDirtyPrev;
  71       }
  72       p->pSynced = pSynced;
  73     }
  74
  75     if( pPage->pDirtyNext ){
  76       pPage->pDirtyNext->pDirtyPrev = pPage->pDirtyPrev;
  77     }else{
  78       assert( pPage==p->pDirtyTail );
  79       p->pDirtyTail = pPage->pDirtyPrev;
  80     }
  81     if( pPage->pDirtyPrev ){
  82       pPage->pDirtyPrev->pDirtyNext = pPage->pDirtyNext;
  83     }else{
  84       assert( pPage==p->pDirty );
  85       p->pDirty = pPage->pDirtyNext;
  86       if( p->pDirty==0 && p->bPurgeable ){
  87         assert( p->eCreate==1 );
  88         p->eCreate = 2;
  89       }
  90     }
  91     pPage->pDirtyNext = 0;
  92     pPage->pDirtyPrev = 0;
  93   }
  94   if( addRemove & PCACHE_DIRTYLIST_ADD ){
  95     assert( pPage->pDirtyNext==0 && pPage->pDirtyPrev==0 && p->pDirty!=pPage );
  96
  97     pPage->pDirtyNext = p->pDirty;
  98     if( pPage->pDirtyNext ){
  99       assert( pPage->pDirtyNext->pDirtyPrev==0 );
 100       pPage->pDirtyNext->pDirtyPrev = pPage;
 101     }else{
 102       p->pDirtyTail = pPage;
 103       if( p->bPurgeable ){
 104         assert( p->eCreate==2 );
 105         p->eCreate = 1;
 106       }
 107     }
 108     p->pDirty = pPage;
 109     if( !p->pSynced && 0==(pPage->flags&PGHDR_NEED_SYNC) ){
 110       p->pSynced = pPage;
 111     }
 112   }
 113 }
 114
 115 /*
 116 ** Wrapper around the pluggable caches xUnpin method. If the cache is
 117 ** being used for an in-memory database, this function is a no-op.
 118 */
 119 static void pcacheUnpin(PgHdr *p){
 120   if( p->pCache->bPurgeable ){
 121     if( p->pgno==1 ){
 122       p->pCache->pPage1 = 0;
 123     }
 124     sqlite3GlobalConfig.pcache2.xUnpin(p->pCache->pCache, p->pPage, 0);
 125   }
 126 }
 127
 128 /*
 129 ** Compute the number of pages of cache requested.
 130 */
 131 static int numberOfCachePages(PCache *p){
 132   if( p->szCache>=0 ){
 133     return p->szCache;
 134   }else{
 135     return (int)((-1024*(i64)p->szCache)/(p->szPage+p->szExtra));
 136   }
 137 }
 138
 139 /*************************************************** General Interfaces ******
 140 **
 141 ** Initialize and shutdown the page cache subsystem. Neither of these
 142 ** functions are threadsafe.
 143 */
 144 int sqlite3PcacheInitialize(void){
 145   if( sqlite3GlobalConfig.pcache2.xInit==0 ){
 146     /* IMPLEMENTATION-OF: R-26801-64137 If the xInit() method is NULL, then the
 147     ** built-in default page cache is used instead of the application defined
 148     ** page cache. */
 149     sqlite3PCacheSetDefault();
 150   }
 151   return sqlite3GlobalConfig.pcache2.xInit(sqlite3GlobalConfig.pcache2.pArg);
 152 }
 153 void sqlite3PcacheShutdown(void){
 154   if( sqlite3GlobalConfig.pcache2.xShutdown ){
 155     /* IMPLEMENTATION-OF: R-26000-56589 The xShutdown() method may be NULL. */
 156     sqlite3GlobalConfig.pcache2.xShutdown(sqlite3GlobalConfig.pcache2.pArg);
 157   }
 158 }
 159
 160 /*
 161 ** Return the size in bytes of a PCache object.
 162 */
 163 int sqlite3PcacheSize(void){ return sizeof(PCache); }
 164
 165 /*
 166 ** Create a new PCache object. Storage space to hold the object
 167 ** has already been allocated and is passed in as the p pointer.
 168 ** The caller discovers how much space needs to be allocated by
 169 ** calling sqlite3PcacheSize().
 170 */
 171 int sqlite3PcacheOpen(
 172   int szPage,                  /* Size of every page */
 173   int szExtra,                 /* Extra space associated with each page */
 174   int bPurgeable,              /* True if pages are on backing store */
 175   int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
 176   void *pStress,               /* Argument to xStress */
 177   PCache *p                    /* Preallocated space for the PCache */
 178 ){
 179   memset(p, 0, sizeof(PCache));
 180   p->szPage = 1;
 181   p->szExtra = szExtra;
 182   p->bPurgeable = bPurgeable;
 183   p->eCreate = 2;
 184   p->xStress = xStress;
 185   p->pStress = pStress;
 186   p->szCache = 100;
 187   return sqlite3PcacheSetPageSize(p, szPage);
 188 }
 189
 190 /*
 191 ** Change the page size for PCache object. The caller must ensure that there
 192 ** are no outstanding page references when this function is called.
 193 */
 194 int sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
 195   assert( pCache->nRef==0 && pCache->pDirty==0 );
 196   if( pCache->szPage ){
 197     sqlite3_pcache *pNew;
 198     pNew = sqlite3GlobalConfig.pcache2.xCreate(
 199                 szPage, pCache->szExtra + sizeof(PgHdr), pCache->bPurgeable
 200     );
 201     if( pNew==0 ) return SQLITE_NOMEM;
 202     sqlite3GlobalConfig.pcache2.xCachesize(pNew, numberOfCachePages(pCache));
 203     if( pCache->pCache ){
 204       sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
 205     }
 206     pCache->pCache = pNew;
 207     pCache->pPage1 = 0;
 208     pCache->szPage = szPage;
 209   }
 210   return SQLITE_OK;
 211 }
 212
 213 /*
 214 ** Try to obtain a page from the cache.
 215 **
 216 ** This routine returns a pointer to an sqlite3_pcache_page object if
 217 ** such an object is already in cache, or if a new one is created.
 218 ** This routine returns a NULL pointer if the object was not in cache
 219 ** and could not be created.
 220 **
 221 ** The createFlags should be 0 to check for existing pages and should
 222 ** be 3 (not 1, but 3) to try to create a new page.
 223 **
 224 ** If the createFlag is 0, then NULL is always returned if the page
 225 ** is not already in the cache.  If createFlag is 1, then a new page
 226 ** is created only if that can be done without spilling dirty pages
 227 ** and without exceeding the cache size limit.
 228 **
 229 ** The caller needs to invoke sqlite3PcacheFetchFinish() to properly
 230 ** initialize the sqlite3_pcache_page object and convert it into a
 231 ** PgHdr object.  The sqlite3PcacheFetch() and sqlite3PcacheFetchFinish()
 232 ** routines are split this way for performance reasons. When separated
 233 ** they can both (usually) operate without having to push values to
 234 ** the stack on entry and pop them back off on exit, which saves a
 235 ** lot of pushing and popping.
 236 */
 237 sqlite3_pcache_page *sqlite3PcacheFetch(
 238   PCache *pCache,       /* Obtain the page from this cache */
 239   Pgno pgno,            /* Page number to obtain */
 240   int createFlag        /* If true, create page if it does not exist already */
 241 ){
 242   int eCreate;
 243
 244   assert( pCache!=0 );
 245   assert( pCache->pCache!=0 );
 246   assert( createFlag==3 || createFlag==0 );
 247   assert( pgno>0 );
 248
 249   /* eCreate defines what to do if the page does not exist.
 250   **    0     Do not allocate a new page.  (createFlag==0)
 251   **    1     Allocate a new page if doing so is inexpensive.
 252   **          (createFlag==1 AND bPurgeable AND pDirty)
 253   **    2     Allocate a new page even it doing so is difficult.
 254   **          (createFlag==1 AND !(bPurgeable AND pDirty)
 255   */
 256   eCreate = createFlag & pCache->eCreate;
 257   assert( eCreate==0 || eCreate==1 || eCreate==2 );
 258   assert( createFlag==0 || pCache->eCreate==eCreate );
 259   assert( createFlag==0 || eCreate==1+(!pCache->bPurgeable||!pCache->pDirty) );
 260   return sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, eCreate);
 261 }
 262
 263 /*
 264 ** If the sqlite3PcacheFetch() routine is unable to allocate a new
 265 ** page because new clean pages are available for reuse and the cache
 266 ** size limit has been reached, then this routine can be invoked to
 267 ** try harder to allocate a page.  This routine might invoke the stress
 268 ** callback to spill dirty pages to the journal.  It will then try to
 269 ** allocate the new page and will only fail to allocate a new page on
 270 ** an OOM error.
 271 **
 272 ** This routine should be invoked only after sqlite3PcacheFetch() fails.
 273 */
 274 int sqlite3PcacheFetchStress(
 275   PCache *pCache,                 /* Obtain the page from this cache */
 276   Pgno pgno,                      /* Page number to obtain */
 277   sqlite3_pcache_page **ppPage    /* Write result here */
 278 ){
 279   PgHdr *pPg;
 280   if( pCache->eCreate==2 ) return 0;
 281
 282
 283   /* Find a dirty page to write-out and recycle. First try to find a
 284   ** page that does not require a journal-sync (one with PGHDR_NEED_SYNC
 285   ** cleared), but if that is not possible settle for any other
 286   ** unreferenced dirty page.
 287   */
 288   for(pPg=pCache->pSynced;
 289       pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC));
 290       pPg=pPg->pDirtyPrev
 291   );
 292   pCache->pSynced = pPg;
 293   if( !pPg ){
 294     for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pDirtyPrev);
 295   }
 296   if( pPg ){
 297     int rc;
 298 #ifdef SQLITE_LOG_CACHE_SPILL
 299     sqlite3_log(SQLITE_FULL,
 300                 "spill page %d making room for %d - cache used: %d/%d",
 301                 pPg->pgno, pgno,
 302                 sqlite3GlobalConfig.pcache.xPagecount(pCache->pCache),
 303                 numberOfCachePages(pCache));
 304 #endif
 305     rc = pCache->xStress(pCache->pStress, pPg);
 306     if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
 307       return rc;
 308     }
 309   }
 310   *ppPage = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, 2);
 311   return *ppPage==0 ? SQLITE_NOMEM : SQLITE_OK;
 312 }
 313
 314 /*
 315 ** This is a helper routine for sqlite3PcacheFetchFinish()
 316 **
 317 ** In the uncommon case where the page being fetched has not been
 318 ** initialized, this routine is invoked to do the initialization.
 319 ** This routine is broken out into a separate function since it
 320 ** requires extra stack manipulation that can be avoided in the common
 321 ** case.
 322 */
 323 static SQLITE_NOINLINE PgHdr *pcacheFetchFinishWithInit(
 324   PCache *pCache,             /* Obtain the page from this cache */
 325   Pgno pgno,                  /* Page number obtained */
 326   sqlite3_pcache_page *pPage  /* Page obtained by prior PcacheFetch() call */
 327 ){
 328   PgHdr *pPgHdr;
 329   assert( pPage!=0 );
 330   pPgHdr = (PgHdr*)pPage->pExtra;
 331   assert( pPgHdr->pPage==0 );
 332  memset(pPgHdr, 0, sizeof(PgHdr));
 333   pPgHdr->pPage = pPage;
 334   pPgHdr->pData = pPage->pBuf;
 335   pPgHdr->pExtra = (void *)&pPgHdr[1];
 336   memset(pPgHdr->pExtra, 0, pCache->szExtra);
 337   pPgHdr->pCache = pCache;
 338   pPgHdr->pgno = pgno;
 339   return sqlite3PcacheFetchFinish(pCache,pgno,pPage);
 340 }
 341
 342 /*
 343 ** This routine converts the sqlite3_pcache_page object returned by
 344 ** sqlite3PcacheFetch() into an initialized PgHdr object.  This routine
 345 ** must be called after sqlite3PcacheFetch() in order to get a usable
 346 ** result.
 347 */
 348 PgHdr *sqlite3PcacheFetchFinish(
 349   PCache *pCache,             /* Obtain the page from this cache */
 350   Pgno pgno,                  /* Page number obtained */
 351   sqlite3_pcache_page *pPage  /* Page obtained by prior PcacheFetch() call */
 352 ){
 353   PgHdr *pPgHdr;
 354
 355   if( pPage==0 ) return 0;
 356   pPgHdr = (PgHdr *)pPage->pExtra;
 357
 358   if( !pPgHdr->pPage ){
 359     return pcacheFetchFinishWithInit(pCache, pgno, pPage);
 360   }
 361   if( 0==pPgHdr->nRef ){
 362     pCache->nRef++;
 363   }
 364   pPgHdr->nRef++;
 365   if( pgno==1 ){
 366     pCache->pPage1 = pPgHdr;
 367   }
 368   return pPgHdr;
 369 }
 370
 371 /*
 372 ** Decrement the reference count on a page. If the page is clean and the
 373 ** reference count drops to 0, then it is made eligible for recycling.
 374 */
 375 void SQLITE_NOINLINE sqlite3PcacheRelease(PgHdr *p){
 376   assert( p->nRef>0 );
 377   p->nRef--;
 378   if( p->nRef==0 ){
 379     p->pCache->nRef--;
 380     if( (p->flags&PGHDR_DIRTY)==0 ){
 381       pcacheUnpin(p);
 382     }else if( p->pDirtyPrev!=0 ){
 383       /* Move the page to the head of the dirty list. */
 384       pcacheManageDirtyList(p, PCACHE_DIRTYLIST_FRONT);
 385     }
 386   }
 387 }
 388
 389 /*
 390 ** Increase the reference count of a supplied page by 1.
 391 */
 392 void sqlite3PcacheRef(PgHdr *p){
 393   assert(p->nRef>0);
 394   p->nRef++;
 395 }
 396
 397 /*
 398 ** Drop a page from the cache. There must be exactly one reference to the
 399 ** page. This function deletes that reference, so after it returns the
 400 ** page pointed to by p is invalid.
 401 */
 402 void sqlite3PcacheDrop(PgHdr *p){
 403   assert( p->nRef==1 );
 404   if( p->flags&PGHDR_DIRTY ){
 405     pcacheManageDirtyList(p, PCACHE_DIRTYLIST_REMOVE);
 406   }
 407   p->pCache->nRef--;
 408   if( p->pgno==1 ){
 409     p->pCache->pPage1 = 0;
 410   }
 411   sqlite3GlobalConfig.pcache2.xUnpin(p->pCache->pCache, p->pPage, 1);
 412 }
 413
 414 /*
 415 ** Make sure the page is marked as dirty. If it isn't dirty already,
 416 ** make it so.
 417 */
 418 void sqlite3PcacheMakeDirty(PgHdr *p){
 419   p->flags &= ~PGHDR_DONT_WRITE;
 420   assert( p->nRef>0 );
 421   if( 0==(p->flags & PGHDR_DIRTY) ){
 422     p->flags |= PGHDR_DIRTY;
 423     pcacheManageDirtyList(p, PCACHE_DIRTYLIST_ADD);
 424   }
 425 }
 426
 427 /*
 428 ** Make sure the page is marked as clean. If it isn't clean already,
 429 ** make it so.
 430 */
 431 void sqlite3PcacheMakeClean(PgHdr *p){
 432   if( (p->flags & PGHDR_DIRTY) ){
 433     pcacheManageDirtyList(p, PCACHE_DIRTYLIST_REMOVE);
 434     p->flags &= ~(PGHDR_DIRTY|PGHDR_NEED_SYNC);
 435     if( p->nRef==0 ){
 436       pcacheUnpin(p);
 437     }
 438   }
 439 }
 440
 441 /*
 442 ** Make every page in the cache clean.
 443 */
 444 void sqlite3PcacheCleanAll(PCache *pCache){
 445   PgHdr *p;
 446   while( (p = pCache->pDirty)!=0 ){
 447     sqlite3PcacheMakeClean(p);
 448   }
 449 }
 450
 451 /*
 452 ** Clear the PGHDR_NEED_SYNC flag from all dirty pages.
 453 */
 454 void sqlite3PcacheClearSyncFlags(PCache *pCache){
 455   PgHdr *p;
 456   for(p=pCache->pDirty; p; p=p->pDirtyNext){
 457     p->flags &= ~PGHDR_NEED_SYNC;
 458   }
 459   pCache->pSynced = pCache->pDirtyTail;
 460 }
 461
 462 /*
 463 ** Change the page number of page p to newPgno.
 464 */
 465 void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
 466   PCache *pCache = p->pCache;
 467   assert( p->nRef>0 );
 468   assert( newPgno>0 );
 469   sqlite3GlobalConfig.pcache2.xRekey(pCache->pCache, p->pPage, p->pgno,newPgno);
 470   p->pgno = newPgno;
 471   if( (p->flags&PGHDR_DIRTY) && (p->flags&PGHDR_NEED_SYNC) ){
 472     pcacheManageDirtyList(p, PCACHE_DIRTYLIST_FRONT);
 473   }
 474 }
 475
 476 /*
 477 ** Drop every cache entry whose page number is greater than "pgno". The
 478 ** caller must ensure that there are no outstanding references to any pages
 479 ** other than page 1 with a page number greater than pgno.
 480 **
 481 ** If there is a reference to page 1 and the pgno parameter passed to this
 482 ** function is 0, then the data area associated with page 1 is zeroed, but
 483 ** the page object is not dropped.
 484 */
 485 void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){
 486   if( pCache->pCache ){
 487     PgHdr *p;
 488     PgHdr *pNext;
 489     for(p=pCache->pDirty; p; p=pNext){
 490       pNext = p->pDirtyNext;
 491       /* This routine never gets call with a positive pgno except right
 492       ** after sqlite3PcacheCleanAll().  So if there are dirty pages,
 493       ** it must be that pgno==0.
 494       */
 495       assert( p->pgno>0 );
 496       if( ALWAYS(p->pgno>pgno) ){
 497         assert( p->flags&PGHDR_DIRTY );
 498         sqlite3PcacheMakeClean(p);
 499       }
 500     }
 501     if( pgno==0 && pCache->pPage1 ){
 502       memset(pCache->pPage1->pData, 0, pCache->szPage);
 503       pgno = 1;
 504     }
 505     sqlite3GlobalConfig.pcache2.xTruncate(pCache->pCache, pgno+1);
 506   }
 507 }
 508
 509 /*
 510 ** Close a cache.
 511 */
 512 void sqlite3PcacheClose(PCache *pCache){
 513   assert( pCache->pCache!=0 );
 514   sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
 515 }
 516
 517 /*
 518 ** Discard the contents of the cache.
 519 */
 520 void sqlite3PcacheClear(PCache *pCache){
 521   sqlite3PcacheTruncate(pCache, 0);
 522 }
 523
 524 /*
 525 ** Merge two lists of pages connected by pDirty and in pgno order.
 526 ** Do not both fixing the pDirtyPrev pointers.
 527 */
 528 static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
 529   PgHdr result, *pTail;
 530   pTail = &result;
 531   while( pA && pB ){
 532     if( pA->pgno<pB->pgno ){
 533       pTail->pDirty = pA;
 534       pTail = pA;
 535       pA = pA->pDirty;
 536     }else{
 537       pTail->pDirty = pB;
 538       pTail = pB;
 539       pB = pB->pDirty;
 540     }
 541   }
 542   if( pA ){
 543     pTail->pDirty = pA;
 544   }else if( pB ){
 545     pTail->pDirty = pB;
 546   }else{
 547     pTail->pDirty = 0;
 548   }
 549   return result.pDirty;
 550 }
 551
 552 /*
 553 ** Sort the list of pages in accending order by pgno.  Pages are
 554 ** connected by pDirty pointers.  The pDirtyPrev pointers are
 555 ** corrupted by this sort.
 556 **
 557 ** Since there cannot be more than 2^31 distinct pages in a database,
 558 ** there cannot be more than 31 buckets required by the merge sorter.
 559 ** One extra bucket is added to catch overflow in case something
 560 ** ever changes to make the previous sentence incorrect.
 561 */
 562 #define N_SORT_BUCKET  32
 563 static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
 564   PgHdr *a[N_SORT_BUCKET], *p;
 565   int i;
 566   memset(a, 0, sizeof(a));
 567   while( pIn ){
 568     p = pIn;
 569     pIn = p->pDirty;
 570     p->pDirty = 0;
 571     for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){
 572       if( a[i]==0 ){
 573         a[i] = p;
 574         break;
 575       }else{
 576         p = pcacheMergeDirtyList(a[i], p);
 577         a[i] = 0;
 578       }
 579     }
 580     if( NEVER(i==N_SORT_BUCKET-1) ){
 581       /* To get here, there need to be 2^(N_SORT_BUCKET) elements in
 582       ** the input list.  But that is impossible.
 583       */
 584       a[i] = pcacheMergeDirtyList(a[i], p);
 585     }
 586   }
 587   p = a[0];
 588   for(i=1; i<N_SORT_BUCKET; i++){
 589     p = pcacheMergeDirtyList(p, a[i]);
 590   }
 591   return p;
 592 }
 593
 594 /*
 595 ** Return a list of all dirty pages in the cache, sorted by page number.
 596 */
 597 PgHdr *sqlite3PcacheDirtyList(PCache *pCache){
 598   PgHdr *p;
 599   for(p=pCache->pDirty; p; p=p->pDirtyNext){
 600     p->pDirty = p->pDirtyNext;
 601   }
 602   return pcacheSortDirtyList(pCache->pDirty);
 603 }
 604
 605 /*
 606 ** Return the total number of referenced pages held by the cache.
 607 */
 608 int sqlite3PcacheRefCount(PCache *pCache){
 609   return pCache->nRef;
 610 }
 611
 612 /*
 613 ** Return the number of references to the page supplied as an argument.
 614 */
 615 int sqlite3PcachePageRefcount(PgHdr *p){
 616   return p->nRef;
 617 }
 618
 619 /*
 620 ** Return the total number of pages in the cache.
 621 */
 622 int sqlite3PcachePagecount(PCache *pCache){
 623   assert( pCache->pCache!=0 );
 624   return sqlite3GlobalConfig.pcache2.xPagecount(pCache->pCache);
 625 }
 626
 627 #ifdef SQLITE_TEST
 628 /*
 629 ** Get the suggested cache-size value.
 630 */
 631 int sqlite3PcacheGetCachesize(PCache *pCache){
 632   return numberOfCachePages(pCache);
 633 }
 634 #endif
 635
 636 /*
 637 ** Set the suggested cache-size value.
 638 */
 639 void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
 640   assert( pCache->pCache!=0 );
 641   pCache->szCache = mxPage;
 642   sqlite3GlobalConfig.pcache2.xCachesize(pCache->pCache,
 643                                          numberOfCachePages(pCache));
 644 }
 645
 646 /*
 647 ** Free up as much memory as possible from the page cache.
 648 */
 649 void sqlite3PcacheShrink(PCache *pCache){
 650   assert( pCache->pCache!=0 );
 651   sqlite3GlobalConfig.pcache2.xShrink(pCache->pCache);
 652 }
 653
 654 #if defined(SQLITE_CHECK_PAGES) || defined(SQLITE_DEBUG)
 655 /*
 656 ** For all dirty pages currently in the cache, invoke the specified
 657 ** callback. This is only used if the SQLITE_CHECK_PAGES macro is
 658 ** defined.
 659 */
 660 void sqlite3PcacheIterateDirty(PCache *pCache, void (*xIter)(PgHdr *)){
 661   PgHdr *pDirty;
 662   for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext){
 663     xIter(pDirty);
 664   }
 665 }
 666 #endif