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