cacheplcs.c revision 158115
1158115Sume/*- 2158115Sume * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru> 3158115Sume * All rights reserved. 4158115Sume * 5158115Sume * Redistribution and use in source and binary forms, with or without 6158115Sume * modification, are permitted provided that the following conditions 7158115Sume * are met: 8158115Sume * 1. Redistributions of source code must retain the above copyright 9158115Sume * notice, this list of conditions and the following disclaimer. 10158115Sume * 2. Redistributions in binary form must reproduce the above copyright 11158115Sume * notice, this list of conditions and the following disclaimer in the 12158115Sume * documentation and/or other materials provided with the distribution. 13158115Sume * 14158115Sume * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15158115Sume * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16158115Sume * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17158115Sume * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18158115Sume * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19158115Sume * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20158115Sume * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21158115Sume * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22158115Sume * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23158115Sume * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24158115Sume * SUCH DAMAGE. 25158115Sume * 26158115Sume */ 27158115Sume 28158115Sume#include <sys/cdefs.h> 29158115Sume__FBSDID("$FreeBSD: head/usr.sbin/nscd/cacheplcs.c 158115 2006-04-28 12:03:38Z ume $"); 30158115Sume 31158115Sume#include <assert.h> 32158115Sume#include <string.h> 33158115Sume#include "cacheplcs.h" 34158115Sume#include "debug.h" 35158115Sume 36158115Sumestatic void cache_fifo_policy_update_item(struct cache_policy_ *, 37158115Sume struct cache_policy_item_ *); 38158115Sumestatic void cache_lfu_policy_add_item(struct cache_policy_ *, 39158115Sume struct cache_policy_item_ *); 40158115Sumestatic struct cache_policy_item_ * cache_lfu_policy_create_item(void); 41158115Sumestatic void cache_lfu_policy_destroy_item(struct cache_policy_item_ *); 42158115Sumestatic struct cache_policy_item_ *cache_lfu_policy_get_first_item( 43158115Sume struct cache_policy_ *); 44158115Sumestatic struct cache_policy_item_ *cache_lfu_policy_get_last_item( 45158115Sume struct cache_policy_ *); 46158115Sumestatic struct cache_policy_item_ *cache_lfu_policy_get_next_item( 47158115Sume struct cache_policy_ *, struct cache_policy_item_ *); 48158115Sumestatic struct cache_policy_item_ *cache_lfu_policy_get_prev_item( 49158115Sume struct cache_policy_ *, struct cache_policy_item_ *); 50158115Sumestatic void cache_lfu_policy_remove_item(struct cache_policy_ *, 51158115Sume struct cache_policy_item_ *); 52158115Sumestatic void cache_lfu_policy_update_item(struct cache_policy_ *, 53158115Sume struct cache_policy_item_ *); 54158115Sumestatic void cache_lru_policy_update_item(struct cache_policy_ *, 55158115Sume struct cache_policy_item_ *); 56158115Sumestatic void cache_queue_policy_add_item(struct cache_policy_ *, 57158115Sume struct cache_policy_item_ *); 58158115Sumestatic struct cache_policy_item_ * cache_queue_policy_create_item(); 59158115Sumestatic void cache_queue_policy_destroy_item(struct cache_policy_item_ *); 60158115Sumestatic struct cache_policy_item_ *cache_queue_policy_get_first_item( 61158115Sume struct cache_policy_ *); 62158115Sumestatic struct cache_policy_item_ *cache_queue_policy_get_last_item( 63158115Sume struct cache_policy_ *); 64158115Sumestatic struct cache_policy_item_ *cache_queue_policy_get_next_item( 65158115Sume struct cache_policy_ *, struct cache_policy_item_ *); 66158115Sumestatic struct cache_policy_item_ *cache_queue_policy_get_prev_item( 67158115Sume struct cache_policy_ *, struct cache_policy_item_ *); 68158115Sumestatic void cache_queue_policy_remove_item(struct cache_policy_ *, 69158115Sume struct cache_policy_item_ *); 70158115Sumestatic void destroy_cache_queue_policy(struct cache_queue_policy_ *); 71158115Sumestatic struct cache_queue_policy_ *init_cache_queue_policy(void); 72158115Sume 73158115Sume/* 74158115Sume * All cache_queue_policy_XXX functions below will be used to fill 75158115Sume * the cache_queue_policy structure. They implement the most functionality of 76158115Sume * LRU and FIFO policies. LRU and FIFO policies are actually the 77158115Sume * cache_queue_policy_ with cache_update_item function changed. 78158115Sume */ 79158115Sumestatic struct cache_policy_item_ * 80158115Sumecache_queue_policy_create_item() 81158115Sume{ 82158115Sume struct cache_queue_policy_item_ *retval; 83158115Sume 84158115Sume TRACE_IN(cache_queue_policy_create_item); 85158115Sume retval = (struct cache_queue_policy_item_ *)malloc( 86158115Sume sizeof(struct cache_queue_policy_item_)); 87158115Sume assert(retval != NULL); 88158115Sume memset(retval, 0, sizeof(struct cache_queue_policy_item_)); 89158115Sume 90158115Sume TRACE_OUT(cache_queue_policy_create_item); 91158115Sume return ((struct cache_policy_item_ *)retval); 92158115Sume} 93158115Sume 94158115Sumestatic void 95158115Sumecache_queue_policy_destroy_item(struct cache_policy_item_ *item) 96158115Sume{ 97158115Sume 98158115Sume TRACE_IN(cache_queue_policy_destroy_item); 99158115Sume assert(item != NULL); 100158115Sume free(item); 101158115Sume TRACE_OUT(cache_queue_policy_destroy_item); 102158115Sume} 103158115Sume 104158115Sumestatic void 105158115Sumecache_queue_policy_add_item(struct cache_policy_ *policy, 106158115Sume struct cache_policy_item_ *item) 107158115Sume{ 108158115Sume struct cache_queue_policy_ *queue_policy; 109158115Sume struct cache_queue_policy_item_ *queue_item; 110158115Sume 111158115Sume TRACE_IN(cache_queue_policy_add_item); 112158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 113158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 114158115Sume TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 115158115Sume TRACE_OUT(cache_queue_policy_add_item); 116158115Sume} 117158115Sume 118158115Sumestatic void 119158115Sumecache_queue_policy_remove_item(struct cache_policy_ *policy, 120158115Sume struct cache_policy_item_ *item) 121158115Sume{ 122158115Sume struct cache_queue_policy_ *queue_policy; 123158115Sume struct cache_queue_policy_item_ *queue_item; 124158115Sume 125158115Sume TRACE_IN(cache_queue_policy_remove_item); 126158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 127158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 128158115Sume TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 129158115Sume TRACE_OUT(cache_queue_policy_remove_item); 130158115Sume} 131158115Sume 132158115Sumestatic struct cache_policy_item_ * 133158115Sumecache_queue_policy_get_first_item(struct cache_policy_ *policy) 134158115Sume{ 135158115Sume struct cache_queue_policy_ *queue_policy; 136158115Sume 137158115Sume TRACE_IN(cache_queue_policy_get_first_item); 138158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 139158115Sume TRACE_OUT(cache_queue_policy_get_first_item); 140158115Sume return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head)); 141158115Sume} 142158115Sume 143158115Sumestatic struct cache_policy_item_ * 144158115Sumecache_queue_policy_get_last_item(struct cache_policy_ *policy) 145158115Sume{ 146158115Sume struct cache_queue_policy_ *queue_policy; 147158115Sume 148158115Sume TRACE_IN(cache_queue_policy_get_last_item); 149158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 150158115Sume TRACE_OUT(cache_queue_policy_get_last_item); 151158115Sume return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head, 152158115Sume cache_queue_policy_head_)); 153158115Sume} 154158115Sume 155158115Sumestatic struct cache_policy_item_ * 156158115Sumecache_queue_policy_get_next_item(struct cache_policy_ *policy, 157158115Sume struct cache_policy_item_ *item) 158158115Sume{ 159158115Sume struct cache_queue_policy_ *queue_policy; 160158115Sume struct cache_queue_policy_item_ *queue_item; 161158115Sume 162158115Sume TRACE_IN(cache_queue_policy_get_next_item); 163158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 164158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 165158115Sume 166158115Sume TRACE_OUT(cache_queue_policy_get_next_item); 167158115Sume return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries)); 168158115Sume} 169158115Sume 170158115Sumestatic struct cache_policy_item_ * 171158115Sumecache_queue_policy_get_prev_item(struct cache_policy_ *policy, 172158115Sume struct cache_policy_item_ *item) 173158115Sume{ 174158115Sume struct cache_queue_policy_ *queue_policy; 175158115Sume struct cache_queue_policy_item_ *queue_item; 176158115Sume 177158115Sume TRACE_IN(cache_queue_policy_get_prev_item); 178158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 179158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 180158115Sume 181158115Sume TRACE_OUT(cache_queue_policy_get_prev_item); 182158115Sume return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item, 183158115Sume cache_queue_policy_head_, entries)); 184158115Sume} 185158115Sume 186158115Sume/* 187158115Sume * Initializes cache_queue_policy_ by filling the structure with the functions 188158115Sume * pointers, defined above 189158115Sume */ 190158115Sumestatic struct cache_queue_policy_ * 191158115Sumeinit_cache_queue_policy(void) 192158115Sume{ 193158115Sume struct cache_queue_policy_ *retval; 194158115Sume 195158115Sume TRACE_IN(init_cache_queue_policy); 196158115Sume retval = (struct cache_queue_policy_ *)malloc( 197158115Sume sizeof(struct cache_queue_policy_)); 198158115Sume assert(retval != NULL); 199158115Sume memset(retval, 0, sizeof(struct cache_queue_policy_)); 200158115Sume 201158115Sume retval->parent_data.create_item_func = cache_queue_policy_create_item; 202158115Sume retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item; 203158115Sume 204158115Sume retval->parent_data.add_item_func = cache_queue_policy_add_item; 205158115Sume retval->parent_data.remove_item_func = cache_queue_policy_remove_item; 206158115Sume 207158115Sume retval->parent_data.get_first_item_func = 208158115Sume cache_queue_policy_get_first_item; 209158115Sume retval->parent_data.get_last_item_func = 210158115Sume cache_queue_policy_get_last_item; 211158115Sume retval->parent_data.get_next_item_func = 212158115Sume cache_queue_policy_get_next_item; 213158115Sume retval->parent_data.get_prev_item_func = 214158115Sume cache_queue_policy_get_prev_item; 215158115Sume 216158115Sume TAILQ_INIT(&retval->head); 217158115Sume TRACE_OUT(init_cache_queue_policy); 218158115Sume return (retval); 219158115Sume} 220158115Sume 221158115Sumestatic void 222158115Sumedestroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy) 223158115Sume{ 224158115Sume struct cache_queue_policy_item_ *queue_item; 225158115Sume 226158115Sume TRACE_IN(destroy_cache_queue_policy); 227158115Sume while (!TAILQ_EMPTY(&queue_policy->head)) { 228158115Sume queue_item = TAILQ_FIRST(&queue_policy->head); 229158115Sume TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 230158115Sume cache_queue_policy_destroy_item( 231158115Sume (struct cache_policy_item_ *)queue_item); 232158115Sume } 233158115Sume free(queue_policy); 234158115Sume TRACE_OUT(destroy_cache_queue_policy); 235158115Sume} 236158115Sume 237158115Sume/* 238158115Sume * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything, 239158115Sume * when the cache element is updated. So it always stays in its initial 240158115Sume * position in the queue - that is exactly the FIFO functionality. 241158115Sume */ 242158115Sumestatic void 243158115Sumecache_fifo_policy_update_item(struct cache_policy_ *policy, 244158115Sume struct cache_policy_item_ *item) 245158115Sume{ 246158115Sume 247158115Sume TRACE_IN(cache_fifo_policy_update_item); 248158115Sume /* policy and item arguments are ignored */ 249158115Sume TRACE_OUT(cache_fifo_policy_update_item); 250158115Sume} 251158115Sume 252158115Sumestruct cache_policy_ * 253158115Sumeinit_cache_fifo_policy() 254158115Sume{ 255158115Sume struct cache_queue_policy_ *retval; 256158115Sume 257158115Sume TRACE_IN(init_cache_fifo_policy); 258158115Sume retval = init_cache_queue_policy(); 259158115Sume retval->parent_data.update_item_func = cache_fifo_policy_update_item; 260158115Sume 261158115Sume TRACE_OUT(init_cache_fifo_policy); 262158115Sume return ((struct cache_policy_ *)retval); 263158115Sume} 264158115Sume 265158115Sumevoid 266158115Sumedestroy_cache_fifo_policy(struct cache_policy_ *policy) 267158115Sume{ 268158115Sume struct cache_queue_policy_ *queue_policy; 269158115Sume 270158115Sume TRACE_IN(destroy_cache_fifo_policy); 271158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 272158115Sume destroy_cache_queue_policy(queue_policy); 273158115Sume TRACE_OUT(destroy_cache_fifo_policy); 274158115Sume} 275158115Sume 276158115Sume/* 277158115Sume * Makes cache_queue_policy_ behave like LRU policy. On each update, cache 278158115Sume * element is moved to the end of the queue - so it would be deleted in last 279158115Sume * turn. That is exactly the LRU policy functionality. 280158115Sume */ 281158115Sumestatic void 282158115Sumecache_lru_policy_update_item(struct cache_policy_ *policy, 283158115Sume struct cache_policy_item_ *item) 284158115Sume{ 285158115Sume struct cache_queue_policy_ *queue_policy; 286158115Sume struct cache_queue_policy_item_ *queue_item; 287158115Sume 288158115Sume TRACE_IN(cache_lru_policy_update_item); 289158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 290158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 291158115Sume 292158115Sume TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 293158115Sume TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 294158115Sume TRACE_OUT(cache_lru_policy_update_item); 295158115Sume} 296158115Sume 297158115Sumestruct cache_policy_ * 298158115Sumeinit_cache_lru_policy() 299158115Sume{ 300158115Sume struct cache_queue_policy_ *retval; 301158115Sume 302158115Sume TRACE_IN(init_cache_lru_policy); 303158115Sume retval = init_cache_queue_policy(); 304158115Sume retval->parent_data.update_item_func = cache_lru_policy_update_item; 305158115Sume 306158115Sume TRACE_OUT(init_cache_lru_policy); 307158115Sume return ((struct cache_policy_ *)retval); 308158115Sume} 309158115Sume 310158115Sumevoid 311158115Sumedestroy_cache_lru_policy(struct cache_policy_ *policy) 312158115Sume{ 313158115Sume struct cache_queue_policy_ *queue_policy; 314158115Sume 315158115Sume TRACE_IN(destroy_cache_lru_policy); 316158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 317158115Sume destroy_cache_queue_policy(queue_policy); 318158115Sume TRACE_OUT(destroy_cache_lru_policy); 319158115Sume} 320158115Sume 321158115Sume/* 322158115Sume * LFU (least frequently used) policy implementation differs much from the 323158115Sume * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_ 324158115Sume * functions are implemented specifically for this policy. The idea of this 325158115Sume * policy is to represent frequency (real number) as the integer number and 326158115Sume * use it as the index in the array. Each array's element is 327158115Sume * the list of elements. For example, if we have the 100-elements 328158115Sume * array for this policy, the elements with frequency 0.1 (calls per-second) 329158115Sume * would be in 10th element of the array. 330158115Sume */ 331158115Sumestatic struct cache_policy_item_ * 332158115Sumecache_lfu_policy_create_item(void) 333158115Sume{ 334158115Sume struct cache_lfu_policy_item_ *retval; 335158115Sume 336158115Sume TRACE_IN(cache_lfu_policy_create_item); 337158115Sume retval = (struct cache_lfu_policy_item_ *)malloc( 338158115Sume sizeof(struct cache_lfu_policy_item_)); 339158115Sume assert(retval != NULL); 340158115Sume memset(retval, 0, sizeof(struct cache_lfu_policy_item_)); 341158115Sume 342158115Sume TRACE_OUT(cache_lfu_policy_create_item); 343158115Sume return ((struct cache_policy_item_ *)retval); 344158115Sume} 345158115Sume 346158115Sumestatic void 347158115Sumecache_lfu_policy_destroy_item(struct cache_policy_item_ *item) 348158115Sume{ 349158115Sume 350158115Sume TRACE_IN(cache_lfu_policy_destroy_item); 351158115Sume assert(item != NULL); 352158115Sume free(item); 353158115Sume TRACE_OUT(cache_lfu_policy_destroy_item); 354158115Sume} 355158115Sume 356158115Sume/* 357158115Sume * When placed in the LFU policy queue for the first time, the maximum 358158115Sume * frequency is assigned to the element 359158115Sume */ 360158115Sumestatic void 361158115Sumecache_lfu_policy_add_item(struct cache_policy_ *policy, 362158115Sume struct cache_policy_item_ *item) 363158115Sume{ 364158115Sume struct cache_lfu_policy_ *lfu_policy; 365158115Sume struct cache_lfu_policy_item_ *lfu_item; 366158115Sume 367158115Sume TRACE_IN(cache_lfu_policy_add_item); 368158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 369158115Sume lfu_item = (struct cache_lfu_policy_item_ *)item; 370158115Sume 371158115Sume lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1; 372158115Sume TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]), 373158115Sume lfu_item, entries); 374158115Sume TRACE_OUT(cache_lfu_policy_add_item); 375158115Sume} 376158115Sume 377158115Sume/* 378158115Sume * On each update the frequency of the element is recalculated and, if it 379158115Sume * changed, the element would be moved to the another place in the array. 380158115Sume */ 381158115Sumestatic void 382158115Sumecache_lfu_policy_update_item(struct cache_policy_ *policy, 383158115Sume struct cache_policy_item_ *item) 384158115Sume{ 385158115Sume struct cache_lfu_policy_ *lfu_policy; 386158115Sume struct cache_lfu_policy_item_ *lfu_item; 387158115Sume int index; 388158115Sume 389158115Sume TRACE_IN(cache_lfu_policy_update_item); 390158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 391158115Sume lfu_item = (struct cache_lfu_policy_item_ *)item; 392158115Sume 393158115Sume /* 394158115Sume * We calculate the square of the request_count to avoid grouping of 395158115Sume * all elements at the start of the array (for example, if array size is 396158115Sume * 100 and most of its elements has frequency below the 0.01, they 397158115Sume * all would be grouped in the first array's position). Other 398158115Sume * techniques should be used here later to ensure, that elements are 399158115Sume * equally distributed in the array and not grouped in its beginning. 400158115Sume */ 401158115Sume if (lfu_item->parent_data.last_request_time.tv_sec != 402158115Sume lfu_item->parent_data.creation_time.tv_sec) { 403158115Sume index = ((double)lfu_item->parent_data.request_count * 404158115Sume (double)lfu_item->parent_data.request_count / 405158115Sume (lfu_item->parent_data.last_request_time.tv_sec - 406158115Sume lfu_item->parent_data.creation_time.tv_sec + 1)) * 407158115Sume CACHELIB_MAX_FREQUENCY; 408158115Sume if (index >= CACHELIB_MAX_FREQUENCY) 409158115Sume index = CACHELIB_MAX_FREQUENCY - 1; 410158115Sume } else 411158115Sume index = CACHELIB_MAX_FREQUENCY - 1; 412158115Sume 413158115Sume TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 414158115Sume entries); 415158115Sume lfu_item->frequency = index; 416158115Sume TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries); 417158115Sume 418158115Sume TRACE_OUT(cache_lfu_policy_update_item); 419158115Sume} 420158115Sume 421158115Sumestatic void 422158115Sumecache_lfu_policy_remove_item(struct cache_policy_ *policy, 423158115Sume struct cache_policy_item_ *item) 424158115Sume{ 425158115Sume struct cache_lfu_policy_ *lfu_policy; 426158115Sume struct cache_lfu_policy_item_ *lfu_item; 427158115Sume 428158115Sume TRACE_IN(cache_lfu_policy_remove_item); 429158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 430158115Sume lfu_item = (struct cache_lfu_policy_item_ *)item; 431158115Sume 432158115Sume TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 433158115Sume entries); 434158115Sume TRACE_OUT(cache_lfu_policy_remove_item); 435158115Sume} 436158115Sume 437158115Sumestatic struct cache_policy_item_ * 438158115Sumecache_lfu_policy_get_first_item(struct cache_policy_ *policy) 439158115Sume{ 440158115Sume struct cache_lfu_policy_ *lfu_policy; 441158115Sume struct cache_lfu_policy_item_ *lfu_item; 442158115Sume int i; 443158115Sume 444158115Sume TRACE_IN(cache_lfu_policy_get_first_item); 445158115Sume lfu_item = NULL; 446158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 447158115Sume for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 448158115Sume if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 449158115Sume lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 450158115Sume break; 451158115Sume } 452158115Sume 453158115Sume TRACE_OUT(cache_lfu_policy_get_first_item); 454158115Sume return ((struct cache_policy_item_ *)lfu_item); 455158115Sume} 456158115Sume 457158115Sumestatic struct cache_policy_item_ * 458158115Sumecache_lfu_policy_get_last_item(struct cache_policy_ *policy) 459158115Sume{ 460158115Sume struct cache_lfu_policy_ *lfu_policy; 461158115Sume struct cache_lfu_policy_item_ *lfu_item; 462158115Sume int i; 463158115Sume 464158115Sume TRACE_IN(cache_lfu_policy_get_last_item); 465158115Sume lfu_item = NULL; 466158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 467158115Sume for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i) 468158115Sume if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 469158115Sume lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 470158115Sume cache_lfu_policy_group_); 471158115Sume break; 472158115Sume } 473158115Sume 474158115Sume TRACE_OUT(cache_lfu_policy_get_last_item); 475158115Sume return ((struct cache_policy_item_ *)lfu_item); 476158115Sume} 477158115Sume 478158115Sumestatic struct cache_policy_item_ * 479158115Sumecache_lfu_policy_get_next_item(struct cache_policy_ *policy, 480158115Sume struct cache_policy_item_ *item) 481158115Sume{ 482158115Sume struct cache_lfu_policy_ *lfu_policy; 483158115Sume struct cache_lfu_policy_item_ *lfu_item; 484158115Sume int i; 485158115Sume 486158115Sume TRACE_IN(cache_lfu_policy_get_next_item); 487158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 488158115Sume lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries); 489158115Sume if (lfu_item == NULL) 490158115Sume { 491158115Sume for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1; 492158115Sume i < CACHELIB_MAX_FREQUENCY; ++i) { 493158115Sume if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 494158115Sume lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 495158115Sume break; 496158115Sume } 497158115Sume } 498158115Sume } 499158115Sume 500158115Sume TRACE_OUT(cache_lfu_policy_get_next_item); 501158115Sume return ((struct cache_policy_item_ *)lfu_item); 502158115Sume} 503158115Sume 504158115Sumestatic struct cache_policy_item_ * 505158115Sumecache_lfu_policy_get_prev_item(struct cache_policy_ *policy, 506158115Sume struct cache_policy_item_ *item) 507158115Sume{ 508158115Sume struct cache_lfu_policy_ *lfu_policy; 509158115Sume struct cache_lfu_policy_item_ *lfu_item; 510158115Sume int i; 511158115Sume 512158115Sume TRACE_IN(cache_lfu_policy_get_prev_item); 513158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 514158115Sume lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item, 515158115Sume cache_lfu_policy_group_, entries); 516158115Sume if (lfu_item == NULL) 517158115Sume { 518158115Sume for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1; 519158115Sume i >= 0; --i) 520158115Sume if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 521158115Sume lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 522158115Sume cache_lfu_policy_group_); 523158115Sume break; 524158115Sume } 525158115Sume } 526158115Sume 527158115Sume TRACE_OUT(cache_lfu_policy_get_prev_item); 528158115Sume return ((struct cache_policy_item_ *)lfu_item); 529158115Sume} 530158115Sume 531158115Sume/* 532158115Sume * Initializes the cache_policy_ structure by filling it with appropriate 533158115Sume * functions pointers 534158115Sume */ 535158115Sumestruct cache_policy_ * 536158115Sumeinit_cache_lfu_policy() 537158115Sume{ 538158115Sume int i; 539158115Sume struct cache_lfu_policy_ *retval; 540158115Sume 541158115Sume TRACE_IN(init_cache_lfu_policy); 542158115Sume retval = (struct cache_lfu_policy_ *)malloc( 543158115Sume sizeof(struct cache_lfu_policy_)); 544158115Sume assert(retval != NULL); 545158115Sume memset(retval, 0, sizeof(struct cache_lfu_policy_)); 546158115Sume 547158115Sume retval->parent_data.create_item_func = cache_lfu_policy_create_item; 548158115Sume retval->parent_data.destroy_item_func = cache_lfu_policy_destroy_item; 549158115Sume 550158115Sume retval->parent_data.add_item_func = cache_lfu_policy_add_item; 551158115Sume retval->parent_data.update_item_func = cache_lfu_policy_update_item; 552158115Sume retval->parent_data.remove_item_func = cache_lfu_policy_remove_item; 553158115Sume 554158115Sume retval->parent_data.get_first_item_func = 555158115Sume cache_lfu_policy_get_first_item; 556158115Sume retval->parent_data.get_last_item_func = 557158115Sume cache_lfu_policy_get_last_item; 558158115Sume retval->parent_data.get_next_item_func = 559158115Sume cache_lfu_policy_get_next_item; 560158115Sume retval->parent_data.get_prev_item_func = 561158115Sume cache_lfu_policy_get_prev_item; 562158115Sume 563158115Sume for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 564158115Sume TAILQ_INIT(&(retval->groups[i])); 565158115Sume 566158115Sume TRACE_OUT(init_cache_lfu_policy); 567158115Sume return ((struct cache_policy_ *)retval); 568158115Sume} 569158115Sume 570158115Sumevoid 571158115Sumedestroy_cache_lfu_policy(struct cache_policy_ *policy) 572158115Sume{ 573158115Sume int i; 574158115Sume struct cache_lfu_policy_ *lfu_policy; 575158115Sume struct cache_lfu_policy_item_ *lfu_item; 576158115Sume 577158115Sume TRACE_IN(destroy_cache_lfu_policy); 578158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 579158115Sume for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) { 580158115Sume while (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 581158115Sume lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 582158115Sume TAILQ_REMOVE(&(lfu_policy->groups[i]), lfu_item, 583158115Sume entries); 584158115Sume cache_lfu_policy_destroy_item( 585158115Sume (struct cache_policy_item_ *)lfu_item); 586158115Sume } 587158115Sume } 588158115Sume free(policy); 589158115Sume TRACE_OUT(destroy_cache_lfu_policy); 590158115Sume} 591