LRU cache?

[Paul Rubin]

aleax at mac.com (Alex Martelli) writes:
> So what's wrong with Evan Prodromou's lrucache.py module that's in pypi?
> Haven't used it, but can't see anything wrong at a glance.

Thanks, I wasn't aware of that one.  I notice two things about it:
1) it's under a GPL-incompatible license (therefore also incompatible 
   with the PSF license); that's a problem for what I'm doing.

2) it uses heapq to figure out which entry is the oldest.  I guess
that's not too unreasonable and maybe it's necessary.  But unless I'm
missing something it's never necessary to insert new records into the
middle of the list-by-age.  So I think it may be easiest to just keep
a doubly linked list of records with the invariant that they are
ordered by age, keeping track of where both ends are; plus a hash
table to map indices to nodes in the linked list.  On any access that
hits the cache, the found node gets removed and moved to the front of
the list in O(1) operations.  This may be easiest with a circular
list.