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