LeetCode 146. LRU Cache

contributed by < Eric Lin >

Aim

• Introduce Least recently used (LRU).
• Refer source code from Jserv's Linux Kernel Internals to solve LRU Cache.
• Describe how the code works.

Least recently used (LRU)

Least recently used (LRU) is one of the Cache replacement policies. Caching improves performance by keeping recent or often-used data items in memory locations which are faster, or computationally cheaper to access, than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for new data. And LRU discards least-recently-used items first.

source: wiki: Least_recently_used

LRU Cache implementation

Note: include/linux/types.h and include/linux/list.h have to be included.

Data structure

Use circular doubly-linked list structure from include/linux/types.h:

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

• LRUCache

  • capacity: The maximum capacity of the cache.
  • count: The current number of data in the cache.
  • dhead: Recording the frequency of access for each node in the cache.
  • hheads[]: Implementing hash tables. Each index corresponds to a bucket in the hash table.

• LRUNode

  • key: A unique key for hashing.
  • value: The data stored in the cache.
  • hlink: Link for chaining buckets having the same hash value in hash table.
  • dlink: Link for chaining nodes in the cache.

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

lRUCacheCreate

Create LRUCache and doing initialize.
Malloc capacity * sizeof(struct list_head) is for hheads[].

LRUCache *lRUCacheCreate(int capacity)
{   
    LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
    obj->count = 0;
    obj->capacity = capacity;
    INIT_LIST_HEAD(&obj->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_LIST_HEAD(&obj->hheads[i]);
    return obj;
}

lRUCacheFree

The LRUCache maintains a list obj->dhead, containing all the nodes currently present in the cache. Each node is connected by the lru->dlink link. Deleting these nodes effectively clears the cache.

void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    list_for_each_entry_safe(lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}   

lRUCacheGet

• Calculate the hash value for the given key.
• Due to the possibility of different key values producing the same hash value from hash function, it is necessary to access the hash table at obj->hheads[hash] and check for a matching key lru->key == key.
• line 7: If a matching key is found, the corresponding node is moved to the head of the obj->dhead list, indicating that it is now the most recently used item.

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry(lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

lRUCachePut

• line 5: If the key already exists, moves the corresponding node to the head of the list and updates its value.
• line 13: If the cache is full. If the cache is full, replaces the least recently used node in the cache with the new data.

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    list_for_each_entry(lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = list_last_entry(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}