Skip to content


Subversion checkout URL

You can clone with
Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

168 lines (138 sloc) 5.47 kB
# This file is part of the Minecraft Overviewer.
# Minecraft Overviewer is free software: you can redistribute it and/or
# modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, either version 3 of the License, or (at
# your option) any later version.
# Minecraft Overviewer is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# Public License for more details.
# You should have received a copy of the GNU General Public License along
# with the Overviewer. If not, see <>.
"""This module has supporting functions for the caching logic used in
Each cache class should implement the standard container type interface
(__getitem__ and __setitem__), as well as provide a "hits" and "misses"
import functools
import logging
import cPickle
class LRUCache(object):
"""A simple, generic, in-memory LRU cache that implements the standard
python container interface.
An ordered dict type would simplify this implementation a bit, but we want
Python 2.6 compatibility and the standard library ordereddict was added in
2.7. It's probably okay because this implementation can be tuned for
exactly what we need and nothing more.
This implementation keeps a linked-list of cache keys and values, ordered
in least-recently-used order. A dictionary maps keys to linked-list nodes.
On cache hit, the link is moved to the end of the list. On cache miss, the
first item of the list is evicted. All operations have constant time
complexity (dict lookups are worst case O(n) time)
class _LinkNode(object):
__slots__ = ['left', 'right', 'key', 'value']
def __init__(self,l=None,r=None,k=None,v=None):
self.left = l
self.right = r
self.key = k
self.value = v
def __init__(self, size=100, destructor=None):
"""Initialize a new LRU cache with the given size.
destructor, if given, is a callable that is called upon an item being
evicted from the cache. It takes one argument, the value stored in the
self.cache = {}
# Two sentinel nodes at the ends of the linked list simplify boundary
# conditions in the code below.
self.listhead = LRUCache._LinkNode()
self.listtail = LRUCache._LinkNode()
self.listhead.right = self.listtail
self.listtail.left = self.listhead
self.hits = 0
self.misses = 0
self.size = size
self.destructor = destructor
# Initialize an empty cache of the same size for worker processes
def __getstate__(self):
return self.size
def __setstate__(self, size):
def __getitem__(self, key):
link = self.cache[key]
except KeyError:
self.misses += 1
# Disconnect the link from where it is
link.left.right = link.right
link.right.left = link.left
# Insert the link at the end of the list
tail = self.listtail
link.left = tail.left
link.right = tail
tail.left.right = link
tail.left = link
self.hits += 1
return link.value
def __setitem__(self, key, value):
cache = self.cache
if key in cache:
# Shortcut this case
cache[key].value = value
if len(cache) >= self.size:
# Evict a node
link = self.listhead.right
del cache[link.key]
link.left.right = link.right
link.right.left = link.left
d = self.destructor
if d:
del link
# The node doesn't exist already, and we have room for it. Let's do this.
tail = self.listtail
link = LRUCache._LinkNode(tail.left, tail,key,value)
tail.left.right = link
tail.left = link
cache[key] = link
def __delitem__(self, key):
# Used to flush the cache of this key
cache = self.cache
link = cache[key]
del cache[key]
link.left.right = link.right
link.right.left = link.left
# Call the destructor
d = self.destructor
if d:
# memcached is an option, but unless your IO costs are really high, it just
# ends up adding overhead and isn't worth it.
import memcache
except ImportError:
class Memcached(object):
def __init__(*args):
raise ImportError("No module 'memcache' found. Please install python-memcached")
class Memcached(object):
def __init__(self, conn=''):
self.conn = conn = memcache.Client([conn], debug=0, pickler=cPickle.Pickler, unpickler=cPickle.Unpickler)
def __getstate__(self):
return self.conn
def __setstate__(self, conn):
def __getitem__(self, key):
v =
if not v:
raise KeyError()
return v
def __setitem__(self, key, value):, value)
Jump to Line
Something went wrong with that request. Please try again.