#!/n/flip/h/dreeves/mash/mash

(* Cache simulator: 
      this program is runnable from a command line by using MASH, 
  available at 
		http://ai.eecs.umich.edu/people/dreeves/misc/mash/
			After installing mash on your machine, edit the line above to point to it, 
  and make sure that that line is the first line of this 
      file. Alternatively (non-Unix systems) run mash directly with this file 
      as the first command-line argument. *)

(* $Id:caching.nb,v1.11999/05/1322:22:21dreevesExpdreeves$ *)

pout[args__]:=WriteString["stdout",args]
perr[args__]:=WriteString["stderr",args]
SetAttributes[assert,HoldFirst];
assert[test_]:=
  If[!Evaluate[test],{perr["FAILED: ",Hold[test],"\n"];Exit[1];},True];





If[Length[ARGV]<4,
	pout["Usage: ",ARGV[[1]]," url-file request-file cache-size\n"];
	Exit[1]];

urlFilename=ARGV[[2]];
reqFilename=ARGV[[3]];
cacheSize=ToExpression[ARGV[[4]]];

perr["Begin slurping data.\n"];
idSizePairs=ReadList[urlFilename,{Number,Number}];
Scan[(size[#[[1]]]=#[[2]];next[#[[1]]]=Null;prev[#[[1]]]=Null)&,idSizePairs];
perr["Done slurping id/size data.\n"];
requests=ReadList[reqFilename];
perr["Done slurping requests.\n"];

free=cacheSize;
cacheHead=-1;
cacheTail=-2;
next[cacheHead]=cacheTail;prev[cacheHead]=Null;
prev[cacheTail]=cacheHead;next[cacheTail]=Null;
hitCount=0;

in[id_]:=prev[id]=!=Null&&next[id]=!=Null

insertBefore[x_,me_]:=(
		assert[prev[me]===Null&&next[me]===Null];
		prev[me]=prev[x];next[me]=x;
		next[prev[x]]=me;prev[x]=me;
		me)
insertAfter[x_,me_]:=insertBefore[next[x],me]

remove[me_]:=(
		next[prev[me]]=next[me];prev[next[me]]=prev[me];
		prev[me]=Null;next[me]=Null;
		me)

printcache[str_]:=Module[{p},
		pout[str,": "];
		For[p=cacheHead,p!=cacheTail,p=next[p],
			pout[p,", "]];
		pout[cacheTail];
		pout["  free: ",free,"\n"];]

processRequest[id_]:=
	Which[
		in[id],
			hitCount++;
			remove[id];
			insertAfter[cacheHead,id],
		size[id]>cacheSize,Null,
		True,
			While[free<size[id],
				assert[prev[cacheTail]!=cacheHead];
				free+=size[remove[prev[cacheTail]]]];
			free-=size[insertAfter[cacheHead,id]]]

time=Scan[processRequest,requests]//Timing//First;

pout[hitCount,"\n"];
perr["Hit ratio: ",hitCount," / ",Length[requests]," = ",
  N[hitCount/Length[requests]],"\n(CPU time: ",time,")\n"];
