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 } 585