1 /*-
2 * Copyright (c) 2005 Michael Bushkov <[email protected]>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 */
27
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
30
31 #include <sys/time.h>
32
33 #include <assert.h>
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "cacheplcs.h"
38 #include "debug.h"
39
40 static void cache_fifo_policy_update_item(struct cache_policy_ *,
41 struct cache_policy_item_ *);
42 static void cache_lfu_policy_add_item(struct cache_policy_ *,
43 struct cache_policy_item_ *);
44 static struct cache_policy_item_ * cache_lfu_policy_create_item(void);
45 static void cache_lfu_policy_destroy_item(struct cache_policy_item_ *);
46 static struct cache_policy_item_ *cache_lfu_policy_get_first_item(
47 struct cache_policy_ *);
48 static struct cache_policy_item_ *cache_lfu_policy_get_last_item(
49 struct cache_policy_ *);
50 static struct cache_policy_item_ *cache_lfu_policy_get_next_item(
51 struct cache_policy_ *, struct cache_policy_item_ *);
52 static struct cache_policy_item_ *cache_lfu_policy_get_prev_item(
53 struct cache_policy_ *, struct cache_policy_item_ *);
54 static void cache_lfu_policy_remove_item(struct cache_policy_ *,
55 struct cache_policy_item_ *);
56 static void cache_lfu_policy_update_item(struct cache_policy_ *,
57 struct cache_policy_item_ *);
58 static void cache_lru_policy_update_item(struct cache_policy_ *,
59 struct cache_policy_item_ *);
60 static void cache_queue_policy_add_item(struct cache_policy_ *,
61 struct cache_policy_item_ *);
62 static struct cache_policy_item_ * cache_queue_policy_create_item(void);
63 static void cache_queue_policy_destroy_item(struct cache_policy_item_ *);
64 static struct cache_policy_item_ *cache_queue_policy_get_first_item(
65 struct cache_policy_ *);
66 static struct cache_policy_item_ *cache_queue_policy_get_last_item(
67 struct cache_policy_ *);
68 static struct cache_policy_item_ *cache_queue_policy_get_next_item(
69 struct cache_policy_ *, struct cache_policy_item_ *);
70 static struct cache_policy_item_ *cache_queue_policy_get_prev_item(
71 struct cache_policy_ *, struct cache_policy_item_ *);
72 static void cache_queue_policy_remove_item(struct cache_policy_ *,
73 struct cache_policy_item_ *);
74 static void destroy_cache_queue_policy(struct cache_queue_policy_ *);
75 static struct cache_queue_policy_ *init_cache_queue_policy(void);
76
77 /*
78 * All cache_queue_policy_XXX functions below will be used to fill
79 * the cache_queue_policy structure. They implement the most functionality of
80 * LRU and FIFO policies. LRU and FIFO policies are actually the
81 * cache_queue_policy_ with cache_update_item function changed.
82 */
83 static struct cache_policy_item_ *
cache_queue_policy_create_item(void)84 cache_queue_policy_create_item(void)
85 {
86 struct cache_queue_policy_item_ *retval;
87
88 TRACE_IN(cache_queue_policy_create_item);
89 retval = calloc(1,
90 sizeof(*retval));
91 assert(retval != NULL);
92
93 TRACE_OUT(cache_queue_policy_create_item);
94 return ((struct cache_policy_item_ *)retval);
95 }
96
97 static void
cache_queue_policy_destroy_item(struct cache_policy_item_ * item)98 cache_queue_policy_destroy_item(struct cache_policy_item_ *item)
99 {
100
101 TRACE_IN(cache_queue_policy_destroy_item);
102 assert(item != NULL);
103 free(item);
104 TRACE_OUT(cache_queue_policy_destroy_item);
105 }
106
107 static void
cache_queue_policy_add_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)108 cache_queue_policy_add_item(struct cache_policy_ *policy,
109 struct cache_policy_item_ *item)
110 {
111 struct cache_queue_policy_ *queue_policy;
112 struct cache_queue_policy_item_ *queue_item;
113
114 TRACE_IN(cache_queue_policy_add_item);
115 queue_policy = (struct cache_queue_policy_ *)policy;
116 queue_item = (struct cache_queue_policy_item_ *)item;
117 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
118 TRACE_OUT(cache_queue_policy_add_item);
119 }
120
121 static void
cache_queue_policy_remove_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)122 cache_queue_policy_remove_item(struct cache_policy_ *policy,
123 struct cache_policy_item_ *item)
124 {
125 struct cache_queue_policy_ *queue_policy;
126 struct cache_queue_policy_item_ *queue_item;
127
128 TRACE_IN(cache_queue_policy_remove_item);
129 queue_policy = (struct cache_queue_policy_ *)policy;
130 queue_item = (struct cache_queue_policy_item_ *)item;
131 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
132 TRACE_OUT(cache_queue_policy_remove_item);
133 }
134
135 static struct cache_policy_item_ *
cache_queue_policy_get_first_item(struct cache_policy_ * policy)136 cache_queue_policy_get_first_item(struct cache_policy_ *policy)
137 {
138 struct cache_queue_policy_ *queue_policy;
139
140 TRACE_IN(cache_queue_policy_get_first_item);
141 queue_policy = (struct cache_queue_policy_ *)policy;
142 TRACE_OUT(cache_queue_policy_get_first_item);
143 return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head));
144 }
145
146 static struct cache_policy_item_ *
cache_queue_policy_get_last_item(struct cache_policy_ * policy)147 cache_queue_policy_get_last_item(struct cache_policy_ *policy)
148 {
149 struct cache_queue_policy_ *queue_policy;
150
151 TRACE_IN(cache_queue_policy_get_last_item);
152 queue_policy = (struct cache_queue_policy_ *)policy;
153 TRACE_OUT(cache_queue_policy_get_last_item);
154 return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head,
155 cache_queue_policy_head_));
156 }
157
158 static struct cache_policy_item_ *
cache_queue_policy_get_next_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)159 cache_queue_policy_get_next_item(struct cache_policy_ *policy,
160 struct cache_policy_item_ *item)
161 {
162 struct cache_queue_policy_ *queue_policy;
163 struct cache_queue_policy_item_ *queue_item;
164
165 TRACE_IN(cache_queue_policy_get_next_item);
166 queue_policy = (struct cache_queue_policy_ *)policy;
167 queue_item = (struct cache_queue_policy_item_ *)item;
168
169 TRACE_OUT(cache_queue_policy_get_next_item);
170 return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries));
171 }
172
173 static struct cache_policy_item_ *
cache_queue_policy_get_prev_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)174 cache_queue_policy_get_prev_item(struct cache_policy_ *policy,
175 struct cache_policy_item_ *item)
176 {
177 struct cache_queue_policy_ *queue_policy;
178 struct cache_queue_policy_item_ *queue_item;
179
180 TRACE_IN(cache_queue_policy_get_prev_item);
181 queue_policy = (struct cache_queue_policy_ *)policy;
182 queue_item = (struct cache_queue_policy_item_ *)item;
183
184 TRACE_OUT(cache_queue_policy_get_prev_item);
185 return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item,
186 cache_queue_policy_head_, entries));
187 }
188
189 /*
190 * Initializes cache_queue_policy_ by filling the structure with the functions
191 * pointers, defined above
192 */
193 static struct cache_queue_policy_ *
init_cache_queue_policy(void)194 init_cache_queue_policy(void)
195 {
196 struct cache_queue_policy_ *retval;
197
198 TRACE_IN(init_cache_queue_policy);
199 retval = calloc(1,
200 sizeof(*retval));
201 assert(retval != NULL);
202
203 retval->parent_data.create_item_func = cache_queue_policy_create_item;
204 retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item;
205
206 retval->parent_data.add_item_func = cache_queue_policy_add_item;
207 retval->parent_data.remove_item_func = cache_queue_policy_remove_item;
208
209 retval->parent_data.get_first_item_func =
210 cache_queue_policy_get_first_item;
211 retval->parent_data.get_last_item_func =
212 cache_queue_policy_get_last_item;
213 retval->parent_data.get_next_item_func =
214 cache_queue_policy_get_next_item;
215 retval->parent_data.get_prev_item_func =
216 cache_queue_policy_get_prev_item;
217
218 TAILQ_INIT(&retval->head);
219 TRACE_OUT(init_cache_queue_policy);
220 return (retval);
221 }
222
223 static void
destroy_cache_queue_policy(struct cache_queue_policy_ * queue_policy)224 destroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy)
225 {
226 struct cache_queue_policy_item_ *queue_item;
227
228 TRACE_IN(destroy_cache_queue_policy);
229 while (!TAILQ_EMPTY(&queue_policy->head)) {
230 queue_item = TAILQ_FIRST(&queue_policy->head);
231 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
232 cache_queue_policy_destroy_item(
233 (struct cache_policy_item_ *)queue_item);
234 }
235 free(queue_policy);
236 TRACE_OUT(destroy_cache_queue_policy);
237 }
238
239 /*
240 * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything,
241 * when the cache element is updated. So it always stays in its initial
242 * position in the queue - that is exactly the FIFO functionality.
243 */
244 static void
cache_fifo_policy_update_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)245 cache_fifo_policy_update_item(struct cache_policy_ *policy,
246 struct cache_policy_item_ *item)
247 {
248
249 TRACE_IN(cache_fifo_policy_update_item);
250 /* policy and item arguments are ignored */
251 TRACE_OUT(cache_fifo_policy_update_item);
252 }
253
254 struct cache_policy_ *
init_cache_fifo_policy(void)255 init_cache_fifo_policy(void)
256 {
257 struct cache_queue_policy_ *retval;
258
259 TRACE_IN(init_cache_fifo_policy);
260 retval = init_cache_queue_policy();
261 retval->parent_data.update_item_func = cache_fifo_policy_update_item;
262
263 TRACE_OUT(init_cache_fifo_policy);
264 return ((struct cache_policy_ *)retval);
265 }
266
267 void
destroy_cache_fifo_policy(struct cache_policy_ * policy)268 destroy_cache_fifo_policy(struct cache_policy_ *policy)
269 {
270 struct cache_queue_policy_ *queue_policy;
271
272 TRACE_IN(destroy_cache_fifo_policy);
273 queue_policy = (struct cache_queue_policy_ *)policy;
274 destroy_cache_queue_policy(queue_policy);
275 TRACE_OUT(destroy_cache_fifo_policy);
276 }
277
278 /*
279 * Makes cache_queue_policy_ behave like LRU policy. On each update, cache
280 * element is moved to the end of the queue - so it would be deleted in last
281 * turn. That is exactly the LRU policy functionality.
282 */
283 static void
cache_lru_policy_update_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)284 cache_lru_policy_update_item(struct cache_policy_ *policy,
285 struct cache_policy_item_ *item)
286 {
287 struct cache_queue_policy_ *queue_policy;
288 struct cache_queue_policy_item_ *queue_item;
289
290 TRACE_IN(cache_lru_policy_update_item);
291 queue_policy = (struct cache_queue_policy_ *)policy;
292 queue_item = (struct cache_queue_policy_item_ *)item;
293
294 TAILQ_REMOVE(&queue_policy->head, queue_item, entries);
295 TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries);
296 TRACE_OUT(cache_lru_policy_update_item);
297 }
298
299 struct cache_policy_ *
init_cache_lru_policy(void)300 init_cache_lru_policy(void)
301 {
302 struct cache_queue_policy_ *retval;
303
304 TRACE_IN(init_cache_lru_policy);
305 retval = init_cache_queue_policy();
306 retval->parent_data.update_item_func = cache_lru_policy_update_item;
307
308 TRACE_OUT(init_cache_lru_policy);
309 return ((struct cache_policy_ *)retval);
310 }
311
312 void
destroy_cache_lru_policy(struct cache_policy_ * policy)313 destroy_cache_lru_policy(struct cache_policy_ *policy)
314 {
315 struct cache_queue_policy_ *queue_policy;
316
317 TRACE_IN(destroy_cache_lru_policy);
318 queue_policy = (struct cache_queue_policy_ *)policy;
319 destroy_cache_queue_policy(queue_policy);
320 TRACE_OUT(destroy_cache_lru_policy);
321 }
322
323 /*
324 * LFU (least frequently used) policy implementation differs much from the
325 * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_
326 * functions are implemented specifically for this policy. The idea of this
327 * policy is to represent frequency (real number) as the integer number and
328 * use it as the index in the array. Each array's element is
329 * the list of elements. For example, if we have the 100-elements
330 * array for this policy, the elements with frequency 0.1 (calls per-second)
331 * would be in 10th element of the array.
332 */
333 static struct cache_policy_item_ *
cache_lfu_policy_create_item(void)334 cache_lfu_policy_create_item(void)
335 {
336 struct cache_lfu_policy_item_ *retval;
337
338 TRACE_IN(cache_lfu_policy_create_item);
339 retval = calloc(1,
340 sizeof(*retval));
341 assert(retval != NULL);
342
343 TRACE_OUT(cache_lfu_policy_create_item);
344 return ((struct cache_policy_item_ *)retval);
345 }
346
347 static void
cache_lfu_policy_destroy_item(struct cache_policy_item_ * item)348 cache_lfu_policy_destroy_item(struct cache_policy_item_ *item)
349 {
350
351 TRACE_IN(cache_lfu_policy_destroy_item);
352 assert(item != NULL);
353 free(item);
354 TRACE_OUT(cache_lfu_policy_destroy_item);
355 }
356
357 /*
358 * When placed in the LFU policy queue for the first time, the maximum
359 * frequency is assigned to the element
360 */
361 static void
cache_lfu_policy_add_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)362 cache_lfu_policy_add_item(struct cache_policy_ *policy,
363 struct cache_policy_item_ *item)
364 {
365 struct cache_lfu_policy_ *lfu_policy;
366 struct cache_lfu_policy_item_ *lfu_item;
367
368 TRACE_IN(cache_lfu_policy_add_item);
369 lfu_policy = (struct cache_lfu_policy_ *)policy;
370 lfu_item = (struct cache_lfu_policy_item_ *)item;
371
372 lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1;
373 TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]),
374 lfu_item, entries);
375 TRACE_OUT(cache_lfu_policy_add_item);
376 }
377
378 /*
379 * On each update the frequency of the element is recalculated and, if it
380 * changed, the element would be moved to the another place in the array.
381 */
382 static void
cache_lfu_policy_update_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)383 cache_lfu_policy_update_item(struct cache_policy_ *policy,
384 struct cache_policy_item_ *item)
385 {
386 struct cache_lfu_policy_ *lfu_policy;
387 struct cache_lfu_policy_item_ *lfu_item;
388 int index;
389
390 TRACE_IN(cache_lfu_policy_update_item);
391 lfu_policy = (struct cache_lfu_policy_ *)policy;
392 lfu_item = (struct cache_lfu_policy_item_ *)item;
393
394 /*
395 * We calculate the square of the request_count to avoid grouping of
396 * all elements at the start of the array (for example, if array size is
397 * 100 and most of its elements has frequency below the 0.01, they
398 * all would be grouped in the first array's position). Other
399 * techniques should be used here later to ensure, that elements are
400 * equally distributed in the array and not grouped in its beginning.
401 */
402 if (lfu_item->parent_data.last_request_time.tv_sec !=
403 lfu_item->parent_data.creation_time.tv_sec) {
404 index = ((double)lfu_item->parent_data.request_count *
405 (double)lfu_item->parent_data.request_count /
406 (lfu_item->parent_data.last_request_time.tv_sec -
407 lfu_item->parent_data.creation_time.tv_sec + 1)) *
408 CACHELIB_MAX_FREQUENCY;
409 if (index >= CACHELIB_MAX_FREQUENCY)
410 index = CACHELIB_MAX_FREQUENCY - 1;
411 } else
412 index = CACHELIB_MAX_FREQUENCY - 1;
413
414 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
415 entries);
416 lfu_item->frequency = index;
417 TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries);
418
419 TRACE_OUT(cache_lfu_policy_update_item);
420 }
421
422 static void
cache_lfu_policy_remove_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)423 cache_lfu_policy_remove_item(struct cache_policy_ *policy,
424 struct cache_policy_item_ *item)
425 {
426 struct cache_lfu_policy_ *lfu_policy;
427 struct cache_lfu_policy_item_ *lfu_item;
428
429 TRACE_IN(cache_lfu_policy_remove_item);
430 lfu_policy = (struct cache_lfu_policy_ *)policy;
431 lfu_item = (struct cache_lfu_policy_item_ *)item;
432
433 TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item,
434 entries);
435 TRACE_OUT(cache_lfu_policy_remove_item);
436 }
437
438 static struct cache_policy_item_ *
cache_lfu_policy_get_first_item(struct cache_policy_ * policy)439 cache_lfu_policy_get_first_item(struct cache_policy_ *policy)
440 {
441 struct cache_lfu_policy_ *lfu_policy;
442 struct cache_lfu_policy_item_ *lfu_item;
443 int i;
444
445 TRACE_IN(cache_lfu_policy_get_first_item);
446 lfu_item = NULL;
447 lfu_policy = (struct cache_lfu_policy_ *)policy;
448 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
449 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
450 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
451 break;
452 }
453
454 TRACE_OUT(cache_lfu_policy_get_first_item);
455 return ((struct cache_policy_item_ *)lfu_item);
456 }
457
458 static struct cache_policy_item_ *
cache_lfu_policy_get_last_item(struct cache_policy_ * policy)459 cache_lfu_policy_get_last_item(struct cache_policy_ *policy)
460 {
461 struct cache_lfu_policy_ *lfu_policy;
462 struct cache_lfu_policy_item_ *lfu_item;
463 int i;
464
465 TRACE_IN(cache_lfu_policy_get_last_item);
466 lfu_item = NULL;
467 lfu_policy = (struct cache_lfu_policy_ *)policy;
468 for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i)
469 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
470 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
471 cache_lfu_policy_group_);
472 break;
473 }
474
475 TRACE_OUT(cache_lfu_policy_get_last_item);
476 return ((struct cache_policy_item_ *)lfu_item);
477 }
478
479 static struct cache_policy_item_ *
cache_lfu_policy_get_next_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)480 cache_lfu_policy_get_next_item(struct cache_policy_ *policy,
481 struct cache_policy_item_ *item)
482 {
483 struct cache_lfu_policy_ *lfu_policy;
484 struct cache_lfu_policy_item_ *lfu_item;
485 int i;
486
487 TRACE_IN(cache_lfu_policy_get_next_item);
488 lfu_policy = (struct cache_lfu_policy_ *)policy;
489 lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries);
490 if (lfu_item == NULL)
491 {
492 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1;
493 i < CACHELIB_MAX_FREQUENCY; ++i) {
494 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
495 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
496 break;
497 }
498 }
499 }
500
501 TRACE_OUT(cache_lfu_policy_get_next_item);
502 return ((struct cache_policy_item_ *)lfu_item);
503 }
504
505 static struct cache_policy_item_ *
cache_lfu_policy_get_prev_item(struct cache_policy_ * policy,struct cache_policy_item_ * item)506 cache_lfu_policy_get_prev_item(struct cache_policy_ *policy,
507 struct cache_policy_item_ *item)
508 {
509 struct cache_lfu_policy_ *lfu_policy;
510 struct cache_lfu_policy_item_ *lfu_item;
511 int i;
512
513 TRACE_IN(cache_lfu_policy_get_prev_item);
514 lfu_policy = (struct cache_lfu_policy_ *)policy;
515 lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item,
516 cache_lfu_policy_group_, entries);
517 if (lfu_item == NULL)
518 {
519 for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1;
520 i >= 0; --i)
521 if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
522 lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]),
523 cache_lfu_policy_group_);
524 break;
525 }
526 }
527
528 TRACE_OUT(cache_lfu_policy_get_prev_item);
529 return ((struct cache_policy_item_ *)lfu_item);
530 }
531
532 /*
533 * Initializes the cache_policy_ structure by filling it with appropriate
534 * functions pointers
535 */
536 struct cache_policy_ *
init_cache_lfu_policy(void)537 init_cache_lfu_policy(void)
538 {
539 int i;
540 struct cache_lfu_policy_ *retval;
541
542 TRACE_IN(init_cache_lfu_policy);
543 retval = calloc(1,
544 sizeof(*retval));
545 assert(retval != NULL);
546
547 retval->parent_data.create_item_func = cache_lfu_policy_create_item;
548 retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item;
549
550 retval->parent_data.add_item_func = cache_lfu_policy_add_item;
551 retval->parent_data.update_item_func = cache_lfu_policy_update_item;
552 retval->parent_data.remove_item_func = cache_lfu_policy_remove_item;
553
554 retval->parent_data.get_first_item_func =
555 cache_lfu_policy_get_first_item;
556 retval->parent_data.get_last_item_func =
557 cache_lfu_policy_get_last_item;
558 retval->parent_data.get_next_item_func =
559 cache_lfu_policy_get_next_item;
560 retval->parent_data.get_prev_item_func =
561 cache_lfu_policy_get_prev_item;
562
563 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i)
564 TAILQ_INIT(&(retval->groups[i]));
565
566 TRACE_OUT(init_cache_lfu_policy);
567 return ((struct cache_policy_ *)retval);
568 }
569
570 void
destroy_cache_lfu_policy(struct cache_policy_ * policy)571 destroy_cache_lfu_policy(struct cache_policy_ *policy)
572 {
573 int i;
574 struct cache_lfu_policy_ *lfu_policy;
575 struct cache_lfu_policy_item_ *lfu_item;
576
577 TRACE_IN(destroy_cache_lfu_policy);
578 lfu_policy = (struct cache_lfu_policy_ *)policy;
579 for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) {
580 while (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) {
581 lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i]));
582 TAILQ_REMOVE(&(lfu_policy->groups[i]), lfu_item,
583 entries);
584 cache_lfu_policy_destroy_item(
585 (struct cache_policy_item_ *)lfu_item);
586 }
587 }
588 free(policy);
589 TRACE_OUT(destroy_cache_lfu_policy);
590 }
591