From 7585a1cd68ca7c2ea5724116638cd61100f877e1 Mon Sep 17 00:00:00 2001
From: Forrest Voight <forrest.voight@gmail.com>
Date: Sat, 25 Aug 2012 01:59:38 -0400
Subject: [PATCH] added LRU caching of skiplist results

---
 p2pool/util/memoize.py  |   18 ++++++++++++++++++
 p2pool/util/skiplist.py |    3 ++-
 2 files changed, 20 insertions(+), 1 deletions(-)

diff --git a/p2pool/util/memoize.py b/p2pool/util/memoize.py
index b5efab2..4199ccb 100644
--- a/p2pool/util/memoize.py
+++ b/p2pool/util/memoize.py
@@ -1,3 +1,21 @@
+import itertools
+
+class LRUDict(object):
+    def __init__(self, n):
+        self.n = n
+        self.inner = {}
+        self.counter = itertools.count()
+    def get(self, key, default=None):
+        if key in self.inner:
+            x, value = self.inner[key]
+            self.inner[key] = self.counter.next(), value
+            return value
+        return default
+    def __setitem__(self, key, value):
+        self.inner[key] = self.counter.next(), value
+        while len(self.inner) > self.n:
+            self.inner.pop(min(self.inner, key=lambda k: self.inner[k][0]))
+
 _nothing = object()
 
 def memoize_with_backing(backing, has_inverses=set()):
diff --git a/p2pool/util/skiplist.py b/p2pool/util/skiplist.py
index 154edeb..d913128 100644
--- a/p2pool/util/skiplist.py
+++ b/p2pool/util/skiplist.py
@@ -1,4 +1,4 @@
-from p2pool.util import math
+from p2pool.util import math, memoize
 
 class SkipList(object):
     def __init__(self, p=0.5):
@@ -9,6 +9,7 @@ class SkipList(object):
     def forget_item(self, item):
         self.skips.pop(item, None)
     
+    @memoize.memoize_with_backing(memoize.LRUDict(5))
     def __call__(self, start, *args):
         updates = {}
         pos = start
-- 
1.7.1