//an LRU 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

const bool TRACE = false

component provides Cache(Destructor) requires io.Output out, data.IntUtil iu {

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

	int CACHE_REC_SIZE = 0

	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()
			}
		
		CACHE_REC_SIZE = 256
		}
	
	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 + CACHE_REC_SIZE + c.key.arrayLength)

		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 + CACHE_REC_SIZE + c.key.arrayLength)
			deleteItem(c)
			if (TRACE) out.println("evi: $(c.key) with $(c.size) [total $curSize / $maxSize]")
			}
		}
	
	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 + CACHE_REC_SIZE + key.arrayLength)

			//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 + CACHE_REC_SIZE + key.arrayLength

			if (TRACE) out.println("put: $(key) with $size [total $curSize / $maxSize]")
			}
		}
	
	void updateUse(CacheEntry w)
		{
		//move the item to the front of the age list, as the new most-recently-used item
		if (ageList !== w)
			{
			if (ageListEnd === w)
				{
				ageListEnd = w.agePrev
				ageListEnd.ageNext = null
				}
				else 
				{
				w.agePrev.ageNext = w.ageNext
				w.ageNext.agePrev = w.agePrev
				}
			
			w.ageNext = ageList
			w.agePrev = null
			ageList.agePrev = w
			ageList = w
			}
		}
	
	byte[] Cache:get(char key[])
		{
		mutex(lock)
			{
			CacheEntry w = find(key)

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

		while (w != null)
			{
			CacheEntry td = w
			w = w.ageNext
			td.ageNext = null
			td.agePrev = null
			}
		
		ageList = null
		ageListEnd = null

		for (int i = 0; i < buckets.arrayLength; i++)
			{
			w = buckets[i].list

			while (w != null)
				{
				CacheEntry td = w
				w = w.next
				td.next = null
				td.prev = null
				}
			}
		}
}