LRU and MRU Cache

This code has been declared by its author to be Public Domain code.

LRU and MRU Cache by col

2016

This simple piece of code is a 'least recent used' and 'most recent used' cache. When you hit an object in the cache then it goes to front of a list. If the object isn't in the cache then it will be added. The least recent items then get naturally bubbled to the backend of the list. You can inspect and/or remove the least recently used item(s) if you needed. It uses a map to get to the required object in the list as fast as possible instead of iterating over the list.

EDITED:- I thought I may as well add in a little more code to allow access to the most recent used item as well.

Legacy BlitzMax and BlitzmaxNG compatible.

Type TCache
	Field _map:TMap
	Field _list:TList
	
	Method New()
		_map = New TMap
		_list = New TList
	EndMethod
	
	Method hit(obj:Object)
		Local link:TLink = TLink(_map.valueforkey(obj))
		
		' add to the cache if not in it
		If Not link
			Local link:TLink = _list.addfirst(obj)
			_map.insert(obj,link)
			Return
		EndIf

		' remove link from list
		link._succ._pred = link._pred
		link._pred._succ = link._succ
		
		' move link to the front
		link._pred = _list._head
		link._succ = _list._head._succ
		link._succ._pred = link
		_list._head._succ = link
	EndMethod
	
	Method dropLRU:Object()
		Return _list.removelast()
	EndMethod
	
	Method dropMRU:Object()
		Return _list.removefirst()
	EndMethod
	
	Method getLRU:Object()
		Return _list.last()
	EndMethod
	
	Method getMRU:Object()
		Return _list.first()
	EndMethod
	
	Method clear()
		_map.clear()
		_list.clear()
	EndMethod
EndType



' EXAMPLE USE
		
Local cache:TCache = New TCache

cache.hit("a")
cache.hit("b")
cache.hit("c")
cache.hit("d")
cache.hit("e")

cache.hit("d")
cache.hit("a")
cache.hit("c")
cache.hit("d")
cache.hit("c")

Print
Print "Dropping '" + String(cache.dropLRU()) + "' from the cache"
Print

' show cache contents
Print "Cache contents:"
For Local i:String = EachIn cache._list
	WriteStdout i + " "
Next

Print
Print
Print "Most recent used item: " + String(cache.getMRU())

Comments

Derron

2016

For last recently used you could even store it in an extra field of TCache. This would save the call to First().

Of course it then gets more expensive (more todo in hit()) when not accessing that information regularily.

Bye
Ron

Code Archives Forum