SegPageEntryIter< EntryT > Class Template Reference

SegPageEntryIter extends SegPageIter. More...

#include <SegPageEntryIter.h>

Inheritance diagram for SegPageEntryIter< EntryT >:

List of all members.

Public Member Functions
	SegPageEntryIter ()
	Constructor: iterator starts out singular.
	SegPageEntryIter (uint nEntriesInit)
	Constructor: iterator starts out singular.
void	resize (uint nEntries)
	Resizes the object to allow for storage of N pre-fetch entries.
void	setPrefetchSource (SegPageEntryIterSource< EntryT > &prefetchSource)
	Sets the pre-fetch source for this iterator.
void	mapRange (SegmentAccessor const &segmentAccessor, PageId beginPageId, PageId endPageId=NULL_PAGE_ID)
	Begins a new iteration.
std::pair< PageId, EntryT > &	operator * ()
	Returns: the current (PageId, EntryT) in the iteration
void	operator++ ()
	Moves to the next prefetched PageId.
void	makeSingular ()
	Aborts any iteration in progress and release all resources.
bool	isSingular () const
	Returns: true iff no iteration is in progress
PageId	operator * () const
	Returns: the current PageId in the iteration
void	forcePrefetchReject ()
	Forces the next pre-fetch request to be rejected.
Protected Member Functions
void	initPrefetchQueue ()
	Reads the pre-fetch parameters, sizes the pre-fetch queue, and initializes various state variables related to the queue.
void	prefetchPage (PageId pageId)
	Pre-fetches a specified page.
Protected Attributes
SegmentAccessor	segmentAccessor
	Accessor for the Segment containing the pages to be visited.
PageId	endPageId
	PageId at which to stop iteration.
std::vector< PageId >	prefetchQueue
	Fixed-size circular queue of prefetched PageIds, indexed by iFetch.
uint	iFetch
	Position in prefetchQueue.
bool	atEnd
	Whether end of iteration has been reached by prefetch (but not necessarily by fetch).
uint	queueSize
	Current size of the pre-fetch queue.
int	nFreePageSlots
	Number of slots available in the prefetchQueue.
Private Member Functions
void	init ()
	Initializes object.
void	prefetchPages (PageId prevPageId, bool oneIter)
	Determines a set of pages that should be pre-fetched and pre-fetches them.
Private Attributes
CircularBuffer< std::pair< PageId, EntryT > >	entryQueue
	Circular vector with the context-specific information associated with each pre-fetched page.
SegPageEntryIterSource< EntryT > *	pPrefetchSource
	Pointer to the source that provides the callback method that determines which pages to pre-fetch.

---

Detailed Description

template<class EntryT>
class SegPageEntryIter< EntryT >

SegPageEntryIter extends SegPageIter.

Rather than pre-fetching successor pages, it takes a source parameter that provides a callback method that's used to determine which pages should be pre-fetched. The class is a template class, which allows context-specific information to be associated with each pre-fetched page.

Definition at line 42 of file SegPageEntryIter.h.

---

Constructor & Destructor Documentation

template<class EntryT>

FENNEL_BEGIN_NAMESPACE SegPageEntryIter< EntryT >::SegPageEntryIter

(

)

[explicit]

Constructor: iterator starts out singular.

Initializes the object with no storage yet for pre-fetch entries.

Definition at line 33 of file SegPageEntryIterImpl.h.

References SegPageEntryIter< EntryT >::init().

{
    init();
}

template<class EntryT>

SegPageEntryIter< EntryT >::SegPageEntryIter

(

uint

nEntriesInit

)

[explicit]

Constructor: iterator starts out singular.

Parameters:

nEntriesInit

number of pre-fetch entries

Definition at line 39 of file SegPageEntryIterImpl.h.

References SegPageEntryIter< EntryT >::init().

    : entryQueue(nEntriesInit)
{
    init();
}

---

Member Function Documentation

template<class EntryT>

void SegPageEntryIter< EntryT >::init

(

)

[private]

Initializes object.

Definition at line 46 of file SegPageEntryIterImpl.h.

References SegPageEntryIter< EntryT >::pPrefetchSource.

Referenced by SegPageEntryIter< EntryT >::SegPageEntryIter().

{
    pPrefetchSource = NULL;
}

template<class EntryT>

void SegPageEntryIter< EntryT >::prefetchPages	(	PageId	prevPageId,
		bool	oneIter
	)			[private]

Determines a set of pages that should be pre-fetched and pre-fetches them.

