Implementing a cache

[Nikolaus Rath]

Hello,

I want to implement a caching data structure in Python that allows me
to:

 1. Quickly look up objects using a key
 2. Keep track of the order in which the objects are accessed (most
    recently and least recently accessed one, not a complete history)
 3. Quickly retrieve and remove the least recently accessed object.


Here's my idea for the implementation:

The objects in the cache are encapsulated in wrapper objects:

class OrderedDictElement(object):
    __slots__ = [ "next", "prev", "key", "value" ]

These wrapper objects are then kept in a linked lists and in an ordinary
dict (self.data) in parallel. Object access then works as follows:

    def __setitem__(self, key, value):
        if key in self.data:
            # Key already exists, just overwrite value
            self.data[key].value = value
        else:
            # New key, attach at head of list
            with self.lock:
                el = OrderedDictElement(key, value, next=self.head.next, prev=self.head)
                self.head.next.prev = el
                self.head.next = el
                self.data[key] = el

    def __getitem__(self, key):
        return self.data[key].value
    
To 'update the access time' of an object, I use
    
    def to_head(self, key):
        with self.lock:
            el = self.data[key]
            # Splice out
            el.prev.next = el.next
            el.next.prev = el.prev
            
            # Insert back at front
            el.next = self.head.next
            el.prev = self.head
            
            self.head.next.prev = el
            self.head.next = el
        

self.head and self.tail are special sentinel objects that only have a
.next and .prev attribute respectively.


While this is probably going to work, I'm not sure if its the best
solution, so I'd appreciate any comments. Can it be done more elegantly?
Or is there an entirely different way to construct the data structure
that also fulfills my requirements?


I already looked at the new OrderedDict class in Python 3.1, but
apparently it does not allow me to change the ordering and is therefore
not suitable for my purpose. (I can move something to one end by
deleting and reinserting it, but I'd like to keep at least the option of also
moving objects to the opposite end).


Best,


   -Nikolaus

-- 
 »Time flies like an arrow, fruit flies like a Banana.«

  PGP fingerprint: 5B93 61F8 4EA2 E279 ABF6  02CF A9AD B7F8 AE4E 425C