//a FIFO cache

data CacheEntry {
	char key[]
	byte value[]
	int size

	int index

	CacheEntry next
	CacheEntry prev

	CacheEntry ageNext
	CacheEntry agePrev
}

data CacheBucket {
	CacheEntry list
}

const int BUCKET_COUNT = 50
const int MAX_KEY_HASH = 10 //characters

component provides Cache {

	CacheBucket buckets[]
	CacheEntry ageList
	CacheEntry ageListEnd
	Mutex lock = new Mutex()

	int maxSize
	int curSize

	int hash(char key[])
		{
		int result = key[0]
		for (int i = 0; i < key.arrayLength && i < MAX_KEY_HASH; i++)
			{
			result = result * key[i]
			}
		
		return result % BUCKET_COUNT
		}

	Cache:Cache(int max)
		{
		maxSize = max
		buckets = new CacheBucket[BUCKET_COUNT]
		for (int i = 0; i < buckets.arrayLength; i++)
			{
			buckets[i] = new CacheBucket()
			}
		}
	
	void Cache:setSize(int max)
		{
		maxSize = max
		evict(curSize)
		}
	
	CacheEntry find(char key[])
		{
		CacheEntry w = buckets[hash(key)].list

		while (w != null)
			{
			if (w.key == key)
				{
				return w
				}
			
			w = w.next
			}
		
		return null
		}
	
	void deleteItem(CacheEntry c)
		{
		curSize -= c.size

		if (ageList === c)
			{
			ageList = c.ageNext
			if (ageList != null)
				ageList.agePrev = null
				else
				ageListEnd = null
			}
			else if (ageListEnd === c)
			{
			ageListEnd = c.agePrev
			if (ageListEnd != null)
				ageListEnd.ageNext = null
				else
				ageList = null
			}
			else
			{
			c.agePrev.ageNext = c.ageNext
			c.ageNext.agePrev = c.agePrev
			}
		
		c.ageNext = null
		c.agePrev = null

		if (buckets[c.index].list === c)
			{
			buckets[c.index].list = c.next
			if (buckets[c.index].list != null) buckets[c.index].list.prev = null
			}
			else
			{
			c.prev.next = c.next
			if (c.next != null) c.next.prev = c.prev
			}
		
		c.next = null
		c.prev = null
		}
	
	void evict(int size)
		{
		while (size > maxSize)
			{
			CacheEntry c = ageListEnd

			size -= c.size
			deleteItem(c)
			}
		}

	void Cache:put(char key[], byte value[])
		{
		int size = value.arrayLength
		mutex(lock)
			{
			if (size > maxSize) throw new Exception("item with key '$(key)' is larger than maximum cache size")
			
			//search for existing
			CacheEntry w = find(key)
			if (w != null)
				{
				deleteItem(w)
				}

			//eviction
			evict(curSize + size)

			//addition
			int index = hash(key)

			CacheEntry nce = new CacheEntry(key, value, size, index)

			CacheBucket bucket = buckets[index]
			nce.next = bucket.list
			if (bucket.list != null) bucket.list.prev = nce
			bucket.list = nce

			nce.ageNext = ageList
			if (ageList != null) ageList.agePrev = nce
			if (ageListEnd == null) ageListEnd = ageList
			ageList = nce

			curSize += size
			}
		}
	
	byte[] Cache:get(char key[])
		{
		mutex(lock)
			{
			CacheEntry w = find(key)

			if (w != null)
				{
				return w.value
				}
			
			return null
			}
		}
	
	void Cache:delete(char key[])
		{
		mutex(lock)
			{
			CacheEntry w = find(key)
			if (w != null) deleteItem(w)
			}
		}
}