Project

General

Profile

Revision 88570136

ID8857013663442a00545cfa77de9cc86cb3448fa7
Parent e247ef4d
Child 6fbe093f

Added by Thomas Mullins over 10 years ago

Added LRU eviction to cache. Not tested yet.

View differences:

mainbox/cache.c
1 1
#include "cache.h"
2 2
#include "log.h"
3 3
#include <stdlib.h>
4
#include <time.h>
4 5

  
5 6
struct entry_t {
6 7
  unsigned int key;
......
9 10
  struct entry_t *next;
10 11
};
11 12

  
12
struct entry_t *cache[CACHE_SIZE];
13
static struct entry_t *cache[CACHE_SIZE];
14
static int n_entries;
15

  
16
static void cache_remove_lru() {
17
  struct entry_t *entry, **ptr;
18
  struct entry_t *lru, **lru_ptr;
19
  int i;
20

  
21
  lru = NULL;
22
  for (i = 0; i < CACHE_SIZE; i++) {
23
    ptr = &cache[i];
24
    for (entry = cache[i]; entry; entry = entry->next) {
25
      if (lru == NULL || entry->retrieved < lru->retrieved) {
26
        lru = entry;
27
        lru_ptr = ptr;
28
      }
29
      ptr = &entry->next;
30
    }
31
  }
32

  
33
  if (lru != NULL) {
34
    *lru_ptr = lru->next;
35
    free(lru);
36
    n_entries--;
37
  }
38
}
13 39

  
14 40
void cache_foreach(cache_func f) {
15 41
  struct entry_t *entry;
......
32 58
    }
33 59
    cache[i] = NULL;
34 60
  }
61

  
62
  n_entries = 0;
35 63
}
36 64

  
37 65
struct entry_t *cache_find(unsigned int key) {
38 66
  struct entry_t *entry;
39 67

  
40 68
  for (entry = cache[key % CACHE_SIZE]; entry; entry = entry->next) {
41
    if (entry->key == key)
69
    if (entry->key == key) {
70
      entry->retrieved = time(NULL);
42 71
      return entry;
72
    }
43 73
  }
44 74

  
45 75
  return NULL;
......
51 81

  
52 82
  entry = malloc(sizeof(struct entry_t));
53 83
  if (!entry) {
54
    log_print("ERROR: Out of memory; clearing cache");
55
    cache_clear();
84
    log_print("ERROR: Out of memory");
56 85
    return;
57 86
  }
58 87

  
88
  if (n_entries == CACHE_MAX_ENTRIES) {
89
    cache_remove_lru();
90
  }
91
  n_entries++;
92

  
59 93
  i = key % CACHE_SIZE;
60 94
  entry->key = key;
61 95
  entry->value = value;
mainbox/cache.h
2 2
#define CACHE_H
3 3

  
4 4
#define CACHE_SIZE 256
5
#define CACHE_MAX_ENTRIES 160
5 6

  
6 7
typedef void (*cache_func)(unsigned int key);
7 8

  

Also available in: Unified diff