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