Lines Matching refs:cache
30 * Improved cache implementation.
76 /** Max entries in the cache */
82 /** Number of entries in the cache */
91 ensure_sanity(const struct util_cache *cache);
96 * Create a new cache with 'size' entries. Also provide functions for
105 struct util_cache *cache;
107 cache = CALLOC_STRUCT(util_cache);
108 if (!cache)
111 cache->hash = hash;
112 cache->compare = compare;
113 cache->destroy = destroy;
115 make_empty_list(&cache->lru);
118 cache->size = size;
120 cache->entries = CALLOC(size, sizeof(struct util_cache_entry));
121 if (!cache->entries) {
122 FREE(cache);
126 ensure_sanity(cache);
127 return cache;
132 * Try to find a cache entry, given the key and hash of the key.
135 util_cache_entry_get(struct util_cache *cache,
140 uint32_t index = hash % cache->size;
150 for (probe = 0; probe < cache->size; probe++) {
151 uint32_t i = (index + probe) % cache->size;
152 struct util_cache_entry *current = &cache->entries[i];
156 cache->compare(key, current->key) == 0)
172 util_cache_entry_destroy(struct util_cache *cache,
183 cache->count--;
185 if (cache->destroy)
186 cache->destroy(key, value);
194 * Insert an entry in the cache, given the key and value.
197 util_cache_set(struct util_cache *cache,
204 assert(cache);
205 if (!cache)
207 hash = cache->hash(key);
208 entry = util_cache_entry_get(cache, hash, key);
210 entry = cache->lru.prev;
212 if (cache->count >= cache->size / CACHE_DEFAULT_ALPHA)
213 util_cache_entry_destroy(cache, cache->lru.prev);
215 util_cache_entry_destroy(cache, entry);
225 insert_at_head(&cache->lru, entry);
226 cache->count++;
228 ensure_sanity(cache);
233 * Search the cache for an entry with the given key. Return the corresponding
237 util_cache_get(struct util_cache *cache,
243 assert(cache);
244 if (!cache)
246 hash = cache->hash(key);
247 entry = util_cache_entry_get(cache, hash, key);
252 move_to_head(&cache->lru, entry);
259 * Remove all entries from the cache. The 'destroy' function will be called
263 util_cache_clear(struct util_cache *cache)
267 assert(cache);
268 if (!cache)
271 for (i = 0; i < cache->size; ++i) {
272 util_cache_entry_destroy(cache, &cache->entries[i]);
273 cache->entries[i].state = EMPTY;
276 assert(cache->count == 0);
277 assert(is_empty_list(&cache->lru));
278 ensure_sanity(cache);
283 * Destroy the cache and all entries.
286 util_cache_destroy(struct util_cache *cache)
288 assert(cache);
289 if (!cache)
293 if (cache->count >= 20*cache->size) {
295 double mean = (double)cache->count/(double)cache->size;
298 for (i = 0; i < cache->size; ++i) {
299 double z = fabs(cache->entries[i].count - mean)/stddev;
307 util_cache_clear(cache);
309 FREE(cache->entries);
310 FREE(cache);
315 * Remove the cache entry which matches the given key.
318 util_cache_remove(struct util_cache *cache,
324 assert(cache);
325 if (!cache)
328 hash = cache->hash(key);
330 entry = util_cache_entry_get(cache, hash, key);
335 util_cache_entry_destroy(cache, entry);
337 ensure_sanity(cache);
342 ensure_sanity(const struct util_cache *cache)
347 assert(cache);
348 for (i = 0; i < cache->size; i++) {
349 struct util_cache_entry *header = &cache->entries[i];
357 assert(header->hash == cache->hash(header->key));
361 assert(cnt == cache->count);
362 assert(cache->size >= cnt);
364 if (cache->count == 0) {
365 assert (is_empty_list(&cache->lru));
368 struct util_cache_entry *header = cache->lru.next;
371 assert (!is_empty_list(&cache->lru));
373 for (i = 0; i < cache->count; i++)
376 assert(header == &cache->lru);
380 (void)cache;
