Lines Matching full:page
210 /* Maximum page size. The upper bound on this value is 32768. This a limit
212 ** and the fact that the page size must be a power of 2.
216 ** a process operating on a database with a page-size of 65536 bytes
217 ** crashes, then an instance of SQLite compiled with the default page-size
227 ** The default size of a database page.
239 ** with page size SQLITE_DEFAULT_PAGE_SIZE. However, based on certain
1264 ** file will be doing page-aligned sector reads and writes in a random
1681 ** page size. ^If SQLite needs needs additional scratch memory beyond
1687 ** the database page cache with the default page cache implemenation.
1688 ** This configuration should not be used if an application-define page
1691 ** memory, the size of each page buffer (sz), and the number of pages (N).
1692 ** The sz argument should be the size of the largest database page
1694 ** page header. ^The page header size is 20 to 40 bytes depending on
1700 ** page cache memory is needed beyond what is provided by this option, then
1760 ** to a custom page cache implementation.)^ ^SQLite makes a copy of the
1761 ** object and uses it for page cache memory allocations.</dd>
1766 ** page cache implementation into that object.)^ </dd>
2081 ** CorruptionFollowingBusyError</a> wiki page for a discussion of why
5383 #define SQLITE_MUTEX_STATIC_LRU 6 /* lru page list */
5384 #define SQLITE_MUTEX_STATIC_LRU2 7 /* lru page list */
5516 ** controlled by [SQLITE_CONFIG_SCRATCH] and auxiliary page-cache
5535 ** <dd>This parameter returns the number of bytes of page cache
5541 ** no space was left in the page cache.</dd>)^
5684 ** CAPI3REF: Custom Page Cache Object
5698 ** CAPI3REF: Application Defined Page Cache.
5699 ** KEYWORDS: {page cache}
5703 ** register an alternative page cache implementation by passing in an
5705 ** heap memory used by SQLite is used by the page cache to cache data read
5707 ** custom page cache using this API, an application can control more
5722 ** required by the custom page cache implementation.
5742 ** will the page size of the database file that is to be cached plus an
5744 ** extra R bytes on each page to store metadata about the underlying
5745 ** database page on disk. The value of R depends
5753 ** never invoke xUnpin() except to deliberately delete a page.
5767 ** ^The xFetch() method is used to fetch a page and return a pointer to it.
5768 ** ^A 'page', in this context, is a buffer of szPage bytes aligned at an
5769 ** 8-byte boundary. ^The page to be fetched is determined by the key. ^The
5770 ** mimimum key value is 1. After it has been retrieved using xFetch, the page
5773 ** ^If the requested page is already in the page cache, then the page cache
5774 ** implementation must return a pointer to the page buffer with its content
5775 ** intact. ^(If the requested page is not already in the cache, then the
5780 ** <tr><th> createFlag <th> Behaviour when page is not already in cache
5781 ** <tr><td> 0 <td> Do not allocate a new page. Return NULL.
5782 ** <tr><td> 1 <td> Allocate a new page if it easy and convenient to do so.
5784 ** <tr><td> 2 <td> Make every effort to allocate a new page. Only return
5785 ** NULL if allocating a new page is effectively impossible.
5795 ** ^xUnpin() is called by SQLite with a pointer to a currently pinned page
5797 ** then the page should be evicted from the cache. In this case SQLite
5798 ** assumes that the next time the page is retrieved from the cache using
5800 ** zero, then the page is considered to be unpinned. ^The cache implementation
5804 ** call to xUnpin() unpins the page regardless of the number of prior calls
5808 ** page passed as the second argument from oldKey to newKey. ^If the cache
5814 ** existing cache entries with page numbers (keys) greater than or equal
5926 ** the destination is an in-memory database with a different page size
6710 ** The root-page of the master database table.
6957 ** For example, the free-page-count field is located at byte offset 36 of
6972 int iTable, /* Index of root page */
7501 ** This header file defines the interface that the sqlite page cache
7502 ** subsystem. The page cache subsystem reads and writes a file a page
7519 ** The type used to represent a page number. The first page in a file
7520 ** is called page 1. 0 is used to represent "not a page".
7535 ** Page number PAGER_MJ_PGNO is never used in an SQLite database (it is
7599 /* Functions used to obtain and release page references. */
7606 /* Operations on page references. */
7671 ** This header file defines the interface that the sqlite page cache
7681 ** Every page in the cache is controlled by an instance of the following
7685 void *pData; /* Content of this page */
7688 Pgno pgno; /* Page number for this page */
7689 Pager *pPager; /* The pager this page is part of */
7691 u32 pageHash; /* Hash of page content */
7699 i16 nRef; /* Number of users of this page */
7700 PCache *pCache; /* Cache that owns this page */
7707 #define PGHDR_DIRTY 0x002 /* Page has changed */
7709 ** writing this page to the database */
7714 /* Initialize and shutdown the page cache subsystem */
7718 /* Page cache buffer management:
7728 int szPage, /* Size of every page */
7729 int szExtra, /* Extra space associated with each page */
7736 /* Modify the page-size after the cache has been created. */
7744 /* One release per successful fetch. Page is pinned until released.
7750 SQLITE_PRIVATE void sqlite3PcacheDrop(PgHdr*); /* Remove page from cache */
7751 SQLITE_PRIVATE void sqlite3PcacheMakeDirty(PgHdr*); /* Make sure page is marked dirty */
7752 SQLITE_PRIVATE void sqlite3PcacheMakeClean(PgHdr*); /* Mark a single page as clean */
7755 /* Change a page number. Used by incr-vacuum. */
7761 /* Get a list of all dirty pages in the cache, sorted by page number */
7767 /* Clear flags from pages of the page cache */
7773 /* Return the total number of outstanding page references */
7776 /* Increment the reference count of an existing page */
8027 ** that all locks will fit on a single page even at the minimum page size.
8029 ** is set high so that we don't have to allocate an unused page except
8030 ** for very large databases. But one should test the page skipping logic
8739 ** Table.tnum is the page number for the root BTree page of the table in the
8746 ** page number. Transient tables are used to hold the results of a
8958 int tnum; /* Page containing root of this index in database file */
9673 int regRoot; /* Register holding root page number for new objects */
9884 sqlite3_pcache_methods pcache; /* Low-level page-cache interface */
9891 void *pPage; /* Page cache memory */
9892 int szPage; /* Size of each page in pPage[] */
10797 ** the database page that contains the pending byte. It never attempts
10798 ** to read or write that page. The pending byte page is set assign
11175 ** Reference: Meeus page 61
15693 /* Number of free pages for scratch and page-cache memory */
17607 u8 *aRow; /* Data for the current row, if all on one page */
22500 ** the first page of the database, no damage is done.
22684 ** the range of bytes on the locking page between SHARED_FIRST and
29666 ** This file implements that page cache.
29670 ** A complete page cache is an instance of this structure.
29674 PgHdr *pSynced; /* Last synced page in dirty page list */
29677 int szPage; /* Size of every page in this cache */
29678 int szExtra; /* Size of extra space for each page */
29680 int (*xStress)(void*,PgHdr*); /* Call to try make a page clean */
29683 PgHdr *pPage1; /* Reference to page 1 */
29718 ** Remove page pPage from the list of dirty pages.
29754 ** Add page pPage to the head of the dirty list (PCache1.pDirty is set to
29793 ** Initialize and shutdown the page cache subsystem. Neither of these
29820 int szPage, /* Size of every page */
29821 int szExtra, /* Extra space associated with each page */
29837 ** Change the page size for PCache object. The caller must ensure that there
29838 ** are no outstanding page references when this function is called.
29851 ** Try to obtain a page from the cache.
29854 PCache *pCache, /* Obtain the page from this cache */
29855 Pgno pgno, /* Page number to obtain */
29856 int createFlag, /* If true, create page if it does not exist already */
29857 PgHdr **ppPage /* Write the page here */
29889 /* Find a dirty page to write-out and recycle. First try to find a
29890 ** page that does not require a journal-sync (one with PGHDR_NEED_SYNC
29892 ** unreferenced dirty page.
29939 ** Decrement the reference count on a page. If the page is clean and the
29951 /* Move the page to the head of the dirty list. */
29959 ** Increase the reference count of a supplied page by 1.
29967 ** Drop a page from the cache. There must be exactly one reference to the
29968 ** page. This function deletes that reference, so after it returns the
29969 ** page pointed to by p is invalid.
29986 ** Make sure the page is marked as dirty. If it isn't dirty already,
29999 ** Make sure the page is marked as clean. If it isn't clean already,
30013 ** Make every page in the cache clean.
30034 ** Change the page number of page p to newPgno.
30049 ** Drop every cache entry whose page number is greater than "pgno". The
30051 ** other than page 1 with a page number greater than pgno.
30053 ** If there is a reference to page 1 and the pgno parameter passed to this
30054 ** function is 0, then the data area associated with page 1 is zeroed, but
30055 ** the page object is not dropped.
30163 ** Return a list of all dirty pages in the cache, sorted by page number.
30181 ** Return the number of references to the page supplied as an argument.
30245 ** This file implements the default page cache implementation (the
30248 ** If the default page cache implementation is overriden, then neither of
30261 /* Cache configuration parameters. Page size (szPage) and the purgeable
30290 unsigned int iKey; /* Key value (page number) */
30292 PCache1 *pCache; /* Cache that currently owns this page */
30319 PgFreeslot *pFree; /* Free page blocks */
30352 /******** Page Allocation/SQLITE_CONFIG_PCACHE Related Functions **************/
30356 ** supplied to use for the page-cache by passing the SQLITE_CONFIG_PAGECACHE
30431 ** Allocate a new page object initially associated with cache pCache.
30449 ** Free a page object allocated by pcache1AllocPage().
30533 ** This function is used internally to remove the page pPage from the
30562 ** Remove the page supplied as an argument from the hash table
30594 ** Discard all pages from cache pCache with a page number (key value)
30706 ** Fetch a page by key value.
30708 ** Whether or not a new page may be allocated by this function depends on
30710 ** page. 1 means allocate a new page if space is easily available. 2
30711 ** means to try really hard to allocate a new page.
30718 ** There are three different approaches to obtaining space for a page,
30722 ** copy of the requested page. If one is found, it is returned.
30724 ** 2. If createFlag==0 and the page is not already in the cache, NULL is
30727 ** 3. If createFlag is 1, and the page is not already in the cache,
30746 ** then attempt to recycle a page from the LRU list. If it is the right
30750 ** 5. Otherwise, allocate and return a new page buffer.
30785 /* Step 4. Try to recycle a page buffer if appropriate. */
30800 /* Step 5. If a usable page buffer has still not been found,
30832 ** Mark a page as unpinned (eligible for asynchronous recycling).
30841 /* It is an error to call this function if the page is already
30851 /* Add the page to the global LRU list. Normally, the page is added to
30852 ** the head of the list (last page to be recycled). However, if the
30853 ** reuseUnlikely flag passed to this function is true, the page is added
30854 ** to the tail of the list (first page to be recycled).
30909 ** Discard all unpinned pages in the cache with a page number equal to
30910 ** or greater than parameter iLimit. Any pinned pages with a page number
31449 ** This is the implementation of the page cache subsystem or "pager".
31483 ** The page cache as a whole is always in one of the following
31486 ** PAGER_UNLOCK The page cache is not currently reading or
31491 ** PAGER_SHARED The page cache is reading the database.
31503 ** PAGER_EXCLUSIVE The page cache is writing the database.
31515 ** The page cache comes up in PAGER_UNLOCK. The first time a
31521 ** called on an outstanding page which means that the pager must
31581 ** A open page cache is an instance of the following structure.
31628 ** The dbModified flag is set whenever a database page is dirtied.
31716 Bitvec *pInJournal; /* One bit for each page in the database file */
31727 u16 nExtra; /* Add this many bytes to each in-memory page */
31728 i16 nReserve; /* Number of unused bytes at end of each page */
31730 int pageSize; /* Number of bytes in a page */
31743 void (*xCodecSizeChng)(void*,int,int); /* Notify of page size changes */
31749 PCache *pPCache; /* Pointer to page cache object */
31782 ** of a 32-bit checksum on each page of data. The checksum covers both
31783 ** the page number and the pPager->pageSize bytes of data for the page.
31797 ** The size of the of each page record in the journal is given by
31821 ** The maximum legal page number is (2^31 - 1).
31844 ** Return true if it is necessary to write page *pPg into the sub-journal.
31845 ** A page needs to be written into the sub-journal if there exists one
31848 ** * The page-number is less than or equal to PagerSavepoint.nOrig, and
31849 ** * The bit corresponding to the page-number is not set in
31866 ** Return true if the page is already in the journal file.
31932 ** a database page may be written atomically, and
31934 ** to the page size.
31942 ** contains rollback data for exactly one page.
31950 int szPage; /* Page size */
31975 ** Return a 32-bit hash of the page data for pPage.
31995 ** that the page is either dirty or still matches the calculated page-hash.
32163 ** - 4 bytes: Random number used for page hash.
32164 ** - 4 bytes: Initial database page count.
32166 ** - 4 bytes: Database page size.
32196 ** Write the nRec Field - the number of page records that follow this
32204 ** rest of the journal file contains valid page records. This assumption
32233 /* The page size */
32257 ** database page size. Since the zHeader buffer is only Pager.pageSize
32278 ** page records following this header and *pDbSize is set to the size of the
32337 u32 iPageSize; /* Page-size field of journal header */
32341 /* Read the page-size and sector-size journal header fields. */
32348 /* Check that the values read from the page-size and sector-size fields
32357 /* If the either the page-size or sector-size in the journal-header is
32365 /* Update the page-size to match the value read from the journal.
32401 ** The master journal page checksum is the sum of the bytes in the master
32429 ** the master journal name. This is in case the previous page written to
32470 ** Find a page in the hash table given its page number. Return
32471 ** a pointer to the page or NULL if the requested page is not
32785 ** page of data and the current value of pPager->cksumInit.
32789 ** of the page data, starting with byte offset (pPager->pageSize%200).
32812 ** Read a single page from either the journal file (if isMainJrnl==1) or
32813 ** from the sub-journal (if isMainJrnl==0) and playback that page.
32814 ** The page begins at offset *pOffset into the file. The *pOffset
32815 ** value is increased to the start of the next page in the journal.
32821 ** If the page number of the page record read from the (sub-)journal file
32826 ** been played back. If the page at *pOffset has already been played back
32828 ** Make sure the pDone bit corresponding to the *pOffset page is set
32831 ** If the page record is successfully read from the (sub-)journal file
32839 ** * If the record page-number is illegal (0 or PAGER_MJ_PGNO), or
32858 PgHdr *pPg; /* An existing page in the cache */
32859 Pgno pgno; /* The page number of a page in journal */
32861 char *aData; /* Temporary storage for the page */
32872 /* Read the page number and page data from the journal or sub-journal
32882 /* Sanity checking on the page. This is more important that I originally
32909 ** page in the pager cache. In this case just update the pager cache,
32910 ** not the database file. The page is left marked dirty in this case.
32913 ** and a page is moved during an incremental vacuum then the page may
32915 ** during a Movepage() call, then the page may not be in the cache
32920 ** and the main file. The page is then marked not dirty.
32922 ** Ticket #1171: The statement journal might contain page content that is
32923 ** different from the page content at the start of the transaction.
32924 ** This occurs when a page is changed prior to the start of a statement
32927 ** for certain that original page contents are synced into the main rollback
32932 ** locked. (2) we know that the original page content is fully synced
32933 ** in the main journal either because the page is not in cache or else
32934 ** the page is marked as needSync==0.
32942 PAGERTRACE(("PLAYBACK %d page %d hash(%08x) %s\n",
32963 ** the database and the page is not in-memory, there is a potential
32964 ** problem. When the page is next fetched by the b-tree layer, it
32970 ** if the page is on the free-list at the start of the transaction, then
32973 ** The solution is to add an in-memory page to the cache containing
32974 ** the data just read from the sub-journal. Mark the page as dirty
32975 ** and if the pager requires a journal-sync, then mark the page as
32986 /* No page should ever be explicitly rolled back that is in use, except
32987 ** for page 1 which is held in use in order to keep the lock on the
32988 ** database active. However such a page may be rolled back as a result
32997 /* If the contents of this page were just restored from the main
32999 ** transaction was first opened. In this case we can mark the page
33002 ** There is one exception to this rule. If the page is being rolled
33005 ** to mark the page as clean. This is because marking the page as
33006 ** clean will clear the PGHDR_NEED_SYNC flag. Since the page is
33008 ** the PGHDR_NEED_SYNC flag is cleared, if the page is written to
33020 /* If this was page 1, then restore the value of Pager.dbFileVers.
33026 /* Decode the page just read from disk */
33073 ** a couple of kilobytes or so - potentially larger than the page
33249 ** (2) 4 byte big-endian integer which is the number of valid page records
33251 ** number of page records from the journal size.
33258 ** (6) 4 byte big-endian integer which is the page size.
33261 ** + 4 byte page number.
33269 ** valid page entries in the journal. In most cases, you can compute the
33284 ** journal file then all pages up to the first corrupted page are rolled
33308 int needPagerReset; /* True to reset page prior to first page rollback */
33404 ** database file and/or page cache.
33504 ** Throughout the rollback process, each time a page is rolled back, the
33506 ** implementation below). This is used to ensure that a page is only
33514 ** (or transaction). No page with a page-number greater than this value
33547 ** There might be records in the main journal that have a page number
33592 /* Finally, rollback pages from the sub-journal. Page that were
33728 ** Report the current page size and number of reserved bytes back
33743 ** Change the page size used by the Pager object. The new page size
33752 ** * the new page size (value of *pPageSize) is valid (a power
33755 ** * there are no outstanding page references, and
33760 ** then the pager object page size is set to *pPageSize.
33762 ** If the page size is changed, then this function uses sqlite3PagerMalloc()
33764 ** fails, SQLITE_NOMEM is returned and the page size remains unchanged.
33767 ** If the page size is not changed, either because one of the enumerated
33770 ** then *pPageSize is set to the old, retained page size before returning.
33803 ** Return a pointer to the "temporary page" buffer held internally
33805 ** entire content of a database page. This buffer is used internally
33815 ** Attempt to set the maximum database page count if mxPage is positive.
33817 ** maximum page count below the current size of the database.
33819 ** Regardless of mxPage, return the current maximum page count.
33883 ** with pPager. Normally, this is calculated as (<db file size>/<page-size>).
33884 ** However, if the file is between 1 and <page-size> bytes in size, then
33885 ** this is considered a 1 page file.
33998 ** following is true for all dirty pages currently in the page-cache:
34000 ** a) The page number is less than or equal to the size of the
34003 ** b) if the page content were written at this time, it would not
34008 ** dirty page were to be discarded from the cache via the pagerStress()
34009 ** routine, pagerStress() would not write the current page content to
34012 ** content of the page. However, since this content is not present in either
34045 ** Shutdown the page cache. Free all memory and close all files.
34049 ** and their memory is freed. Any attempt to use a page associated
34050 ** with this page cache after this function returns will likely
34097 ** Return the page number for page pPg.
34105 ** Increment the reference count for page pPg.
34146 ** page currently held in memory before returning SQLITE_OK. If an IO
34259 ** a page is skipped if it meets either of the following criteria:
34261 ** * The page number is greater than Pager.dbSize, or
34262 ** * The PGHDR_DONT_WRITE flag is set on the page.
34264 ** If writing out a page causes the database file to grow, Pager.dbFileSize
34265 ** is updated accordingly. If page 1 is written out, then the value cached
34311 /* If there are dirty pages in the page cache with page numbers greater
34316 ** Also, do not write out any page that has the PGHDR_DONT_WRITE flag
34328 /* Write out the page data. */
34331 /* If page 1 was just written, update Pager.dbFileVers to match
34333 ** page caused the database file to grow, update dbFileSize.
34345 PAGERTRACE(("STORE %d page %d hash(%08x)\n",
34351 PAGERTRACE(("NOSTORE %d page %d\n", PAGERID(pPager), pgno));
34363 ** Append a record of the current state of page pPg to the sub-journal.
34384 PAGERTRACE(("STMT-JOURNAL %d page %d\n", PAGERID(pPager), pPg->pgno));
34405 ** database). The second argument is a reference to a page that is
34406 ** currently dirty but has no outstanding references. The page
34414 ** If successful, sqlite3PcacheMakeClean() is called on the page and
34416 ** page clean, the IO error code is returned. If the page cannot be
34431 ** set of pages are synced to disk together. So, if the page this function
34434 ** just have to go ahead and allocate a new page buffer instead of
34458 /* If the page number of this page is larger than the current size of
34466 ** <journal page X>
34467 ** <modify page X>
34470 ** pagerStress(page X)
34473 ** If (X>Y), then when pagerStress is called page X will not be written
34475 ** following the "ROLLBACK TO sp" statement, reading page X will read
34476 ** data from the database file. This will be the copy of page X as it
34480 ** The solution is to write the current data for page X into the
34491 /* Write the contents of the page out to the database file. */
34497 /* Mark the page as clean. */
34499 PAGERTRACE(("STRESS %d page %d\n", PAGERID(pPager), pPg->pgno));
34520 ** along with each page reference. This space is available to the user
34541 int nExtra, /* Extra bytes append to each in-memory page */
34558 u16 szPageDflt = SQLITE_DEFAULT_PAGE_SIZE; /* Default page size */
34667 ** choose a default page size in case we have to create the
34668 ** database file. The default page size is the maximum of:
34672 ** + The largest page size that can be written atomically.
34701 ** In this case we accept the default page size and delay actually
34902 ** Read the content for page pPg out of the database file and into
34906 ** If page 1 is read, then the value of Pager.dbFileVers[] is set to
34913 Pager *pPager = pPg->pPager; /* Pager object associated with page pPg */
34914 Pgno pgno = pPg->pgno; /* Page number to read */
34940 PAGERTRACE(("FETCH %d page %d hash(%08x)\n",
34966 ** the contents of the page cache and rolling back any open journal
35173 ** Acquire a reference to page number pgno in pager pPager (a page
35177 ** If the requested page is already in the cache, it is returned.
35178 ** Otherwise, a new page object is allocated and populated with data
35180 ** choose not to allocate a new page object and may reuse an existing
35183 ** The extra data appended to a page is always initialized to zeros the
35184 ** first time a page is loaded into memory. If the page requested is
35186 ** data is left as it was when the page object was last used.
35188 ** If the database image is smaller than the requested page or if a
35190 ** requested page is not already stored in the cache, then no
35192 ** page is initialized to all zeros.
35195 ** of the page. This occurs in two seperate scenarios:
35197 ** a) When reading a free-list leaf page from the database, and
35200 ** a new page into the cache to populate with the data read
35207 ** savepoints are set. This means if the page is made writable at any
35215 ** to find a page in the in-memory cache first. If the page is not already
35224 Pgno pgno, /* Page number to fetch */
35225 DbPage **ppPage, /* Write a pointer to the page here */
35239 ** Otherwise, request the page from the PCache layer. */
35258 ** the page. Return without further ado. */
35264 /* The pager cache has created a new page. Its content needs to
35272 /* The maximum page number is 2^31. Return SQLITE_CORRUPT if a page
35273 ** number greater than this, or the unused locking-page, is requested. */
35292 ** page that does not need to be journaled. Nevertheless, be sure
35333 ** Acquire a page if it is already in the in-memory cache. Do
35334 ** not read the page from disk. Return a pointer to the page,
35335 ** or 0 if the page is not in cache. Also, return 0 if the
35341 ** in the page if the page is not already in cache. This routine
35342 ** returns NULL if the page is not in cache or if a disk I/O error
35356 ** Release a page reference.
35358 ** If the number of references to the page drop to zero, then the
35359 ** page is added to the LRU list. When all references to all pages
35567 ** Mark a single data page as writeable. The page is written into the
35568 ** main journal or sub-journal as required. If the page is written into
35596 /* Mark the page as dirty. If the page has already been written
35604 /* If we get this far, it means that the page needs to be
35624 ** EXCLUSIVE lock on the main database file. Write the current page to
35632 /* We should never write to the journal file the page that
35651 PAGERTRACE(("JOURNAL %d page %d needSync=%d hash(%08x)\n",
35656 ** page in the block above, set the need-sync flag for the page.
35658 ** playback_one_page() will think that the page needs to be restored
35689 PAGERTRACE(("APPEND %d page %d needSync=%d\n",
35695 /* If the statement journal is open and the page is not in it,
35696 ** then write the current page to the statement journal. Note that
35715 ** Mark a data page as writeable. This routine must be called before
35716 ** making changes to a page. The caller must check the return value
35717 ** of this function and be careful not to change any page data unless
35737 Pgno pg1; /* First page of the sector pPg is located on. */
35740 int needSync = 0; /* True if any page has PGHDR_NEED_SYNC */
35749 /* This trick assumes that both the page-size and sector-size are
35751 ** of the first page of the sector pPg is located on.
35817 ** Return TRUE if the page given in the argument was previously passed
35819 ** to change the content of the page.
35830 ** write the information on page pPg back to the disk, even though
35831 ** that page might be marked as dirty. This happens, for example, when
35832 ** the page has been added as a leaf of the freelist and so its
35836 ** on the given page is unused. The pager marks the page as clean so
35845 PAGERTRACE(("DONT_WRITE page %d of %d\n", pPg->pgno, PAGERID(pPager)));
35861 ** sqlite3PagerWrite() on page 1, then modifying the contents of the
35862 ** page data. In this case the file will be updated when the current
35868 ** by writing an updated version of page 1 using a call to the
35894 PgHdr *pPgHdr; /* Reference to page 1 */
35899 /* Open page 1 of the file for writing. */
35903 /* If page one was fetched successfully, and this function is not
35904 ** operating in direct-mode, make page 1 writable. When not in
35905 ** direct mode, page 1 is always held in cache and hence the PagerGet()
35918 /* If running in direct mode, write the contents of page 1 to the file. */
35931 /* Release the page reference. */
36013 ** blocks of size page-size, and
36015 ** * Exactly one page has been modified and store in the journal file.
36039 ** following call will modify the in-memory representation of page 1
36040 ** to include the updated change counter and then write page 1
36060 ** Before reading the pages with page numbers larger than the
36074 const Pgno iSkip = PAGER_MJ_PGNO(pPager); /* Pending lock page */
36079 PgHdr *pPage; /* Page to journal */
36284 ** Return the number of references to the specified page.
36518 ** Move the page pPg to location pgno in the file.
36520 ** There must be no references to the page previously located at
36521 ** pgno (which we call pPgOld) though that page is allowed to be
36522 ** in cache. If the page previously located at pgno is not already
36525 ** References to the page pPg remain valid. Updating any
36527 ** allocated along with the page) is the responsibility of the caller.
36531 ** has been removed (CREATE INDEX needs to move a page when a statement
36534 ** If the fourth argument, isCommit, is non-zero, then this page is being
36536 ** is being committed. In this case, it is guaranteed that the database page
36543 PgHdr *pPgOld; /* The page being overwritten. */
36546 Pgno origPgno; /* The original page number */
36551 ** the page we are moving from.
36558 /* If the page being moved is dirty and has not been saved by the latest
36559 ** savepoint, then save the current contents of the page into the
36563 ** <journal page X, then modify it in memory>
36565 ** <Move page X to location Y>
36568 ** If page X were not written to the sub-journal here, it would not
36583 PAGERTRACE(("MOVE %d page %d (needSync=%d) moves to %d\n",
36587 /* If the journal needs to be sync()ed before page pPg->pgno can
36591 ** the journal needs to be sync()ed before database page pPg->pgno
36601 /* If the cache contains a page with page-number pgno, remove it
36603 ** page pgno before the 'move' operation, it needs to be retained
36604 ** for the page moved there.
36613 ** need to rollback later. Just move the page out of the way. */
36628 ** sync()ed before any data is written to database file page needSyncPgno.
36629 ** Currently, no such page exists in the page-cache and the
36631 ** loading the page into the pager-cache and setting the PgHdr.needSync
36634 ** If the attempt to load the page into the page-cache fails, (due
36636 ** array. Otherwise, if the page is loaded and written again in
36662 ** For an in-memory database, make sure the original page continues
36664 ** as the original page since it has already been allocated.
36676 ** Return a pointer to the data for the specified page.
36685 ** allocated along with the specified page.
36820 ** The basic idea is that each page of the file contains N database
36827 ** All of the keys on the page that Ptr(0) points to have values less
36828 ** than Key(0). All of the keys on page Ptr(1) and its subpages have
36837 ** BTrees. Each BTree is identified by the index of its root page. The
36840 ** page. If the payload is larger than the preset amount then surplus
36843 ** page has a small header which contains the Ptr(N) pointer and other
36848 ** The file is divided into pages. The first page is called page 1,
36849 ** the second is page 2, and so forth. A page number of zero indicates
36850 ** "no such page". The page size can be any power of 2 between 512 and 32768.
36851 ** Each page can be either a btree page, a freelist page, an overflow
36852 ** page, or a pointer-map page.
36854 ** The first page is always a btree page. The first 100 bytes of the first
36855 ** page contain a special header (the "file header") that describes the file.
36860 ** 16 2 Page size in bytes.
36863 ** 20 1 Bytes of unused space at the end of each page
36869 ** 32 4 First freelist page
36875 ** 48 4 Size of page cache
36876 ** 52 4 Largest root-page (auto/incr_vacuum)
36891 ** space in a page that can be consumed by a single cell for standard
36894 ** on one page. Thus the default max embedded payload fraction is 64.
36897 ** payload is spilled to overflow pages. Once an overflow page is allocated,
36907 ** cell pointer array, and the cell content area. Page 1 also has a 100-byte
36908 ** file header that occurs before the page header.
36911 ** | file header | 100 bytes. Page 1 only.
36913 ** | page header | 8 bytes for leaves. 12 bytes for interior nodes
36926 ** The page headers looks like this:
36931 ** 3 2 number of cells on this page
36936 ** The flags define the format of this btree page. The leaf flag means that
36937 ** this page has no children. The zerodata flag means that this page carries
36942 ** The cell pointer array begins on the first byte after the page header.
36944 ** offsets from the beginning of the page to the cell content in the cell
36947 ** be easily added without having to defragment the page.
36949 ** Cell content is stored at the very end of the page and grows toward the
36950 ** beginning of the page.
36959 ** in the page header at offset 7.
36966 ** the end of the page. Pointers to the cells are in the cell pointer array
36967 ** that immediately follows the page header. Cells is not necessarily
36992 ** 4 Page number of the left child. Omitted if leaf flag is set.
36996 ** 4 First page of the overflow chain. Omitted if no overflow
36998 ** Overflow pages form a linked list. Each page except the last is completely
36999 ** filled with data (pagesize - 4 bytes). The last page can have as little
37003 ** 4 Page number of next overflow page
37007 ** file header points to the first in a linked list of trunk page. Each trunk
37008 ** page points to multiple leaf pages. The content of a leaf page is
37009 ** unspecified. A trunk page looks like this:
37012 ** 4 Page number of next trunk page
37013 ** 4 Number of leaf pointers on this page
37018 /* The following value is the maximum cell size assuming a maximum page
37023 /* The maximum number of cells on a single page of the database. This
37025 ** plus 2 bytes for the index to the cell in the page header). Such
37051 ** Page type flags. An ORed combination of these flags appear as the
37052 ** first byte of on-disk image of every BTree page.
37060 ** As each page of the file is loaded into memory, an instance of the following
37062 ** information about the page that is decoded from the raw file page.
37064 ** The pParent field points back to the parent page. This allows us to
37066 ** unref() the parent page pointer when this page is no longer referenced.
37077 u8 hasData; /* True if this page stores data */
37078 u8 hdrOffset; /* 100 for page 1. 0 otherwise */
37083 u16 nFree; /* Number of free bytes on the page */
37084 u16 nCell; /* Number of cells on this page, local and ovfl */
37085 u16 maskPage; /* Mask for page offset */
37090 BtShared *pBt; /* Pointer to BtShared that this page
37091 u8 *aData; /* Pointer to disk image of the page data */
37092 DbPage *pDbPage; /* Pager page handle */
37093 Pgno pgno; /* Page number for this page */
37097 ** The in-memory image of a disk page has the auxiliary information appended
37106 ** is opened on the table with root page BtShared.iTable. Locks are removed
37112 Pgno iTable; /* Root page of table */
37153 BtLock lock; /* Object used to lock page 1 */
37204 Pager *pPager; /* The page cache */
37207 MemPage *pPage1; /* First page of the database */
37209 u8 pageSizeFixed; /* True if the page size can no longer be changed */
37214 u16 pageSize; /* Total number of bytes on a page */
37215 u16 usableSize; /* Number of usable bytes on each page */
37240 ** based on information extract from the raw disk page.
37250 u16 iOverflow; /* Offset to overflow page number. Zero if no overflow */
37251 u16 nSize; /* Size of the cell content on the main b-tree page */
37284 Pgno pgnoRoot; /* The root page of this tree */
37296 Pgno *aOverflow; /* Cache of overflow page locations */
37298 i16 iPage; /* Index of current page in apPage */
37299 MemPage *apPage[BTCURSOR_MAX_DEPTH]; /* Pages from root to current page */
37334 ** The database page the PENDING_BYTE occupies. This page is never used.
37340 ** database page. The first argument to each is the number of usable
37341 ** bytes on each page of the database (often 1024). The second is the
37342 ** page number to look up in the pointer map.
37344 ** PTRMAP_PAGENO returns the database page number of the pointer-map
37345 ** page that stores the required pointer. PTRMAP_PTROFFSET returns
37348 ** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,
37350 ** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements
37358 ** The pointer map is a lookup table that identifies the parent page for
37359 ** each child page in the database file. The parent page is the page that
37360 ** contains a pointer to the child. Every page in the database contains
37361 ** 0 or 1 parent pages. (In this context 'database page' refers
37362 ** to any page that is not part of the pointer map itself.) Each pointer map
37363 ** entry consists of a single byte 'type' and a 4 byte parent page number.
37367 ** position in the file to another as part of autovacuum. When a page
37369 ** new location. The pointer map is used to locate the parent page quickly.
37371 ** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
37374 ** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number
37377 ** PTRMAP_OVERFLOW1: The database page is the first page in a list of
37378 ** overflow pages. The page number identifies the page that
37379 ** contains the cell with a pointer to this overflow page.
37381 ** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of
37382 ** overflow pages. The page-number identifies the previous
37383 ** page in the overflow page list.
37385 ** PTRMAP_BTREE: The database page is a non-root btree page. The page number
37386 ** identifies the parent page in the btree.
37425 int *anRef; /* Number of times each page is referenced */
37877 ** table with root page iRoot. Return 1 if it does and 0 if not.
37879 ** For example, when writing to a table with root-page iRoot via
37885 ** caller should have first obtained a lock specifying the root page of
37891 ** Instead of a lock on the table/index rooted at page iRoot, the caller may
37892 ** hold a write-lock on the schema table (root page 1). This is also
37897 Pgno iRoot, /* Root page of b-tree */
37924 /* Figure out the root-page that the lock should be held on. For table
37925 ** b-trees, this is just the root page of the b-tree being read or
37926 ** written. For index b-trees, it is the root page of the associated
37940 /* Search for the required lock. Either a write-lock on root-page iTab, a
37972 ** rooted at page iRoot, one should call:
37992 ** (READ_LOCK or WRITE_LOCK) on the table with root-page iTab. Return
38052 ** Add a lock on the table with root-page iTable to the shared-btree used
38209 ** Invalidate the overflow page-list cache for cursor pCur, if any.
38218 ** Invalidate the overflow page-list cache for all cursors opened
38236 ** cursors open on any row within the table with root-page pgnoRoot.
38266 ** when a page that previously contained data becomes a free-list leaf
38267 ** page.
38273 ** 1) When all data is deleted from a page and the page becomes
38274 ** a free-list leaf page, the page is not written to the database
38276 ** such a page is not even journalled (as it will not be modified,
38279 ** 2) When a free-list leaf page is reused, its content is not read
38285 ** a page is moved to the free-list and then reused within the same
38286 ** transaction, a problem comes up. If the page is not journalled when
38292 ** The solution is the BtShared.pHasContent bitvec. Whenever a page is
38293 ** moved to become a free-list leaf page, the corresponding bit is
38294 ** set in the bitvec. Whenever a leaf page is extracted from the free-list,
38320 ** This function is called when a free-list leaf page is removed from the
38322 ** page from the pager layer with the 'no-content' flag set. True otherwise.
38392 ** the table with root-page iRoot. Usually, this is called just before cursor
38507 ** Given a page number of a regular database page, return the page
38508 ** number for the pointer-map page that contains the entry for the
38509 ** input page number.
38527 ** This routine updates the pointer map entry for page number 'key'
38528 ** so that it maps to type 'eType' and parent page number 'pgno'.
38535 DbPage *pDbPage; /* The pointer map page */
38537 Pgno iPtrmap; /* The pointer map page number */
38538 int offset; /* Offset in pointer map page */
38544 /* The master-journal page number must never be used as a pointer map page */
38581 ** This routine retrieves the pointer map entry for page 'key', writing
38582 ** the type and parent page number to *pEType and *pPgno respectively.
38586 DbPage *pDbPage; /* The pointer map page */
38587 int iPtrmap; /* Pointer map page index */
38588 u8 *pPtrmap; /* Pointer map page data */
38618 ** Given a btree page and a cell index (0 means the first cell on
38619 ** the page, 1 means the second cell, and so forth) return a pointer
38659 MemPage *pPage, /* Page containing the cell */
38691 ** on the local page. No overflow is required.
38702 /* If the payload will not fit completely on the local page, we have
38732 MemPage *pPage, /* Page containing the cell */
38741 ** data area of the btree-page. The return number includes the cell
38742 ** data header and the local payload, but not any overflow page or
38808 ** If the cell pCell, part of page pPage contains a pointer
38809 ** to an overflow page, insert an entry into the pointer-map
38810 ** for the overflow page.
38827 ** Defragment the page given. All Cells are moved to the
38828 ** end of the page and all free space is collected into one
38835 int hdr; /* Offset to the page header */
38837 int usableSize; /* Number of usable bytes on a page */
38840 int nCell; /* Number of cells on the page */
38841 unsigned char *data; /* The page data */
38910 ** Allocate nByte bytes of space from within the B-Tree page passed
38929 int usableSize; /* Usable size of the page */
38972 ** fragmented bytes within the page. */
39003 ** is no way that the allocation can extend off the end of the page.
39043 ** cell content area exceeds the value in the page header. If these
39103 ** Decode the flags byte (the first byte of the header) for a page
39142 ** Return SQLITE_OK on success. If we see that the page does
39143 ** not contain a well-formed database page, then return
39145 ** guarantee that the page is well-formed. It only shows that
39158 u8 hdr; /* Offset to beginning of page header */
39161 u16 usableSize; /* Amount of usable space on each page */
39162 u16 cellOffset; /* Offset from start of page to first cell pointer */
39163 u16 nFree; /* Number of unused bytes on the page */
39181 /* To many cells for a single page. The page must be corrupt */
39186 /* A malformed database page might cause us to read past the end
39187 ** of page when parsing a cell.
39190 ** past the end of a page boundary and causes SQLITE_CORRUPT to be
39218 /* Compute the total free space on the page */
39224 /* Start of free block is off the page */
39231 ** the free-block must lie on the database page. */
39241 ** of the page, then the page must be corrupted. This check also
39243 ** area, according to the page header, lies within the page.
39255 ** Set up a raw page so that it looks like a database page holding
39304 ** Get a page from the pager. Initialize the MemPage.pBt and
39308 ** the content of the page at this time. So do not go to the disk
39310 ** If in the future we call sqlite3PagerWrite() on this page, that
39316 Pgno pgno, /* Number of the page to fetch */
39317 MemPage **ppPage, /* Return the page in this parameter */
39318 int noContent /* Do not load page content if true */
39331 ** Retrieve a page from the pager cache. If the requested page is not
39359 ** Get a page from the pager and initialize it. This routine is just a
39368 Pgno pgno, /* Number of the page to get */
39369 MemPage **ppPage /* Write the page pointer here */
39383 /* If the requested page number was either 0 or greater than the page
39384 ** number of the last page in the database, this function should return
39412 ** the transaction, for each page restored this routine is called.
39415 ** page to agree with the restored data.
39425 /* pPage might not be a btree page; it might be an overflow page
39426 ** or ptrmap page or a free page. In those cases, the following
39429 ** btreeInitPage() be called on every btree page so we make
39430 ** the call for every page that comes in for re-initing. */
39473 u8 nReserve; /* Byte of unused space on each page */
39869 ** Change the default pages size and the number of reserved bytes per page.
39870 ** Or, if the page size has already been fixed, return SQLITE_READONLY
39873 ** The page size must be a power of 2 between 512 and 65536. If the page
39874 ** size supplied does not meet this constraint then the page size is not
39877 ** Page sizes are constrained to be a power of two so that the region
39880 ** at the beginning of a page.
39883 ** bytes per page is left unchanged.
39885 ** If the iFix!=0 then the pageSizeFixed flag is set so that the page size
39916 ** Return the currently defined page size
39923 ** Return the number of bytes of space at the end of every page that
39936 ** Set the maximum page count for a database if mxPage is positive.
39938 ** Regardless of the value of mxPage, return the maximum page count.
40055 /* After reading the first page of the database assuming a page size
40056 ** of BtShared.pageSize, we have discovered that the page-size is
40059 ** again with the correct page-size.
40082 ** cells can will fit on one page. We assume a 10-byte page header.
40088 ** 4-byte overflow page pointer
40091 ** page pointer.
40116 ** this routine unrefs the first page of the database file which
40135 ** into a new empty database by initializing the first page of
40257 ** page 1. So if some other shared-cache client already has a write-lock
40258 ** on page 1, the transaction cannot be opened. */
40266 ** reading page 1 it discovers that the page-size of the database
40268 ** pBt->pageSize to the page-size of the file on disk.
40332 ** Set the pointer-map entries for all children of page pPage. Also, if
40338 int nCell; /* Number of cells in page pPage */
40373 ** Somewhere on pPage is a pointer to page iFrom. Modify this pointer so
40377 ** PTRMAP_BTREE: pPage is a btree-page. The pointer points at a child
40378 ** page of pPage.
40380 ** PTRMAP_OVERFLOW1: pPage is a btree-page. The pointer points at an overflow
40381 ** page pointed to by one of the cells on pPage.
40383 ** PTRMAP_OVERFLOW2: pPage is an overflow-page. The pointer points at the next
40384 ** overflow page in the list.
40390 /* The pointer is always the first 4 bytes of the page in this case. */
40437 ** Move the open database page pDbPage to location iFreePage in the
40441 ** the journal needs to be sync()ed before database page pDbPage->pgno
40443 ** page.
40447 MemPage *pDbPage, /* Open page to move */
40449 Pgno iPtrPage, /* Pointer map 'page-no' entry for pDbPage */
40453 MemPage *pPtrPage; /* The page that contains a pointer to pDbPage */
40463 /* Move page iDbPage from its current location to page number iFreePage */
40464 TRACE(("AUTOVACUUM: Moving %d to free page %d (ptr page %d type %d)\n",
40472 /* If pDbPage was a btree-page, then it may have child pages and/or cells
40476 ** If pDbPage is an overflow page, then the first 4 bytes may store a
40477 ** pointer to a subsequent overflow page. If this is the case, then
40478 ** the pointer map needs to be updated for the subsequent overflow page.
40495 /* Fix the database pointer on page iPtrPage that pointed at iDbPage so
40527 ** database so that the last page of the file currently in use
40565 /* Remove the page from the files free-list. This is not required
40580 Pgno iFreePg; /* Index of free page to move pLastPg to */
40588 /* If nFin is zero, this loop runs exactly once and page pLastPg
40589 ** is swapped with the first free page pulled off the free list.
40592 ** looping until a free-page located within the first nFin pages
40684 Pgno iFree; /* The next page to be freed */
40685 int nEntry; /* Number of entries on one ptrmap page */
40690 /* It is not possible to create a database for which the final page
40691 ** is either a pointer-map page or the pending-byte page. If one
40964 ** call btreeGetPage() on page 1 again to make
41048 ** Create a new cursor for the BTree whose root is on the page
41072 ** No checking is done to make sure that page iTable really is the
41073 ** root page of a b-tree. If it is not, then the cursor acquired
41081 int iTable, /* Root page of table to open */
41129 int iTable, /* Root page of table to open */
41167 ** as pCur and having the same root page number as pCur. The value is
41330 ** Given the page number of an overflow page in the database (parameter
41331 ** ovfl), this function finds the page number of the next page in the
41333 ** pointer-map data instead of reading the content of page ovfl to do so.
41337 ** The page number of the next overflow page in the linked list is
41338 ** written to *pPgnoNext. If page ovfl is the last page in its linked
41342 ** to page number pOvfl was obtained, then *ppPage is set to point to that
41350 Pgno ovfl, /* Current overflow page number */
41352 Pgno *pPgnoNext /* OUT: Next overflow page number */
41362 /* Try to find the next page in the overflow list using the
41363 ** autovacuum pointer-map pages. Guess that the next page in
41364 ** the overflow list is page number (ovfl+1). If that guess turns
41365 ** out to be wrong, fall back to loading the data of page
41366 ** number ovfl to determine the next page number.
41406 ** Copy data from a buffer to a page, or from a page to a buffer.
41408 ** pPayload is a pointer to data stored on database page pDbPage.
41417 void *pPayload, /* Pointer to page data */
41420 int eOp, /* 0 -> copy from page, 1 -> copy to page */
41421 DbPage *pDbPage /* Page containing pPayload */
41424 /* Copy data from buffer to page (a write operation) */
41431 /* Copy data from page to buffer (a read operation) */
41447 ** The content being read or written might appear on the main page
41452 ** allocates space for and lazily popluates the overflow page-list
41456 ** Once an overflow page-list cache has been allocated, it may be
41459 ** mode, the following events may invalidate an overflow page-list cache.
41463 ** * Creating a table (may require moving an overflow page).
41476 MemPage *pPage = pCur->apPage[pCur->iPage]; /* Btree page of current entry */
41495 /* Check if data must be read/written to/from the btree page itself. */
41510 const u32 ovflSize = pBt->usableSize - 4; /* Bytes content per ovfl page */
41518 ** one entry for each overflow page in the overflow chain. The
41519 ** page number of the first overflow page is stored in aOverflow[0],
41533 /* If the overflow page-list cache has been allocated and the
41534 ** entry for the first required overflow page is valid, skip
41547 /* If required, populate the overflow page-list cache. */
41555 /* The only reason to read this page is to obtain the page
41556 ** number for the next page in the overflow chain. The page
41558 ** page-list cache, if any, then fall back to the getOverflowPage()
41569 /* Need to read this page properly. It contains some of the
41655 ** and data to fit on the local page and for there to be no overflow
41662 ** page of the database. The data might change or move the next time
41706 ** b-tree page. Write the number of available bytes into *pAmt.
41738 ** Move the cursor down to a new child page. The newPgno argument is the
41739 ** page number of the child page to move to.
41741 ** This function returns SQLITE_CORRUPT if the page-header flags field of
41742 ** the new child page does not match the flags field of the parent (i.e.
41743 ** if an intkey page appears to be the parent of a non-intkey page, or
41774 ** Page pParent is an internal (non-leaf) tree page. This function
41775 ** asserts that page number iChild is the left-child if the iIdx'th
41776 ** cell in page pParent. Or, if iIdx is equal to the total number of
41777 ** cells in pParent, that page number iChild is the right-child of
41778 ** the page.
41793 ** Move the cursor up to the parent page.
41796 ** to the page we are coming from. If we are coming from the
41797 ** right-most child page then pCur->idx is set to one more than
41817 ** Move the cursor to point to the root page of its b-tree structure.
41819 ** If the table has a virtual root page, then the cursor is moved to point
41820 ** to the virtual root page instead of the actual root page. A table has a
41821 ** virtual root page when the actual root page contains no cells and a
41822 ** single child page. This can only happen with the table rooted at page 1.
41826 ** cell located on the root (or virtual root) page and the cursor state
41830 ** page-header flags indicate that the [virtual] root-page is the expected
41831 ** kind of b-tree page (i.e. if when opening the cursor the caller did not
41879 /* Assert that the root page is of the correct type. This must be the
41880 ** case as the call to this function that loaded the root-page (either
41884 ** to the page. */
41930 ** page to which it is currently pointing. Notice the difference
41933 ** finds the right-most entry beneath the *page*.
42030 ** left pointing at a leaf page which would hold the entry if it
42098 /* pPage->nCell must be greater than zero. If this is the root-page
42100 ** not run. If this is not the root-page, then the moveToChild() routine
42102 ** be the right kind (index or table) of b-tree page. Otherwise
42137 /* The maximum supported page-size is 32768 bytes. This means that
42139 ** page is at most 8198 bytes, which may be stored as a 2-byte
42142 ** stored entirely within the b-tree page by inspecting the first
42149 ** b-tree page. */
42155 ** fits entirely on the main b-tree page. */
42372 ** Allocate a new page from the database file.
42374 ** The new page is marked as dirty. (In other words, sqlite3PagerWrite()
42375 ** has already been called on the new page.) The new page has also
42377 ** sqlite3PagerUnref() on the new page when it is done.
42384 ** locate a page close to the page number "nearby". This can be used in an
42388 ** If the "exact" parameter is not 0, and the page-number nearby exists
42421 ** shows that the page 'nearby' is somewhere on the free-list, then
42422 ** the entire-list will be searched for that page.
42439 ** first free-list trunk page. iPrevTrunk is initially 1.
42446 ** is not true. Otherwise, it runs once for each trunk-page on the
42447 ** free-list until the page 'nearby' is located.
42470 ** So extract the trunk page itself and use it as the newly
42471 ** allocated page */
42488 /* The list is being searched and this trunk page is the page
42505 /* The trunk page is required by the caller but it contains
42507 ** page in this case.
42603 /* There are no pages on the freelist, so create a new page at the
42614 /* If *pPgno refers to a pointer-map page, allocate two new pages
42615 ** at the end of the file instead of one. The first allocated page
42616 ** becomes a new pointer-map page, the second is used by the caller.
42619 TRACE(("ALLOCATE: %d from end of file (pointer-map page)\n", *pPgno));
42660 ** This function is used to add page iPage to the database file free-list.
42661 ** It is assumed that the page is not already a part of the free-list.
42665 ** corresponding to page iPage handy, it may pass it as the second value.
42672 MemPage *pTrunk = 0; /* Free-list trunk page */
42673 Pgno iTrunk = 0; /* Page number of free-list trunk page */
42674 MemPage *pPage1 = pBt->pPage1; /* Local reference to page 1 */
42675 MemPage *pPage; /* Page being freed. May be NULL. */
42690 /* Increment the free page count on pPage1 */
42709 ** to indicate that the page is free.
42718 ** trunk page in the free-list is full, then this page will become a
42719 ** new free-list trunk page. Otherwise, it will become a leaf of the
42720 ** first trunk page in the current free-list. This block tests if it
42721 ** is possible to add the page as a new free-list leaf.
42724 u32 nLeaf; /* Initial number of leaf cells on trunk page */
42739 /* In this case there is room on the trunk page to insert the page
42742 ** Note that the trunk page is not really full until it contains
42764 TRACE(("FREE-PAGE: %d leaf on trunk page %d\n",pPage->pgno,pTrunk->pgno));
42770 ** the page being freed as a leaf page of the first trunk in the free-list.
42772 ** first trunk in the free-list is full. Either way, the page being freed
42773 ** will become the new first trunk page in the free-list.
42785 TRACE(("FREE-PAGE: %d new trunk page replacing %d\n", pPage->pgno, iTrunk));
42826 /* 0 is not a legal page number and page 1 cannot be an
42827 ** overflow page. Therefore if ovflPgno<2 or past the end of the
42846 ** Create the byte sequence used to represent a cell on page pPage
42858 MemPage *pPage, /* The page that contains the cell */
42923 Pgno pgnoPtrmap = pgnoOvfl; /* Overflow page pointer-map entry page */
42935 ** overflow page is being allocated, add an entry to the pointer-map
42936 ** for that page now.
42938 ** If this is the first overflow page
43021 int hdr; /* Beginning of the header. 0 most pages. 100 page 1 */
43057 ** If the cell content will fit on the page, then put it there. If it
43071 MemPage *pPage, /* Page into which we are copying */
43072 int i, /* New cell becomes the i-th cell of the page */
43084 u8 *data; /* The content of the whole page */
43096 ** malformed cell from a leaf page to an interior page, if the cell size
43144 /* The cell may contain a pointer to an overflow page. If so, write
43145 ** the entry for the overflow page into the pointer map.
43154 ** Add a list of cells to a page. The page should be initially empty.
43155 ** The cells are guaranteed to fit on the page.
43158 MemPage *pPage, /* The page to be assemblied */
43159 int nCell, /* The number of cells to add to this page */
43168 const int nUsable = pPage->pBt->usableSize; /* Usable size of page */
43175 /* Check that the page has just been zeroed by zeroPage() */
43196 ** of the page that participate in the balancing operation. NB is the
43197 ** total number of pages that participate, including the target page and
43217 ** a new page to the right-hand side and put the one new entry in
43218 ** that page. This leaves the right side of the tree somewhat
43220 ** at the end soon afterwards so the nearly empty page will quickly
43223 ** pPage is the leaf page which is the right-most page in the tree.
43225 ** which is also the right-most entry on the page.
43229 ** byte page number followed by a variable length integer. In other
43235 MemPage *pNew; /* Newly allocated page */
43237 Pgno pgnoNew; /* Page number of pNew */
43245 /* Allocate a new page. This page will become the right-sibling of
43246 ** pPage. Make the parent page writable, so that the new divider cell
43264 ** with entries for the new page, and any pointer from the
43265 ** cell on the page to an overflow page. If either of these
43267 ** of the parent page are still manipulated by thh code below.
43268 ** That is Ok, at this point the parent page is guaranteed to
43270 ** rollback, undoing any changes made to the parent page.
43280 ** consists of a 4-byte page number (the page number of pPage) and
43302 /* Set the right-child pointer of pParent to point to the new page. */
43305 /* Release the reference to the new page. */
43357 ** on page pFrom to page pTo. If page pFrom was not a leaf page, then
43358 ** the pointer-map entries for each child page are updated so that the
43359 ** parent page stored in the pointer map is page pTo. If pFrom contained
43360 ** any cells with overflow page pointers, then the corresponding pointer
43361 ** map entries are also updated so that the parent page is page pTo.
43366 ** Before returning, page pTo is reinitialized using btreeInitPage().
43387 /* Copy the b-tree node content from page pFrom to page pTo. */
43392 /* Reinitialize page pTo so that the contents of the MemPage structure
43395 ** page pFrom.
43415 ** (hereafter "the page") and up to 2 siblings so that all pages have about the
43417 ** page are used in the balancing, though both siblings might come from one
43418 ** side if the page is the first or last child of its parent. If the page
43419 ** has fewer than 2 siblings (something which can only happen if the page
43420 ** is a root page or a child of a root page) then all available siblings
43423 ** The number of siblings of the page might be increased or decreased by
43426 ** Note that when this routine is called, some of the cells on the page
43428 ** if the page is overfull. This routine ensures that all cells allocated
43429 ** to the page and its siblings fit into MemPage.aData[] before returning.
43431 ** In the course of balancing the page and its siblings, cells may be
43432 ** inserted into or removed from the parent page (pParent). Doing so
43433 ** may cause the parent page to become overfull or underfull. If this
43442 ** buffer big enough to hold one page. If while inserting cells into the parent
43443 ** page (pParent) the parent page becomes overfull, this buffer is
43445 ** a maximum of four divider cells into the parent page, and the maximum
43447 ** of the page-size, the aOvflSpace[] buffer is guaranteed to be large
43454 MemPage *pParent, /* Parent page of siblings being balanced */
43455 int iParentIdx, /* Index of "the page" in pParent */
43456 u8 *aOvflSpace, /* page-size bytes of space for parent ovfl */
43457 int isRoot /* True if pParent is a root-page */
43471 int subtotal; /* Subtotal of bytes in cells on one page */
43480 int cntNew[NB+2]; /* Index in aCell[] of cell after i-th page */
43481 int szNew[NB+2]; /* Combined size of cells place on i-th page */
43485 Pgno pgno; /* Temp var to store a page number in */
43492 TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));
43513 ** This loop also drops the divider cells from the parent page. This
43515 ** overflow cells in the parent page, since if any existed they will
43558 /* Drop the cell from the parent page. apDiv[i] still points to
43590 + k*nOld; /* Page copies (apCopy) */
43653 /* The right pointer of the child page pOld becomes the left
43670 ** size of all cells on the i-th page and cntNew[] which is the index
43671 ** in apCell[] of the cell that divides page i from page i+1.
43677 ** szNew[i]: Spaced used on the i-th sibling page.
43679 ** the right of the i-th sibling page.
43732 ** a virtual root page. A virtual root page is when the real root
43733 ** page is page 1 and we are the only child of that page.
43766 /* Set the pointer-map entry for the new sibling page. */
43834 /* Assemble the new sibling page. */
43844 /* If the sibling page assembled above was not the right-most sibling,
43845 ** insert a divider cell into the parent page.
43863 ** the sibling-page assembled above only.
43909 /* The root page of the b-tree now contains no cells. The only sibling
43910 ** page is the right-child of the parent. Copy the contents of the
43911 ** child page into the parent, decreasing the overall height of the
43919 ** The second assert below verifies that the child page is defragmented
43921 ** is important if the parent page happens to be page 1 of the database
43942 ** page in any overflow chains used by new divider cells. These
43966 j = 0; /* Current 'old' sibling page */
43967 k = 0; /* Current 'new' sibling page */
43972 ** sibling page j. If the siblings are not leaf pages of an
43995 ** sibling page k. If the siblings are not leaf pages of an
44005 ** page before the balancing, then the pointer map entries associated
44055 ** This function is called when the root page of a b-tree structure is
44058 ** A new child page is allocated and the contents of the current root
44059 ** page, including overflow cells, are copied into the child. The root
44060 ** page is then overwritten to make it an empty page with the right-child
44061 ** pointer pointing to the new page.
44064 ** that the new child-page now contains pointers to are updated. The
44066 ** page is also updated.
44069 ** page and SQLITE_OK is returned. In this case the caller is required
44075 MemPage *pChild = 0; /* Pointer to a new child page */
44076 Pgno pgnoChild = 0; /* Page number of the new child page */
44082 /* Make pRoot, the root page of the b-tree, writable. Allocate a new
44083 ** page that will become the new right-child of pPage. Copy the contents
44084 ** of the node stored on pRoot into the new child page.
44118 ** The page that pCur currently points to has just been modified in
44142 /* The root page of the b-tree is overfull. In this case call the
44143 ** balance_deeper() function to create a new child for the root-page
44144 ** and copy the current contents of the root-page to it. The
44145 ** next iteration of the do-loop will balance the child page.
44195 ** will balance the parent page to correct this.
44197 ** If the parent page becomes overfull, the overflow cell or cells
44202 ** different page). Once this subsequent call to balance_nonroot()
44205 ** copied either into the body of a database page or into the new
44227 page. */
44326 TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
44368 ** back to the root page as balance() used to invalidate the contents
44408 MemPage *pPage; /* Page to delete cell from */
44437 /* If the page containing the entry to delete is not a leaf page, move
44442 ** sub-tree headed by the child page of the cell being deleted. This makes
44451 ** making any modifications. Make the page containing the entry to be
44453 ** entry and finally remove the cell itself from within the page.
44463 /* If the cell deleted was not located on a leaf page, then the cursor
44465 ** by the child-page of the cell that was just deleted from an internal
44487 /* Balance the tree. If the entry deleted was located on a leaf page,
44488 ** then the cursor still points to that page. In this case the first
44492 ** Otherwise, if the entry deleted was on an internal node page, then
44493 ** pCur is pointing to the leaf page from which a cell was removed to
44517 ** Create a new BTree table. Write into *piTable the page
44518 ** number for the root page of the new table.
44544 Pgno pgnoMove; /* Move a page here to make room for the root-page */
44545 MemPage *pPageMove; /* The page to move to. */
44548 ** to make room for the new tables root page. In case this page turns
44549 ** out to be an overflow page, delete all overflow page-map caches
44555 ** root page of the new table should go. meta[3] is the largest root-page
44556 ** created so far, so the new root-page is (meta[3]+1).
44561 /* The new root-page may not be allocated on a pointer-map page, or the
44562 ** PENDING_BYTE page.
44570 /* Allocate a page. The page that currently resides at pgnoRoot will
44571 ** be moved to the allocated page (unless the allocated page happens
44580 /* pgnoRoot is the page that will be used for the root-page of
44583 ** by extending the file), the current page at position pgnoMove
44591 /* Move the page currently at pgnoRoot to pgnoMove. */
44609 /* Obtain the page at pgnoRoot */
44626 /* Update the pointer-map and meta-data with the new root-page number. */
44658 ** Erase the given database page and all its children. Return
44659 ** the page to the freelist.
44663 Pgno pgno, /* Page number to clear */
44664 int freePageFlag, /* Deallocate page if true */
44708 ** the page number of the root of the table. After this routine returns,
44709 ** the root page is empty, but still exists.
44741 ** page 1) is never added to the freelist.
44746 ** If AUTOVACUUM is enabled and the page at iTable is not the last
44747 ** root page in the database file, then the last root page
44749 ** iTable and that last slot formerly occupied by the last root page
44753 ** page number that used to be the last root page in the file before
44754 ** the move. If no page gets moved, *piMoved is set to 0.
44755 ** The last root page is recorded in meta[3] and the value of
44768 ** need to move another root-page to fill a gap left by the deleted
44769 ** root page. If an open cursor was using this page a problem would
44799 /* If the table being dropped is the table with the largest root-page
44800 ** number in the database, put the root page on the free list.
44808 /* The table being dropped does not have the largest root-page
44809 ** number in the database. So move the page that does into the
44810 ** gap left by the deleted root-page.
44833 /* Set the new 'max-root-page' value in the database header. This
44835 ** be a root-page number, less one again if that is the
44852 /* If sqlite3BtreeDropTable was called on page 1.
44946 ** page in the B-Tree structure (not including overflow pages).
44950 MemPage *pPage; /* Current page of the b-tree */
44952 /* If this is a leaf page or the tree is not an int-key tree, then
44953 ** this page contains countable entries. Increment the entry counter
44963 ** the next page in the tree that has not yet been visited. The
44965 ** of the page, or to the number of cells in the page if the next page
45040 ** Add 1 to the reference count for page iPage. If this is the second
45041 ** reference to the page, add an error message to pCheck->zErrMsg.
45042 ** Return 1 if there are 2 ore more references to the page and 0 if
45043 ** if this is the first reference to the page.
45045 ** Also check that the page number is in bounds.
45050 checkAppendMsg(pCheck, zContext, "invalid page number %d", iPage);
45054 checkAppendMsg(pCheck, zContext, "2nd reference to page %d", iPage);
45062 ** Check that the entry in the pointer-map for page iChild maps to
45063 ** page iParent, pointer type ptrType. If not, append an error message
45068 Pgno iChild, /* Child page number */
45070 Pgno iParent, /* Expected pointer map parent page number */
45093 ** Check the integrity of the freelist or of an overflow page list.
45098 int isFreeList, /* True for a freelist. False for overflow page list */
45099 int iPage, /* Page number for first page in the list */
45117 checkAppendMsg(pCheck, zContext, "failed to get page %d", iPage);
45130 "freelist leaf count too big on page %d", iPage);
45148 ** page in this overflow list, check that the pointer-map entry for
45149 ** the following page matches iPage.
45165 ** Do various sanity checks on a single page of a tree. Return
45172 ** but combine to completely cover the page.
45179 ** 8. Make sure this page is at least 33% full or else it is
45184 int iPage, /* Page number of the page to check */
45201 sqlite3_snprintf(sizeof(zContext), zContext, "Page %d: ", iPage);
45203 /* Check that the page exists
45211 "unable to get the page. error code=%d", rc);
45237 "On tree page %d cell %d: ", iPage, i);
45266 /* Check sanity of left child page.
45277 checkAppendMsg(pCheck, zContext, "Child page depth differs");
45286 "On page %d at right child: ", iPage);
45299 /* if we are a left child page */
45301 /* if we are the left most child page */
45321 /* else if we're a right child page */
45331 /* Check for complete coverage of the page
45354 "Corruption detected in cell %d on page %d",i,iPage);
45376 "Multiple uses for byte %d of page %d", i, iPage);
45382 "Fragmentation of %d bytes reported as %d on page %d",
45395 ** an array of pages numbers were each page number is the root page of
45463 /* Make sure every page in the file is referenced
45468 checkAppendMsg(&sCheck, 0, "Page %d is never used", i);
45476 checkAppendMsg(&sCheck, 0, "Page %d is never used", i);
45480 checkAppendMsg(&sCheck, 0, "Pointer map page %d is referenced", i);
45491 "Outstanding page count goes from %d to %d during this analysis",
45607 ** Obtain a lock on the table whose root page is iTab. The
45679 ** This function sets a flag only. The actual page location cache
45725 Pgno iNext; /* Page number of the next source page to copy */
45754 ** the page cache associated with the source database. The mutex
45891 ** page iSrcPg from the source database. Copy this data into the
45910 ** page sizes of the source and destination differ.
45916 /* This loop runs once for each destination page spanned by the source
45917 ** page. For each iteration, variable iOff is set to the byte offset
45918 ** of the destination page.
45931 /* Copy the data from the source page into the destination page.
45934 ** of the page 'extra' space to invalidate the Btree layers
45935 ** cached parse of the page). MemPage.isInit is marked
46030 const Pgno iSrcPg = p->iNext; /* Source page number */
46032 DbPage *pSrcPg; /* Source page object */
46068 ** database. The complication here is that the destination page
46069 ** size may be different to the source page size.
46071 ** If the source page size is smaller than the destination page size,
46075 ** destination file that lie beyond the nDestTruncate page mark are
46091 /* If the source page-size is smaller than the destination page-size,
46097 ** pending-byte page in the source database may need to be
46228 ** This function is called after the contents of page iPage of the
46229 ** source database have been modified. If page iPage has already been
46244 /* The backup process p has already copied page iPage. But now it
47203 int available = 0; /* Number of bytes available on the local btree page */
54658 ** record header if the record header does not fit on a single page
55375 ** Open a read-only cursor for the database table whose root page is
55383 ** If P5!=0 then use the content of register P2 as the root page, not
55406 ** page is P2. Or if P5!=0 use the content of register P2 to find the
55407 ** root page.
55489 ** rooted at page 1 of a zero-byte database. */
55497 ** SQLite used to check if the root-page flags were sane at this point
55547 ** automatically created table with root-page 1 (an INTKEY table).
56896 ** Delete an entire database table or index whose root page in the database
56903 ** If AUTOVACUUM is enabled then it is possible that another root page
56904 ** might be moved into the newly deleted root page in order to keep all
56906 ** value of the root page that moved - its value before the move occurred -
56907 ** is stored in register P2. If no page
56954 ** Delete all contents of the database table or index whose root page
56993 ** P1>1. Write the root page number of the new table into
57006 ** P1>1. Write the root page number of the new table into
57172 ** The root page numbers of all tables in the database are integer
57742 ** P2 contains the root-page of the table to lock.
58147 ** page count has already been successfully read and cached. So the
66526 int iTab; /* The root page of the table to be locked */
66534 ** The table to be locked has root page iTab and is found in database iDb.
66544 int iTab, /* Root page number of the table to be locked */
67364 ** The root page number of the new table is left in reg pParse->regRoot.
67365 ** The rowid and root page number values are needed by the code that
67968 ** So do not write to the disk again. Extract the root page number
67969 ** for the table from the db->init.newTnum field. (The page number
68010 ** statement to populate the new table. The root-page number for the
68321 ** used by SQLite when the btree layer moves a table root page. The
68322 ** root-page of a table or index in database iDb has changed from iFrom
68359 ** Write code to erase the table with root-page iTable from database iDb.
68361 ** if a root-page of another table is moved by the btree-layer whilst
68371 ** is non-zero, then it is the root page number of a table moved to
68389 ** in case a root-page belonging to another table is moved by the btree layer
68404 ** largest root-page number. This guarantees that none of the root-pages
68412 ** and root page 5 happened to be the largest root-page number in the
68413 ** database, then root page 5 would be moved to page 4 by the
68415 ** a free-list page.
68763 ** root page number of the index. If memRootPage is negative, then
68765 ** the root page number of the index is taken from pIndex->tnum.
68772 int tnum; /* Root page of index */
77274 ** page
77275 ** pages in the page cache. The second form sets both the current
77276 ** page cache size value and the persistent page cache size value
77279 ** The default cache size is stored in meta-value 2 of page 1 of the
77327 ** database page size in bytes. The second form sets the
77328 ** database page size value. The value can only be set if
77338 /* Malloc may fail when setting the page-size, as there is an internal
77604 ** page cache size. The local setting can be different from
77607 ** pages in the page cache. The second form sets the local
77608 ** page cache size value. It does not change the persistent
78430 ** argv[1] = root page number for table or index. 0 for trigger or view.
78487 ** to do here is record the root page number for that index.
78615 ** meta[2] Size of the page cache.
83296 int iRoot = pTab->tnum; /* Root page of scanned b-tree */
83305 ** In this case set iRoot to the root page number of the index b-tree
85755 BTREE_DEFAULT_CACHE_SIZE, 0, /* Preserve the default page cache size */
85766 ** we already have page 1 loaded into cache and marked dirty. */
95781 /* Designate a buffer for page
95789 /* Specify an alternative page cache implementation */
96691 int nCache, /* How many pages in the page cache */
99619 int isFirstTerm = 1; /* True when processing first term on page */
105375 int nReq; /* Number of bytes required on leaf page */
107748 ** child page.
108101 ** an internal node, then the 64-bit integer is a child page number.
108281 ** Cursor pCursor currently points to a cell in a non-leaf page.
108864 RtreeNode **ppLeaf /* OUT: Selected leaf page */
110163 ** This routine queries database handle db for the page-size used by
110164 ** database zDb. If successful, the page-size in bytes is written to
110251 ** the database page-size. This ensures that each node is stored on
110252 ** a single database page.
110254 ** If the databasd page-size is so large that more than RTREE_MAXCELLS
