Leetcode 146. LRU Cache

lrucache.c

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

#define list_for_each(pos, head) \
	for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, __typeof__(*(pos)), member)

#define list_entry_is_head(pos, head, member)				\
	(&pos->member == (head))

#define list_for_each_entry_safe_continue(pos, n, head, member) 		\
	for (pos = list_next_entry(pos, member), 				\
		n = list_next_entry(pos, member);				\
	     !list_entry_is_head(pos, head, member);				\
	     pos = n, n = list_next_entry(n, member))


#define list_for_each_entry_safe_from(pos, n, head, member) 			\
	for (n = list_next_entry(pos, member);					\
	     !list_entry_is_head(pos, head, member);				\
	     pos = n, n = list_next_entry(n, member))


#define myoffsetof(type, member) \
    (size_t)(&(((type *)0)->member))

#define container_of(p, type, member) \
    (type *)((size_t)p - offsetof(type, member))

typedef struct {
    int key;
    int val;
    struct list_head hlink;
    struct list_head dlink;
} LRUNode;

typedef struct {
    int count;
    int capacity;
    struct list_head dhead;
    struct list_head hheads[];
} LRUCache;

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}


static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = NULL;
    entry->prev = NULL;
}

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}


static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}


static inline int list_is_head(const struct list_head *list, const struct list_head *head)
{
   return list == head; 
}


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

int lRUCacheGet(LRUCache* obj, int key) {
    struct list_head *hlist = &obj->hheads[key % obj->capacity];
    struct list_head *cur;
    list_for_each(cur, hlist) {
        LRUNode *n = container_of(cur, LRUNode, hlink);
        if (n->key == key) {
            // update dlink
            list_del(&n->dlink);
            list_add(&n->dlink, &obj->dhead);
            return n->val;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    struct list_head *hlist = &obj->hheads[key % obj->capacity];
    struct list_head *cur;
    list_for_each(cur, hlist) {
        LRUNode *n = container_of(cur, LRUNode, hlink);
        if (n->key == key) {
            n->val = value;
            // update dlink
            list_del(&n->dlink);
            list_add(&n->dlink, &obj->dhead);
            return;
        }
    }
 
    LRUNode *new = NULL;
    if ((new = malloc(sizeof(LRUNode))) == NULL)
        return;   
    new->key = key;
    new->val = value;
    
    if (obj->count == obj->capacity) {
        // remove last element
        struct list_node *tbd = (&(obj->dhead))->prev;
        LRUNode *n = container_of(tbd, LRUNode, dlink);
        list_del(&n->dlink);
        list_del(&n->hlink);
    } else {
        obj->count++;
    }
    list_add(&new->dlink, &obj->dhead);
    list_add(&new->hlink, hlist);
}

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

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 
 * lRUCachePut(obj, key, value);
 
 * lRUCacheFree(obj);
*/