usr.sbin/nscd/cacheplcs.c

   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 __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_ *
  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
  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
 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
 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_ *
 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_ *
 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_ *
 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_ *
 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_ *
 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
 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
 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_ *
 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
 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
 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_ *
 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
 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_ *
 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
 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
 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
 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
 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_ *
 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_ *
 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_ *
 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_ *
 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_ *
 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
 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 }