91 ensure_sanity(const struct util_cache *cache);
105    struct util_cache *cache;  in util_cache_create()  local
107    cache = CALLOC_STRUCT(util_cache);  in util_cache_create()
108    if (!cache)  in util_cache_create()
111    cache->hash = hash;  in util_cache_create()
112    cache->compare = compare;  in util_cache_create()
113    cache->destroy = destroy;  in util_cache_create()
115    make_empty_list(&cache->lru);  in util_cache_create()
118    cache->size = size;  in util_cache_create()
120    cache->entries = CALLOC(size, sizeof(struct util_cache_entry));  in util_cache_create()
121    if (!cache->entries) {  in util_cache_create()
122       FREE(cache);  in util_cache_create()
126    ensure_sanity(cache);  in util_cache_create()
127    return cache;  in util_cache_create()
135 util_cache_entry_get(struct util_cache *cache,  in util_cache_entry_get()  argument
140    uint32_t index = hash % cache->size;  in util_cache_entry_get()
150    for (probe = 0; probe < cache->size; probe++) {  in util_cache_entry_get()
151       uint32_t i = (index + probe) % cache->size;  in util_cache_entry_get()
152       struct util_cache_entry *current = &cache->entries[i];  in util_cache_entry_get()
156              cache->compare(key, current->key) == 0)  in util_cache_entry_get()
172 util_cache_entry_destroy(struct util_cache *cache,  in util_cache_entry_destroy()  argument
183       cache->count--;  in util_cache_entry_destroy()
185       if (cache->destroy)  in util_cache_entry_destroy()
186          cache->destroy(key, value);  in util_cache_entry_destroy()
197 util_cache_set(struct util_cache *cache,  in util_cache_set()  argument
204    assert(cache);  in util_cache_set()
205    if (!cache)  in util_cache_set()
207    hash = cache->hash(key);  in util_cache_set()
208    entry = util_cache_entry_get(cache, hash, key);  in util_cache_set()
210       entry = cache->lru.prev;  in util_cache_set()
212    if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA)  in util_cache_set()
213       util_cache_entry_destroy(cache, cache->lru.prev);  in util_cache_set()
215    util_cache_entry_destroy(cache, entry);  in util_cache_set()
225    insert_at_head(&cache->lru, entry);  in util_cache_set()
226    cache->count++;  in util_cache_set()
228    ensure_sanity(cache);  in util_cache_set()
237 util_cache_get(struct util_cache *cache,   in util_cache_get()  argument
243    assert(cache);  in util_cache_get()
244    if (!cache)  in util_cache_get()
246    hash = cache->hash(key);  in util_cache_get()
247    entry = util_cache_entry_get(cache, hash, key);  in util_cache_get()
252       move_to_head(&cache->lru, entry);  in util_cache_get()
263 util_cache_clear(struct util_cache *cache)  in util_cache_clear()  argument
267    assert(cache);  in util_cache_clear()
268    if (!cache)  in util_cache_clear()
271    for (i = 0; i < cache->size; ++i) {  in util_cache_clear()
272       util_cache_entry_destroy(cache, &cache->entries[i]);  in util_cache_clear()
273       cache->entries[i].state = EMPTY;  in util_cache_clear()
276    assert(cache->count == 0);  in util_cache_clear()
277    assert(is_empty_list(&cache->lru));  in util_cache_clear()
278    ensure_sanity(cache);  in util_cache_clear()
286 util_cache_destroy(struct util_cache *cache)  in util_cache_destroy()  argument
288    assert(cache);  in util_cache_destroy()
289    if (!cache)  in util_cache_destroy()
293    if (cache->count >= 20*cache->size) {  in util_cache_destroy()
295       double mean = (double)cache->count/(double)cache->size;  in util_cache_destroy()
298       for (i = 0; i < cache->size; ++i) {  in util_cache_destroy()
299          double z = fabs(cache->entries[i].count - mean)/stddev;  in util_cache_destroy()
307    util_cache_clear(cache);  in util_cache_destroy()
309    FREE(cache->entries);  in util_cache_destroy()
310    FREE(cache);  in util_cache_destroy()
318 util_cache_remove(struct util_cache *cache,  in util_cache_remove()  argument
324    assert(cache);  in util_cache_remove()
325    if (!cache)  in util_cache_remove()
328    hash = cache->hash(key);  in util_cache_remove()
330    entry = util_cache_entry_get(cache, hash, key);  in util_cache_remove()
335       util_cache_entry_destroy(cache, entry);  in util_cache_remove()
337    ensure_sanity(cache);  in util_cache_remove()
342 ensure_sanity(const struct util_cache *cache)  in ensure_sanity()  argument
347    assert(cache);  in ensure_sanity()
348    for (i = 0; i < cache->size; i++) {  in ensure_sanity()
349       struct util_cache_entry *header = &cache->entries[i];  in ensure_sanity()
357          assert(header->hash == cache->hash(header->key));  in ensure_sanity()
361    assert(cnt == cache->count);  in ensure_sanity()
362    assert(cache->size >= cnt);  in ensure_sanity()
364    if (cache->count == 0) {  in ensure_sanity()
365       assert (is_empty_list(&cache->lru));  in ensure_sanity()
368       struct util_cache_entry *header = cache->lru.next;  in ensure_sanity()
371       assert (!is_empty_list(&cache->lru));  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()