/* Copyright 1997 Pei Cao
 */

/*
This is how GD works: pick min cost, then substract min_cost from every
other page's cost; if the document is touched again, its cost is restored to
its original cost;

This is how I am going to change it.  pick min cost, evict it, and add 
min_cost to a global count inflation; and when a document is touched, its cost
is restored to its original cost + inflation;

The problem to watch for, is that inflation should not overflow.  Thus,
I check for it and do a scan of priority queue reducing inflation;
*/


/* for GreedyDual, the definition of "cost" can vary.  it is defined based on
	the value of GD_Cost_Def;
*/
/*
#define DEBUG
*/
int GD_Caculate_Cost(page,cost,size)
PageID page;
int  size;
long  cost;
{
	int gd_cost;

	if (size ==0)
		return(0);

	switch(GD_Cost_Def) {

	case FOR_SIZE: {
		return((long)(1*1e6/size));
	}

	case FOR_PACKETS: {
		return((long)(GET_PACKET(size)*1e6/size));
	}

	case PURE_LATENCY:

		if (cost < 0)
			cost = 0;
		return(cost/1e3);	/* count only millisec */

	case PURE_PERBYTE_LATENCY:

		if (cost < 0)
			cost = 0;
		return((long)(cost/size));

	case AVG_LATENCY: {
        	long conn; 
		int s = page.server;

        	if (Servers[s].connect == 0) 
           		conn = Ave_Connect; 
        	else conn = Servers[s].connect; 

        	if ( Servers[s].bandwidth > 0) 
           		gd_cost =  
				(long)(conn + size/Servers[s].bandwidth); 
        	else 
			gd_cost = conn; 
		return(gd_cost/1e3); 	/* count only to millisec */
	}

	case AVG_PERBYTE_LATENCY: {
        	long conn; 
		int s = page.server;

        	if (Servers[s].connect == 0) 
           		conn = Ave_Connect; 
        	else conn = Servers[s].connect; 

        	if ( Servers[s].bandwidth > 0) 
           		gd_cost = (long)((conn+W_b/Servers[s].bandwidth)/size ); 
        	else 
			gd_cost = (long)(conn/size ) ; 
		return(gd_cost);
	}

	case RANDOM_HOPS: {
		int hops = (page.server % 32) + 1;
		return(hops);
	}

	case HOPS_PERBYTE: {
		int hops = (page.server % 32) + 1;
		return((long)(hops*1e5/size));
	}

	case BIMODAL_HOPS: {

		if ((page.server % 32) > 27)
			return(32);
		else
			return(1);
	}

	case BIMODAL_HOPS_PERBYTE: {

		if ((page.server % 32) > 27)
			return((long)(32*1e6/size));
		else
			return((long)(1*1e6/size));
	}

	}

}


long inflation = 0;
void reduce_inflation();

void GreedyDual(Cache_Size)
float Cache_Size;
{
	struct alg_stat gd;
	int total_entry_in_cache = 0;
	int i; 
	long gd_cost; /* gd_cost must be a positive integer; */

	INIT_STAT(gd);

	if (GD_Cost_Def == AVG_LATENCY)
		Clear_ServerArray();

	inflation = 0;
	total_in_mem = 0.0;

        /* Read in values for page_sequence and cost_sequence */

	for (i=0;i<Total_Req;i++) {
		PageID page;
		int  size;
		long  cost;
		int last_mod;

		int hops;
		int place; 

		char file_changed;
		char miss;

		SCAN_INPUT;

		place = Seen(page);
		if(place < 0)
			fprintf(stderr,"Problem\n");

		if (GD_Cost_Def == AVG_LATENCY)
			Update_LatencyEstimate(page, size, cost);

		SET_FILE_CHANGED;
		
		miss = 0;

		gd_cost = GD_Caculate_Cost(page,cost,size);
			/* if gd_cost < 0, it is probably a overflow... */
		if (gd_cost <0 || gd_cost > MAX_INT) {
			gd_cost = MAX_INT - 1000;
		}

	   	if(pages_in[place].where!=NULL) {
			PAGE *tmp = pages_in[place].where;

			CHANGE_SIZE_FILE_CHANGED;

			pq_remove(&q, tmp->queuenum);
			if (i% 100000 == 0)
				pq_verify(&q);

			if (gd_cost + inflation >= MAX_INT) {
				fprintf(stderr, "reducing inflation.\n");
				reduce_inflation();
				fprintf(stderr, "inflation reduced.\n");
			}

			tmp->sorting_order = 0 - (gd_cost + inflation);
				/* see comment above*/
                        tmp->H = gd_cost;
				/* actually, I am not using H in this version */

			pq_insert(&q, tmp);
			if (i% 100001 == 0)
				pq_verify(&q);
		
	 	} else {

			miss = 1;

			if (size < Cache_Size) {
				GD_Add(page,size,place,gd_cost);
				total_entry_in_cache++;
			}
	    	}
	
		if (miss)
			UPDATE_STAT(gd);

		while(total_in_mem > Cache_Size) {
			GD_Evict();
			total_entry_in_cache--;
		}

		if (i%100000 == 0)
			fprintf(stderr, "GreedyDual Progress  %d\n", i);

        }

	while (total_entry_in_cache>0) {
		GD_Evict();
		total_entry_in_cache--;
	}

	assert(pq_empty(&q));

	printf("GreedyDual simulation end; total_in_mem is %f\n", total_in_mem);
	
/*
	fprintf(fpout, "GreedyDual (Cost Def = %d )\n", GD_Cost_Def);
*/

	{ char s[80];
	sprintf(s, "GreedyDual(%d)", GD_Cost_Def);
	print_algstat(s, gd);
	}
}

