TwoQPageQueue Class Reference

TwoQPageQueue is used to implement the page queues used by the TwoQVictimPolicy. More...

#include <TwoQVictimPolicy.h>

List of all members.

Public Member Functions

 TwoQPageQueue ()
void insertAtHead (IntrusiveDListNode &page)
 Inserts a page at the head of a queue.
void moveToHead (IntrusiveDListNode &page)
 Moves a page from its current position to the head of the queue.
void insertAtTail (IntrusiveDListNode &page)
 Inserts a page at the tail of the queue.
void moveToTail (IntrusiveDListNode &page)
 Moves a page from its current position to the tail of the queue.
void remove (IntrusiveDListNode &page)
 Removes a page from the queue.
uint size ()
 
Returns:
size of the queue

IntrusiveDListNode * getHead ()
 
Returns:
a pointer to the head of the queue; NULL if the queue is empty


Private Member Functions

void validateQueue ()
 Validates the contents of the queue.

Private Attributes

IntrusiveDListNode * head
 Head of the queue.
IntrusiveDListNode * tail
 Tail of the queue.
uint len
 Length of the queue.

Detailed Description

TwoQPageQueue is used to implement the page queues used by the TwoQVictimPolicy.

It can be used to implement LRU and FIFO queues, based on how the caller inserts and moves elements in the queue.

Definition at line 38 of file TwoQVictimPolicy.h.

Constructor & Destructor Documentation

TwoQPageQueue::TwoQPageQueue (  )  [inline]

Definition at line 81 of file TwoQVictimPolicy.h.

00082     {
00083         head = NULL;
00084         tail = NULL;
00085         len = 0;
00086     }

Member Function Documentation

void TwoQPageQueue::validateQueue (  )  [inline, private]

Validates the contents of the queue.

Used for debugging.

Definition at line 58 of file TwoQVictimPolicy.h.

References IntrusiveDListNode::getNext(), and IntrusiveDListNode::getPrev().

00059     {
00060         assert(head == NULL || head->getPrev() == NULL);
00061         assert(tail == NULL || tail->getNext() == NULL);
00062 
00063         uint actualLen = 0;
00064         IntrusiveDListNode *curr = head;
00065         while (curr != NULL) {
00066             actualLen++;
00067             curr = curr->getNext();
00068         }
00069         assert(actualLen == len);
00070 
00071         curr = tail;
00072         actualLen = 0;
00073         while (curr != NULL) {
00074             actualLen++;
00075             curr = curr->getPrev();
00076         }
00077         assert(actualLen == len);
00078     }

void TwoQPageQueue::insertAtHead ( IntrusiveDListNode &  page  )  [inline]

Inserts a page at the head of a queue.

Parameters:
page the page being inserted

Definition at line 93 of file TwoQVictimPolicy.h.

References IntrusiveDListNode::insertBefore().

00094     {
00095         if (head == NULL) {
00096             assert(tail == NULL);
00097             tail = &page;
00098         } else {
00099             page.insertBefore(*head);
00100         }
00101         head = &page;
00102         len++;
00103     }

void TwoQPageQueue::moveToHead ( IntrusiveDListNode &  page  )  [inline]

Moves a page from its current position to the head of the queue.

Parameters:
page the page being moved

Definition at line 110 of file TwoQVictimPolicy.h.

References IntrusiveDListNode::detach(), IntrusiveDListNode::getPrev(), and IntrusiveDListNode::insertBefore().

Referenced by TwoQVictimPolicy< PageT >::notifyPageNice().

00111     {
00112         if (head == &page) {
00113             return;
00114         }
00115         if (tail == &page) {
00116             tail = page.getPrev();
00117         }
00118         page.detach();
00119         page.insertBefore(*head);
00120         head = &page;
00121     }

void TwoQPageQueue::insertAtTail ( IntrusiveDListNode &  page  )  [inline]

Inserts a page at the tail of the queue.

Parameters:
page the page being inserted

Definition at line 128 of file TwoQVictimPolicy.h.

References IntrusiveDListNode::insertAfter().

Referenced by TwoQVictimPolicy< PageT >::notifyPageAccess(), TwoQVictimPolicy< PageT >::notifyPageDirty(), TwoQVictimPolicy< PageT >::notifyPageUnpin(), and TwoQVictimPolicy< PageT >::notifyPopularPageAccess().

00129     {
00130         if (tail == NULL) {
00131             assert(head == NULL);
00132             head = &page;
00133         } else {
00134             page.insertAfter(*tail);
00135         }
00136         tail = &page;
00137         len++;
00138     }

void TwoQPageQueue::moveToTail ( IntrusiveDListNode &  page  )  [inline]

Moves a page from its current position to the tail of the queue.

Parameters:
page the page being moved

Definition at line 145 of file TwoQVictimPolicy.h.

References IntrusiveDListNode::detach(), IntrusiveDListNode::getNext(), and IntrusiveDListNode::insertAfter().

Referenced by TwoQVictimPolicy< PageT >::notifyPopularPageAccess().

00146     {
00147         if (tail == &page) {
00148             return;
00149         }
00150         if (head == &page) {
00151             head = page.getNext();
00152         }
00153         page.detach();
00154         page.insertAfter(*tail);
00155         tail = &page;
00156     }

void TwoQPageQueue::remove ( IntrusiveDListNode &  page  )  [inline]

Removes a page from the queue.

Parameters:
page the page being removed

Definition at line 163 of file TwoQVictimPolicy.h.

References IntrusiveDListNode::detach(), IntrusiveDListNode::getNext(), and IntrusiveDListNode::getPrev().

Referenced by TwoQVictimPolicy< PageT >::notifyPageClean(), TwoQVictimPolicy< PageT >::notifyPageUnmap(), TwoQVictimPolicy< PageT >::notifyPageUnpin(), and TwoQVictimPolicy< PageT >::notifyPopularPageAccess().

00164     {
00165         assert(len == 1 || (page.getNext() != NULL || page.getPrev() != NULL));
00166         if (&page == head && &page == tail) {
00167             assert(len == 1);
00168             head = tail = NULL;
00169         } else if (&page == head) {
00170             head = head->getNext();
00171         } else if (&page == tail) {
00172             tail = tail->getPrev();
00173         }
00174         page.detach();
00175         assert(len > 0);
00176         len--;
00177     }

uint TwoQPageQueue::size (  )  [inline]

Returns:
size of the queue

Definition at line 182 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::getDirtyVictimRange(), and TwoQVictimPolicy< PageT >::getVictimRange().

00183     {
00184         return len;
00185     }

IntrusiveDListNode* TwoQPageQueue::getHead (  )  [inline]

Returns:
a pointer to the head of the queue; NULL if the queue is empty

Definition at line 190 of file TwoQVictimPolicy.h.

Referenced by TwoQVictimPolicy< PageT >::getDirtyVictimRange(), and TwoQVictimPolicy< PageT >::getVictimRange().

00191     {
00192         return head;
00193     }

Member Data Documentation

IntrusiveDListNode* TwoQPageQueue::head [private]

Head of the queue.

Definition at line 43 of file TwoQVictimPolicy.h.

IntrusiveDListNode* TwoQPageQueue::tail [private]

Tail of the queue.

Definition at line 48 of file TwoQVictimPolicy.h.

uint TwoQPageQueue::len [private]

Length of the queue.

Definition at line 53 of file TwoQVictimPolicy.h.

The documentation for this class was generated from the following file:
Generated on Mon Jun 22 04:00:48 2009 for Fennel by  doxygen 1.5.1