LRUCache - a simple least recently used cache

[Charles D Hixson]

janderson wrote:
> Charles D Hixson wrote:
>>
>> 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?
> 
> A good form of documentation is to use contracts for this sort of thing.
> 
> -Joel
One of us is grossly misunderstanding the other.  I can't see 
any application of contracts to this problem.

Note that the maximum length is specified as a ushort, so it's 
guaranteed that there will always be enough allocatable 
nodeId's to hold all the entries in the list.  (This *doesn't* 
mean that this would be a good idea.  A cache that large would 
usually be a very bad idea.)

Also, an LRUCache is allowed to drop entries on the grounds 
that they "haven't been used recently enough", so you can't 
depend on the thing that you stuck in there awhile ago to 
still be there.

The problem was a quick way of renumbering the entries that 
retained the time ordering.  The current version gives up on 
retaining the time ordering, and after a cache clear that 
leaves the highest node near the maximum nodeId value, it just 
renumbers everything from by hashcode order.  This should work 
well enough in most cases, but it would be better if I didn't 
need to lose the order of last access.  I just haven't thought 
of a way to do that that's even close to efficient.

N.B.:  While thinking of this I've just noticed a potential 
flaw.  With frequent access and no additions the maximum 
nodeId could increase to too large a number without invoking a 
cache compression, so I'd better move the check for 
renumbering to where the nodeId is assigned.