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$"); 30158115Sume 31194089Sdes#include <sys/time.h> 32194089Sdes 33158115Sume#include <assert.h> 34194089Sdes#include <stdlib.h> 35158115Sume#include <string.h> 36194089Sdes 37158115Sume#include "cacheplcs.h" 38158115Sume#include "debug.h" 39158115Sume 40158115Sumestatic void cache_fifo_policy_update_item(struct cache_policy_ *, 41158115Sume struct cache_policy_item_ *); 42158115Sumestatic void cache_lfu_policy_add_item(struct cache_policy_ *, 43158115Sume struct cache_policy_item_ *); 44158115Sumestatic struct cache_policy_item_ * cache_lfu_policy_create_item(void); 45158115Sumestatic void cache_lfu_policy_destroy_item(struct cache_policy_item_ *); 46158115Sumestatic struct cache_policy_item_ *cache_lfu_policy_get_first_item( 47158115Sume struct cache_policy_ *); 48158115Sumestatic struct cache_policy_item_ *cache_lfu_policy_get_last_item( 49158115Sume struct cache_policy_ *); 50158115Sumestatic struct cache_policy_item_ *cache_lfu_policy_get_next_item( 51158115Sume struct cache_policy_ *, struct cache_policy_item_ *); 52158115Sumestatic struct cache_policy_item_ *cache_lfu_policy_get_prev_item( 53158115Sume struct cache_policy_ *, struct cache_policy_item_ *); 54158115Sumestatic void cache_lfu_policy_remove_item(struct cache_policy_ *, 55158115Sume struct cache_policy_item_ *); 56158115Sumestatic void cache_lfu_policy_update_item(struct cache_policy_ *, 57158115Sume struct cache_policy_item_ *); 58158115Sumestatic void cache_lru_policy_update_item(struct cache_policy_ *, 59158115Sume struct cache_policy_item_ *); 60158115Sumestatic void cache_queue_policy_add_item(struct cache_policy_ *, 61158115Sume struct cache_policy_item_ *); 62194087Sdesstatic struct cache_policy_item_ * cache_queue_policy_create_item(void); 63158115Sumestatic void cache_queue_policy_destroy_item(struct cache_policy_item_ *); 64158115Sumestatic struct cache_policy_item_ *cache_queue_policy_get_first_item( 65158115Sume struct cache_policy_ *); 66158115Sumestatic struct cache_policy_item_ *cache_queue_policy_get_last_item( 67158115Sume struct cache_policy_ *); 68158115Sumestatic struct cache_policy_item_ *cache_queue_policy_get_next_item( 69158115Sume struct cache_policy_ *, struct cache_policy_item_ *); 70158115Sumestatic struct cache_policy_item_ *cache_queue_policy_get_prev_item( 71158115Sume struct cache_policy_ *, struct cache_policy_item_ *); 72158115Sumestatic void cache_queue_policy_remove_item(struct cache_policy_ *, 73158115Sume struct cache_policy_item_ *); 74158115Sumestatic void destroy_cache_queue_policy(struct cache_queue_policy_ *); 75158115Sumestatic struct cache_queue_policy_ *init_cache_queue_policy(void); 76158115Sume 77158115Sume/* 78158115Sume * All cache_queue_policy_XXX functions below will be used to fill 79158115Sume * the cache_queue_policy structure. They implement the most functionality of 80158115Sume * LRU and FIFO policies. LRU and FIFO policies are actually the 81158115Sume * cache_queue_policy_ with cache_update_item function changed. 82158115Sume */ 83158115Sumestatic struct cache_policy_item_ * 84194087Sdescache_queue_policy_create_item(void) 85158115Sume{ 86158115Sume struct cache_queue_policy_item_ *retval; 87158115Sume 88158115Sume TRACE_IN(cache_queue_policy_create_item); 89194104Sdes retval = calloc(1, 90194104Sdes sizeof(*retval)); 91158115Sume assert(retval != NULL); 92158115Sume 93158115Sume TRACE_OUT(cache_queue_policy_create_item); 94158115Sume return ((struct cache_policy_item_ *)retval); 95158115Sume} 96158115Sume 97158115Sumestatic void 98158115Sumecache_queue_policy_destroy_item(struct cache_policy_item_ *item) 99158115Sume{ 100158115Sume 101158115Sume TRACE_IN(cache_queue_policy_destroy_item); 102158115Sume assert(item != NULL); 103158115Sume free(item); 104158115Sume TRACE_OUT(cache_queue_policy_destroy_item); 105158115Sume} 106158115Sume 107158115Sumestatic void 108158115Sumecache_queue_policy_add_item(struct cache_policy_ *policy, 109158115Sume struct cache_policy_item_ *item) 110158115Sume{ 111158115Sume struct cache_queue_policy_ *queue_policy; 112158115Sume struct cache_queue_policy_item_ *queue_item; 113158115Sume 114158115Sume TRACE_IN(cache_queue_policy_add_item); 115158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 116158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 117158115Sume TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 118158115Sume TRACE_OUT(cache_queue_policy_add_item); 119158115Sume} 120158115Sume 121158115Sumestatic void 122158115Sumecache_queue_policy_remove_item(struct cache_policy_ *policy, 123158115Sume struct cache_policy_item_ *item) 124158115Sume{ 125158115Sume struct cache_queue_policy_ *queue_policy; 126158115Sume struct cache_queue_policy_item_ *queue_item; 127158115Sume 128158115Sume TRACE_IN(cache_queue_policy_remove_item); 129158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 130158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 131158115Sume TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 132158115Sume TRACE_OUT(cache_queue_policy_remove_item); 133158115Sume} 134158115Sume 135158115Sumestatic struct cache_policy_item_ * 136158115Sumecache_queue_policy_get_first_item(struct cache_policy_ *policy) 137158115Sume{ 138158115Sume struct cache_queue_policy_ *queue_policy; 139158115Sume 140158115Sume TRACE_IN(cache_queue_policy_get_first_item); 141158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 142158115Sume TRACE_OUT(cache_queue_policy_get_first_item); 143158115Sume return ((struct cache_policy_item_ *)TAILQ_FIRST(&queue_policy->head)); 144158115Sume} 145158115Sume 146158115Sumestatic struct cache_policy_item_ * 147158115Sumecache_queue_policy_get_last_item(struct cache_policy_ *policy) 148158115Sume{ 149158115Sume struct cache_queue_policy_ *queue_policy; 150158115Sume 151158115Sume TRACE_IN(cache_queue_policy_get_last_item); 152158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 153158115Sume TRACE_OUT(cache_queue_policy_get_last_item); 154158115Sume return ((struct cache_policy_item_ *)TAILQ_LAST(&queue_policy->head, 155158115Sume cache_queue_policy_head_)); 156158115Sume} 157158115Sume 158158115Sumestatic struct cache_policy_item_ * 159158115Sumecache_queue_policy_get_next_item(struct cache_policy_ *policy, 160158115Sume struct cache_policy_item_ *item) 161158115Sume{ 162158115Sume struct cache_queue_policy_ *queue_policy; 163158115Sume struct cache_queue_policy_item_ *queue_item; 164158115Sume 165158115Sume TRACE_IN(cache_queue_policy_get_next_item); 166158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 167158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 168158115Sume 169158115Sume TRACE_OUT(cache_queue_policy_get_next_item); 170158115Sume return ((struct cache_policy_item_ *)TAILQ_NEXT(queue_item, entries)); 171158115Sume} 172158115Sume 173158115Sumestatic struct cache_policy_item_ * 174158115Sumecache_queue_policy_get_prev_item(struct cache_policy_ *policy, 175158115Sume struct cache_policy_item_ *item) 176158115Sume{ 177158115Sume struct cache_queue_policy_ *queue_policy; 178158115Sume struct cache_queue_policy_item_ *queue_item; 179158115Sume 180158115Sume TRACE_IN(cache_queue_policy_get_prev_item); 181158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 182158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 183158115Sume 184158115Sume TRACE_OUT(cache_queue_policy_get_prev_item); 185158115Sume return ((struct cache_policy_item_ *)TAILQ_PREV(queue_item, 186158115Sume cache_queue_policy_head_, entries)); 187158115Sume} 188158115Sume 189158115Sume/* 190158115Sume * Initializes cache_queue_policy_ by filling the structure with the functions 191158115Sume * pointers, defined above 192158115Sume */ 193158115Sumestatic struct cache_queue_policy_ * 194158115Sumeinit_cache_queue_policy(void) 195158115Sume{ 196158115Sume struct cache_queue_policy_ *retval; 197158115Sume 198158115Sume TRACE_IN(init_cache_queue_policy); 199194104Sdes retval = calloc(1, 200194104Sdes sizeof(*retval)); 201158115Sume assert(retval != NULL); 202158115Sume 203158115Sume retval->parent_data.create_item_func = cache_queue_policy_create_item; 204158115Sume retval->parent_data.destroy_item_func = cache_queue_policy_destroy_item; 205158115Sume 206158115Sume retval->parent_data.add_item_func = cache_queue_policy_add_item; 207158115Sume retval->parent_data.remove_item_func = cache_queue_policy_remove_item; 208158115Sume 209158115Sume retval->parent_data.get_first_item_func = 210158115Sume cache_queue_policy_get_first_item; 211158115Sume retval->parent_data.get_last_item_func = 212158115Sume cache_queue_policy_get_last_item; 213158115Sume retval->parent_data.get_next_item_func = 214158115Sume cache_queue_policy_get_next_item; 215158115Sume retval->parent_data.get_prev_item_func = 216158115Sume cache_queue_policy_get_prev_item; 217158115Sume 218158115Sume TAILQ_INIT(&retval->head); 219158115Sume TRACE_OUT(init_cache_queue_policy); 220158115Sume return (retval); 221158115Sume} 222158115Sume 223158115Sumestatic void 224158115Sumedestroy_cache_queue_policy(struct cache_queue_policy_ *queue_policy) 225158115Sume{ 226158115Sume struct cache_queue_policy_item_ *queue_item; 227158115Sume 228158115Sume TRACE_IN(destroy_cache_queue_policy); 229158115Sume while (!TAILQ_EMPTY(&queue_policy->head)) { 230158115Sume queue_item = TAILQ_FIRST(&queue_policy->head); 231158115Sume TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 232158115Sume cache_queue_policy_destroy_item( 233158115Sume (struct cache_policy_item_ *)queue_item); 234158115Sume } 235158115Sume free(queue_policy); 236158115Sume TRACE_OUT(destroy_cache_queue_policy); 237158115Sume} 238158115Sume 239158115Sume/* 240158115Sume * Makes cache_queue_policy_ behave like FIFO policy - we don't do anything, 241158115Sume * when the cache element is updated. So it always stays in its initial 242158115Sume * position in the queue - that is exactly the FIFO functionality. 243158115Sume */ 244158115Sumestatic void 245158115Sumecache_fifo_policy_update_item(struct cache_policy_ *policy, 246158115Sume struct cache_policy_item_ *item) 247158115Sume{ 248158115Sume 249158115Sume TRACE_IN(cache_fifo_policy_update_item); 250158115Sume /* policy and item arguments are ignored */ 251158115Sume TRACE_OUT(cache_fifo_policy_update_item); 252158115Sume} 253158115Sume 254158115Sumestruct cache_policy_ * 255194087Sdesinit_cache_fifo_policy(void) 256158115Sume{ 257158115Sume struct cache_queue_policy_ *retval; 258158115Sume 259158115Sume TRACE_IN(init_cache_fifo_policy); 260158115Sume retval = init_cache_queue_policy(); 261158115Sume retval->parent_data.update_item_func = cache_fifo_policy_update_item; 262158115Sume 263158115Sume TRACE_OUT(init_cache_fifo_policy); 264158115Sume return ((struct cache_policy_ *)retval); 265158115Sume} 266158115Sume 267158115Sumevoid 268158115Sumedestroy_cache_fifo_policy(struct cache_policy_ *policy) 269158115Sume{ 270158115Sume struct cache_queue_policy_ *queue_policy; 271158115Sume 272158115Sume TRACE_IN(destroy_cache_fifo_policy); 273158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 274158115Sume destroy_cache_queue_policy(queue_policy); 275158115Sume TRACE_OUT(destroy_cache_fifo_policy); 276158115Sume} 277158115Sume 278158115Sume/* 279158115Sume * Makes cache_queue_policy_ behave like LRU policy. On each update, cache 280158115Sume * element is moved to the end of the queue - so it would be deleted in last 281158115Sume * turn. That is exactly the LRU policy functionality. 282158115Sume */ 283158115Sumestatic void 284158115Sumecache_lru_policy_update_item(struct cache_policy_ *policy, 285158115Sume struct cache_policy_item_ *item) 286158115Sume{ 287158115Sume struct cache_queue_policy_ *queue_policy; 288158115Sume struct cache_queue_policy_item_ *queue_item; 289158115Sume 290158115Sume TRACE_IN(cache_lru_policy_update_item); 291158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 292158115Sume queue_item = (struct cache_queue_policy_item_ *)item; 293158115Sume 294158115Sume TAILQ_REMOVE(&queue_policy->head, queue_item, entries); 295158115Sume TAILQ_INSERT_TAIL(&queue_policy->head, queue_item, entries); 296158115Sume TRACE_OUT(cache_lru_policy_update_item); 297158115Sume} 298158115Sume 299158115Sumestruct cache_policy_ * 300194087Sdesinit_cache_lru_policy(void) 301158115Sume{ 302158115Sume struct cache_queue_policy_ *retval; 303158115Sume 304158115Sume TRACE_IN(init_cache_lru_policy); 305158115Sume retval = init_cache_queue_policy(); 306158115Sume retval->parent_data.update_item_func = cache_lru_policy_update_item; 307158115Sume 308158115Sume TRACE_OUT(init_cache_lru_policy); 309158115Sume return ((struct cache_policy_ *)retval); 310158115Sume} 311158115Sume 312158115Sumevoid 313158115Sumedestroy_cache_lru_policy(struct cache_policy_ *policy) 314158115Sume{ 315158115Sume struct cache_queue_policy_ *queue_policy; 316158115Sume 317158115Sume TRACE_IN(destroy_cache_lru_policy); 318158115Sume queue_policy = (struct cache_queue_policy_ *)policy; 319158115Sume destroy_cache_queue_policy(queue_policy); 320158115Sume TRACE_OUT(destroy_cache_lru_policy); 321158115Sume} 322158115Sume 323158115Sume/* 324158115Sume * LFU (least frequently used) policy implementation differs much from the 325158115Sume * LRU and FIFO (both based on cache_queue_policy_). Almost all cache_policy_ 326158115Sume * functions are implemented specifically for this policy. The idea of this 327158115Sume * policy is to represent frequency (real number) as the integer number and 328158115Sume * use it as the index in the array. Each array's element is 329158115Sume * the list of elements. For example, if we have the 100-elements 330158115Sume * array for this policy, the elements with frequency 0.1 (calls per-second) 331158115Sume * would be in 10th element of the array. 332158115Sume */ 333158115Sumestatic struct cache_policy_item_ * 334158115Sumecache_lfu_policy_create_item(void) 335158115Sume{ 336158115Sume struct cache_lfu_policy_item_ *retval; 337158115Sume 338158115Sume TRACE_IN(cache_lfu_policy_create_item); 339194104Sdes retval = calloc(1, 340194104Sdes sizeof(*retval)); 341158115Sume assert(retval != NULL); 342158115Sume 343158115Sume TRACE_OUT(cache_lfu_policy_create_item); 344158115Sume return ((struct cache_policy_item_ *)retval); 345158115Sume} 346158115Sume 347158115Sumestatic void 348158115Sumecache_lfu_policy_destroy_item(struct cache_policy_item_ *item) 349158115Sume{ 350158115Sume 351158115Sume TRACE_IN(cache_lfu_policy_destroy_item); 352158115Sume assert(item != NULL); 353158115Sume free(item); 354158115Sume TRACE_OUT(cache_lfu_policy_destroy_item); 355158115Sume} 356158115Sume 357158115Sume/* 358158115Sume * When placed in the LFU policy queue for the first time, the maximum 359158115Sume * frequency is assigned to the element 360158115Sume */ 361158115Sumestatic void 362158115Sumecache_lfu_policy_add_item(struct cache_policy_ *policy, 363158115Sume struct cache_policy_item_ *item) 364158115Sume{ 365158115Sume struct cache_lfu_policy_ *lfu_policy; 366158115Sume struct cache_lfu_policy_item_ *lfu_item; 367158115Sume 368158115Sume TRACE_IN(cache_lfu_policy_add_item); 369158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 370158115Sume lfu_item = (struct cache_lfu_policy_item_ *)item; 371158115Sume 372158115Sume lfu_item->frequency = CACHELIB_MAX_FREQUENCY - 1; 373158115Sume TAILQ_INSERT_HEAD(&(lfu_policy->groups[CACHELIB_MAX_FREQUENCY - 1]), 374158115Sume lfu_item, entries); 375158115Sume TRACE_OUT(cache_lfu_policy_add_item); 376158115Sume} 377158115Sume 378158115Sume/* 379158115Sume * On each update the frequency of the element is recalculated and, if it 380158115Sume * changed, the element would be moved to the another place in the array. 381158115Sume */ 382158115Sumestatic void 383158115Sumecache_lfu_policy_update_item(struct cache_policy_ *policy, 384158115Sume struct cache_policy_item_ *item) 385158115Sume{ 386158115Sume struct cache_lfu_policy_ *lfu_policy; 387158115Sume struct cache_lfu_policy_item_ *lfu_item; 388158115Sume int index; 389158115Sume 390158115Sume TRACE_IN(cache_lfu_policy_update_item); 391158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 392158115Sume lfu_item = (struct cache_lfu_policy_item_ *)item; 393158115Sume 394158115Sume /* 395158115Sume * We calculate the square of the request_count to avoid grouping of 396158115Sume * all elements at the start of the array (for example, if array size is 397158115Sume * 100 and most of its elements has frequency below the 0.01, they 398158115Sume * all would be grouped in the first array's position). Other 399158115Sume * techniques should be used here later to ensure, that elements are 400158115Sume * equally distributed in the array and not grouped in its beginning. 401158115Sume */ 402158115Sume if (lfu_item->parent_data.last_request_time.tv_sec != 403158115Sume lfu_item->parent_data.creation_time.tv_sec) { 404158115Sume index = ((double)lfu_item->parent_data.request_count * 405158115Sume (double)lfu_item->parent_data.request_count / 406158115Sume (lfu_item->parent_data.last_request_time.tv_sec - 407158115Sume lfu_item->parent_data.creation_time.tv_sec + 1)) * 408158115Sume CACHELIB_MAX_FREQUENCY; 409158115Sume if (index >= CACHELIB_MAX_FREQUENCY) 410158115Sume index = CACHELIB_MAX_FREQUENCY - 1; 411158115Sume } else 412158115Sume index = CACHELIB_MAX_FREQUENCY - 1; 413158115Sume 414158115Sume TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 415158115Sume entries); 416158115Sume lfu_item->frequency = index; 417158115Sume TAILQ_INSERT_HEAD(&(lfu_policy->groups[index]), lfu_item, entries); 418158115Sume 419158115Sume TRACE_OUT(cache_lfu_policy_update_item); 420158115Sume} 421158115Sume 422158115Sumestatic void 423158115Sumecache_lfu_policy_remove_item(struct cache_policy_ *policy, 424158115Sume struct cache_policy_item_ *item) 425158115Sume{ 426158115Sume struct cache_lfu_policy_ *lfu_policy; 427158115Sume struct cache_lfu_policy_item_ *lfu_item; 428158115Sume 429158115Sume TRACE_IN(cache_lfu_policy_remove_item); 430158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 431158115Sume lfu_item = (struct cache_lfu_policy_item_ *)item; 432158115Sume 433158115Sume TAILQ_REMOVE(&(lfu_policy->groups[lfu_item->frequency]), lfu_item, 434158115Sume entries); 435158115Sume TRACE_OUT(cache_lfu_policy_remove_item); 436158115Sume} 437158115Sume 438158115Sumestatic struct cache_policy_item_ * 439158115Sumecache_lfu_policy_get_first_item(struct cache_policy_ *policy) 440158115Sume{ 441158115Sume struct cache_lfu_policy_ *lfu_policy; 442158115Sume struct cache_lfu_policy_item_ *lfu_item; 443158115Sume int i; 444158115Sume 445158115Sume TRACE_IN(cache_lfu_policy_get_first_item); 446158115Sume lfu_item = NULL; 447158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 448158115Sume for (i = 0; i < CACHELIB_MAX_FREQUENCY; ++i) 449158115Sume if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 450158115Sume lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 451158115Sume break; 452158115Sume } 453158115Sume 454158115Sume TRACE_OUT(cache_lfu_policy_get_first_item); 455158115Sume return ((struct cache_policy_item_ *)lfu_item); 456158115Sume} 457158115Sume 458158115Sumestatic struct cache_policy_item_ * 459158115Sumecache_lfu_policy_get_last_item(struct cache_policy_ *policy) 460158115Sume{ 461158115Sume struct cache_lfu_policy_ *lfu_policy; 462158115Sume struct cache_lfu_policy_item_ *lfu_item; 463158115Sume int i; 464158115Sume 465158115Sume TRACE_IN(cache_lfu_policy_get_last_item); 466158115Sume lfu_item = NULL; 467158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 468158115Sume for (i = CACHELIB_MAX_FREQUENCY - 1; i >= 0; --i) 469158115Sume if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 470158115Sume lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 471158115Sume cache_lfu_policy_group_); 472158115Sume break; 473158115Sume } 474158115Sume 475158115Sume TRACE_OUT(cache_lfu_policy_get_last_item); 476158115Sume return ((struct cache_policy_item_ *)lfu_item); 477158115Sume} 478158115Sume 479158115Sumestatic struct cache_policy_item_ * 480158115Sumecache_lfu_policy_get_next_item(struct cache_policy_ *policy, 481158115Sume struct cache_policy_item_ *item) 482158115Sume{ 483158115Sume struct cache_lfu_policy_ *lfu_policy; 484158115Sume struct cache_lfu_policy_item_ *lfu_item; 485158115Sume int i; 486158115Sume 487158115Sume TRACE_IN(cache_lfu_policy_get_next_item); 488158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 489158115Sume lfu_item = TAILQ_NEXT((struct cache_lfu_policy_item_ *)item, entries); 490158115Sume if (lfu_item == NULL) 491158115Sume { 492158115Sume for (i = ((struct cache_lfu_policy_item_ *)item)->frequency + 1; 493158115Sume i < CACHELIB_MAX_FREQUENCY; ++i) { 494158115Sume if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 495158115Sume lfu_item = TAILQ_FIRST(&(lfu_policy->groups[i])); 496158115Sume break; 497158115Sume } 498158115Sume } 499158115Sume } 500158115Sume 501158115Sume TRACE_OUT(cache_lfu_policy_get_next_item); 502158115Sume return ((struct cache_policy_item_ *)lfu_item); 503158115Sume} 504158115Sume 505158115Sumestatic struct cache_policy_item_ * 506158115Sumecache_lfu_policy_get_prev_item(struct cache_policy_ *policy, 507158115Sume struct cache_policy_item_ *item) 508158115Sume{ 509158115Sume struct cache_lfu_policy_ *lfu_policy; 510158115Sume struct cache_lfu_policy_item_ *lfu_item; 511158115Sume int i; 512158115Sume 513158115Sume TRACE_IN(cache_lfu_policy_get_prev_item); 514158115Sume lfu_policy = (struct cache_lfu_policy_ *)policy; 515158115Sume lfu_item = TAILQ_PREV((struct cache_lfu_policy_item_ *)item, 516158115Sume cache_lfu_policy_group_, entries); 517158115Sume if (lfu_item == NULL) 518158115Sume { 519158115Sume for (i = ((struct cache_lfu_policy_item_ *)item)->frequency - 1; 520158115Sume i >= 0; --i) 521158115Sume if (!TAILQ_EMPTY(&(lfu_policy->groups[i]))) { 522158115Sume lfu_item = TAILQ_LAST(&(lfu_policy->groups[i]), 523158115Sume cache_lfu_policy_group_); 524158115Sume break; 525158115Sume } 526158115Sume } 527158115Sume 528158115Sume TRACE_OUT(cache_lfu_policy_get_prev_item); 529158115Sume return ((struct cache_policy_item_ *)lfu_item); 530158115Sume} 531158115Sume 532158115Sume/* 533158115Sume * Initializes the cache_policy_ structure by filling it with appropriate 534158115Sume * functions pointers 535158115Sume */ 536158115Sumestruct cache_policy_ * 537194087Sdesinit_cache_lfu_policy(void) 538158115Sume{ 539158115Sume int i; 540158115Sume struct cache_lfu_policy_ *retval; 541158115Sume 542158115Sume TRACE_IN(init_cache_lfu_policy); 543194104Sdes retval = calloc(1, 544194104Sdes sizeof(*retval)); 545158115Sume assert(retval != NULL); 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