Code archives/Algorithms/LRU and MRU Cache
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
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
| ||
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