tvsimbuf.c

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.c,v $
// $Author: davelin $
// $Date: 1995/02/25 02:33:09 $
// $Revision: 9.1 $

#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>
#include "TVdefine.h"


// extra include file for use in subsequence matching

#include "TVsimbuf.h"


Storage::Storage(int ps, int buffercount) 
{ 
   pagesize = ps;
   nextpage = 1;
  
   // initialize buffers
   bufmaxcount = buffercount;

   diskpagenumber = new PageNumber[bufmaxcount];
   dirty = new int[bufmaxcount]; 
   bufcount = 0;
   int i;
   for (i = 0; i < bufmaxcount; i++)
      {
         diskpagenumber[i] = BUFAVAILABLE;
         dirty[i] = FALSE;
      }

   // For LRU 
   ptrtoqnode = new DoublyLinkedListTVNode*[bufmaxcount];
   for (i = 0; i < bufmaxcount; i++)
      {
        ptrtoqnode[i] = new DoublyLinkedListTVNode(i);
	LRUqueue.inserttail(ptrtoqnode[i]);
      } 

   // For round robin
   int nextrelease = 0;

   // Initialize stats
   initstats();
}

Storage::~Storage() 
{ 
  delete [] diskpagenumber;
  delete [] dirty;
}

Storage& Storage::initstats()
{
   readrequestcount = 0;
   writerequestcount = 0;
   diskfetchcount = 0;
   pagewritecount = 0;
   return *this;
}
void Storage::MovetoLRUtail(const BufPageNumber pn)
{
   LRUqueue.deletenode(ptrtoqnode[pn]);
   LRUqueue.inserttail(ptrtoqnode[pn]);
}

Storage& Storage::fetch(PageNumber pn)
{
  readrequestcount++;

  int i = SearchPage(pn);
  if (i == BUFNOTFOUND)
     {
       // Not in buffer, fetch a buffer to store it
       BufPageNumber bpn = GetFreeBufNum();
       diskpagenumber[bpn] = pn;
       fetchfromstorage(bpn, pn);
       MovetoLRUtail(bpn);
     }
  else
     MovetoLRUtail(i);
  return *this;
}

Storage& Storage::writepage(PageNumber pn)
{
  writerequestcount++;
  int i = SearchPage(pn);
  if (i != BUFNOTFOUND)
     {
        dirty[i] = TRUE;
        MovetoLRUtail(i);
     }
  return *this;
}

Storage& Storage::flushbuffer()
{
  for (BufPageNumber i = 0; i < bufmaxcount; i++)
      writetostorage(i); 
  return *this;
}

Storage& Storage::emptybuffer()
{
  for (BufPageNumber i = 0; i < bufmaxcount; i++)
   {
      writetostorage(i); 
      diskpagenumber[i] = BUFAVAILABLE;
   }
 
  return *this;
}

PageNumber Storage::newpage()
{
//cout << "Assign new page\n";
  BufPageNumber freebufnum = GetFreeBufNum();
  diskpagenumber[freebufnum] = nextpage;
  dirty[freebufnum] = TRUE;
  MovetoLRUtail(freebufnum);
  return nextpage++;
}

int Storage::getpagesize() 
{
  return pagesize;
}

// Make that page useable again
Storage& Storage::clearpage(PageNumber pn)
{
  int i = SearchPage(pn);
  if (i != BUFNOTFOUND)
     dirty[i] = FALSE;
  return *this;
}


 
BufPageNumber Storage::GetFreeBufNum()
{
   BufPageNumber i;
   for (i = 0; (i < bufmaxcount) && (diskpagenumber[i] != BUFAVAILABLE); i++)
       ;
   BufPageNumber res;
   if (i == bufmaxcount)
      {
         // Find a replacement
         /*
         writetostorage(nextrelease);
         res = nextrelease++;
	 nextrelease = nextrelease % bufmaxcount;
	 */
         res = LRUqueue.headnum(); 
	 writetostorage(res);
      }
    else
       res = i; 
  return res;
}

// return Bufpagenumber,
// return BUFNOTFOUND is NOT found
BufPageNumber Storage::SearchPage(PageNumber pn)
{
  BufPageNumber i;
  for (i = 0; (i < bufmaxcount) && (diskpagenumber[i] != pn); i++) 
     ;
  return (i == bufmaxcount ? BUFNOTFOUND : i);
} 


void Storage::fetchfromstorage(BufPageNumber bpn, PageNumber pn)
{
   diskfetchcount++;
   diskpagenumber[bpn] = pn;

}
 
void Storage::writetostorage(BufPageNumber bpn)
{
    if (dirty[bpn])
       {
	  pagewritecount++; 
	  dirty[bpn] = FALSE;
       }
}

void Storage::printstats(ostream& os) const
{
   os << "Read request : " << readrequestcount << "  Write request : " << writerequestcount;
   os << "  Disk fetch : " << diskfetchcount << "  Pgae writes : " << pagewritecount;
}

  

ostream& operator<<(ostream& os, const Storage& s)
{
   os << "Pagesize : " << s.pagesize << "   No. of buffers : " << s.bufmaxcount << endl;
   os << "Total page used : " << s.nextpage - 1 << endl;
   DoublyLinkedListTVNode *p = s.LRUqueue.head->next;

   os << "Buffer content : {" <<  s.diskpagenumber[p->bpn] << (s.dirty[0] ? "*" : "");
   p = p->next;
   while (p != s.LRUqueue.head)
      {
        os << ", " <<  s.diskpagenumber[p->bpn] << (s.dirty[0] ? "*" : "");
	p = p->next;
      }
   os << "}\n";
   s.printstats(os);
   return os;
}