void reduce_inflation()
{
	int i;

	for (i=0; i<Total_Req; i++) 
		if (pages_in[i].where != NULL) {
			PAGE *tmp = pages_in[i].where;

			if (tmp->queuenum != 0) {
				
			pq_remove(&q, tmp->queuenum);

			assert(tmp->sorting_order <=0);
			tmp->sorting_order += inflation;
			assert(tmp->sorting_order < MAX_INT);
			pq_insert(&q, tmp);

			}
		}

	pq_verify(&q);

	inflation = 0;
}
		
	
/* cost here is an argument passed by the calling routine;
   the calling routine will use the proper definition of
   cost;
*/
void GD_Add(page,size,place,cost)
int size, place;
PageID page;
long cost;
{
	PAGE *bring_in;

	assert(cost >= 0);

	bring_in = (PAGE *)malloc(sizeof(PAGE));

	bring_in->size = size;
	SET_PAGE(bring_in->page, page);
	bring_in->place = place;
	bring_in->queuenum = 0;

	/* Priority Queue */
	if (cost + inflation >= MAX_INT) {
		fprintf(stderr, "reducing inflation. cost is %d inflation is %d\n", cost, inflation);
		reduce_inflation();
		fprintf(stderr, "inflation reduced.\n");
	}

	bring_in->sorting_order = 0 - (cost + inflation) ;	
	bring_in->H = cost;

				/* GD will replace the lowest cost first */
	pq_insert(&q, bring_in);	
	pq_insert_count++;
	/*assert(pq_verify(&q) == 0);*/

	assert(SAME_PAGEID(pages_in[place].page, page));
        pages_in[place].where = bring_in;

/*
	printf("In ( %d %d ) size %d cost %d sorted %d\n",
			bring_in->page.server, bring_in->page.path,
			bring_in->size, bring_in->H, 0- bring_in->sorting_order);
*/
        total_in_mem += size;
}	

void GD_Evict()
{
	PAGE *temp;

	/*assert(pq_verify(&q) == 0);*/
	temp = pq_top(&q);	/* temp is removed from q by pq_top */
	pq_top_count++;
	/*assert(pq_verify(&q) == 0);*/

	/* the following test is a simple check on whether pq_top returns
		the top element */
  if ((q.pqsize && temp->sorting_order < q.pqdata[1]->sorting_order) ||
      (temp->sorting_order > q.pqdata[0]->sorting_order)) {

    fprintf(stderr, " got mangled pq: \n"
            "    q.pqdata[0]: sorting_order = %d, path = %x\n"
            "    q.pqdata[1]: sorting_order = %d, path = %x\n"
            "    q.pqdata[2]: sorting_order = %d, path = %x\n"
            "    toswap:      sorting_order = %d, path = %x\n",
            q.pqdata[0]->sorting_order, q.pqdata[0]->page.path,
            q.pqdata[1]->sorting_order, q.pqdata[1]->page.path,
            q.pqdata[2]->sorting_order, q.pqdata[2]->page.path,
            temp->sorting_order, temp->page.path);
  }

	/*
	{
	long old_inflation = (0 - temp->sorting_order) - temp->H;
        long actual_H = temp->H - (inflation - old_inflation);

	inflation = inflation + actual_H;
	}
	*/
	inflation = (0 - temp->sorting_order);



  	   total_in_mem -= temp->size;
	   assert(SAME_PAGEID(pages_in[temp->place].page, temp->page));
           pages_in[temp->place].where=NULL;
#ifdef DEBUG
	   fprintf(stderr, "Evict Page GD:\t%d\t%d\t%d\n", pages_in[temp->place].page.server, pages_in[temp->place].page.path, 0-temp->sorting_order);
#endif

/*
	printf("Kick entry ( %d %d ) size %d cost %d sorted %d\n",
		temp->page.server, temp->page.path, temp->size, temp->H, (0- temp->sorting_order));
*/
	   free(temp);
}