1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
#ifndef __CACHE_H__
#define __CACHE_H__
#include "list.h"
#define CACHE_LISTS 256
typedef struct
{
list_elem link;
list_elem lru_link;
} cache_link;
typedef struct
{
/* LRU list holds unused items */
unsigned int lru_entries;
list_elem lru_list;
unsigned int max_free_entries;
unsigned int entries;
list_elem lists[CACHE_LISTS];
unsigned int (*elem_val)(cache_link *elem);
void (*freed)(cache_link *elem);
} listcache;
static inline void
cache_add(listcache *c, cache_link *elem)
{
unsigned int hash = c->elem_val(elem) % CACHE_LISTS;
int delcount = c->lru_entries - c->max_free_entries;
if (delcount > 0) {
/* Delete some unused items. */
list_elem *lru, *next;
cache_link *l;
list_for_each_elem_safe(&c->lru_list, lru, next) {
l = container_of(lru, cache_link, lru_link);
list_del(lru);
list_del(&l->link);
c->entries--;
c->lru_entries--;
c->freed(l);
delcount--;
if (delcount <= 0)
break;
}
}
c->entries++;
list_item_init(&elem->lru_link); /* Mark it not in the LRU list */
list_add_after(&c->lists[hash], &elem->link);
}
static inline void
cache_item_set_unused(listcache *c, cache_link *elem)
{
list_add_before(&c->lru_list, &elem->lru_link);
c->lru_entries++;
}
static inline cache_link *
cache_find(listcache *c, unsigned int val)
{
unsigned int hash = val % CACHE_LISTS;
list_elem *elem;
list_for_each_elem(&c->lists[hash], elem) {
cache_link *l = container_of(elem, cache_link, link);
if (c->elem_val(l) == val) {
if (!list_empty(&l->lru_link)) {
/* It's in the unused list, remove it. */
list_del(&l->lru_link);
list_item_init(&l->lru_link);
c->lru_entries--;
}
return l;
}
}
return NULL;
}
static inline int
cache_flush(listcache *c)
{
list_elem *elem, *next;
cache_link *l;
int i;
list_for_each_elem_safe(&c->lru_list, elem, next) {
l = container_of(elem, cache_link, lru_link);
list_del(elem);
list_del(&l->link);
c->entries--;
c->lru_entries--;
c->freed(l);
}
for (i = 0; i < CACHE_LISTS; i++) {
list_for_each_elem_safe(&c->lists[i], elem, next) {
l = container_of(elem, cache_link, link);
list_del(&l->link);
c->entries--;
c->freed(l);
}
}
return c->entries || c->lru_entries;
}
static inline void
cache_init(listcache *c, unsigned int max_free_entries,
unsigned int (*elem_val)(cache_link *elem),
void (*freed)(cache_link *elem))
{
int i;
c->entries = 0;
c->lru_entries = 0;
c->max_free_entries = max_free_entries;
list_init(&c->lru_list);
for (i = 0; i < CACHE_LISTS; i++)
list_init(&c->lists[i]);
c->elem_val = elem_val;
c->freed = freed;
}
#endif /* __CACHE_H__ */
|
