30  * Improved cache implementation.
85 ensure_sanity(const struct util_cache *cache);
95    struct util_cache *cache;  in util_cache_create()  local
97    cache = CALLOC_STRUCT(util_cache);  in util_cache_create()
98    if(!cache)  in util_cache_create()
101    cache->hash = hash;  in util_cache_create()
102    cache->compare = compare;  in util_cache_create()
103    cache->destroy = destroy;  in util_cache_create()
105    make_empty_list(&cache->lru);  in util_cache_create()
108    cache->size = size;  in util_cache_create()
110    cache->entries = CALLOC(size, sizeof(struct util_cache_entry));  in util_cache_create()
111    if(!cache->entries) {  in util_cache_create()
112       FREE(cache);  in util_cache_create()
116    ensure_sanity(cache);  in util_cache_create()
117    return cache;  in util_cache_create()
122 util_cache_entry_get(struct util_cache *cache,  in util_cache_entry_get()  argument
127    uint32_t index = hash % cache->size;  in util_cache_entry_get()
137    for (probe = 0; probe < cache->size; probe++) {  in util_cache_entry_get()
138       uint32_t i = (index + probe) % cache->size;  in util_cache_entry_get()
139       struct util_cache_entry *current = &cache->entries[i];  in util_cache_entry_get()
143              cache->compare(key, current->key) == 0)  in util_cache_entry_get()
159 util_cache_entry_destroy(struct util_cache *cache,  in util_cache_entry_destroy()  argument
170       cache->count--;  in util_cache_entry_destroy()
172       if(cache->destroy)  in util_cache_entry_destroy()
173          cache->destroy(key, value);  in util_cache_entry_destroy()
181 util_cache_set(struct util_cache *cache,  in util_cache_set()  argument
186    uint32_t hash = cache->hash(key);  in util_cache_set()
188    assert(cache);  in util_cache_set()
189    if (!cache)  in util_cache_set()
192    entry = util_cache_entry_get(cache, hash, key);  in util_cache_set()
194       entry = cache->lru.prev;  in util_cache_set()
196    if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA)  in util_cache_set()
197       util_cache_entry_destroy(cache, cache->lru.prev);  in util_cache_set()
199    util_cache_entry_destroy(cache, entry);  in util_cache_set()
209    insert_at_head(&cache->lru, entry);  in util_cache_set()
210    cache->count++;  in util_cache_set()
212    ensure_sanity(cache);  in util_cache_set()
217 util_cache_get(struct util_cache *cache,   in util_cache_get()  argument
221    uint32_t hash = cache->hash(key);  in util_cache_get()
223    assert(cache);  in util_cache_get()
224    if (!cache)  in util_cache_get()
227    entry = util_cache_entry_get(cache, hash, key);  in util_cache_get()
232       move_to_head(&cache->lru, entry);  in util_cache_get()
239 util_cache_clear(struct util_cache *cache)  in util_cache_clear()  argument
243    assert(cache);  in util_cache_clear()
244    if (!cache)  in util_cache_clear()
247    for(i = 0; i < cache->size; ++i) {  in util_cache_clear()
248       util_cache_entry_destroy(cache, &cache->entries[i]);  in util_cache_clear()
249       cache->entries[i].state = EMPTY;  in util_cache_clear()
252    assert(cache->count == 0);  in util_cache_clear()
253    assert(is_empty_list(&cache->lru));  in util_cache_clear()
254    ensure_sanity(cache);  in util_cache_clear()
259 util_cache_destroy(struct util_cache *cache)  in util_cache_destroy()  argument
261    assert(cache);  in util_cache_destroy()
262    if (!cache)  in util_cache_destroy()
266    if(cache->count >= 20*cache->size) {  in util_cache_destroy()
268       double mean = (double)cache->count/(double)cache->size;  in util_cache_destroy()
271       for(i = 0; i < cache->size; ++i) {  in util_cache_destroy()
272          double z = fabs(cache->entries[i].count - mean)/stddev;  in util_cache_destroy()
280    util_cache_clear(cache);  in util_cache_destroy()
282    FREE(cache->entries);  in util_cache_destroy()
283    FREE(cache);  in util_cache_destroy()
288 util_cache_remove(struct util_cache *cache,  in util_cache_remove()  argument
294    assert(cache);  in util_cache_remove()
295    if (!cache)  in util_cache_remove()
298    hash = cache->hash(key);  in util_cache_remove()
300    entry = util_cache_entry_get(cache, hash, key);  in util_cache_remove()
305       util_cache_entry_destroy(cache, entry);  in util_cache_remove()
307    ensure_sanity(cache);  in util_cache_remove()
312 ensure_sanity(const struct util_cache *cache)  in ensure_sanity()  argument
317    assert(cache);  in ensure_sanity()
318    for (i = 0; i < cache->size; i++) {  in ensure_sanity()
319       struct util_cache_entry *header = &cache->entries[i];  in ensure_sanity()
327          assert(header->hash == cache->hash(header->key));  in ensure_sanity()
331    assert(cnt == cache->count);  in ensure_sanity()
332    assert(cache->size >= cnt);  in ensure_sanity()
334    if (cache->count == 0) {  in ensure_sanity()
335       assert (is_empty_list(&cache->lru));  in ensure_sanity()
338       struct util_cache_entry *header = cache->lru.next;  in ensure_sanity()
341       assert (!is_empty_list(&cache->lru));  in ensure_sanity()
343       for (i = 0; i < cache->count; i++)  in ensure_sanity()
346       assert(header == &cache->lru);  in ensure_sanity()
350    (void)cache;  in ensure_sanity()