From ted@squall.cis.ufl.edu Mon Oct 25 11:27:05 1993
Received: from squall.cis.ufl.edu by SHASHA.CS.NYU.EDU (5.61/1.34)
	id AA03832; Mon, 25 Oct 93 11:27:00 -0400
Received:  by squall.cis.ufl.edu (5.61ufl/4.12)
	id AA26034; Mon, 25 Oct 93 11:25:19 -0400
Date: Mon, 25 Oct 93 11:25:19 -0400
From: "Ted Johnson" <ted@squall.cis.ufl.edu>
Message-Id: <9310251525.AA26034@squall.cis.ufl.edu>
To: shasha@SHASHA.CS.NYU.EDU
Status: R

/*	Dennis,
	Here is the simulator code.  It implement
	the algorithm we discusses over the weekend.
	fifo1 corresponds to A1in, fifo2 corresponds to A1out.
	I thought that you could use it when you talk
	to the guys at oracle.
	BTW, this code works and I ran some experiments over the
	weekend.  I note that A1in-only and A1out-only
	are available from this algorithm by putting in the right parameters.
*/

/*	This module contains the routines to
	simulate the 2-queue algoritm.
	The drivers are attached seperately.

	ASSUME: add to tail, remove from head
	        next points towards head, prev towards tail

	This algorithm implements the 3-part queue:
	fifo stores actual buffers
	fifo2 stores pointers
	lru stores buffers.

	numit (numitems) is the database size. 
	N is the total number of buffers
	available.  fifo is limited to K_1 buffers, except for startup.
        fifo2 is limited in size to K_2 entries.

*/

#include<stdio.h>
#include "def.h"


struct item_st item[MAXITEM];

int fifohist[MAXITEM],fifo2hist[MAXITEM];
int fifohead,fifotail,fifo2head,fifo2tail,lruhead,lrutail,K_1,K_2,N,numit;
int fifosize,fifo2size,lrusize;



init_queue(k1,k2,n,numitems)
int k1,k2,n,numitems; {
  int j;

	printf("******************* 2-Q algorithm ******************** \n");

    fifohead=fifotail=fifo2head=fifo2tail=lruhead=lrutail=(-1);
    fifosize=fifo2size=lrusize=0;
    K_1=k1;
    K_2=k2;
    N=n;
    numit=numitems;

    for(j=0;j<numitems;j++){
	item[j].next=(-1);	/*	list pointers	*/
	item[j].prev=(-1);
	item[j].touchcount=0;	/* keep track of # accesses */
	item[j].fifohit=0;      /* keep track of # hits	    */
        item[j].fifo2hit=0;
	item[j].lruhit=0;
	item[j].state=OUT;	/* out, lru. fifo1, fifo2   */

	fifohist[j]=0;		/* keep track of the sizes of */
	fifo2hist[j]=0;         /* the fifo queues	      */
    }
}

