30  * Improved cache implementation.
74    /** Max entries in the cache */
80    /** Number of entries in the cache */
89 ensure_sanity(const struct util_cache *cache);
94  * Create a new cache with 'size' entries.  Also provide functions for
103    struct util_cache *cache;  in util_cache_create()  local
105    cache = CALLOC_STRUCT(util_cache);  in util_cache_create()
106    if (!cache)  in util_cache_create()
109    cache->hash = hash;  in util_cache_create()
110    cache->compare = compare;  in util_cache_create()
111    cache->destroy = destroy;  in util_cache_create()
113    list_inithead(&cache->lru.list);  in util_cache_create()
116    cache->size = size;  in util_cache_create()
118    cache->entries = CALLOC(size, sizeof(struct util_cache_entry));  in util_cache_create()
119    if (!cache->entries) {  in util_cache_create()
120       FREE(cache);  in util_cache_create()
124    ensure_sanity(cache);  in util_cache_create()
125    return cache;  in util_cache_create()
130  * Try to find a cache entry, given the key and hash of the key.
133 util_cache_entry_get(struct util_cache *cache,  in util_cache_entry_get()  argument
138    uint32_t index = hash % cache->size;  in util_cache_entry_get()
148    for (probe = 0; probe < cache->size; probe++) {  in util_cache_entry_get()
149       uint32_t i = (index + probe) % cache->size;  in util_cache_entry_get()
150       struct util_cache_entry *current = &cache->entries[i];  in util_cache_entry_get()
154              cache->compare(key, current->key) == 0)  in util_cache_entry_get()
170 util_cache_entry_destroy(struct util_cache *cache,  in util_cache_entry_destroy()  argument
181       cache->count--;  in util_cache_entry_destroy()
183       if (cache->destroy)  in util_cache_entry_destroy()
184          cache->destroy(key, value);  in util_cache_entry_destroy()
192  * Insert an entry in the cache, given the key and value.
195 util_cache_set(struct util_cache *cache,  in util_cache_set()  argument
202    assert(cache);  in util_cache_set()
203    if (!cache)  in util_cache_set()
205    hash = cache->hash(key);  in util_cache_set()
206    entry = util_cache_entry_get(cache, hash, key);  in util_cache_set()
208       entry = list_last_entry(&cache->lru.list, struct util_cache_entry, list);  in util_cache_set()
210    if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA)  in util_cache_set()
211 … util_cache_entry_destroy(cache, list_last_entry(&cache->lru.list, struct util_cache_entry, list));  in util_cache_set()
213    util_cache_entry_destroy(cache, entry);  in util_cache_set()
223    list_add(&cache->lru.list, &entry->list);  in util_cache_set()
224    cache->count++;  in util_cache_set()
226    ensure_sanity(cache);  in util_cache_set()
231  * Search the cache for an entry with the given key.  Return the corresponding
235 util_cache_get(struct util_cache *cache,  in util_cache_get()  argument
241    assert(cache);  in util_cache_get()
242    if (!cache)  in util_cache_get()
244    hash = cache->hash(key);  in util_cache_get()
245    entry = util_cache_entry_get(cache, hash, key);  in util_cache_get()
250       list_move_to(&cache->lru.list, &entry->list);  in util_cache_get()
258  * Remove all entries from the cache.  The 'destroy' function will be called
262 util_cache_clear(struct util_cache *cache)  in util_cache_clear()  argument
266    assert(cache);  in util_cache_clear()
267    if (!cache)  in util_cache_clear()
270    for (i = 0; i < cache->size; ++i) {  in util_cache_clear()
271       util_cache_entry_destroy(cache, &cache->entries[i]);  in util_cache_clear()
272       cache->entries[i].state = EMPTY;  in util_cache_clear()
275    assert(cache->count == 0);  in util_cache_clear()
276    assert(list_is_empty(&cache->lru.list));  in util_cache_clear()
277    ensure_sanity(cache);  in util_cache_clear()
282  * Destroy the cache and all entries.
285 util_cache_destroy(struct util_cache *cache)  in util_cache_destroy()  argument
287    assert(cache);  in util_cache_destroy()
288    if (!cache)  in util_cache_destroy()
292    if (cache->count >= 20*cache->size) {  in util_cache_destroy()
294       double mean = (double)cache->count/(double)cache->size;  in util_cache_destroy()
297       for (i = 0; i < cache->size; ++i) {  in util_cache_destroy()
298          double z = fabs(cache->entries[i].count - mean)/stddev;  in util_cache_destroy()
306    util_cache_clear(cache);  in util_cache_destroy()
308    FREE(cache->entries);  in util_cache_destroy()
309    FREE(cache);  in util_cache_destroy()
314  * Remove the cache entry which matches the given key.
317 util_cache_remove(struct util_cache *cache,  in util_cache_remove()  argument
323    assert(cache);  in util_cache_remove()
324    if (!cache)  in util_cache_remove()
327    hash = cache->hash(key);  in util_cache_remove()
329    entry = util_cache_entry_get(cache, hash, key);  in util_cache_remove()
334       util_cache_entry_destroy(cache, entry);  in util_cache_remove()
336    ensure_sanity(cache);  in util_cache_remove()
341 ensure_sanity(const struct util_cache *cache)  in ensure_sanity()  argument
346    assert(cache);  in ensure_sanity()
347    for (i = 0; i < cache->size; i++) {  in ensure_sanity()
348       struct util_cache_entry *header = &cache->entries[i];  in ensure_sanity()
356          assert(header->hash == cache->hash(header->key));  in ensure_sanity()
360    assert(cnt == cache->count);  in ensure_sanity()
361    assert(cache->size >= cnt);  in ensure_sanity()
363    if (cache->count == 0) {  in ensure_sanity()
364       assert (list_is_empty(&cache->lru.list));  in ensure_sanity()
368          list_entry(&cache->lru, struct util_cache_entry, list);  in ensure_sanity()
371       assert (!list_is_empty(&cache->lru.list));  in ensure_sanity()
373       for (i = 0; i < cache->count; i++)  in ensure_sanity()
376       assert(header == &cache->lru);  in ensure_sanity()
380    (void)cache;  in ensure_sanity()