1 /**************************************************************************
3 * Copyright 2008 VMware, Inc.
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 **************************************************************************/
30 * Improved cache implementation.
32 * Fixed size array with linear probing on collision and LRU eviction
35 * @author Jose Fonseca <jfonseca@vmware.com>
39 #include "pipe/p_compiler.h"
40 #include "util/u_debug.h"
42 #include "util/u_math.h"
43 #include "util/u_memory.h"
44 #include "util/u_cache.h"
45 #include "util/simple_list.h"
48 struct util_cache_entry
50 enum { EMPTY
= 0, FILLED
, DELETED
} state
;
53 struct util_cache_entry
*next
;
54 struct util_cache_entry
*prev
;
68 uint32_t (*hash
)(const void *key
);
70 /** Compare two keys */
71 int (*compare
)(const void *key1
, const void *key2
);
73 /** Destroy a (key, value) pair */
74 void (*destroy
)(void *key
, void *value
);
76 /** Max entries in the cache */
79 /** Array [size] of entries */
80 struct util_cache_entry
*entries
;
82 /** Number of entries in the cache */
85 /** Head of list, sorted from Least-recently used to Most-recently used */
86 struct util_cache_entry lru
;
91 ensure_sanity(const struct util_cache
*cache
);
93 #define CACHE_DEFAULT_ALPHA 2
96 * Create a new cache with 'size' entries. Also provide functions for
97 * hashing keys, comparing keys and destroying (key,value) pairs.
100 util_cache_create(uint32_t (*hash
)(const void *key
),
101 int (*compare
)(const void *key1
, const void *key2
),
102 void (*destroy
)(void *key
, void *value
),
105 struct util_cache
*cache
;
107 cache
= CALLOC_STRUCT(util_cache
);
112 cache
->compare
= compare
;
113 cache
->destroy
= destroy
;
115 make_empty_list(&cache
->lru
);
117 size
*= CACHE_DEFAULT_ALPHA
;
120 cache
->entries
= CALLOC(size
, sizeof(struct util_cache_entry
));
121 if (!cache
->entries
) {
126 ensure_sanity(cache
);
132 * Try to find a cache entry, given the key and hash of the key.
134 static struct util_cache_entry
*
135 util_cache_entry_get(struct util_cache
*cache
,
139 struct util_cache_entry
*first_unfilled
= NULL
;
140 uint32_t index
= hash
% cache
->size
;
143 /* Probe until we find either a matching FILLED entry or an EMPTY
144 * slot (which has never been occupied).
146 * Deleted or non-matching slots are not indicative of completion
147 * as a previous linear probe for the same key could have continued
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
];
154 if (current
->state
== FILLED
) {
155 if (current
->hash
== hash
&&
156 cache
->compare(key
, current
->key
) == 0)
161 first_unfilled
= current
;
163 if (current
->state
== EMPTY
)
164 return first_unfilled
;
172 util_cache_entry_destroy(struct util_cache
*cache
,
173 struct util_cache_entry
*entry
)
175 void *key
= entry
->key
;
176 void *value
= entry
->value
;
181 if (entry
->state
== FILLED
) {
182 remove_from_list(entry
);
186 cache
->destroy(key
, value
);
188 entry
->state
= DELETED
;
194 * Insert an entry in the cache, given the key and value.
197 util_cache_set(struct util_cache
*cache
,
201 struct util_cache_entry
*entry
;
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
);
223 entry
->value
= value
;
224 entry
->state
= FILLED
;
225 insert_at_head(&cache
->lru
, entry
);
228 ensure_sanity(cache
);
233 * Search the cache for an entry with the given key. Return the corresponding
234 * value or NULL if not found.
237 util_cache_get(struct util_cache
*cache
,
240 struct util_cache_entry
*entry
;
246 hash
= cache
->hash(key
);
247 entry
= util_cache_entry_get(cache
, hash
, key
);
251 if (entry
->state
== FILLED
)
252 move_to_head(&cache
->lru
, entry
);
259 * Remove all entries from the cache. The 'destroy' function will be called
260 * for each entry's (key, value).
263 util_cache_clear(struct util_cache
*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
)
293 if (cache
->count
>= 20*cache
->size
) {
294 /* Normal approximation of the Poisson distribution */
295 double mean
= (double)cache
->count
/(double)cache
->size
;
296 double stddev
= sqrt(mean
);
298 for (i
= 0; i
< cache
->size
; ++i
) {
299 double z
= fabs(cache
->entries
[i
].count
- mean
)/stddev
;
300 /* This assert should not fail 99.9999998027% of the times, unless
301 * the hash function is a poor one */
307 util_cache_clear(cache
);
309 FREE(cache
->entries
);
315 * Remove the cache entry which matches the given key.
318 util_cache_remove(struct util_cache
*cache
,
321 struct util_cache_entry
*entry
;
328 hash
= cache
->hash(key
);
330 entry
= util_cache_entry_get(cache
, hash
, key
);
334 if (entry
->state
== FILLED
)
335 util_cache_entry_destroy(cache
, entry
);
337 ensure_sanity(cache
);
342 ensure_sanity(const struct util_cache
*cache
)
348 for (i
= 0; i
< cache
->size
; i
++) {
349 struct util_cache_entry
*header
= &cache
->entries
[i
];
352 assert(header
->state
== FILLED
||
353 header
->state
== EMPTY
||
354 header
->state
== DELETED
);
355 if (header
->state
== FILLED
) {
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
++)
374 header
= header
->next
;
376 assert(header
== &cache
->lru
);