implement Cache;

include "sys.m";
	sys : Sys;

include "bufio.m";
	bufio : Bufio;
Iobuf : import bufio;

dbg_log : ref Sys->FD;

include "cache.m";

HASHSIZE : con 1019;

lru ,cache_size : int; # lru link, and maximum size of cache.
cur_size, cur_tag : int; # current size of cache and current number.

lockch : chan of int;

Cache_link : adt{
	name : string; 			# name of file
	contents : array of byte; 	# contents
	length : int; 			# length of file
	qid:Sys->Qid;			
	tag : int;
};

tab := array[HASHSIZE] of list of Cache_link;

hashasu(key : string,n : int): int
{
	i, h : int;
	h=0;
	i=0;
        while(i<len key){
		h = 10*h + key[i];
		h = h%n;
		i++;
	}
	return h%n;
}


insert(name: string, ctents: array of byte , length : int, qid:Sys->Qid) : int
{
	tmp : Cache_link;
	hash : int;
	lock();
	hash = hashasu(name,HASHSIZE);
	if (dbg_log!=nil){
		sys->fprint(dbg_log,"current size is %d, adding %s\n", cur_size,name);
	}
	while (cur_size+length > cache_size)
		throw_out();
	tmp.name =name;
	tmp.contents = ctents;
	tmp.length = length;
	tmp.qid = qid;
	tmp.tag = cur_tag;
	cur_size+=length;
	cur_tag++;
	if (cur_tag<0) cur_tag=0;
	tab[hash]= tmp :: tab[hash];
	unlock();
	return 1;
}

find(name : string, qid:Sys->Qid) : (int, array of byte)
{
	hash,flag,stale : int;
	nlist : list of Cache_link;
	retval : array of byte;
	flag=0;
	nlist=nil;
	retval=nil;
	stale=0;
	lock();
	hash = hashasu(name,HASHSIZE);
	tmp:=tab[hash];
	for(;tmp!=nil;tmp = tl tmp){
		link:=hd tmp;
		if (link.name==name){
			if(link.qid.path==qid.path && link.qid.vers==qid.vers){
				link.tag=cur_tag;
				cur_tag++;
				flag = 1;
				retval = (hd tmp).contents;
			} else { # cache is stale
				lru--;  if(lru<0) lru = 0;
				link.tag = lru;
				stale = 1;
			}
		}
		nlist = link :: nlist;
	}
	tab[hash]=nlist;
	if (flag && (dbg_log!=nil))
		sys->fprint(dbg_log,"Found %s in cache, cur_tag is %d\n",name,cur_tag);
	if (stale){
		if (dbg_log!=nil)
			sys->fprint(dbg_log,"Stale %s in cache\n",name);
		throw_out();
	}
	unlock();
	return (flag,retval);
}	

throw_out()
{
	nlist : list of Cache_link;
	for(i:=0;i<HASHSIZE;i++){
		tmp:=tab[i];
		for(;tmp!=nil;tmp = tl tmp)
			if ((hd tmp).tag==lru)
				break;
		if (tmp!=nil)
			break;
	}
	if (i==HASHSIZE && (dbg_log!=nil))
		sys->fprint(dbg_log,"LRU not found!!!\n");
	# now, the lru is in tab[i]...
	nlist=nil;
	for(;tab[i]!=nil;tab[i]=tl tab[i]){
		if ((hd tab[i]).tag==lru){
			if (dbg_log!=nil)
				sys->fprint(dbg_log,"Throwing out %s\n",(hd tab[i]).name);
			cur_size-=(hd tab[i]).length;	
			tab[i] = tl tab[i];
		}
		if (tab[i]!=nil)
			nlist = (hd tab[i]) :: nlist;
		if (tab[i]==nil) break;
	}
	lru=find_lru();
	if (dbg_log!=nil)
		sys->fprint(dbg_log,"New lru is %d",lru);
	tab[i] = nlist;
}

find_lru() : int
{
	min := cur_tag;
	for(i:=0;i<HASHSIZE;i++){
		tmp:=tab[i];
		for(;tmp!=nil;tmp = tl tmp)
			if ((hd tmp).tag<min)
				min=(hd tmp).tag;
	}
	return min;
}

cache_init(log : ref Sys->FD, csize : int)
{
	n : int;
	for(n=0;n<HASHSIZE;n++)
		tab[n]= nil;
	lru=0;
	cur_size=0;
	cache_size = csize*1024;
	sys = load Sys Sys->PATH;
	dbg_log = log;
	lockch = chan of int;
	spawn lockproc();
	if (dbg_log!=nil)
		sys->fprint(dbg_log,"Cache initialised, max size is %d K\n",cache_size);
}


dump() : list of (string,int,int)
{
	retval: list of (string,int,int);
	lock();
	for(i:=0;i<HASHSIZE;i++){
		tmp:=tab[i];
		while(tmp!=nil){
			retval = ((hd tmp).name, (hd tmp).length,
					(hd tmp).tag) :: retval;
			tmp = tl tmp;
		}
	}
	unlock();
	return retval;
}

lockproc()
{
	for(;;) {
		<- lockch;
		lockch <-=0;
	}
}

lock()
{
	lockch <-= 0;
}

unlock() 
{
	<-lockch;
}