| 1 |
# vim:fileencoding=utf-8 |
| 2 |
# License: GPL v3 Copyright: 2017, Kovid Goyal <kovid at kovidgoyal.net> |
| 3 |
from __python__ import hash_literals, bound_methods |
| 4 |
|
| 5 |
|
| 6 |
def lru_node(key, val): |
| 7 |
return {'key': key, 'val': val, 'prev': None, 'next': None} |
| 8 |
|
| 9 |
|
| 10 |
class LRUCache: |
| 11 |
def __init__(self, size): |
| 12 |
self.limit = 200 |
| 13 |
self.clear(size) |
| 14 |
|
| 15 |
def set_head(self, node): |
| 16 |
node.next = self.head |
| 17 |
node.prev = None |
| 18 |
if self.head is not None: |
| 19 |
self.head.prev = node |
| 20 |
self.head = node |
| 21 |
if self.tail is None: |
| 22 |
self.tail = node |
| 23 |
self.size += 1 |
| 24 |
self.map[node.key] = node |
| 25 |
|
| 26 |
def pop(self, key): |
| 27 |
node = self.map[key] |
| 28 |
if not node: |
| 29 |
return |
| 30 |
if node.prev is not None: |
| 31 |
node.prev.next = node.next |
| 32 |
else: |
| 33 |
self.head = node.next |
| 34 |
if node.next is not None: |
| 35 |
node.next.prev = node.prev |
| 36 |
else: |
| 37 |
self.tail = node.prev |
| 38 |
v'delete self.map[key]' |
| 39 |
self.size -= 1 |
| 40 |
|
| 41 |
def set(self, key, val): |
| 42 |
node = lru_node(key, val) |
| 43 |
existing = self.map[key] |
| 44 |
if existing: |
| 45 |
existing.value = node.value |
| 46 |
self.pop(node.key) |
| 47 |
elif self.size > self.limit: |
| 48 |
v'delete self.map[self.tail.key]' |
| 49 |
self.size -= 1 |
| 50 |
self.tail = self.tail.prev |
| 51 |
self.tail.next = None |
| 52 |
self.set_head(node) |
| 53 |
|
| 54 |
def get(self, key, defval): |
| 55 |
existing = self.map[key] |
| 56 |
if not existing: |
| 57 |
return None if defval is undefined else defval |
| 58 |
val = existing.value |
| 59 |
node = lru_node(key, val) |
| 60 |
self.pop(key) |
| 61 |
self.set_head(node) |
| 62 |
return val |
| 63 |
|
| 64 |
def clear(self, size): |
| 65 |
self.size = 0 |
| 66 |
self.map = {} |
| 67 |
self.head = self.tail = None |
| 68 |
if jstype(size) is 'number': |
| 69 |
self.limit = size |