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