void access(d)
int d; {
  int temp,lost;


    item[d].touchcount++;
    fifohist[fifosize]++;
    fifo2hist[fifo2size]++;

    switch(item[d].state){
     case OUT:
      if(fifosize==0){		/* initialize fifo1	*/
	if(fifohead!=(-1) || fifotail!=(-1)){
	  printf("FIFO queue corrupt. 1\n");
	  exit(0);
	}
	fifohead=fifotail=d;
	item[d].prev=item[d].next=(-1);
	item[d].state=FIFO;
	fifosize++;
      }
      else{			/* add to tail	*/
	if(fifohead==(-1) || fifotail==(-1)){
          printf("FIFO queue corrupt. 2\n");
          exit(0);
        }
	item[d].next=fifotail;
        item[d].prev=(-1);
        item[d].state=FIFO;

        if(item[fifotail].prev!=(-1) || item[fifotail].state!=FIFO){
          printf("FIFO queue corrupt. 3\n");
          exit(0);
        }
        item[fifotail].prev=d;
	fifotail=d;
	fifosize++;
    }


        if(fifosize+lrusize>N){  /* out of free buffers */

	  if(fifosize>K_1){    /* take from fifo-1 */
	    if(item[fifohead].prev==(-1) || item[fifohead].state!=FIFO){
              printf("FIFO queue corrupt. 4\n");
              exit(0);
            }
	    lost=fifohead;	/* record to put it into fifo-2 */
	    temp=item[fifohead].prev;
	    item[fifohead].prev=item[fifohead].next=(-1);
            item[fifohead].state=OUT;
            item[temp].next=(-1);
	    fifohead=temp;
            fifosize--;

		/* now, add lost to fifo2	*/
      	  if(fifo2size==0){
	    if(fifo2head!=(-1) || fifo2tail!=(-1)){
	      printf("FIFO2 queue corrupt. a\n");
	      exit(0);
	    }
	    fifo2head=fifo2tail=lost;
	    item[lost].prev=item[lost].next=(-1);
	    item[lost].state=FIFO2;
	    fifo2size++;
          }
          else{
	    if(fifo2head==(-1) || fifo2tail==(-1)){
              printf("FIFO2 queue corrupt. 2\n");
              exit(0);
            }
	    item[lost].next=fifo2tail;
            item[lost].prev=(-1);
            item[lost].state=FIFO2;

            if(item[fifo2tail].prev!=(-1) || item[fifo2tail].state!=FIFO2){
              printf("FIFO2 queue corrupt. 3\n");
              exit(0);
            }
            item[fifo2tail].prev=lost;
	    fifo2tail=lost;
	    fifo2size++;
	  }
		/* if fifo-2 too large, shorten it.*/
	  if(fifo2size>K_2+1){    /* take from fifo-1 */
	    if(item[fifo2head].prev==(-1) || item[fifo2head].state!=FIFO2){
              printf("FIFO2 queue corrupt. 4\n");
              exit(0);
            }
	    temp=item[fifo2head].prev;
	    item[fifo2head].prev=item[fifo2head].next=(-1);
            item[fifo2head].state=OUT;
            item[temp].next=(-1);
	    fifo2head=temp;
            fifo2size--;
	  }
	}
	else{  /*	remove from LRU		*/
          if(item[lruhead].prev==(-1) || item[lruhead].state!=LRU){
            printf("LRU queue corrupt. 1\n");
            exit(0);
          }
          temp=item[lruhead].prev;
          item[lruhead].prev=item[lruhead].next=(-1);
          item[lruhead].state=OUT;
          item[temp].next=(-1);
          lruhead=temp;
          lrusize--;
        }
      }
      break;
     case FIFO:
        fifosize--;
	lrusize++;
	item[d].fifohit++;

	if(d==fifohead){
          if(item[d].next!=(-1)){
            printf("FIFO queue corrupt. 5\n");
            exit(0);
          }
          temp=item[fifohead].prev;
	  if(temp!=(-1))
            item[temp].next=(-1);
          fifohead=temp;
	}
        if(d==fifotail){
          if(item[d].prev!=(-1)){
            printf("FIFO queue corrupt. 6\n");
            exit(0);
          }
          temp=item[fifotail].next;
          if(temp!=(-1))
            item[temp].prev=(-1);
          fifotail=temp;
	}
        if(item[d].next!=(-1))
	  item[item[d].next].prev=item[d].prev;
	if(item[d].prev!=(-1))
	  item[item[d].prev].next=item[d].next;
	
	item[d].next=lrutail;
	if(lrutail!=(-1)){
          if(item[lrutail].prev!=(-1)){
            printf("LRU queue corrupt. 2\n");
            exit(0);
          }
	  item[lrutail].prev=d;
	}
	lrutail=d;
	item[d].prev=(-1);
	if(lrusize==1)
	  lruhead=d;

	item[d].state=LRU;
	break;

      case FIFO2:
        fifo2size--;
	lrusize++;
	item[d].fifo2hit++;

	if(d==fifo2head){
          if(item[d].next!=(-1)){
            printf("FIFO2 queue corrupt. 5\n");
            exit(0);
          }
          temp=item[fifo2head].prev;
	  if(temp!=(-1))
            item[temp].next=(-1);
          fifo2head=temp;
	}
        if(d==fifo2tail){
          if(item[d].prev!=(-1)){
            printf("FIFO2 queue corrupt. 6\n");
            exit(0);
          }
          temp=item[fifo2tail].next;
          if(temp!=(-1))
            item[temp].prev=(-1);
          fifo2tail=temp;
	}

        if(item[d].next!=(-1))
	  item[item[d].next].prev=item[d].prev;
	if(item[d].prev!=(-1))
	  item[item[d].prev].next=item[d].next;
	
	item[d].next=lrutail;
	if(lrutail!=(-1)){
          if(item[lrutail].prev!=(-1)){
            printf("LRU queue corrupt. 2\n");
            exit(0);
          }
	  item[lrutail].prev=d;
	}
	lrutail=d;
	item[d].prev=(-1);
	if(lrusize==1)
	  lruhead=d;

	item[d].state=LRU;
        if(fifosize+lrusize>N){  /* out of free buffers */

	  if(fifosize>K_1){    /* take from fifo-1 */
	    if(item[fifohead].prev==(-1) || item[fifohead].state!=FIFO){
              printf("FIFO queue corrupt. 4\n");
              exit(0);
            }
	    lost=fifohead;	/* record to put it into fifo-2 */
	    temp=item[fifohead].prev;
	    item[fifohead].prev=item[fifohead].next=(-1);
            item[fifohead].state=OUT;
            item[temp].next=(-1);
	    fifohead=temp;
            fifosize--;

		/* now, add lost to fifo2	*/
      	  if(fifo2size==0){
	    if(fifo2head!=(-1) || fifo2tail!=(-1)){
	      printf("FIFO2 queue corrupt. a\n");
	      exit(0);
	    }
	    fifo2head=fifo2tail=lost;
	    item[lost].prev=item[lost].next=(-1);
	    item[lost].state=FIFO2;
	    fifo2size++;
          }
          else{
	    if(fifo2head==(-1) || fifo2tail==(-1)){
              printf("FIFO2 queue corrupt. 2\n");
              exit(0);
            }
	    item[lost].next=fifo2tail;
            item[lost].prev=(-1);
            item[lost].state=FIFO2;

            if(item[fifo2tail].prev!=(-1) || item[fifo2tail].state!=FIFO2){
              printf("FIFO2 queue corrupt. 3\n");
              exit(0);
            }
            item[fifo2tail].prev=lost;
	    fifo2tail=lost;
	    fifo2size++;
	  }
		/* if fifo-2 too large, shorten it.*/
	  if(fifo2size>K_2+1){    /* take from fifo-1 */
	    if(item[fifo2head].prev==(-1) || item[fifo2head].state!=FIFO2){
              printf("FIFO2 queue corrupt. 4\n");
              exit(0);
            }
	    temp=item[fifo2head].prev;
	    item[fifo2head].prev=item[fifo2head].next=(-1);
            item[fifo2head].state=OUT;
            item[temp].next=(-1);
	    fifo2head=temp;
            fifo2size--;
	  }
	}
	else{  /*	remove from LRU		*/
          if(item[lruhead].prev==(-1) || item[lruhead].state!=LRU){
            printf("LRU queue corrupt. 1\n");
            exit(0);
          }
          temp=item[lruhead].prev;
          item[lruhead].prev=item[lruhead].next=(-1);
          item[lruhead].state=OUT;
          item[temp].next=(-1);
          lruhead=temp;
          lrusize--;
        }
      }
      break;

      case LRU:
	item[d].lruhit++;
	if(lrusize>1 && d!=lrutail){
          if(d==lruhead){
            if(item[d].next!=(-1)){
              printf("LRU queue corrupt. 4\n");
              exit(0);
            }
            temp=item[lruhead].prev;
	    if(temp==(-1)){
              printf("LRU queue corrupt. 7\n");
              exit(0);
            }
            item[temp].next=(-1);
            lruhead=temp;
          }
	  else
	  {
            if(item[d].next!=(-1))
              item[item[d].next].prev=item[d].prev;
            if(item[d].prev!=(-1))
              item[item[d].prev].next=item[d].next;
	  }
  
          item[d].next=lrutail;
	  item[d].prev=(-1);
          if(lrutail!=(-1)){
            if(item[lrutail].prev!=(-1)){
              printf("LRU queue corrupt. 5\n");
              exit(0);
            }
            item[lrutail].prev=d;
          }
          lrutail=d;
	}

	
	break;
    }
}


