from collections import namedtuple
from threading import RLock

_CacheInfo = namedtuple('CacheInfo', 'maxsize currsize')

class LruCache:

    PRE, NEXT, KEY, VALUE = 0, 1, 2, 3

    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.currsize = 0
        self.cache = {}
        self.lock = RLock()
        self.root = []
        self.root[:] = [self.root, self.root, None, None]  # [PRE, NEXT, KEY, VALUE]

    def put(self, key, value):
        with self.lock:
            if self.maxsize <= len(self.cache):
                oldroot = self.root
                oldroot[self.KEY] = key
                oldroot[self.VALUE] = value
                self.root = oldroot[self.NEXT]
                oldkey = self.root[self.KEY]
                oldvalue = self.root[self.VALUE]
                self.root[self.KEY] = self.root[self.VALUE] = None
                del self.cache[oldkey]
                self.cache[key] = oldroot
            else:
                last = self.root[self.PRE]
                link = [last, self.root, key, value]
                last[self.NEXT] = self.root[self.PRE] = self.cache[key] = link

            self.currsize = len(self.cache)

    def get(self, key):

        with self.lock:
            link = self.cache.get(key)
            if link is not None:
                link_last, link_next, _key, _value = link

                # 在链表中取出数据节点
                link_last[self.NEXT] = link_next
                link_next[self.PRE] = link_last

                # 重新放入链表
                last = self.root[self.PRE]
                link[self.PRE] = last
                link[self.NEXT] = self.root
                last[self.NEXT] = self.root[self.PRE] = link

                return _value
            return None

    def get_info(self):
        return _CacheInfo(self.maxsize, self.currsize)


cache = LruCache(maxsize=2)

cache.put('a', 1)
v = cache.get('a')
cache.put('b', 2)
v = cache.get('b')
cache.put('c', 3)
v = cache.get('a')

print(cache.get_info())