135ec34563a04b6a29c16d53825e42bf56dcf4e0
[fb-resolver] / lru_cache_test.c
1 #include <stdlib.h>
2 #include <unistd.h>
3 #include <stdio.h>
4 #include <assert.h>
5
6 /* wrap the whole module */
7 #include "lru_cache.c"
8
9 static unsigned int g_verbose_ = 0;
10
11 struct test_kv_cache_entry {
12 struct lru_cache_entry lru_;
13
14 char key[128];
15 char value[128];
16 };
17 typedef struct test_kv_cache_entry kve_t;
18
19 static
20 void
21 test_kv_hash_feed(lru_entry_t *entry, char **bufp, size_t *szp)
22 {
23 struct test_kv_cache_entry *e = (struct test_kv_cache_entry *)entry;
24 *bufp = e->key;
25 *szp = sizeof e->key;
26 }
27
28 static
29 int
30 test_kv_cmp(lru_entry_t *a, lru_entry_t *b)
31 {
32 kve_t *kv_a = (kve_t *)a,
33 *kv_b = (kve_t *)b;
34
35 return strcmp(kv_a->key, kv_b->key);
36 }
37
38 static
39 void
40 kv_dump(struct lru_cache *c)
41 {
42 struct test_kv_cache_entry *kve;
43 lru_entry_t *e;
44 size_t i;
45
46 fprintf(stderr, "\nLRU, %zu entries\n", c->num_entries);
47
48 if (g_verbose_ == 0)
49 return;
50
51 fprintf(stderr, "-- hash --\n");
52 for (i = 0; i < c->hash_sz; i++) {
53 int s;
54 for (s = 0, e = c->hash[i].entry; e; e = e->hash_next, s++) {
55 kve = (struct test_kv_cache_entry *)e;
56 if (e != NULL) {
57 if (e->hash_slot != i)
58 fprintf(stderr, "!!! sanity failure, entry has hash slot %zu, but is in slot %zu !!!\n", e->hash_slot, i);
59 fprintf(stderr, "%*s[%zu]: (%p) '%s':'%s'\n", s, "", i, kve, kve->key, kve->value);
60 }
61 }
62 }
63
64 fprintf(stderr, "-- queue --\n");
65 for (e = c->newest; e; e = e->next) {
66 kve = (struct test_kv_cache_entry *)e;
67 fprintf(stderr, "(%p) '%s':'%s'\n", kve, kve->key, kve->value);
68 }
69
70 fprintf(stderr, "\n");
71 }
72
73 void
74 kv_genstats(lru_entry_t *e, size_t i, void *data)
75 {
76 struct test_kv_cache_entry *kve = (struct test_kv_cache_entry *)e;
77 size_t *hash_depth = (size_t *)data;
78 (void)i, (void)kve;
79
80 hash_depth[e->hash_slot]++;
81 }
82 void
83 kv_dumpstats(struct lru_cache *c, size_t *stats, size_t sz)
84 {
85 size_t i;
86
87 for (i = 0; i < sz; i++)
88 fprintf(stderr, "slot %04zu: %zu (expect: %zu)\n", i, stats[i], c->hash[i].tally);
89 }
90
91 int
92 main(int argc, char *argv[])
93 {
94 const size_t hash_sz = 31;
95 const size_t capacity = 256;
96
97 struct lru_cache *cache;
98 struct test_kv_cache_entry *e, *r, m;
99 int i;
100
101 size_t *stats;
102
103 while ( (i = getopt(argc, argv, "vh")) != EOF ) {
104 switch (i) {
105 case 'v':
106 g_verbose_++;
107 break;
108
109 case 'h':
110 default:
111 exit(EXIT_FAILURE);
112 }
113 }
114
115 stats = malloc(hash_sz * sizeof *stats);
116 memset(stats, 0, hash_sz * sizeof *stats);
117
118 cache = lru_cache_new(hash_sz, capacity, test_kv_hash_feed, test_kv_cmp);
119 assert(cache != NULL);
120
121 kv_dump(cache);
122
123 e = malloc(sizeof *e);
124 assert(e != NULL);
125
126 strncpy(e->key, "key", sizeof e->key);
127 strncpy(e->value, "value", sizeof e->value);
128
129 lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
130 assert(r == NULL);
131
132 kv_dump(cache);
133
134 memset(&m, 0, sizeof m);
135 strncpy(m.key, "key", sizeof e->key);
136 e = (struct test_kv_cache_entry *)lru_cache_locate(cache, (lru_entry_t *)&m);
137 assert(e != NULL);
138
139 lru_cache_extract(cache, (lru_entry_t *)e);
140 free(e);
141
142 kv_dump(cache);
143
144 for (i = 0; i < 500; i++) {
145 r = NULL;
146 e = malloc(sizeof *e);
147 assert(e != NULL);
148 memset(e, 0, sizeof *e);
149 snprintf(e->key, sizeof e->key, "test %d key", i);
150 snprintf(e->value, sizeof e->value, "some %d value", i);
151 lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
152 if (r) {
153 if (g_verbose_)
154 fprintf(stderr, "freeing (%p) '%s':'%s'\n", r, r->key, r->value);
155 free(r);
156 }
157 }
158
159 kv_dump(cache);
160
161 for (i = 0; i < 500; i += 3) {
162 memset(&m, 0, sizeof m);
163 snprintf(m.key, sizeof m.key, "test %d key", i);
164 e = (struct test_kv_cache_entry *)lru_cache_locate(cache, (lru_entry_t *)&m);
165 if (e == NULL) {
166 if (g_verbose_)
167 fprintf(stderr, "key %d was not cached\n", i);
168 continue;
169 }
170 lru_cache_extract(cache, (lru_entry_t *)e);
171 if (g_verbose_)
172 fprintf(stderr, "extracted '%s'\n", e->key);
173 free(e);
174 }
175
176 kv_dump(cache);
177
178 for (i = 0; i < 10; i += 2) {
179 e = malloc(sizeof *e);
180 assert(e != NULL);
181 memset(e, 0, sizeof *e);
182 snprintf(e->key, sizeof e->key, "new key %d", i);
183 snprintf(e->value, sizeof e->value, "new value %d", i);
184 lru_cache_insert(cache, (lru_entry_t *)e, (lru_entry_t **)&r);
185 if (r) {
186 if (g_verbose_)
187 fprintf(stderr, "freeing (%p) '%s':'%s'\n", r, r->key, r->value);
188 free(r);
189 }
190 }
191
192 kv_dump(cache);
193
194 lru_cache_foreach(cache, kv_genstats, stats);
195 kv_dumpstats(cache, stats, hash_sz);
196
197 exit(EXIT_SUCCESS);
198 }