Parameters:

	prevPageId	the id of the last page pre-fetched; only needed in the case where the entry queue is currently empty
	oneIter	if true, pre-fetch no more than one page

Definition at line 87 of file SegPageEntryIterImpl.h.

References SegPageIter::atEnd, CircularBuffer< T >::empty(), SegPageIter::endPageId, SegPageEntryIter< EntryT >::entryQueue, CircularBuffer< T >::getLastPos(), SegPageIter::nFreePageSlots, SegPageEntryIter< EntryT >::pPrefetchSource, SegPageIter::prefetchPage(), CircularBuffer< T >::push_back(), CircularBuffer< T >::reference_back(), and CircularBuffer< T >::spaceAvailable().

Referenced by SegPageEntryIter< EntryT >::mapRange(), and SegPageEntryIter< EntryT >::operator++().

{
    if (!entryQueue.empty()) {
        prevPageId = entryQueue.reference_back().first;
    }

    // Continue retrieving pageIds while we have available space in
    // the prefetch queue
    while (nFreePageSlots != 0 || oneIter) {
        // But make sure we have space in the entryQueue
        if (!entryQueue.spaceAvailable()) {
            break;
        }

        std::pair<PageId, EntryT> &entryPair =
            entryQueue[entryQueue.getLastPos() + 1];
        bool found;
        entryPair.first =
            pPrefetchSource->getNextPageForPrefetch(entryPair.second, found);
        if (!found) {
            break;
        }
        entryQueue.push_back(entryPair);

        if (entryPair.first == endPageId) {
            atEnd = 1;
        }

        if (atEnd || entryPair.first != prevPageId) {
            prefetchPage(entryPair.first);
        }

        if (atEnd || oneIter) {
            break;
        }

        prevPageId = entryPair.first;
    }
}

template<class EntryT>

void SegPageEntryIter< EntryT >::resize

(

uint

nEntries

)

Resizes the object to allow for storage of N pre-fetch entries.

Parameters:

nEntries

the number of storage slots

Definition at line 52 of file SegPageEntryIterImpl.h.

References SegPageEntryIter< EntryT >::entryQueue, and CircularBuffer< T >::resize().

Referenced by BTreePrefetchSearchExecStream::open().

{
    entryQueue.resize(nEntries);
}

template<class EntryT>

void SegPageEntryIter< EntryT >::setPrefetchSource

(

SegPageEntryIterSource< EntryT > &

prefetchSource

)

Sets the pre-fetch source for this iterator.

Parameters:

prefetchSource

the source

Definition at line 58 of file SegPageEntryIterImpl.h.

References SegPageEntryIter< EntryT >::entryQueue, SegPageEntryIterSource< EntryT >::initPrefetchEntry(), SegPageEntryIter< EntryT >::pPrefetchSource, and CircularBuffer< T >::size().

Referenced by LcsClusterReader::LcsClusterReader(), BTreePrefetchSearchExecStream::open(), and SegPageEntryIterTest::testIter().

{
    assert(entryQueue.size() > 0);
    pPrefetchSource = &prefetchSource;
    for (uint i = 0; i < entryQueue.size(); i++) {
        pPrefetchSource->initPrefetchEntry(entryQueue[i].second);
    }
}

template<class EntryT>

void SegPageEntryIter< EntryT >::mapRange	(	SegmentAccessor const &	segmentAccessor,
		PageId	beginPageId,
		PageId	endPageId = NULL_PAGE_ID
	)

Begins a new iteration.

Parameters:

	segmentAccessor	accessor for the segment containing the pages to visit
	beginPageId	the ID of the first page to visit; always set to NULL_PAGE_ID for this class, as the initial page is provided by the source parameter
	endPageId	the ID at which to end iteration; by default, this is NULL_PAGE_ID (representing the sentinel end of a chain) but the iteration (and prefetch) can be stopped earlier with some other known PageId; note that endPageId itself will not be prefetched

Reimplemented from SegPageIter.

Definition at line 69 of file SegPageEntryIterImpl.h.

References CircularBuffer< T >::clear(), SegPageIter::endPageId, SegPageEntryIter< EntryT >::entryQueue, SegPageIter::initPrefetchQueue(), NULL_PAGE_ID, SegmentAccessor::pCacheAccessor, SegPageEntryIter< EntryT >::prefetchPages(), SegmentAccessor::pSegment, and SegPageIter::segmentAccessor.

