Attachment 107615 Details for Bug 67823 – Patch

[patch] Patch

bug-67823-20110916162653.patch (text/plain), 9.29 KB, created by Ai Makabi on 2011-09-16 00:26:54 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Ai Makabi

Created: 2011-09-16 00:26:54 PDT

Size: 9.29 KB

patch

obsolete

>Subversion Revision: 94182
>diff --git a/Tools/ChangeLog b/Tools/ChangeLog
>index 1b9bc2ebc1188d2ce5bf8d2526ff2aa8ff2cc8fc..95903ff2737011c018013d3a8d690b887ff1885f 100644
>--- a/Tools/ChangeLog
>+++ b/Tools/ChangeLog
>@@ -1,3 +1,14 @@
>+2011-09-15  Ai Makabi  <makabi@google.com>
>+
>+        Provides a simple LRU cache class in Python.
>+
>+        https://bugs.webkit.org/show_bug.cgi?id=67823
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        * Scripts/webkitpy/common/lru_cache.py:
>+        * Scripts/webkitpy/common/lru_cache_unittest.py:
>+
> 2011-08-31  Ai Makabi  <makabi@google.com>
> 
>         Extract reference links from reftest test file.
>diff --git a/Tools/Scripts/webkitpy/common/lru_cache.py b/Tools/Scripts/webkitpy/common/lru_cache.py
>new file mode 100644
>index 0000000000000000000000000000000000000000..b5293109a3b4353216b37720f57df1d1ff96a466
>--- /dev/null
>+++ b/Tools/Scripts/webkitpy/common/lru_cache.py
>@@ -0,0 +1,132 @@
>+#!/usr/bin/env python
>+# Copyright (C) 2011 Google Inc. All rights reserved.
>+#
>+# Redistribution and use in source and binary forms, with or without
>+# modification, are permitted provided that the following conditions are
>+# met:
>+#
>+#     * Redistributions of source code must retain the above copyright
>+# notice, this list of conditions and the following disclaimer.
>+#     * Redistributions in binary form must reproduce the above
>+# copyright notice, this list of conditions and the following disclaimer
>+# in the documentation and/or other materials provided with the
>+# distribution.
>+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
>+# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
>+# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
>+# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
>+# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
>+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
>+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
>+# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
>+# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
>+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
>+# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
>+
>+
>+class Node():
>+    def __init__(self, key, value, prev, next=None):
>+        self.key = key
>+        self.value = value
>+        self.prev = prev
>+        self.next = next
>+
>+
>+class LRUCache():
>+    """An implementation of Least Recently Used (LRU) Algorithm.
>+
>+    Args:
>+        capacity: a cache memory capacity
>+    """
>+    def __init__(self, capacity):
>+        assert capacity > 0, "capacity (%s) must be greater than zero." % capacity
>+        self._first = None
>+        self._last = None
>+        self._dict = {}
>+        self._capacity = capacity
>+
>+    def __setitem__(self, key, value):
>+        if key in self._dict:
>+            self.__delitem__(key)
>+        if not self._first:
>+            self._one_node(key, value)
>+            return
>+        if len(self._dict) >= self._capacity:
>+            del self._dict[self._last.key]
>+            if self._capacity == 1:
>+                self._one_node(key, value)
>+                return
>+            self._last = self._last.next
>+            self._last.prev = None
>+        node = Node(key, value, self._first)
>+        self._first.next = node
>+        self._first = node
>+        self._dict[key] = node
>+
>+    def _one_node(self, key, value):
>+        node = Node(key, value, self._first)
>+        self._dict[key] = node
>+        self._first = node
>+        self._last = node
>+
>+    def __getitem__(self, key):
>+        if not self._first:
>+            raise KeyError(str(key))
>+        if self._first.key == key:
>+            return self._first.value
>+
>+        if self._last.key == key:
>+            next_last = self._last.next
>+            next_last.prev = None
>+            next_first = self._last
>+            next_first.prev = self._first
>+            next_first.next = None
>+            self._first.next = next_first
>+            self._first = next_first
>+            self._last = next_last
>+            return self._first.value
>+
>+        node = self._dict[key]
>+        node.next.prev = node.prev
>+        node.prev.next = node.next
>+        node.prev = self._first
>+        node.next = None
>+        self._first.next = node
>+        self._first = node
>+        return self._first.value
>+
>+    def __delitem__(self, key):
>+        node = self._dict[key]
>+        del self._dict[key]
>+        if self._first is self._last:
>+            self._last = None
>+            self._first = None
>+            return
>+        if self._first is node:
>+            self._first = node.prev
>+            self._first.next = None
>+            return
>+        if self._last is node:
>+            self._last = node.next
>+            self._last.prev = None
>+            return
>+        node.next.prev = node.prev
>+        node.prev.next = node.next
>+
>+    def __len__(self):
>+        return len(self._dict)
>+
>+    def __contains__(self, key):
>+        return key in self._dict
>+
>+    def __iter__(self):
>+        return iter(self._dict)
>+
>+    def items(self):
>+        return [(key, node.value) for key, node in self._dict.items()]
>+
>+    def values(self):
>+        return [node.value for node in self._dict.values()]
>+
>+    def keys(self):
>+        return self._dict.keys()
>diff --git a/Tools/Scripts/webkitpy/common/lru_cache_unittest.py b/Tools/Scripts/webkitpy/common/lru_cache_unittest.py
>new file mode 100644
>index 0000000000000000000000000000000000000000..44a09e661bac7568a45d4c73c29af60de4f1cfa9
>--- /dev/null
>+++ b/Tools/Scripts/webkitpy/common/lru_cache_unittest.py
>@@ -0,0 +1,98 @@
>+#!/usr/bin/env python
>+# Copyright (C) 2011 Google Inc. All rights reserved.
>+#
>+# Redistribution and use in source and binary forms, with or without
>+# modification, are permitted provided that the following conditions are
>+# met:
>+#
>+#     * Redistributions of source code must retain the above copyright
>+# notice, this list of conditions and the following disclaimer.
>+#     * Redistributions in binary form must reproduce the above
>+# copyright notice, this list of conditions and the following disclaimer
>+# in the documentation and/or other materials provided with the
>+# distribution.
>+
>+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
>+# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
>+# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
>+# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
>+# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
>+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
>+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
>+# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
>+# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
>+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
>+# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
>+
>+
>+import unittest
>+
>+from webkitpy.common import lru_cache
>+
>+
>+class LRUCacheTest(unittest.TestCase):
>+
>+    def setUp(self):
>+        self.lru = lru_cache.LRUCache(3)
>+        self.lru['key_1'] = 'item_1'
>+        self.lru['key_2'] = 'item_2'
>+        self.lru['key_3'] = 'item_3'
>+
>+        self.lru2 = lru_cache.LRUCache(1)
>+        self.lru2['key_1'] = 'item_1'
>+
>+    def test_items(self):
>+        self.assertEqual(set(self.lru.items()), set([('key_1', 'item_1'), ('key_3', 'item_3'), ('key_2', 'item_2')]))
>+
>+    def test_put(self):
>+        self.lru['key_4'] = 'item_4'
>+        self.assertEqual(set(self.lru.items()), set([('key_4', 'item_4'), ('key_3', 'item_3'), ('key_2', 'item_2')]))
>+
>+    def test_update(self):
>+        self.lru['key_1']
>+        self.lru['key_5'] = 'item_5'
>+        self.assertEqual(set(self.lru.items()), set([('key_1', 'item_1'), ('key_3', 'item_3'), ('key_5', 'item_5')]))
>+
>+    def test_keys(self):
>+        self.assertEqual(set(self.lru.keys()), set(['key_1', 'key_2', 'key_3']))
>+
>+    def test_delete(self):
>+        del self.lru['key_1']
>+        self.assertFalse('key_1' in self.lru)
>+
>+    def test_contain(self):
>+        self.assertTrue('key_1' in self.lru)
>+        self.assertFalse('key_4' in self.lru)
>+
>+    def test_values(self):
>+        self.assertEqual(set(self.lru.values()), set(['item_1', 'item_2', 'item_3']))
>+
>+    def test_len(self):
>+        self.assertEqual(len(self.lru), 3)
>+
>+    def test_size_one_pop(self):
>+        self.lru2['key_2'] = 'item_2'
>+        self.assertEqual(self.lru2.keys(), ['key_2'])
>+
>+    def test_size_one_delete(self):
>+        del self.lru2['key_1']
>+        self.assertFalse('key_1' in self.lru2)
>+
>+    def test_pop_error(self):
>+        self.assertRaises(KeyError, self.lru2.__getitem__, 'key_2')
>+        del self.lru2['key_1']
>+        self.assertRaises(KeyError, self.lru2.__getitem__, 'key_2')
>+
>+    def test_get_middle_item(self):
>+        self.lru['key_2']
>+        self.lru['key_4'] = 'item_4'
>+        self.lru['key_5'] = 'item_5'
>+        self.assertEqual(set(self.lru.keys()), set(['key_2', 'key_4', 'key_5']))
>+
>+    def test_set_again(self):
>+        self.lru['key_1'] = 'item_4'
>+        self.assertEqual(set(self.lru.items()), set([('key_1', 'item_4'), ('key_3', 'item_3'), ('key_2', 'item_2')]))
>+
>+
>+if __name__ == "__main__":
>+    unittest.main()

Actions: View | Formatted Diff | Diff

Attachments on bug 67823: 107297 | 107322 | 107494 | 107582 | 107604 | 107615 | 108278