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