Referenced by BTreePrefetchSearchExecStream::innerSearchLoop(), LcsClusterReader::position(), and SegPageEntryIterTest::testIter().

{
    assert(segmentAccessorInit.pSegment);
    assert(segmentAccessorInit.pCacheAccessor);
    assert(beginPageIdInit == NULL_PAGE_ID);
    segmentAccessor = segmentAccessorInit;
    endPageId = endPageIdInit;
    initPrefetchQueue();
    entryQueue.clear();

    // Pre-populate the queues
    prefetchPages(NULL_PAGE_ID, false);
}

template<class EntryT>

std::pair<PageId, EntryT>& SegPageEntryIter< EntryT >::operator *

(

)

[inline]

Returns:

the current (PageId, EntryT) in the iteration

Definition at line 125 of file SegPageEntryIter.h.

    {
        assert(!isSingular());
        std::pair<PageId, EntryT> &entryPair = entryQueue.reference_front();
        assert(entryPair.first == prefetchQueue[iFetch]);
        return entryPair;
    }

template<class EntryT>

void SegPageEntryIter< EntryT >::operator++

(

)

Moves to the next prefetched PageId.

An assertion violation results if called when positioned on endPageId.

Reimplemented from SegPageIter.

Definition at line 128 of file SegPageEntryIterImpl.h.

References SegPageIter::atEnd, CircularBuffer< T >::empty(), SegPageIter::endPageId, SegPageEntryIter< EntryT >::entryQueue, SegPageIter::iFetch, SegPageEntryIter< EntryT >::isSingular(), SegPageIter::nFreePageSlots, NULL_PAGE_ID, CircularBuffer< T >::pop_front(), SegPageEntryIter< EntryT >::prefetchPages(), SegPageIter::queueSize, and CircularBuffer< T >::reference_front().

{
    assert(!isSingular());
    std::pair<PageId, EntryT> &entryPair = entryQueue.reference_front();
    PageId currPageId = entryPair.first;
    assert(currPageId != endPageId);

    entryQueue.pop_front();

    // If the queue is empty, we have to try and pre-fetch some more entries.
    // Worst case, we'll hit the ending page.  The queueSize == 1 case needs
    // special handling because:
    // 1) There are currently no free slots in the prefetch queue.  The one
    //    slot is occupied by the last page pre-fetched.
    // 2) We can only replace that slot with a new page if it's different
    //    from that last pre-fetched page.
    // Therefore, we can't assume that the current page will always be
    // replaced by a new one.
    if (entryQueue.empty()) {
        prefetchPages(currPageId, (queueSize == 1));
    }

    PageId nextPageId = entryQueue.reference_front().first;
    // Bump up the prefetch queue only if we've moved on to a new page
    if (nextPageId != currPageId) {
        iFetch = (iFetch + 1) % queueSize;
        nFreePageSlots++;
    }

    // Re-populate the queues if there's available space
    if (!atEnd) {
        prefetchPages(NULL_PAGE_ID, false);
    }
}

template<class EntryT>

void SegPageEntryIter< EntryT >::makeSingular

(

)

[inline]

Aborts any iteration in progress and release all resources.

Reimplemented from SegPageIter.

Definition at line 142 of file SegPageEntryIter.h.

Referenced by SegPageEntryIterTest::testIter().

    {
        SegPageIter::makeSingular();
        pPrefetchSource = NULL;
    }

template<class EntryT>

bool SegPageEntryIter< EntryT >::isSingular

(

)

const [inline]

Returns:

true iff no iteration is in progress

Reimplemented from SegPageIter.

Definition at line 151 of file SegPageEntryIter.h.

Referenced by SegPageEntryIter< LcsRid >::operator *(), and SegPageEntryIter< EntryT >::operator++().

    {
        return (pPrefetchSource == NULL || SegPageIter::isSingular());
    }

void SegPageIter::initPrefetchQueue

(

)

[protected, inherited]

Reads the pre-fetch parameters, sizes the pre-fetch queue, and initializes various state variables related to the queue.

Definition at line 66 of file SegPageIter.cpp.

References SegPageIter::atEnd, SegPageIter::currPageSlot, SegPageIter::forceReject, SegPageIter::iFetch, SegPageIter::nFreePageSlots, SegPageIter::noPrefetch, SegmentAccessor::pCacheAccessor, SegPageIter::prefetchPagesMax, SegPageIter::prefetchQueue, SegPageIter::prefetchThrottleRate, SegPageIter::queueSize, SegPageIter::segmentAccessor, and SegPageIter::throttleCount.

