-/**
- * Find the latest version of a page, starting from the
- * page supplied by \a page_array.
- * The pages are read from the disk until a different
- * inode or page offset is found.
- * The lastest version of the page is moved in the first
- * position of \a page_array.
- * \return the number of old versions of the page or PAGE_ERROR
- * on disk read errors.
- */
-static pgcnt_t findLastVersion(struct BattFsSuper *disk, pgcnt_t *page_array)
-{
- pgcnt_t *array_start = page_array;
- BattFsPageHeader hdr;
- if (!battfs_readHeader(disk, *page_array++, &hdr))
- return PAGE_ERROR;
-
- /* Free space: early bailout */
- if (hdr.fcs != computeFcs(&hdr))
- return 0;
-
- /*
- * If the first page is valid,
- * inode and pg_off in the array are taken
- * as the current page markers.
- */
- inode_t curr_inode = hdr.inode;
- pgoff_t curr_pgoff = hdr.pgoff;
-
- /* Temps used to find the sequence number range */
- seq_t minl = HALF_SEQ - 1;
- seq_t maxl = 0;
- seq_t minh = MAX_SEQ;
- seq_t maxh = MAX_SEQ;
- pgcnt_t lpos = 0, hpos = 0, dup_cnt = 0;
-
- /*
- * Find min and max values for the two
- * half of seq_num range.
- * With this we can find seqnum wraparounds.
- * seq_t is a type that has at least 1 bit more than
- * pgaddr_t. So all version of a page blocks can be numbered using
- * at most half numbers of a seq_t type.
- * The sequence number algorithm increments by 1 the previous seq_num
- * every time a page is rewritten. So the sequence is
- * guaranteed to be countiguous.
- * Only wrap arounds may happen, but due to half size sequence limitation,
- * there are only 4 possible situations:
- *
- * \verbatim
- * |------lower half------|-------upper half-------|
- *
- * 1) |------minl*****maxl---|------------------------|
- * 2) |------minl********maxl|minh******maxh----------|
- * 3) |----------------------|----minh*******maxh-----|
- * 4) |minl******maxl--------|------------minh****maxh|
- * \endverbatim
- *
- * Situations 1 and 3 are easy to detect, while 2 and 4 require more care.
- */
- do
- {
- if (hdr.seq < HALF_SEQ)
- {
- minl = MIN(minl, hdr.seq);
- if (hdr.seq > maxl)
- {
- maxl = hdr.seq;
- lpos = dup_cnt;
- }
- }
- else
- {
- minh = MIN(minh, hdr.seq);
- if (hdr.seq > maxh)
- {
- maxh = hdr.seq;
- hpos = dup_cnt;
- }
- }
-
- if (!battfs_readHeader(disk, *page_array++, &hdr))
- return PAGE_ERROR;
- dup_cnt++;
- }
- while (curr_inode == hdr.inode && curr_pgoff == hdr.pgoff && hdr.fcs == computeFcs(&hdr));
-
-
- /* Return early if there is only one version of the current page */
- if (dup_cnt == 1)
- return 0;
-
- /* Find the position in the array of the last version of the page */
- pgcnt_t last_ver = hpos;
- if (maxl >= minl)
- {
- /* Valid interval found in lower half */
- if (maxh >= minh)
- {
- /* Valid interval also found in upper half */
- if (maxl != minh - 1)
- {
- /* Interval starts in upper half and ends in lower */
- ASSERT(minl == 0);
- ASSERT(maxh == MAX_SEQ);
-
- last_ver = lpos;
- }
- }
- else
- /*
- * Upper interval is invalid.
- * Use lower values.
- */
- last_ver = lpos;
- }
-
- /* Put last page version at array start position */
- SWAP(array_start[0], array_start[last_ver]);
-
- return dup_cnt - 1;
-}