/* * Copyright (C) 2008 Timothy D. Morgan * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; version 3 of the License. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * * $Id: $ */ #include "../include/lru_cache.h" #define LRU_CACHE_DEBUG 0 /* XXX: really should replace this with a real universal hash or other * fast HMAC. */ static uint32_t lru_cache_compute_hash(uint32_t num_buckets, uint32_t secret, const void* buf, uint32_t buf_len) { uint32_t i; uint32_t ret_val = 0x243f6a88; unsigned char* s = (unsigned char*)&secret; const unsigned char* b = (unsigned char*)buf; for(i=0; i 1; ret_val--) if((n & (1 << ret_val)) != 0) return ret_val; return 0; } static void lru_cache_print(lru_cache* ht) { uint32_t i; lru_cache_element* cur; printf("from newest to oldest:\n"); for(cur=ht->newest; cur != NULL; cur=cur->older) { /* write(STDOUT_FILENO, cur->index, cur->index_len);*/ printf("%p", (void*)cur); printf("\n"); if(cur->older == ht->newest) { printf("??? Loop in LRU list!!"); break; } } printf("\n"); printf("table:\n"); for(i=0; inum_buckets; i++) { printf("%.8X: ", i); for(cur=ht->table[i]; cur != NULL; cur=cur->next) { /* write(STDOUT_FILENO, cur->index, cur->index_len);*/ printf("%p", (void*)cur); printf("|"); if(cur->next == ht->table[i]) { printf("??? Loop in table chain!!"); break; } } printf("\n"); } } lru_cache* lru_cache_create(uint32_t max_keys, uint32_t secret, bool free_data) { lru_cache* ret_val; if(max_keys < 2) return NULL; ret_val = (lru_cache*)malloc(sizeof(lru_cache)); if(ret_val == NULL) return NULL; ret_val->num_buckets = max_keys/lru_cache_floor_log2(max_keys); if(ret_val->num_buckets < 1) ret_val->num_buckets = 1; ret_val->table = (lru_cache_element**)malloc(sizeof(lru_cache_element*) * ret_val->num_buckets); if(ret_val->table == NULL) { free(ret_val); return NULL; } ret_val->oldest = NULL; ret_val->newest = NULL; ret_val->max_keys = max_keys; ret_val->secret = secret; ret_val->free_data = free_data; ret_val->num_keys = 0; memset(ret_val->table, 0, ret_val->num_buckets*sizeof(lru_cache_element*)); return ret_val; } void lru_cache_destroy(lru_cache* ht) { lru_cache_element* cur; lru_cache_element* last = NULL; for(cur=ht->oldest; cur != NULL; last=cur,cur=cur->newer) { if(last != NULL) { if(ht->free_data) free(last->data); free(last->index); free(last); } } free(ht->table); ht->secret = 0; free(ht); } bool lru_cache_update(lru_cache* ht, const void* index, uint32_t index_len, void* data) { uint32_t hash, lru_hash; lru_cache_element* cur; lru_cache_element* last = NULL; lru_cache_element* e = NULL; void* tmp_index; hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len); for(cur = ht->table[hash]; cur != NULL && e == NULL; cur=cur->next) { if((index_len == cur->index_len) && memcmp(cur->index, index, index_len) == 0) { e = cur; } } if(e != NULL) { /* We found the index, so we're going to overwrite the data. * We also need to reposition the element to the newest position, * so remove it from the list for now. */ if(ht->free_data) free(e->data); if(e->newer == NULL) ht->newest = e->older; else e->newer->older = e->older; if(e->older == NULL) ht->oldest = e->newer; else e->older->newer = e->newer; } else { /* We didn't find an identical index. */ if(ht->num_keys >= ht->max_keys) { /* Eliminate the least recently used item, but reuse the element * structure to minimize reallocation. */ e = ht->oldest; if(ht->newest == ht->oldest) { ht->newest = NULL; ht->oldest = NULL; } else { ht->oldest = e->newer; e->newer->older = NULL; } e->newer = NULL; e->older = NULL; last = NULL; lru_hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, e->index, e->index_len); for(cur = ht->table[lru_hash]; cur != e && cur != NULL; last=cur, cur=cur->next) { continue; } if(last == NULL) ht->table[lru_hash] = e->next; else last->next = e->next; e->next = NULL; if(ht->free_data) free(e->data); tmp_index = realloc(e->index, index_len); if(tmp_index == NULL) { free(e->index); free(e); return false; } } else { /* Brand new element because we have room to spare. */ e = (lru_cache_element*)malloc(sizeof(lru_cache_element)); if(e == NULL) return false; e->index = malloc(index_len); if(e->index == NULL) { free(e); return false; } /* New entry, increment counters. */ ht->num_keys++; } memcpy(e->index, index, index_len); e->index_len = index_len; /* Insert at beginning of chain, in a vaguely LRU style */ e->next = ht->table[hash]; ht->table[hash] = e; } e->data = data; /* Finally, let's insert the element to the newest position in the LRU list.*/ if(ht->newest != NULL) ht->newest->newer = e; e->newer = NULL; e->older = ht->newest; ht->newest = e; if(ht->oldest == NULL) ht->oldest = e; return true; } void* lru_cache_find(lru_cache* ht, const void* index, uint32_t index_len) { uint32_t hash; lru_cache_element* cur; hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len); for(cur = ht->table[hash]; (cur != NULL); cur = cur->next) { if((index_len == cur->index_len) && memcmp(cur->index, index, index_len) == 0) { break; } } if(cur != NULL && cur->newer != NULL) { /* Need to move this element up to the newest slot. */ cur->newer->older = cur->older; if(cur->older == NULL) ht->oldest = cur->newer; else cur->older->newer = cur->newer; cur->newer = NULL; cur->older = ht->newest; ht->newest->newer = cur; ht->newest = cur; } if(cur != NULL) return cur->data; else return NULL; } bool lru_cache_remove(lru_cache* ht, const void* index, uint32_t index_len) { uint32_t hash; lru_cache_element* cur; lru_cache_element* last = NULL; hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len); for(cur=ht->table[hash]; (cur != NULL); last=cur, cur=cur->next) { if((index_len == cur->index_len) && memcmp(cur->index, index, index_len) == 0) { break; } } if(cur == NULL) return false; if(ht->free_data) free(cur->data); /* Detach from list */ if(cur->newer == NULL) ht->newest = cur->older; else cur->newer->older = cur->older; if(cur->older == NULL) ht->oldest = cur->newer; else cur->older->newer = cur->newer; /* Detach from hash table */ if(last == NULL) ht->table[hash] = cur->next; else last->next = cur->next; free(cur->index); free(cur); /* Removing entry, decrement counters. */ ht->num_keys--; return true; }