1 /* $NetBSD: ctable.c,v 1.1.1.1 2009/06/23 10:08:59 tron Exp $ */ 2 3 /*++ 4 /* NAME 5 /* ctable 3 6 /* SUMMARY 7 /* cache manager 8 /* SYNOPSIS 9 /* #include <ctable.h> 10 /* 11 /* CTABLE *ctable_create(limit, create, delete, context) 12 /* int limit; 13 /* void *(*create)(const char *key, void *context); 14 /* void (*delete)(void *value, void *context); 15 /* void *context; 16 /* 17 /* const void *ctable_locate(cache, key) 18 /* CTABLE *cache; 19 /* const char *key; 20 /* 21 /* void ctable_free(cache) 22 /* CTABLE *cache; 23 /* 24 /* void ctable_walk(cache, action) 25 /* CTABLE *cache; 26 /* void (*action)(const char *key, const void *value); 27 /* DESCRIPTION 28 /* This module maintains multiple caches. Cache items are purged 29 /* automatically when the number of items exceeds a configurable 30 /* limit. Caches never shrink. Each cache entry consists of a 31 /* string-valued lookup key and a generic data pointer value. 32 /* 33 /* ctable_create() creates a cache with the specified size limit, and 34 /* returns a pointer to the result. The create and delete arguments 35 /* specify pointers to call-back functions that create a value, given 36 /* a key, and delete a given value, respectively. The context argument 37 /* is passed on to the call-back routines. 38 /* 39 /* ctable_locate() looks up or generates the value that corresponds to 40 /* the specified key, and returns that value. 41 /* 42 /* ctable_free() destroys the specified cache, including its contents. 43 /* 44 /* ctable_walk() iterates over all elements in the cache, and invokes 45 /* the action function for each cache element with the corresponding 46 /* key and value as arguments. This function is useful mainly for 47 /* cache performance debugging. 48 /* DIAGNOSTICS 49 /* Fatal errors: out of memory. Panic: interface violation. 50 /* LICENSE 51 /* .ad 52 /* .fi 53 /* The Secure Mailer license must be distributed with this software. 54 /* AUTHOR(S) 55 /* Wietse Venema 56 /* IBM T.J. Watson Research 57 /* P.O. Box 704 58 /* Yorktown Heights, NY 10598, USA 59 /*--*/ 60 61 /* System library. */ 62 63 #include <sys_defs.h> 64 #include <stdlib.h> 65 #include <stddef.h> 66 67 /* Utility library. */ 68 69 #include <msg.h> 70 #include <mymalloc.h> 71 #include <ring.h> 72 #include <htable.h> 73 #include <ctable.h> 74 75 /* 76 * Cache entries are kept in most-recently used order. We use a hash table 77 * to quickly locate cache entries. 78 */ 79 #define CTABLE_ENTRY struct ctable_entry 80 81 struct ctable_entry { 82 RING ring; /* MRU linkage */ 83 const char *key; /* lookup key */ 84 void *value; /* corresponding value */ 85 }; 86 87 #define RING_TO_CTABLE_ENTRY(ring_ptr) \ 88 RING_TO_APPL(ring_ptr, CTABLE_ENTRY, ring) 89 #define RING_PTR_OF(x) (&((x)->ring)) 90 91 struct ctable { 92 HTABLE *table; /* table with key, ctable_entry pairs */ 93 unsigned limit; /* max nr of entries */ 94 unsigned used; /* current nr of entries */ 95 CTABLE_CREATE_FN create; /* constructor */ 96 CTABLE_DELETE_FN delete; /* destructor */ 97 RING ring; /* MRU linkage */ 98 void *context; /* application context */ 99 }; 100 101 #define CTABLE_MIN_SIZE 5 102 103 /* ctable_create - create empty cache */ 104 105 CTABLE *ctable_create(int limit, CTABLE_CREATE_FN create, 106 CTABLE_DELETE_FN delete, void *context) 107 { 108 CTABLE *cache = (CTABLE *) mymalloc(sizeof(CTABLE)); 109 const char *myname = "ctable_create"; 110 111 if (limit < 1) 112 msg_panic("%s: bad cache limit: %d", myname, limit); 113 114 cache->table = htable_create(limit); 115 cache->limit = (limit < CTABLE_MIN_SIZE ? CTABLE_MIN_SIZE : limit); 116 cache->used = 0; 117 cache->create = create; 118 cache->delete = delete; 119 ring_init(RING_PTR_OF(cache)); 120 cache->context = context; 121 return (cache); 122 } 123 124 /* ctable_locate - look up or create cache item */ 125 126 const void *ctable_locate(CTABLE *cache, const char *key) 127 { 128 const char *myname = "ctable_locate"; 129 CTABLE_ENTRY *entry; 130 131 /* 132 * If the entry is not in the cache, make sure there is room for a new 133 * entry and install it at the front of the MRU chain. Otherwise, move 134 * the entry to the front of the MRU chain if it is not already there. 135 * All this means that the cache never shrinks. 136 */ 137 if ((entry = (CTABLE_ENTRY *) htable_find(cache->table, key)) == 0) { 138 if (cache->used >= cache->limit) { 139 entry = RING_TO_CTABLE_ENTRY(ring_pred(RING_PTR_OF(cache))); 140 if (msg_verbose) 141 msg_info("%s: purge entry key %s", myname, entry->key); 142 ring_detach(RING_PTR_OF(entry)); 143 cache->delete(entry->value, cache->context); 144 htable_delete(cache->table, entry->key, (void (*) (char *)) 0); 145 } else { 146 entry = (CTABLE_ENTRY *) mymalloc(sizeof(CTABLE_ENTRY)); 147 cache->used++; 148 } 149 entry->value = cache->create(key, cache->context); 150 entry->key = htable_enter(cache->table, key, (char *) entry)->key; 151 ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry)); 152 if (msg_verbose) 153 msg_info("%s: install entry key %s", myname, entry->key); 154 } else if (entry == RING_TO_CTABLE_ENTRY(ring_succ(RING_PTR_OF(cache)))) { 155 if (msg_verbose) 156 msg_info("%s: leave existing entry key %s", myname, entry->key); 157 } else { 158 ring_detach(RING_PTR_OF(entry)); 159 ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry)); 160 if (msg_verbose) 161 msg_info("%s: move existing entry key %s", myname, entry->key); 162 } 163 return (entry->value); 164 } 165 166 static CTABLE *ctable_free_cache; 167 168 /* ctable_free_callback - callback function */ 169 170 static void ctable_free_callback(char *ptr) 171 { 172 CTABLE_ENTRY *entry = (CTABLE_ENTRY *) ptr; 173 174 ctable_free_cache->delete(entry->value, ctable_free_cache->context); 175 myfree((char *) entry); 176 } 177 178 /* ctable_free - destroy cache and contents */ 179 180 void ctable_free(CTABLE *cache) 181 { 182 CTABLE *saved_cache = ctable_free_cache; 183 184 /* 185 * XXX the hash table does not pass application context so we have to 186 * store it in a global variable. 187 */ 188 ctable_free_cache = cache; 189 htable_free(cache->table, ctable_free_callback); 190 myfree((char *) cache); 191 ctable_free_cache = saved_cache; 192 } 193 194 /* ctable_walk - iterate over all cache entries */ 195 196 void ctable_walk(CTABLE *cache, void (*action) (const char *, const void *)) 197 { 198 RING *entry = RING_PTR_OF(cache); 199 200 /* Walking down the MRU chain is less work than using ht_walk(). */ 201 202 while ((entry = ring_succ(entry)) != RING_PTR_OF(cache)) 203 action((RING_TO_CTABLE_ENTRY(entry)->key), 204 (RING_TO_CTABLE_ENTRY(entry)->value)); 205 } 206 207 #ifdef TEST 208 209 /* 210 * Proof-of-concept test program. Read keys from stdin, ask for values not 211 * in cache. 212 */ 213 #include <unistd.h> 214 #include <vstream.h> 215 #include <vstring.h> 216 #include <vstring_vstream.h> 217 #include <msg_vstream.h> 218 219 #define STR(x) vstring_str(x) 220 221 static void *ask(const char *key, void *context) 222 { 223 VSTRING *data_buf = (VSTRING *) context; 224 225 vstream_printf("ask: %s = ", key); 226 vstream_fflush(VSTREAM_OUT); 227 if (vstring_get_nonl(data_buf, VSTREAM_IN) == VSTREAM_EOF) 228 vstream_longjmp(VSTREAM_IN, 1); 229 if (!isatty(0)) { 230 vstream_printf("%s\n", STR(data_buf)); 231 vstream_fflush(VSTREAM_OUT); 232 } 233 return (mystrdup(STR(data_buf))); 234 } 235 236 static void drop(void *data, void *unused_context) 237 { 238 myfree(data); 239 } 240 241 int main(int unused_argc, char **argv) 242 { 243 VSTRING *key_buf; 244 VSTRING *data_buf; 245 CTABLE *cache; 246 const char *value; 247 248 msg_vstream_init(argv[0], VSTREAM_ERR); 249 key_buf = vstring_alloc(100); 250 data_buf = vstring_alloc(100); 251 cache = ctable_create(1, ask, drop, (void *) data_buf); 252 msg_verbose = 1; 253 vstream_control(VSTREAM_IN, VSTREAM_CTL_EXCEPT, VSTREAM_CTL_END); 254 255 if (vstream_setjmp(VSTREAM_IN) == 0) { 256 for (;;) { 257 vstream_printf("key = "); 258 vstream_fflush(VSTREAM_OUT); 259 if (vstring_get_nonl(key_buf, VSTREAM_IN) == VSTREAM_EOF) 260 vstream_longjmp(VSTREAM_IN, 1); 261 if (!isatty(0)) { 262 vstream_printf("%s\n", STR(key_buf)); 263 vstream_fflush(VSTREAM_OUT); 264 } 265 value = ctable_locate(cache, STR(key_buf)); 266 vstream_printf("result: %s\n", value); 267 } 268 } 269 ctable_free(cache); 270 vstring_free(key_buf); 271 vstring_free(data_buf); 272 return (0); 273 } 274 275 #endif 276