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 27 #ifndef __NSCD_CACHEPLCS_H__ 28 #define __NSCD_CACHEPLCS_H__ 29 30 #include <sys/queue.h> 31 32 /* common policy definitions */ 33 #define CACHELIB_MAX_FREQUENCY 100 34 35 /* 36 * cache_policy_item_ represents some abstract cache element in the policy 37 * queue. connected_item pointers to the corresponding cache_policy_item_ in 38 * another policy queue. 39 */ 40 struct cache_policy_item_ { 41 char *key; 42 size_t key_size; 43 44 size_t request_count; 45 struct timeval last_request_time; 46 struct timeval creation_time; 47 48 struct cache_policy_item_ *connected_item; 49 }; 50 51 /* 52 * cache_policy_ represents an abstract policy queue. It can be customized by 53 * setting appropriate function pointers 54 */ 55 struct cache_policy_ { 56 struct cache_policy_item_* (*create_item_func)(void); 57 void (*destroy_item_func)(struct cache_policy_item_ *); 58 59 void (*add_item_func)(struct cache_policy_ *, 60 struct cache_policy_item_ *); 61 void (*remove_item_func)(struct cache_policy_ *, 62 struct cache_policy_item_ *); 63 void (*update_item_func)(struct cache_policy_ *, 64 struct cache_policy_item_ *); 65 66 struct cache_policy_item_ *(*get_first_item_func)( 67 struct cache_policy_ *); 68 struct cache_policy_item_ *(*get_last_item_func)( 69 struct cache_policy_ *); 70 struct cache_policy_item_ *(*get_next_item_func)( 71 struct cache_policy_ *, struct cache_policy_item_ *); 72 struct cache_policy_item_ *(*get_prev_item_func)( 73 struct cache_policy_ *, struct cache_policy_item_ *); 74 }; 75 76 /* 77 * LFU cache policy item "inherited" from cache_policy_item_ structure 78 */ 79 struct cache_lfu_policy_item_ { 80 struct cache_policy_item_ parent_data; 81 int frequency; 82 83 TAILQ_ENTRY(cache_lfu_policy_item_) entries; 84 }; 85 86 TAILQ_HEAD(cache_lfu_policy_group_, cache_lfu_policy_item_); 87 88 /* 89 * LFU policy queue "inherited" from cache_policy_. 90 */ 91 struct cache_lfu_policy_ { 92 struct cache_policy_ parent_data; 93 struct cache_lfu_policy_group_ groups[CACHELIB_MAX_FREQUENCY]; 94 }; 95 96 /* 97 * LRU and FIFO policies item "inherited" from cache_policy_item_ 98 */ 99 struct cache_queue_policy_item_ { 100 struct cache_policy_item_ parent_data; 101 TAILQ_ENTRY(cache_queue_policy_item_) entries; 102 }; 103 104 /* 105 * LRU and FIFO policies "inherited" from cache_policy_ 106 */ 107 struct cache_queue_policy_ { 108 struct cache_policy_ parent_data; 109 TAILQ_HEAD(cache_queue_policy_head_, cache_queue_policy_item_) head; 110 }; 111 112 typedef struct cache_queue_policy_ cache_fifo_policy_; 113 typedef struct cache_queue_policy_ cache_lru_policy_; 114 115 /* fifo policy routines */ 116 struct cache_policy_ *init_cache_fifo_policy(void); 117 void destroy_cache_fifo_policy(struct cache_policy_ *); 118 119 /* lru policy routines */ 120 struct cache_policy_ *init_cache_lru_policy(void); 121 void destroy_cache_lru_policy(struct cache_policy_ *); 122 123 /* lfu policy routines */ 124 struct cache_policy_ *init_cache_lfu_policy(void); 125 void destroy_cache_lfu_policy(struct cache_policy_ *); 126 127 #endif 128