fifo_cache.py

class Node:
    def __init__(self, key, data):
        self.prev = None
        self.next = None
        self.key  = key
        self.data = data


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def prepend(self, key, data):
        node = Node(key, data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
        return node
        
    def pop_node(self, node: Node):
        if node.prev is None:
            self.head = node.next
        else:
            node.prev.next = node.next

        if node.next is None:
            self.tail = node.prev
        else:
            node.next.prev = node.prev

    def pop_tail(self):
        node = self.tail
        self.pop_node(node)
        return node

    def __iter__(self):
        node = self.head
        while node is not None:
            yield node
            node = node.next
    
    def __str__(self):
        return f"[{' -> '.join([str(node.key) for node in self])}]"


class Cache:
    def __init__(self, max_size=256*1024):
        self.store = {}
        self.linked_list = LinkedList()
        self.size = 0
        self.max_size = max_size
    
    def __setitem__(self, key, data):
        print(f"Cache :: Inserting key ({key}) of size {len(data)} Byte")
        if key in self.store:
            node = self.store[key]
            self.linked_list.pop_node(node)
            print(f"\tFound key ({key}) in cache. Removing from cache (size -= {len(node.data)} Byte)")
            self.size -= len(node.data)

        node = self.linked_list.prepend(key, data)
        self.store[key] = node
        self.size += len(data)

        while self.size > self.max_size:
            node = self.linked_list.pop_tail()
            print(f"\tCache full. Removing key ({node.key}) from cache (size -= {len(node.data)} Byte)")
            self.size -= len(node.data)
            del self.store[node.key]
        
        print(f"\tCache is now: {self.size} Byte, with linked list: {self.linked_list}\n")
        
    def __getitem__(self, key):
        return self.store[key].data


if __name__ == "__main__":
    cache = Cache(1024)

    for i in range(5):
        cache[i] = bytes(256)

    cache[3] = bytes(768)

    """
    Cache :: Inserting key (0) of size 256 Byte
            Cache is now: 256 Byte, with linked list: [0]

    Cache :: Inserting key (1) of size 256 Byte
            Cache is now: 512 Byte, with linked list: [1 -> 0]

    Cache :: Inserting key (2) of size 256 Byte
            Cache is now: 768 Byte, with linked list: [2 -> 1 -> 0]

    Cache :: Inserting key (3) of size 256 Byte
            Cache is now: 1024 Byte, with linked list: [3 -> 2 -> 1 -> 0]

    Cache :: Inserting key (4) of size 256 Byte
            Cache full. Removing key (0) from cache (size -= 256 Byte)
            Cache is now: 1024 Byte, with linked list: [4 -> 3 -> 2 -> 1]

    Cache :: Inserting key (3) of size 768 Byte
            Found key (3) in cache. Removing from cache (size -= 256 Byte)
            Cache full. Removing key (1) from cache (size -= 256 Byte)
            Cache full. Removing key (2) from cache (size -= 256 Byte)
            Cache is now: 1024 Byte, with linked list: [3 -> 4]
    """