external/ibm-public/postfix/dist/src/util/ctable.c

   1 /*      $NetBSD$        */
   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