Revision 88570136
Added LRU eviction to cache. Not tested yet.
mainbox/cache.c | ||
---|---|---|
1 | 1 |
#include "cache.h" |
2 | 2 |
#include "log.h" |
3 | 3 |
#include <stdlib.h> |
4 |
#include <time.h> |
|
4 | 5 |
|
5 | 6 |
struct entry_t { |
6 | 7 |
unsigned int key; |
... | ... | |
9 | 10 |
struct entry_t *next; |
10 | 11 |
}; |
11 | 12 |
|
12 |
struct entry_t *cache[CACHE_SIZE]; |
|
13 |
static struct entry_t *cache[CACHE_SIZE]; |
|
14 |
static int n_entries; |
|
15 |
|
|
16 |
static void cache_remove_lru() { |
|
17 |
struct entry_t *entry, **ptr; |
|
18 |
struct entry_t *lru, **lru_ptr; |
|
19 |
int i; |
|
20 |
|
|
21 |
lru = NULL; |
|
22 |
for (i = 0; i < CACHE_SIZE; i++) { |
|
23 |
ptr = &cache[i]; |
|
24 |
for (entry = cache[i]; entry; entry = entry->next) { |
|
25 |
if (lru == NULL || entry->retrieved < lru->retrieved) { |
|
26 |
lru = entry; |
|
27 |
lru_ptr = ptr; |
|
28 |
} |
|
29 |
ptr = &entry->next; |
|
30 |
} |
|
31 |
} |
|
32 |
|
|
33 |
if (lru != NULL) { |
|
34 |
*lru_ptr = lru->next; |
|
35 |
free(lru); |
|
36 |
n_entries--; |
|
37 |
} |
|
38 |
} |
|
13 | 39 |
|
14 | 40 |
void cache_foreach(cache_func f) { |
15 | 41 |
struct entry_t *entry; |
... | ... | |
32 | 58 |
} |
33 | 59 |
cache[i] = NULL; |
34 | 60 |
} |
61 |
|
|
62 |
n_entries = 0; |
|
35 | 63 |
} |
36 | 64 |
|
37 | 65 |
struct entry_t *cache_find(unsigned int key) { |
38 | 66 |
struct entry_t *entry; |
39 | 67 |
|
40 | 68 |
for (entry = cache[key % CACHE_SIZE]; entry; entry = entry->next) { |
41 |
if (entry->key == key) |
|
69 |
if (entry->key == key) { |
|
70 |
entry->retrieved = time(NULL); |
|
42 | 71 |
return entry; |
72 |
} |
|
43 | 73 |
} |
44 | 74 |
|
45 | 75 |
return NULL; |
... | ... | |
51 | 81 |
|
52 | 82 |
entry = malloc(sizeof(struct entry_t)); |
53 | 83 |
if (!entry) { |
54 |
log_print("ERROR: Out of memory; clearing cache"); |
|
55 |
cache_clear(); |
|
84 |
log_print("ERROR: Out of memory"); |
|
56 | 85 |
return; |
57 | 86 |
} |
58 | 87 |
|
88 |
if (n_entries == CACHE_MAX_ENTRIES) { |
|
89 |
cache_remove_lru(); |
|
90 |
} |
|
91 |
n_entries++; |
|
92 |
|
|
59 | 93 |
i = key % CACHE_SIZE; |
60 | 94 |
entry->key = key; |
61 | 95 |
entry->value = value; |
mainbox/cache.h | ||
---|---|---|
2 | 2 |
#define CACHE_H |
3 | 3 |
|
4 | 4 |
#define CACHE_SIZE 256 |
5 |
#define CACHE_MAX_ENTRIES 160 |
|
5 | 6 |
|
6 | 7 |
typedef void (*cache_func)(unsigned int key); |
7 | 8 |
|
Also available in: Unified diff