cppadvanced15 minutes

Fix Memory Leak and Concurrency Bug in Thread-Safe Cache Implementation

Given an incomplete and buggy thread-safe LRU cache implementation in C++, identify and fix issues related to memory leaks, data races, and incorrect cache eviction logic.

Challenge prompt

You are provided with a broken C++ implementation of a thread-safe LRU cache. The cache is supposed to store a fixed maximum number of key-value pairs, evicting the least recently used element when full. It uses a doubly linked list and a hash map for O(1) access and eviction. However, the current implementation has memory leaks, concurrency bugs, and incorrect eviction behavior. Identify and fix the bugs to ensure: - No memory leaks occur - The cache is safe to access concurrently - The LRU eviction logic works correctly under concurrent accesses You should only modify the methods inside the Cache class and ensure the class has proper RAII semantics and thread safety.

Guidance

• Check ownership and deletion of nodes to fix memory leaks.
• Use proper synchronization primitives (e.g. std::mutex) to prevent data races.
• Verify logic that moves accessed nodes to the front and evicts from the tail.

Hints

• Consider using std::unique_ptr or ensure you delete nodes when evicted.
• Lock the mutex at the beginning of each public method and unlock at the end.
• Make sure to update both the linked list pointers and the hash map entries when modifying the cache.

Starter code

#include <unordered_map>
#include <mutex>

template<typename K, typename V>
class Cache {
    struct Node {
        K key;
        V value;
        Node* prev;
        Node* next;
        Node(K k, V v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    std::unordered_map<K, Node*> map;
    Node* head = nullptr;
    Node* tail = nullptr;
    int capacity;
    int size = 0;
    std::mutex mtx;

    void removeNode(Node* node) {
        if (node->prev) node->prev->next = node->next;
        else head = node->next;
        if (node->next) node->next->prev = node->prev;
        else tail = node->prev;
    }

    void addToFront(Node* node) {
        node->next = head;
        node->prev = nullptr;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = head;
    }

public:
    Cache(int cap) : capacity(cap) {}

    V get(const K& key) {
        std::lock_guard<std::mutex> lock(mtx);
        if (map.find(key) == map.end()) return V();
        Node* node = map[key];
        removeNode(node);
        addToFront(node);
        return node->value;
    }

    void put(const K& key, const V& value) {
        std::lock_guard<std::mutex> lock(mtx);
        if (map.find(key) != map.end()) {
            Node* node = map[key];
            node->value = value;
            removeNode(node);
            addToFront(node);
        } else {
            Node* node = new Node(key, value);
            if (size == capacity) {
                map.erase(tail->key);
                removeNode(tail);
            } else {
                size++;
            }
            addToFront(node);
            map[key] = node;
        }
    }

    ~Cache() {
        Node* curr = head;
        while (curr) {
            Node* next = curr->next;
            delete curr;
            curr = next;
        }
    }
};

Expected output

Correct cache behavior with no memory leaks under concurrent get and put calls, and LRU eviction policy maintained correctly.

Core concepts

concurrencymemory managementLRU cachemutex synchronization

Challenge a Friend

Send this duel to someone else and see if they can solve it.