Back to index

php5  5.3.10
gdcache.c
Go to the documentation of this file.
00001 /*
00002  * $Id: gdcache.c 307588 2011-01-19 15:23:07Z pajoye $
00003  *
00004  * Caches of pointers to user structs in which the least-recently-used
00005  * element is replaced in the event of a cache miss after the cache has
00006  * reached a given size.
00007  *
00008  * John Ellson  (ellson@lucent.com)  Oct 31, 1997
00009  *
00010  * Test this with:
00011  *             gcc -o gdcache -g -Wall -DTEST gdcache.c
00012  *
00013  * The cache is implemented by a singly-linked list of elements
00014  * each containing a pointer to a user struct that is being managed by
00015  * the cache.
00016  *
00017  * The head structure has a pointer to the most-recently-used
00018  * element, and elements are moved to this position in the list each
00019  * time they are used.  The head also contains pointers to three
00020  * user defined functions:
00021  *            - a function to test if a cached userdata matches some keydata
00022  *            - a function to provide a new userdata struct to the cache
00023  *          if there has been a cache miss.
00024  *            - a function to release a userdata struct when it is
00025  *          no longer being managed by the cache
00026  *
00027  * In the event of a cache miss the cache is allowed to grow up to
00028  * a specified maximum size.  After the maximum size is reached then
00029  * the least-recently-used element is discarded to make room for the
00030  * new.  The most-recently-returned value is always left at the
00031  * beginning of the list after retrieval.
00032  *
00033  * In the current implementation the cache is traversed by a linear
00034  * search from most-recent to least-recent.  This linear search
00035  * probably limits the usefulness of this implementation to cache
00036  * sizes of a few tens of elements.
00037  */
00038 
00039 #include "php.h"
00040 
00041 /* This just seems unessacary */
00042 #if PHP_WIN32
00043 #define ENABLE_GD_TTF
00044 #else
00045 #include <php_config.h>
00046 #endif
00047 #if HAVE_LIBFREETYPE && !defined(HAVE_GD_CACHE_CREATE)
00048 
00049 #include "gdcache.h"
00050 
00051 /*********************************************************/
00052 /* implementation                                        */
00053 /*********************************************************/
00054 
00055 
00056 /* create a new cache */
00057 gdCache_head_t *
00058 gdCacheCreate(
00059        int                                size,
00060        gdCacheTestFn_t             gdCacheTest,
00061        gdCacheFetchFn_t     gdCacheFetch,
00062        gdCacheReleaseFn_t   gdCacheRelease )
00063 {
00064        gdCache_head_t *head;
00065 
00066        head = (gdCache_head_t *)pemalloc(sizeof(gdCache_head_t), 1);
00067        head->mru = NULL;
00068        head->size = size;
00069        head->gdCacheTest = gdCacheTest;
00070        head->gdCacheFetch = gdCacheFetch;
00071        head->gdCacheRelease = gdCacheRelease;
00072        return head;
00073 }
00074 
00075 void
00076 gdCacheDelete( gdCache_head_t *head )
00077 {
00078        gdCache_element_t *elem, *prev;
00079 
00080        elem = head->mru;
00081        while(elem) {
00082               (*(head->gdCacheRelease))(elem->userdata);
00083               prev = elem;
00084               elem = elem->next;
00085               pefree((char *)prev, 1);
00086        }
00087        pefree((char *)head, 1);
00088 }
00089 
00090 void *
00091 gdCacheGet( gdCache_head_t *head, void *keydata )
00092 {
00093        int                         i=0;
00094        gdCache_element_t *elem, *prev = NULL, *prevprev = NULL;
00095        void                 *userdata;
00096 
00097        elem = head->mru;
00098        while(elem) {
00099               if ((*(head->gdCacheTest))(elem->userdata, keydata)) {
00100                      if (i) {  /* if not already most-recently-used */
00101                             /* relink to top of list */
00102                             prev->next = elem->next;
00103                             elem->next = head->mru;
00104                             head->mru = elem;
00105                      }
00106                      return elem->userdata;
00107               }
00108               prevprev = prev;
00109               prev = elem;
00110               elem = elem->next;
00111               i++;
00112        }
00113        userdata = (*(head->gdCacheFetch))(&(head->error), keydata);
00114        if (! userdata) {
00115               /* if there was an error in the fetch then don't cache */
00116               return NULL;
00117        }
00118        if (i < head->size) {  /* cache still growing - add new elem */
00119               elem = (gdCache_element_t *)pemalloc(sizeof(gdCache_element_t), 1);
00120        }
00121        else { /* cache full - replace least-recently-used */
00122               /* preveprev becomes new end of list */
00123               prevprev->next = NULL;
00124               elem = prev;
00125               (*(head->gdCacheRelease))(elem->userdata);
00126        }
00127        /* relink to top of list */
00128        elem->next = head->mru;
00129        head->mru = elem;
00130        elem->userdata = userdata;
00131        return userdata;
00132 }
00133 
00134 
00135 
00136 /*********************************************************/
00137 /* test stub                                             */
00138 /*********************************************************/
00139 
00140 
00141 #ifdef GDCACHE_TEST
00142 
00143 #include <stdio.h>
00144 
00145 typedef struct {
00146        int key;
00147        int value;
00148 } key_value_t;
00149 
00150 static int
00151 cacheTest( void *map, void *key )
00152 {
00153        return (((key_value_t *)map)->key == *(int *)key);
00154 }
00155 
00156 static void *
00157 cacheFetch( char **error, void *key )
00158 {
00159        key_value_t *map;
00160 
00161        map = (key_value_t *)malloc(sizeof(key_value_t));
00162        if (map == NULL) {
00163               return NULL;
00164        }
00165        map->key = *(int *)key;
00166        map->value = 3;
00167 
00168        *error = NULL;
00169        return (void *)map;
00170 }
00171 
00172 static void
00173 cacheRelease( void *map)
00174 {
00175        free( (char *)map );
00176 }
00177 
00178 int
00179 main(char *argv[], int argc)
00180 {
00181        gdCache_head_t       *cacheTable;
00182        int                  elem, key;
00183 
00184        cacheTable = gdCacheCreate(3, cacheTest, cacheFetch, cacheRelease);
00185 
00186        key = 20;
00187        elem = *(int *)gdCacheGet(cacheTable, &key);
00188        key = 30;
00189        elem = *(int *)gdCacheGet(cacheTable, &key);
00190        key = 40;
00191        elem = *(int *)gdCacheGet(cacheTable, &key);
00192        key = 50;
00193        elem = *(int *)gdCacheGet(cacheTable, &key);
00194        key = 30;
00195        elem = *(int *)gdCacheGet(cacheTable, &key);
00196        key = 30;
00197        elem = *(int *)gdCacheGet(cacheTable, &key);
00198 
00199        gdCacheDelete(cacheTable);
00200 
00201        return 0;
00202 }
00203 
00204 #endif
00205 
00206 #endif /* ENABLE_GD_TTF */