From 5ea4a54bd03f1d7814fa0d24638b7b5260bb8901 Mon Sep 17 00:00:00 2001 From: Jay Hutchinson Date: Mon, 25 Jul 2011 01:40:08 -0500 Subject: A key can now be None. --- README.txt | 6 ----- pylru.py | 89 +++++++++++++++++++++++++++++++------------------------------- setup.py | 2 +- test.py | 8 +++--- 4 files changed, 50 insertions(+), 55 deletions(-) diff --git a/README.txt b/README.txt index ed0ce33..7f77865 100644 --- a/README.txt +++ b/README.txt @@ -36,8 +36,6 @@ An lrucache object has a dictionary like interface and can be used in the same w # Lookup and insert both move the key/value to the most # recently used position. Delete (obviously) removes a # key/value from whatever position it was in. - # - # WARNING - keys can't be None key in cache # Test for membership. Does not affect the cache order. @@ -113,8 +111,6 @@ The WriteThroughCacheManager class takes as arguments the store object you want value = cached[key] # Lookup a value given its key. cached[key] = value # Insert a key/value pair. del cached[key] # Delete a value given its key. - # - # WARNING - keys can't be None key in cache # Test for membership. Does not affect the cache order. @@ -153,8 +149,6 @@ Similar to the WriteThroughCacheManager class except write-back semantics are us value = cached[key] # Lookup a value given its key. cached[key] = value # Insert a key/value pair. del cached[key] # Delete a value given its key. - # - # WARNING - keys can't be None key in cache # Test for membership. Does not affect the cache order. diff --git a/pylru.py b/pylru.py index 773d907..bb2a86a 100644 --- a/pylru.py +++ b/pylru.py @@ -20,26 +20,21 @@ -# The cache is implemented using a combination of a hash table (python -# dictionary) and a circular doubly linked list. Objects in the cache are +# The cache is implemented using a combination of a python +# dictionary (hash table) and a circular doubly linked list. Items in the cache are # stored in nodes. These nodes make up the linked list. The list is used to -# efficiently maintain the order that the objects have been used in. The front -# or "head" of the list contains the most recently used object, the "tail" of -# the list contains the least recently used object. When an object is "used" it +# efficiently maintain the order that the items have been used in. The front +# or head of the list contains the most recently used item, the tail of +# the list contains the least recently used item. When an item is used it # can easily (in a constant amount of time) be moved to the front of the list, # thus updating its position in the ordering. These nodes are also placed in # the hash table under their associated key. The hash table allows efficient -# lookup of objects by key. - -# The doubly linked list is composed of nodes. Each -# node has a 'prev' and 'next' variable to hold the node that comes before -# it and after it respectivly. Initially the two variables each point to -# the node itself, creating a circular doubly linked list of size one. Each -# node has a 'obj' and 'key' variable, holding the object and the key it is -# stored under respectivly. +# lookup of values by key. + +# Class for the node objects. class _dlnode(object): def __init__(self): - self.key = None + self.empty = True class lrucache(object): @@ -50,10 +45,14 @@ class lrucache(object): # Initialize the hash table as empty. self.table = {} - - # Initalize the list with one empty node. Create a node and - # assign it to the 'head' variable, which represents the head node in - # the list. + # Initialize the doubly linked list with one empty node. This is an + # invariant. The cache size must always be greater than zero. + # Each + # node has a 'prev' and 'next' variable to hold the node that comes before + # it and after it respectivly. Initially the two variables each point to + # the head node itself, creating a circular doubly linked list of size one. + # Then the size() method is used to adjust the list to the desired size. + self.head = _dlnode() self.head.next = self.head self.head.prev = self.head @@ -69,8 +68,9 @@ class lrucache(object): def clear(self): for node in self.dli(): + node.empty = True node.key = None - node.obj = None + node.value = None self.table.clear() @@ -82,7 +82,7 @@ class lrucache(object): def peek(self, key): # Look up the node node = self.table[key] - return node.obj + return node.value def __getitem__(self, key): @@ -95,20 +95,20 @@ class lrucache(object): self.mtf(node) self.head = node - # Return the object - return node.obj + # Return the value. + return node.value - def __setitem__(self, key, obj): - # First, see if any object is stored under 'key' in the cache already. - # If so we are going to replace that object with the new one. + def __setitem__(self, key, value): + # First, see if any value is stored under 'key' in the cache already. + # If so we are going to replace that value with the new one. if key in self.table: # Lookup the node node = self.table[key] - # Replace the object - node.obj = obj + # Replace the value. + node.value = value # Update the list ordering. self.mtf(node) @@ -116,10 +116,10 @@ class lrucache(object): return - # Ok, no object is currently stored under 'key' in the cache. We need to - # choose a node to place the object 'obj' in. There are two cases. If the - # cache is full some object will have to be pushed out of the cache. We - # want to choose the node with the least recently used object. This is the + # Ok, no value is currently stored under 'key' in the cache. We need to + # choose a node to place the new item in. There are two cases. If the + # cache is full some item will have to be pushed out of the cache. We + # want to choose the node with the least recently used item. This is the # node at the tail of the list. If the cache is not full we want to choose # a node that is empty. Because of the way the list is managed, the empty # nodes are always together at the tail end of the list. Thus, in either @@ -132,14 +132,15 @@ class lrucache(object): # If the node already contains something we need to remove the old key from # the dictionary. - if node.key is not None: + if not node.empty: if self.callback is not None: - self.callback(node.key, node.obj) + self.callback(node.key, node.value) del self.table[node.key] - # Place the new key and object in the node + # Place the new key and value in the node + node.empty = False node.key = key - node.obj = obj + node.value = value # Add the node to the dictionary under the new key. self.table[key] = node @@ -157,11 +158,11 @@ class lrucache(object): node = self.table[key] del self.table[key] - # Set the 'key' to None to indicate that the node is empty. We also set the - # 'obj' to None to release the reference to the object, though it is not - # strictly necessary. + node.empty = True + + # Not strictly necessary. node.key = None - node.obj = None + node.value = None # Because this node is now empty we want to reuse it before any non-empty # node. To do that we want to move it to the tail of the list. We move it @@ -185,7 +186,7 @@ class lrucache(object): # in order from the most recently to least recently used. Does not # modify the cache order. for node in self.dli(): - yield (node.key, node.obj) + yield (node.key, node.value) def keys(self): @@ -201,7 +202,7 @@ class lrucache(object): # the most recently to least recently used. Does not modify the cache # order. for node in self.dli(): - yield node.obj + yield node.value def size(self, size=None): @@ -233,9 +234,9 @@ class lrucache(object): assert self.listSize > 1 # Invarient. XXX REMOVE this line XXX for i in range(n): node = self.head.prev - if node.key is not None: + if not node.empty: if self.callback is not None: - self.callback(node.key, node.obj) + self.callback(node.key, node.value) del self.table[node.key] # Splice the tail node out of the list @@ -247,7 +248,7 @@ class lrucache(object): node.next = None node.key = None - node.obj = None + node.value = None self.listSize -= n diff --git a/setup.py b/setup.py index ca48a30..6491216 100644 --- a/setup.py +++ b/setup.py @@ -2,7 +2,7 @@ from distutils.core import setup setup( name = "pylru", - version = "1.0.4", + version = "1.0.5", py_modules=['pylru'], description = "A least recently used (LRU) cache implementation", author = "Jay Hutchinson", diff --git a/test.py b/test.py index fdbabb2..1dee0f4 100644 --- a/test.py +++ b/test.py @@ -34,12 +34,12 @@ class simplelrucache: raise KeyError - def __setitem__(self, key, obj): + def __setitem__(self, key, value): for i in range(len(self.cache)): x = self.cache[i] if x[0] == key: - x[1] = obj + x[1] = value del self.cache[i] self.cache.append(x) return @@ -47,7 +47,7 @@ class simplelrucache: if len(self.cache) == self.size: self.cache = self.cache[1:] - self.cache.append([key, obj]) + self.cache.append([key, value]) def __delitem__(self, key): @@ -96,7 +96,7 @@ def testcache(): q = [] z = a.head for j in range(len(a.table)): - q.append([z.key, z.obj]) + q.append([z.key, z.value]) z = z.next assert q == b.cache[::-1] -- cgit v1.2.1