cache.h

#ifndef __CACHE_H__
#define __CACHE_H__

#include "list.h"

#define CACHE_LISTS 256

typedef struct
{
    list_elem link;
    list_elem lru_link;
} cache_link;

typedef struct
{
    /* LRU list holds unused items */
    unsigned int lru_entries;
    list_elem lru_list;
    unsigned int max_free_entries;

    unsigned int entries;
    list_elem lists[CACHE_LISTS];
    unsigned int (*elem_val)(cache_link *elem);
    void (*freed)(cache_link *elem);
} listcache;

static inline void
cache_add(listcache *c, cache_link *elem)
{
    unsigned int hash = c->elem_val(elem) % CACHE_LISTS;
    int delcount = c->lru_entries - c->max_free_entries;

    if (delcount > 0) {
        /* Delete some unused items. */
        list_elem *lru, *next;
        cache_link *l;
        list_for_each_elem_safe(&c->lru_list, lru, next) {
            l = container_of(lru, cache_link, lru_link);
            list_del(lru);
            list_del(&l->link);
            c->entries--;
            c->lru_entries--;
            c->freed(l);
            delcount--;
            if (delcount <= 0)
                break;
        }
    }

    c->entries++;
    list_item_init(&elem->lru_link); /* Mark it not in the LRU list */
    list_add_after(&c->lists[hash], &elem->link);
}

static inline void
cache_item_set_unused(listcache *c, cache_link *elem)
{
    list_add_before(&c->lru_list, &elem->lru_link);
    c->lru_entries++;
}

static inline cache_link *
cache_find(listcache *c, unsigned int val)
{
    unsigned int hash = val % CACHE_LISTS;
    list_elem *elem;

    list_for_each_elem(&c->lists[hash], elem) {
        cache_link *l = container_of(elem, cache_link, link);
        if (c->elem_val(l) == val) {
            if (!list_empty(&l->lru_link)) {
                /* It's in the unused list, remove it. */
                list_del(&l->lru_link);
                list_item_init(&l->lru_link);
                c->lru_entries--;
            }
            return l;
        }
    }
    return NULL;
}

static inline int
cache_flush(listcache *c)
{
    list_elem *elem, *next;
    cache_link *l;
    int i;

    list_for_each_elem_safe(&c->lru_list, elem, next) {
        l = container_of(elem, cache_link, lru_link);
        list_del(elem);
        list_del(&l->link);
        c->entries--;
        c->lru_entries--;
        c->freed(l);
    }

    for (i = 0; i < CACHE_LISTS; i++) {
        list_for_each_elem_safe(&c->lists[i], elem, next) {
            l = container_of(elem, cache_link, link);
            list_del(&l->link);
            c->entries--;
            c->freed(l);
        }
    }

    return c->entries || c->lru_entries;
}

static inline void
cache_init(listcache *c, unsigned int max_free_entries,
       unsigned int (*elem_val)(cache_link *elem),
       void (*freed)(cache_link *elem))
{
    int i;

    c->entries = 0;
    c->lru_entries = 0;
    c->max_free_entries = max_free_entries;
    list_init(&c->lru_list);
    for (i = 0; i < CACHE_LISTS; i++)
        list_init(&c->lists[i]);
    c->elem_val = elem_val;
    c->freed = freed;
}

#endif /* __CACHE_H__ */