source: trunk/lib/lru_cache.c @ 133

Last change on this file since 133 was 122, checked in by tim, 16 years ago

fixed an incorrect malloc in range_list.c
minor documentation updates

  • Property svn:keywords set to Id
File size: 7.9 KB
Line 
1/*
2 * Copyright (C) 2008 Timothy D. Morgan
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 3 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 
16 *
17 * $Id: lru_cache.c 122 2008-08-09 20:24:01Z tim $
18 */
19
20#include "../include/lru_cache.h"
21
22
23#define LRU_CACHE_DEBUG 0
24
25/* XXX: really should replace this with a real universal hash or other
26 *      fast HMAC.
27 */ 
28static uint32_t lru_cache_compute_hash(uint32_t num_buckets,
29                                       uint32_t secret,
30                                       const void* buf,
31                                       uint32_t buf_len)
32{
33  uint32_t i;
34  uint32_t ret_val = 0x243f6a88;
35  unsigned char* s = (unsigned char*)&secret;
36  const unsigned char* b = (unsigned char*)buf;
37
38  for(i=0; i<buf_len; i++)
39    ret_val = (ret_val+(i^s[i%4])*b[i]) % num_buckets;
40 
41  return ret_val;
42}
43
44/* Returns approximately floor(log_2(n)) (log base 2 of n, floored)
45 * If n == 0, returns 0
46 */
47static uint32_t lru_cache_floor_log2(uint32_t n)
48{
49  uint32_t ret_val;
50 
51  for(ret_val=31; ret_val > 1; ret_val--)
52    if((n & (1 << ret_val)) != 0)
53      return ret_val;
54
55  return 0;
56}
57
58#if 0
59static void lru_cache_print(lru_cache* ht)
60{
61  uint32_t i;
62  lru_cache_element* cur;
63
64  printf("from newest to oldest:\n");
65  for(cur=ht->newest; cur != NULL; cur=cur->older)
66  {
67    /*    write(STDOUT_FILENO, cur->index, cur->index_len);*/
68    printf("%p", (void*)cur);
69    printf("\n");
70    if(cur->older == ht->newest)
71    {
72      printf("??? Loop in LRU list!!");
73      break;
74    }
75  }
76  printf("\n");
77
78  printf("table:\n");
79  for(i=0; i<ht->num_buckets; i++)
80  {
81    printf("%.8X: ", i);
82    for(cur=ht->table[i]; cur != NULL; cur=cur->next)
83    {
84      /*      write(STDOUT_FILENO, cur->index, cur->index_len);*/
85      printf("%p", (void*)cur);
86      printf("|");
87
88      if(cur->next == ht->table[i])
89      {
90        printf("??? Loop in table chain!!");
91        break;
92      }
93    }
94    printf("\n");
95  }
96}
97#endif
98
99lru_cache* lru_cache_create(uint32_t max_keys, uint32_t secret, bool free_data)
100{
101  lru_cache* ret_val;
102
103  ret_val = (lru_cache*)malloc(sizeof(lru_cache));
104  if(ret_val == NULL)
105    return NULL;
106
107  if(max_keys == 0)
108    ret_val->num_buckets = 2048;
109  else
110  {
111    ret_val->num_buckets = max_keys/lru_cache_floor_log2(max_keys);
112    if(ret_val->num_buckets < 1)
113      ret_val->num_buckets = 1;
114  }
115
116  ret_val->table
117    = (lru_cache_element**)malloc(sizeof(lru_cache_element*) 
118                                  * ret_val->num_buckets);
119  if(ret_val->table == NULL)
120  {
121    free(ret_val);
122    return NULL;
123  }
124 
125  ret_val->oldest = NULL;
126  ret_val->newest = NULL;
127  ret_val->max_keys = max_keys;
128  ret_val->secret = secret;
129  ret_val->free_data = free_data;
130  ret_val->num_keys = 0;
131  memset(ret_val->table, 0, ret_val->num_buckets*sizeof(lru_cache_element*));
132
133  return ret_val;
134}
135
136
137void lru_cache_destroy(lru_cache* ht)
138{
139  lru_cache_element* cur;
140  lru_cache_element* last = NULL;
141 
142  for(cur=ht->oldest; cur != NULL; last=cur,cur=cur->newer)
143  {
144    if(last != NULL)
145    {
146      if(ht->free_data)
147        free(last->data);
148      free(last->index);
149      free(last);
150    }
151  }
152  free(ht->table);
153  ht->secret = 0;
154  free(ht);
155}
156
157
158
159bool lru_cache_update(lru_cache* ht, const void* index, 
160                      uint32_t index_len, void* data)
161{
162  uint32_t hash, lru_hash;
163  lru_cache_element* cur;
164  lru_cache_element* last = NULL;
165  lru_cache_element* e = NULL;
166  void* tmp_index;
167
168  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len);
169  for(cur = ht->table[hash]; cur != NULL && e == NULL; cur=cur->next)
170  {
171    if((index_len == cur->index_len) 
172       && memcmp(cur->index, index, index_len) == 0)
173    { e = cur; }
174  }
175 
176  if(e != NULL)
177  { /* We found the index, so we're going to overwrite the data.
178     * We also need to reposition the element to the newest position,
179     * so remove it from the list for now.
180     */
181    if(ht->free_data)
182      free(e->data);
183
184    if(e->newer == NULL)
185      ht->newest = e->older;
186    else
187      e->newer->older = e->older;
188
189    if(e->older == NULL)
190      ht->oldest = e->newer;
191    else
192      e->older->newer = e->newer;
193  }
194  else
195  { /* We didn't find an identical index. */
196   
197    if((ht->max_keys != 0) && (ht->num_keys >= ht->max_keys))
198    { /* Eliminate the least recently used item, but reuse the element
199       * structure to minimize reallocation.
200       */
201      e = ht->oldest;
202      if(ht->newest == ht->oldest)
203      {
204        ht->newest = NULL;
205        ht->oldest = NULL;
206      }
207      else
208      {
209        ht->oldest = e->newer;
210        e->newer->older = NULL;
211      }
212      e->newer = NULL;
213      e->older = NULL;
214
215      last = NULL;
216      lru_hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, 
217                                        e->index, e->index_len);
218      for(cur = ht->table[lru_hash]; cur != e && cur != NULL; 
219          last=cur, cur=cur->next)
220      { continue; }
221
222      if(last == NULL)
223        ht->table[lru_hash] = e->next;
224      else
225        last->next = e->next;
226      e->next = NULL;
227
228      if(ht->free_data)
229        free(e->data);
230
231      tmp_index = realloc(e->index, index_len);
232      if(tmp_index == NULL)
233      {
234        free(e->index);
235        free(e);
236        return false;
237      }
238    }
239    else
240    { /* Brand new element because we have room to spare. */
241
242      e = (lru_cache_element*)malloc(sizeof(lru_cache_element));
243      if(e == NULL)
244        return false;
245     
246      e->index = malloc(index_len);
247      if(e->index == NULL)
248      {
249        free(e);
250        return false;
251      }
252     
253      /* New entry, increment counters. */
254      ht->num_keys++;
255    }
256    memcpy(e->index, index, index_len);
257    e->index_len = index_len;
258
259    /* Insert at beginning of chain, in a vaguely LRU style */
260    e->next = ht->table[hash];
261    ht->table[hash] = e;
262  }
263  e->data = data;
264
265  /* Finally, let's insert the element to the newest position in the LRU list.*/
266  if(ht->newest != NULL)
267    ht->newest->newer = e;
268  e->newer = NULL;
269  e->older = ht->newest;
270  ht->newest = e;
271  if(ht->oldest == NULL)
272    ht->oldest = e;
273
274  return true;
275}
276
277
278void* lru_cache_find(lru_cache* ht, const void* index,
279                     uint32_t index_len)
280{
281  uint32_t hash;
282  lru_cache_element* cur;
283
284  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret, index, index_len);
285  for(cur = ht->table[hash]; (cur != NULL); cur = cur->next)
286  {
287    if((index_len == cur->index_len)
288       && memcmp(cur->index, index, index_len) == 0)
289    { break; }
290  }
291 
292  if(cur != NULL && cur->newer != NULL)
293  { /* Need to move this element up to the newest slot. */
294
295    cur->newer->older = cur->older;
296
297    if(cur->older == NULL)
298      ht->oldest = cur->newer;
299    else
300      cur->older->newer = cur->newer;
301
302    cur->newer = NULL;
303    cur->older = ht->newest;
304    ht->newest->newer = cur;
305    ht->newest = cur;
306  }
307
308  if(cur != NULL)
309    return cur->data;
310  else
311    return NULL;
312}
313
314
315
316bool lru_cache_remove(lru_cache* ht, const void* index, 
317                      uint32_t index_len)
318{
319  uint32_t hash;
320  lru_cache_element* cur;
321  lru_cache_element* last = NULL;
322
323  hash = lru_cache_compute_hash(ht->num_buckets, ht->secret,
324                                index, index_len);
325  for(cur=ht->table[hash]; (cur != NULL);
326      last=cur, cur=cur->next)
327  {
328    if((index_len == cur->index_len) 
329       && memcmp(cur->index, index, index_len) == 0)
330    { break; }
331  }
332
333  if(cur == NULL)
334    return false;
335
336  if(ht->free_data)
337    free(cur->data);
338
339  /* Detach from list */
340  if(cur->newer == NULL)
341    ht->newest = cur->older;
342  else
343    cur->newer->older = cur->older;
344 
345  if(cur->older == NULL)
346    ht->oldest = cur->newer;
347  else
348    cur->older->newer = cur->newer;
349
350  /* Detach from hash table */
351  if(last == NULL)
352    ht->table[hash] = cur->next;
353  else
354    last->next = cur->next;
355
356  free(cur->index);
357  free(cur);
358 
359  /* Removing entry, decrement counters. */
360  ht->num_keys--;
361 
362  return true;
363}
Note: See TracBrowser for help on using the repository browser.