home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / gd201.zip / gd-2.0.1 / gdcache.c < prev    next >
C/C++ Source or Header  |  2001-04-03  |  5KB  |  215 lines

  1. #include "gd.h"
  2. #include "gdhelpers.h"
  3.  
  4. #ifdef HAVE_LIBTTF
  5. #define NEED_CACHE 1
  6. #else
  7. #ifdef HAVE_LIBFREETYPE
  8. #define NEED_CACHE 1
  9. #endif
  10. #endif
  11.  
  12. #ifdef NEED_CACHE
  13.  
  14. /* 
  15.  * gdcache.c
  16.  *
  17.  * Caches of pointers to user structs in which the least-recently-used 
  18.  * element is replaced in the event of a cache miss after the cache has 
  19.  * reached a given size.
  20.  *
  21.  * John Ellson  (ellson@lucent.com)  Oct 31, 1997
  22.  *
  23.  * Test this with:
  24.  *               gcc -o gdcache -g -Wall -DTEST gdcache.c
  25.  *
  26.  * The cache is implemented by a singly-linked list of elements
  27.  * each containing a pointer to a user struct that is being managed by
  28.  * the cache.
  29.  *
  30.  * The head structure has a pointer to the most-recently-used
  31.  * element, and elements are moved to this position in the list each
  32.  * time they are used.  The head also contains pointers to three
  33.  * user defined functions: 
  34.  *              - a function to test if a cached userdata matches some keydata 
  35.  *              - a function to provide a new userdata struct to the cache 
  36.  *          if there has been a cache miss.
  37.  *              - a function to release a userdata struct when it is
  38.  *          no longer being managed by the cache
  39.  *
  40.  * In the event of a cache miss the cache is allowed to grow up to
  41.  * a specified maximum size.  After the maximum size is reached then
  42.  * the least-recently-used element is discarded to make room for the 
  43.  * new.  The most-recently-returned value is always left at the 
  44.  * beginning of the list after retrieval.
  45.  *
  46.  * In the current implementation the cache is traversed by a linear
  47.  * search from most-recent to least-recent.  This linear search
  48.  * probably limits the usefulness of this implementation to cache
  49.  * sizes of a few tens of elements.
  50.  */
  51.  
  52. #include "gdcache.h"
  53.  
  54. /*********************************************************/
  55. /* implementation                                        */
  56. /*********************************************************/
  57.  
  58.  
  59. /* create a new cache */
  60. gdCache_head_t *
  61. gdCacheCreate (
  62.         int size,
  63.         gdCacheTestFn_t gdCacheTest,
  64.         gdCacheFetchFn_t gdCacheFetch,
  65.         gdCacheReleaseFn_t gdCacheRelease)
  66. {
  67.   gdCache_head_t *head;
  68.  
  69.   head = (gdCache_head_t *) gdMalloc (sizeof (gdCache_head_t));
  70.   head->mru = NULL;
  71.   head->size = size;
  72.   head->gdCacheTest = gdCacheTest;
  73.   head->gdCacheFetch = gdCacheFetch;
  74.   head->gdCacheRelease = gdCacheRelease;
  75.   return head;
  76. }
  77.  
  78. void
  79. gdCacheDelete (gdCache_head_t * head)
  80. {
  81.   gdCache_element_t *elem, *prev;
  82.  
  83.   elem = head->mru;
  84.   while (elem)
  85.     {
  86.       (*(head->gdCacheRelease)) (elem->userdata);
  87.       prev = elem;
  88.       elem = elem->next;
  89.       gdFree ((char *) prev);
  90.     }
  91.   gdFree ((char *) head);
  92. }
  93.  
  94. void *
  95. gdCacheGet (gdCache_head_t * head, void *keydata)
  96. {
  97.   int i = 0;
  98.   gdCache_element_t *elem, *prev = NULL, *prevprev = NULL;
  99.   void *userdata;
  100.  
  101.   elem = head->mru;
  102.   while (elem)
  103.     {
  104.       if ((*(head->gdCacheTest)) (elem->userdata, keydata))
  105.     {
  106.       if (i)
  107.         {            /* if not already most-recently-used */
  108.           /* relink to top of list */
  109.           prev->next = elem->next;
  110.           elem->next = head->mru;
  111.           head->mru = elem;
  112.         }
  113.       return elem->userdata;
  114.     }
  115.       prevprev = prev;
  116.       prev = elem;
  117.       elem = elem->next;
  118.       i++;
  119.     }
  120.   userdata = (*(head->gdCacheFetch)) (&(head->error), keydata);
  121.   if (!userdata)
  122.     {
  123.       /* if there was an error in the fetch then don't cache */
  124.       return NULL;
  125.     }
  126.   if (i < head->size)
  127.     {                /* cache still growing - add new elem */
  128.       elem = (gdCache_element_t *) gdMalloc (sizeof (gdCache_element_t));
  129.     }
  130.   else
  131.     {                /* cache full - replace least-recently-used */
  132.       /* preveprev becomes new end of list */
  133.       prevprev->next = NULL;
  134.       elem = prev;
  135.       (*(head->gdCacheRelease)) (elem->userdata);
  136.     }
  137.   /* relink to top of list */
  138.   elem->next = head->mru;
  139.   head->mru = elem;
  140.   elem->userdata = userdata;
  141.   return userdata;
  142. }
  143.  
  144.  
  145.  
  146. /*********************************************************/
  147. /* test stub                                             */
  148. /*********************************************************/
  149.  
  150.  
  151. #ifdef TEST
  152.  
  153. #include <stdio.h>
  154.  
  155. typedef struct
  156. {
  157.   int key;
  158.   int value;
  159. }
  160. key_value_t;
  161.  
  162. static int
  163. cacheTest (void *map, void *key)
  164. {
  165.   return (((key_value_t *) map)->key == *(int *) key);
  166. }
  167.  
  168. static void *
  169. cacheFetch (char **error, void *key)
  170. {
  171.   key_value_t *map;
  172.  
  173.   map = (key_value_t *) gdMalloc (sizeof (key_value_t));
  174.   map->key = *(int *) key;
  175.   map->value = 3;
  176.  
  177.   *error = NULL;
  178.   return (void *) map;
  179. }
  180.  
  181. static void
  182. cacheRelease (void *map)
  183. {
  184.   gdFree ((char *) map);
  185. }
  186.  
  187. int
  188. main (char *argv[], int argc)
  189. {
  190.   gdCache_head_t *cacheTable;
  191.   int elem, key;
  192.  
  193.   cacheTable = gdCacheCreate (3, cacheTest, cacheFetch, cacheRelease);
  194.  
  195.   key = 20;
  196.   elem = *(int *) gdCacheGet (cacheTable, &key);
  197.   key = 30;
  198.   elem = *(int *) gdCacheGet (cacheTable, &key);
  199.   key = 40;
  200.   elem = *(int *) gdCacheGet (cacheTable, &key);
  201.   key = 50;
  202.   elem = *(int *) gdCacheGet (cacheTable, &key);
  203.   key = 30;
  204.   elem = *(int *) gdCacheGet (cacheTable, &key);
  205.   key = 30;
  206.   elem = *(int *) gdCacheGet (cacheTable, &key);
  207.  
  208.   gdCacheDelete (cacheTable);
  209.  
  210.   return 0;
  211. }
  212.  
  213. #endif /* TEST */
  214. #endif /* HAVE_LIBTTF */
  215.