Referenced by SegPageIter::mapRange(), and SegPageEntryIter< EntryT >::mapRange().

{
    segmentAccessor.pCacheAccessor->getPrefetchParams(
        prefetchPagesMax,
        prefetchThrottleRate);
    queueSize = prefetchPagesMax;
    noPrefetch = (queueSize == 0);
    // Reset the queue size so we have space to store at least one page
    if (queueSize < 1) {
        queueSize = 1;
    }
    prefetchQueue.resize(queueSize);

    nFreePageSlots = queueSize;
    currPageSlot = 0;
    iFetch = 0;
    atEnd = 0;
    throttleCount = 0;
    forceReject = false;
}

void SegPageIter::prefetchPage

(

PageId

pageId

)

[protected, inherited]

Pre-fetches a specified page.

Parameters:

pageId

the id of the page to be pre-fetched

Definition at line 110 of file SegPageIter.cpp.

References SegPageIter::atEnd, SegPageIter::currPageSlot, SegPageIter::endPageId, SegPageIter::forceReject, SegPageIter::iFetch, SegPageIter::nFreePageSlots, SegPageIter::noPrefetch, NULL_BLOCK_ID, SegmentAccessor::pCacheAccessor, SegPageIter::prefetchPagesMax, SegPageIter::prefetchQueue, SegPageIter::prefetchThrottleRate, SegmentAccessor::pSegment, SegPageIter::queueSize, SegPageIter::segmentAccessor, and SegPageIter::throttleCount.

Referenced by SegPageIter::mapRange(), SegPageIter::operator++(), and SegPageEntryIter< EntryT >::prefetchPages().

{
    // Store the page we're about to pre-fetch in the first empty slot
    // in the queue
    prefetchQueue[currPageSlot++] = pageId;
    currPageSlot %= queueSize;
    --nFreePageSlots;

    if (pageId == endPageId) {
        atEnd = 1;
        return;
    }

    // If pre-fetches are turned off, don't bothering issuing the pre-fetch
    // request.
    BlockId blockId = NULL_BLOCK_ID;
    if (!forceReject && !noPrefetch) {
        blockId = segmentAccessor.pSegment->translatePageId(pageId);
    }
    if (!forceReject &&
        (noPrefetch ||
            segmentAccessor.pCacheAccessor->prefetchPage(
                blockId,
                segmentAccessor.pSegment->getMappedPageListener(blockId))))
    {
        // If the pre-fetch rate was throttled down, then wait until we
        // reach the desired number of successful pre-fetches before
        // throttling the rate back up, one page at a time.
        if (throttleCount > 0) {
            assert(prefetchPagesMax != 0);
            if (--throttleCount == 0) {
                // At a minimum, reenable pre-fetches
                noPrefetch = false;

                // If we haven't throttled back to the max pre-fetch
                // rate, then reset the counter so we can continue
                // counting successful pre-fetches to allow the rate
                // to continue throttling up.  In the case where the
                // pre-fetch rate is a single page, no further throttling
                // is possible.
                if (prefetchPagesMax > 1) {
                    nFreePageSlots++;
                    if (nFreePageSlots < prefetchPagesMax) {
                        throttleCount = prefetchThrottleRate;
                    }
                }
            }
        }
    } else {
        // If pre-fetches aren't already disabled, then set the number of
        // pre-fetches to the number of outstanding pre-fetches by
        // disallowing any new pre-fetches until the existing ones are used.
        // If we're down to doing a single pre-fetch, then turn off
        // pre-fetches.
        if (prefetchPagesMax > 0) {
            if (nFreePageSlots > 0) {
                nFreePageSlots = 0;
            }
            if (iFetch == currPageSlot) {
                noPrefetch = true;
            }
            throttleCount = prefetchThrottleRate;
        }
        forceReject = false;
    }
}

PageId SegPageIter::operator *

(

)

const [inline, inherited]

Returns:

the current PageId in the iteration

Definition at line 156 of file SegPageIter.h.

    {
        assert(!isSingular());
        return prefetchQueue[iFetch];
    }

void SegPageIter::forcePrefetchReject

(

)

[inherited]

Forces the next pre-fetch request to be rejected.

Used for testing purposes.

Definition at line 177 of file SegPageIter.cpp.

References SegPageIter::forceReject.

Referenced by SegPageIterTest::testIter(), and SegPageEntryIterTest::testIter().

{
    forceReject = true;
}

