LRUCache - a simple least recently used cache

[Charles D Hixson]

renoX wrote:
> Charles D Hixson a écrit :
>> In the hopes that someone find this useful:
>> http://www.prowiki.org/wiki4d/wiki.cgi?CharlesHixson
>>
>> This particular version presumes D2.x code, but I think the 
>> adjustments are trivial for D1.x.
> 
> I think that there is a flaw in your code: the access counter is a 
> ushort (16bit value) and is incremented each time you access an element 
> in the cache: it can overflow quickly and will wrap around..
> 
> This means that recently used elements could have a _nodeId smaller than 
> nodes used less recently, which means that the overflow handling code 
> will drop the wrong elements..
> 
> This may not be the case in your usage, but this is either a bug or at 
> least a pretty big restriction in the usage which should be clearly 
> indicated.
> 
> 
> Regards,
> renoX

Well, two things:
1)  This code isn't really adapted for large sets of data.  If 
you want that, you'd better hand optimize it for your intended 
application.
2)  Whenever the cache is cleared, all the cache nodeId's are 
decreased by the minimum nodeId (so the new minimum is 
zero...or one, I'd need to check again.  This should decrease 
the rate at which the maximum nodeId grows.

However I *did* take your suggestion about documenting it.

OTOH, it would be better if I could renumber the nodes 
sequentially, but doing that without a sort is difficult 
(i.e., I haven't figured out how).

A different organization would be to keep nodeIds in a queue, 
with pointers to the hash table, but that has other costs. 
Still, I SHOULD add a routine to renumber everything whenever 
the maxT value starts to get withing maxSize of ushort.max. 
This routine will probably be introduced at some later version.

Any suggestions for a quick and simple way to do this?
Would it be reasonable to arbitrarily renumber everything in 
the cache serially (i.e., without considering the current 
nodeIds) whenever the maximum nodeId started to approach 
ushort.max?  (That's the direction that I'm leaning in...but I 
haven't decided whether or not it's reasonable.)