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