tvsimbuf.h

TV-tree的c实现源码

/* 
 
                  COPYRIGHT NOTICE
 
This material was developed by Christos Faloutsos and King-Ip Lin
at the University of Maryland, College Park, Department of Computer Science.
Permission is granted to copy this software, to redistribute it
on a nonprofit basis, and to use it for any purpose, subject to
the following restrictions and understandings.
 
1. Any copy made of this software must include this copyright notice
in full.
 
2. All materials developed as a consequence of the use of this
software shall duly acknowledge such use, in accordance with the usual
standards of acknowledging credit in academic research.
 
3. The authors have made no warranty or representation that the
operation of this software will be error-free or suitable for any
application, and they are under under no obligation to provide any
services, by way of maintenance, update, or otherwise.  The software
is an experimental prototype offered on an as-is basis.
 
4. Redistribution for profit requires the express, written permission
of the authors.
 
*/

// Author : $Author$
// Date : $Date$
// Id : $Id$
// $Source: /afs/alm/cs/quest/subseq/src2/RCS/rplus_simbuf.h,v $
// $Author: davelin $
// $Date: 1995/02/25 02:33:09 $
// $Revision: 9.1 $

typedef int PageNumber;
typedef int BufPageNumber;

#define NEWPAGE -1
#define EMPTYPAGE -2

#define BUFAVAILABLE 0

#define BUFNOTFOUND -1


//Doubly-linked list (for LRU)

class DoublyLinkedListTVNode {

public:
   DoublyLinkedListTVNode() {bpn = -1; prev = next = NULL;};

   DoublyLinkedListTVNode(BufPageNumber b) {bpn = b; prev = next = NULL;};

   DoublyLinkedListTVNode(BufPageNumber b, DoublyLinkedListTVNode *p, DoublyLinkedListTVNode *n)
     {bpn = b; prev = p; next = n;};

   BufPageNumber bpn;
   DoublyLinkedListTVNode *prev, *next;
};

class DoublyLinkedList {

public:
   DoublyLinkedList() {head = new DoublyLinkedListTVNode; head->prev = head->next = head;};

   DoublyLinkedList& inserttail(DoublyLinkedListTVNode *p)
        {p->prev = head->prev; p->next = head; head->prev->next = p; head->prev = p; return *this;};

   DoublyLinkedListTVNode*  deletehead()
        {DoublyLinkedListTVNode *p = head->next;
         if (p != head)
           {
             head->next = p->next;
             head->next->prev = head;
           }
         else
            p = NULL;
         return p;
       };
  
   DoublyLinkedListTVNode* deletenode(DoublyLinkedListTVNode *p)
       {
           p->prev->next = p->next;
           p->next->prev = p->prev;
           return p;
       };
   BufPageNumber headnum() 
     { return head->next->bpn;};


   DoublyLinkedListTVNode *head, *tail;
};


// Storage for all the pages
class Storage{
  friend ostream& operator<<(ostream& os, const Storage& s);

public:
  Storage(int ps, int buffersize);

  ~Storage();
 
  // Fetch the page into the buffer, return the pointer
  Storage& fetch(PageNumber pn);

  // Signal to buffer page is dirty
  Storage& writepage(PageNumber pn);

  // Write all the buffer to disk
  Storage& flushbuffer();
  Storage& emptybuffer(); // flush and EMPTY the buffer

  // Get a new page and put it on the buffer
  PageNumber newpage();

  int getpagesize();

  // Make that page useable again
  Storage& clearpage(PageNumber pn);

  Storage& initstats();

  void printstats(ostream& os) const;

  // Buffer stats (made public for easier manipulation
  int readrequestcount; // total number of page request
  int writerequestcount; // total number of page request
  int diskfetchcount;  // total number of fetch from/to disk 
		        // necessary
  int pagewritecount;  // number of writes made


private:
  BufPageNumber SearchPage(PageNumber pn);
  BufPageNumber GetFreeBufNum();

  void fetchfromstorage(BufPageNumber bpn, PageNumber pn);
  void writetostorage(BufPageNumber bpn);

  void MovetoLRUtail(const BufPageNumber pn);



  
  int pagesize;

  // simulate buffer
  PageNumber *diskpagenumber; // 0 denote buffer available
		              // DISK PAGE START FROM 1
			      // Page 0 is reserved
  int *dirty;    // TRUE if page dirty
  int bufmaxcount;
  int bufcount;

  // vaiables for replacement policy

  // Round Robin
  int nextrelease;

  // LRU
  DoublyLinkedList LRUqueue;
  DoublyLinkedListTVNode **ptrtoqnode; // ptr pointer to position 
				    // of buffer at queue

  // simulate disk
  // Just assume pages are assigned from 1 onwards
  // Pagecount is the NEXT available page number
  int nextpage;


};