---

Member Data Documentation

template<class EntryT>

CircularBuffer<std::pair<PageId, EntryT> > SegPageEntryIter< EntryT >::entryQueue [private]

Circular vector with the context-specific information associated with each pre-fetched page.

The number of entries in this vector is not necessarily the same as the number of pages that have been pre-fetched, as the same page can be associated with multiple entries.

Definition at line 50 of file SegPageEntryIter.h.

Referenced by SegPageEntryIter< EntryT >::mapRange(), SegPageEntryIter< LcsRid >::operator *(), SegPageEntryIter< EntryT >::operator++(), SegPageEntryIter< EntryT >::prefetchPages(), SegPageEntryIter< EntryT >::resize(), and SegPageEntryIter< EntryT >::setPrefetchSource().

template<class EntryT>

SegPageEntryIterSource<EntryT>* SegPageEntryIter< EntryT >::pPrefetchSource [private]

Pointer to the source that provides the callback method that determines which pages to pre-fetch.

Definition at line 56 of file SegPageEntryIter.h.

Referenced by SegPageEntryIter< EntryT >::init(), SegPageEntryIter< LcsRid >::isSingular(), SegPageEntryIter< LcsRid >::makeSingular(), SegPageEntryIter< EntryT >::prefetchPages(), and SegPageEntryIter< EntryT >::setPrefetchSource().

SegmentAccessor SegPageIter::segmentAccessor [protected, inherited]

Accessor for the Segment containing the pages to be visited.

Definition at line 82 of file SegPageIter.h.

Referenced by SegPageIter::initPrefetchQueue(), SegPageIter::mapRange(), SegPageEntryIter< EntryT >::mapRange(), SegPageIter::operator++(), and SegPageIter::prefetchPage().

PageId SegPageIter::endPageId [protected, inherited]

PageId at which to stop iteration.

Definition at line 87 of file SegPageIter.h.

Referenced by SegPageIter::mapRange(), SegPageEntryIter< EntryT >::mapRange(), SegPageIter::operator++(), SegPageEntryIter< EntryT >::operator++(), SegPageIter::prefetchPage(), and SegPageEntryIter< EntryT >::prefetchPages().

std::vector<PageId> SegPageIter::prefetchQueue [protected, inherited]

Fixed-size circular queue of prefetched PageIds, indexed by iFetch.

Definition at line 92 of file SegPageIter.h.

Referenced by SegPageIter::initPrefetchQueue(), SegPageIter::mapRange(), SegPageEntryIter< LcsRid >::operator *(), SegPageIter::operator++(), and SegPageIter::prefetchPage().

uint SegPageIter::iFetch [protected, inherited]

Position in prefetchQueue.

Definition at line 97 of file SegPageIter.h.

Referenced by SegPageIter::initPrefetchQueue(), SegPageEntryIter< LcsRid >::operator *(), SegPageIter::operator++(), SegPageEntryIter< EntryT >::operator++(), and SegPageIter::prefetchPage().

bool SegPageIter::atEnd [protected, inherited]

Whether end of iteration has been reached by prefetch (but not necessarily by fetch).

Definition at line 103 of file SegPageIter.h.

Referenced by SegPageIter::initPrefetchQueue(), SegPageIter::mapRange(), SegPageIter::operator++(), SegPageEntryIter< EntryT >::operator++(), SegPageIter::prefetchPage(), and SegPageEntryIter< EntryT >::prefetchPages().

uint SegPageIter::queueSize [protected, inherited]

Current size of the pre-fetch queue.

Definition at line 108 of file SegPageIter.h.

Referenced by SegPageIter::initPrefetchQueue(), SegPageIter::mapRange(), SegPageIter::operator++(), SegPageEntryIter< EntryT >::operator++(), and SegPageIter::prefetchPage().

int SegPageIter::nFreePageSlots [protected, inherited]

Number of slots available in the prefetchQueue.

May temporarily become negative in the case where pre-fetches are turned off.

Definition at line 114 of file SegPageIter.h.

Referenced by SegPageIter::initPrefetchQueue(), SegPageIter::operator++(), SegPageEntryIter< EntryT >::operator++(), SegPageIter::prefetchPage(), and SegPageEntryIter< EntryT >::prefetchPages().

---

The documentation for this class was generated from the following files:

• /home/pub/open/dev/fennel/segment/SegPageEntryIter.h
• /home/pub/open/dev/fennel/segment/SegPageEntryIterImpl.h

---