1 /**
2  * @file lv_lru.c
3  *
4  * @see https://github.com/willcannings/C-LRU-Cache
5  */
6 
7 /*********************
8  *      INCLUDES
9  *********************/
10 
11 #include "lv_lru.h"
12 #include "lv_math.h"
13 #include "lv_mem.h"
14 #include "lv_assert.h"
15 #include "lv_log.h"
16 
17 /*********************
18  *      DEFINES
19  *********************/
20 
21 /**********************
22  *      TYPEDEFS
23  **********************/
24 
25 struct _lv_lru_item_t {
26     void * value;
27     void * key;
28     size_t value_length;
29     size_t key_length;
30     uint64_t access_count;
31     struct _lv_lru_item_t * next;
32 };
33 
34 /**********************
35  *  STATIC PROTOTYPES
36  **********************/
37 
38 /**
39  * MurmurHash2
40  * @author Austin Appleby
41  * @see http://sites.google.com/site/murmurhash/
42  */
43 static uint32_t lv_lru_hash(lv_lru_t * cache, const void * key, uint32_t key_length);
44 
45 /** compare a key against an existing item's key */
46 static int lv_lru_cmp_keys(lv_lru_item_t * item, const void * key, uint32_t key_length);
47 
48 /** remove an item and push it to the free items queue */
49 static void lv_lru_remove_item(lv_lru_t * cache, lv_lru_item_t * prev, lv_lru_item_t * item, uint32_t hash_index);
50 
51 /** pop an existing item off the free queue, or create a new one */
52 static lv_lru_item_t * lv_lru_pop_or_create_item(lv_lru_t * cache);
53 
54 /**********************
55  *  STATIC VARIABLES
56  **********************/
57 
58 /**********************
59  *      MACROS
60  **********************/
61 
62 /* error helpers */
63 #define error_for(conditions, error)  if(conditions) {return error;}
64 #define test_for_missing_cache()      error_for(!cache, LV_LRU_MISSING_CACHE)
65 #define test_for_missing_key()        error_for(!key, LV_LRU_MISSING_KEY)
66 #define test_for_missing_value()      error_for(!value || value_length == 0, LV_LRU_MISSING_VALUE)
67 #define test_for_value_too_large()    error_for(value_length > cache->total_memory, LV_LRU_VALUE_TOO_LARGE)
68 
69 /**********************
70  *   GLOBAL FUNCTIONS
71  **********************/
72 
lv_lru_create(size_t cache_size,size_t average_length,lv_lru_free_t * value_free,lv_lru_free_t * key_free)73 lv_lru_t * lv_lru_create(size_t cache_size, size_t average_length, lv_lru_free_t * value_free,
74                          lv_lru_free_t * key_free)
75 {
76     // create the cache
77     lv_lru_t * cache = (lv_lru_t *) lv_mem_alloc(sizeof(lv_lru_t));
78     lv_memset_00(cache, sizeof(lv_lru_t));
79     if(!cache) {
80         LV_LOG_WARN("LRU Cache unable to create cache object");
81         return NULL;
82     }
83     cache->hash_table_size = cache_size / average_length;
84     cache->average_item_length = average_length;
85     cache->free_memory = cache_size;
86     cache->total_memory = cache_size;
87     cache->seed = lv_rand(1, UINT32_MAX);
88     cache->value_free = value_free ? value_free : lv_mem_free;
89     cache->key_free = key_free ? key_free : lv_mem_free;
90 
91     // size the hash table to a guestimate of the number of slots required (assuming a perfect hash)
92     cache->items = (lv_lru_item_t **) lv_mem_alloc(sizeof(lv_lru_item_t *) * cache->hash_table_size);
93     lv_memset_00(cache->items, sizeof(lv_lru_item_t *) * cache->hash_table_size);
94     if(!cache->items) {
95         LV_LOG_WARN("LRU Cache unable to create cache hash table");
96         lv_mem_free(cache);
97         return NULL;
98     }
99     return cache;
100 }
101 
lv_lru_del(lv_lru_t * cache)102 void lv_lru_del(lv_lru_t * cache)
103 {
104     LV_ASSERT_NULL(cache);
105 
106     // free each of the cached items, and the hash table
107     lv_lru_item_t * item = NULL, * next = NULL;
108     uint32_t i = 0;
109     if(cache->items) {
110         for(; i < cache->hash_table_size; i++) {
111             item = cache->items[i];
112             while(item) {
113                 next = (lv_lru_item_t *) item->next;
114                 cache->value_free(item->value);
115                 cache->key_free(item->key);
116                 cache->free_memory += item->value_length;
117                 lv_mem_free(item);
118                 item = next;
119             }
120         }
121         lv_mem_free(cache->items);
122     }
123 
124     if(cache->free_items) {
125         item = cache->free_items;
126         while(item) {
127             next = (lv_lru_item_t *) item->next;
128             lv_mem_free(item);
129             item = next;
130         }
131     }
132 
133     // free the cache
134     lv_mem_free(cache);
135 }
136 
lv_lru_set(lv_lru_t * cache,const void * key,size_t key_length,void * value,size_t value_length)137 lv_lru_res_t lv_lru_set(lv_lru_t * cache, const void * key, size_t key_length, void * value, size_t value_length)
138 {
139     test_for_missing_cache();
140     test_for_missing_key();
141     test_for_missing_value();
142     test_for_value_too_large();
143 
144     // see if the key already exists
145     uint32_t hash_index = lv_lru_hash(cache, key, key_length);
146     int required = 0;
147     lv_lru_item_t * item = NULL, * prev = NULL;
148     item = cache->items[hash_index];
149 
150     while(item && lv_lru_cmp_keys(item, key, key_length)) {
151         prev = item;
152         item = (lv_lru_item_t *) item->next;
153     }
154 
155     if(item) {
156         // update the value and value_lengths
157         required = (int)(value_length - item->value_length);
158         cache->value_free(item->value);
159         item->value = value;
160         item->value_length = value_length;
161 
162     }
163     else {
164         // insert a new item
165         item = lv_lru_pop_or_create_item(cache);
166         item->value = value;
167         item->key = lv_mem_alloc(key_length);
168         memcpy(item->key, key, key_length);
169         item->value_length = value_length;
170         item->key_length = key_length;
171         required = (int) value_length;
172 
173         if(prev)
174             prev->next = item;
175         else
176             cache->items[hash_index] = item;
177     }
178     item->access_count = ++cache->access_count;
179 
180     // remove as many items as necessary to free enough space
181     if(required > 0 && (size_t) required > cache->free_memory) {
182         while(cache->free_memory < (size_t) required)
183             lv_lru_remove_lru_item(cache);
184     }
185     cache->free_memory -= required;
186     return LV_LRU_OK;
187 }
188 
lv_lru_get(lv_lru_t * cache,const void * key,size_t key_size,void ** value)189 lv_lru_res_t lv_lru_get(lv_lru_t * cache, const void * key, size_t key_size, void ** value)
190 {
191     test_for_missing_cache();
192     test_for_missing_key();
193 
194     // loop until we find the item, or hit the end of a chain
195     uint32_t hash_index = lv_lru_hash(cache, key, key_size);
196     lv_lru_item_t * item = cache->items[hash_index];
197 
198     while(item && lv_lru_cmp_keys(item, key, key_size))
199         item = (lv_lru_item_t *) item->next;
200 
201     if(item) {
202         *value = item->value;
203         item->access_count = ++cache->access_count;
204     }
205     else {
206         *value = NULL;
207     }
208 
209     return LV_LRU_OK;
210 }
211 
lv_lru_remove(lv_lru_t * cache,const void * key,size_t key_size)212 lv_lru_res_t lv_lru_remove(lv_lru_t * cache, const void * key, size_t key_size)
213 {
214     test_for_missing_cache();
215     test_for_missing_key();
216 
217     // loop until we find the item, or hit the end of a chain
218     lv_lru_item_t * item = NULL, * prev = NULL;
219     uint32_t hash_index = lv_lru_hash(cache, key, key_size);
220     item = cache->items[hash_index];
221 
222     while(item && lv_lru_cmp_keys(item, key, key_size)) {
223         prev = item;
224         item = (lv_lru_item_t *) item->next;
225     }
226 
227     if(item) {
228         lv_lru_remove_item(cache, prev, item, hash_index);
229     }
230 
231     return LV_LRU_OK;
232 }
233 
lv_lru_remove_lru_item(lv_lru_t * cache)234 void lv_lru_remove_lru_item(lv_lru_t * cache)
235 {
236     lv_lru_item_t * min_item = NULL, * min_prev = NULL;
237     lv_lru_item_t * item = NULL, * prev = NULL;
238     uint32_t i = 0, min_index = -1;
239     uint64_t min_access_count = -1;
240 
241     for(; i < cache->hash_table_size; i++) {
242         item = cache->items[i];
243         prev = NULL;
244 
245         while(item) {
246             if(item->access_count < min_access_count || (int64_t) min_access_count == -1) {
247                 min_access_count = item->access_count;
248                 min_item = item;
249                 min_prev = prev;
250                 min_index = i;
251             }
252             prev = item;
253             item = item->next;
254         }
255     }
256 
257     if(min_item) {
258         lv_lru_remove_item(cache, min_prev, min_item, min_index);
259     }
260 }
261 
262 /**********************
263  *   STATIC FUNCTIONS
264  **********************/
265 
lv_lru_hash(lv_lru_t * cache,const void * key,uint32_t key_length)266 static uint32_t lv_lru_hash(lv_lru_t * cache, const void * key, uint32_t key_length)
267 {
268     uint32_t m = 0x5bd1e995;
269     uint32_t r = 24;
270     uint32_t h = cache->seed ^ key_length;
271     char * data = (char *) key;
272 
273     while(key_length >= 4) {
274         uint32_t k = *(uint32_t *) data;
275         k *= m;
276         k ^= k >> r;
277         k *= m;
278         h *= m;
279         h ^= k;
280         data += 4;
281         key_length -= 4;
282     }
283 
284     if(key_length >= 3) {
285         h ^= data[2] << 16;
286     }
287     if(key_length >= 2) {
288         h ^= data[1] << 8;
289     }
290     if(key_length >= 1) {
291         h ^= data[0];
292         h *= m;
293     }
294 
295     h ^= h >> 13;
296     h *= m;
297     h ^= h >> 15;
298     return h % cache->hash_table_size;
299 }
300 
lv_lru_cmp_keys(lv_lru_item_t * item,const void * key,uint32_t key_length)301 static int lv_lru_cmp_keys(lv_lru_item_t * item, const void * key, uint32_t key_length)
302 {
303     if(key_length != item->key_length) {
304         return 1;
305     }
306     else {
307         return memcmp(key, item->key, key_length);
308     }
309 }
310 
lv_lru_remove_item(lv_lru_t * cache,lv_lru_item_t * prev,lv_lru_item_t * item,uint32_t hash_index)311 static void lv_lru_remove_item(lv_lru_t * cache, lv_lru_item_t * prev, lv_lru_item_t * item, uint32_t hash_index)
312 {
313     if(prev) {
314         prev->next = item->next;
315     }
316     else {
317         cache->items[hash_index] = (lv_lru_item_t *) item->next;
318     }
319 
320     // free memory and update the free memory counter
321     cache->free_memory += item->value_length;
322     cache->value_free(item->value);
323     cache->key_free(item->key);
324 
325     // push the item to the free items queue
326     lv_memset_00(item, sizeof(lv_lru_item_t));
327     item->next = cache->free_items;
328     cache->free_items = item;
329 }
330 
lv_lru_pop_or_create_item(lv_lru_t * cache)331 static lv_lru_item_t * lv_lru_pop_or_create_item(lv_lru_t * cache)
332 {
333     lv_lru_item_t * item = NULL;
334 
335     if(cache->free_items) {
336         item = cache->free_items;
337         cache->free_items = item->next;
338         lv_memset_00(item, sizeof(lv_lru_item_t));
339     }
340     else {
341         item = (lv_lru_item_t *) lv_mem_alloc(sizeof(lv_lru_item_t));
342         lv_memset_00(item, sizeof(lv_lru_item_t));
343     }
344 
345     return item;
346 }
347