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