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