/*	--------------  dump routines for debugging ------------------- */


void printqueue()
{
  int point,lfc;

	point=fifotail;
	printf("FIFO:\n");
	lfc=0;
	while(point!=(-1)){
	  printf("%6d ",point);
	  lfc++;
	  if((lfc%10)==0)
	    printf("\n");
	  point=item[point].next;
	}
	printf("\n");

	point=fifo2tail;
	printf("FIFO2:\n");
	lfc=0;
	while(point!=(-1)){
	  printf("%6d ",point);
	  lfc++;
	  if((lfc%10)==0)
	    printf("\n");
	  point=item[point].next;
	}
	printf("\n");

        point=lrutail;
        printf("LRU:\n");
        lfc=0;
        while(point!=(-1)){
          printf("%6d ",point);
          lfc++;
          if((lfc%10)==0)
            printf("\n");
          point=item[point].next;
        }
        printf("\n");
}

dump(){
int i;

printf("fifohead=%d fifotail=%d fifosize=%d\n",fifohead,fifotail,fifosize);
printf("fifo2head=%d fifo2tail=%d fifo2size=%d\n",fifo2head,fifo2tail,fifo2size);
printf("lruhead=%d lrutail=%d lrusize=%d\n",lruhead,lrutail,lrusize);

printf("i	next	prev	touch	fifo	fifo2	lru	state\n");
for(i=0;i<numit;i++){
  printf("%d	%d	%d	%d	%d	%d	%d	%d\n",i,item[i].next,item[i].prev,item[i].touchcount,item[i].fifohit,item[i].fifo2hit,item[i].lruhit,item[i].state);
}
}
  


