1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
// 460. LFU Cache
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_CACHE_ITEM 3192
#define MAX_FREQ 128
// https://en.wikipedia.org/wiki/Least_frequently_used
// http://dhruvbird.com/lfu.pdf
typedef struct LFUCache LFUCache;
typedef struct LFUCache {
int freq;
int val;
bool valid;
LFUCache *prev;
LFUCache *next;
} LFUCache;
struct Freq {
LFUCache *head;
LFUCache *tail;
};
struct CacheData {
int capacity;
int size;
int freqIdx;
LFUCache *cache;
struct Freq *fm;
};
inline void *cacheAlloc(int capacity);
inline void cacheDealloc(void *cache);
inline void refreshCache(LFUCache *item, struct CacheData *cdata,
bool newEntry);
LFUCache *lFUCacheCreate(int capacity) { return cacheAlloc(capacity); }
int lFUCacheGet(LFUCache *obj, int key) {
struct CacheData *cdata = (void *)obj;
LFUCache *item = &cdata->cache[key];
if (cdata->capacity <= 0 || !item->valid)
return -1;
refreshCache(item, cdata, false);
return item->val;
}
void lFUCachePut(LFUCache *obj, int key, int value) {
struct CacheData *cdata = (void *)obj;
LFUCache *item = &cdata->cache[key];
if (cdata->capacity <= 0 || key >= MAX_CACHE_ITEM)
return;
refreshCache(item, cdata, !item->valid);
item->val = value;
}
void lFUCacheFree(LFUCache *obj) { cacheDealloc(obj); }
inline void *cacheAlloc(int capacity) {
if (capacity > MAX_CACHE_ITEM)
return NULL;
struct CacheData *cdata = calloc(1, sizeof(*cdata));
cdata->capacity = capacity;
cdata->cache = calloc(1, sizeof(LFUCache[MAX_CACHE_ITEM]));
cdata->fm = calloc(1, sizeof(struct Freq[MAX_FREQ]));
return cdata;
}
inline void cacheDealloc(void *cache) {
struct CacheData *cdata = cache;
free(cdata->cache);
free(cdata->fm);
free(cdata);
}
inline void fixNode(LFUCache *item) {
LFUCache **prev = &item->prev, **next = &item->next;
*prev ? (*prev)->next = *next : 0;
*next ? (*next)->prev = *prev : 0;
}
inline void fixHeadTailFreq(LFUCache *item, struct CacheData *cdata) {
struct Freq *fm = &cdata->fm[item->freq];
LFUCache **head = &fm->head, **tail = &fm->tail;
item == *head ? *head = item->next : 0;
item == *tail ? *tail = item->prev : 0;
item->freq == cdata->freqIdx && !fm->head ? cdata->freqIdx++ : 0;
}
inline void fixHeadTail(LFUCache *item, struct CacheData *cdata) {
struct Freq *fm = &cdata->fm[++item->freq];
item->prev = NULL;
item->next = fm->head;
fm->head = fm->head ? fm->head->prev = item : (fm->tail = item);
}
inline void evictFreqNode(struct CacheData *cdata) {
struct Freq *fm = &cdata->fm[cdata->freqIdx];
LFUCache *lu = fm->tail;
lu->prev ? lu->prev->next = NULL : 0;
lu->freq = 0;
lu->valid = false;
!(fm->tail = lu->prev) ? fm->head = NULL : 0;
lu->prev = lu->next = NULL;
}
inline void refreshCache(LFUCache *item, struct CacheData *cdata,
bool newEntry) {
if (newEntry)
if (cdata->size == cdata->capacity)
evictFreqNode(cdata);
else
cdata->size++;
else {
fixNode(item);
fixHeadTailFreq(item, cdata);
}
fixHeadTail(item, cdata);
if (!cdata->freqIdx || cdata->freqIdx > item->freq)
cdata->freqIdx = item->freq;
item->valid = true;
}
|