acid-drop

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