diff options
Diffstat (limited to 'Build/source/libs/gd/libgd-2.1.1/src/gdcache.c')
-rw-r--r-- | Build/source/libs/gd/libgd-2.1.1/src/gdcache.c | 224 |
1 files changed, 224 insertions, 0 deletions
diff --git a/Build/source/libs/gd/libgd-2.1.1/src/gdcache.c b/Build/source/libs/gd/libgd-2.1.1/src/gdcache.c new file mode 100644 index 00000000000..b264d6ef859 --- /dev/null +++ b/Build/source/libs/gd/libgd-2.1.1/src/gdcache.c @@ -0,0 +1,224 @@ +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include "gd.h" +#include "gdhelpers.h" + +#ifdef HAVE_LIBTTF +# define NEED_CACHE 1 +#else +#ifdef HAVE_LIBFREETYPE +# define NEED_CACHE 1 +#endif +#endif + +#ifdef NEED_CACHE + +/* + * gdcache.c + * + * Caches of pointers to user structs in which the least-recently-used + * element is replaced in the event of a cache miss after the cache has + * reached a given size. + * + * John Ellson (ellson@graphviz.org) Oct 31, 1997 + * + * Test this with: + * gcc -o gdcache -g -Wall -DTEST gdcache.c + * + * The cache is implemented by a singly-linked list of elements + * each containing a pointer to a user struct that is being managed by + * the cache. + * + * The head structure has a pointer to the most-recently-used + * element, and elements are moved to this position in the list each + * time they are used. The head also contains pointers to three + * user defined functions: + * - a function to test if a cached userdata matches some keydata + * - a function to provide a new userdata struct to the cache + * if there has been a cache miss. + * - a function to release a userdata struct when it is + * no longer being managed by the cache + * + * In the event of a cache miss the cache is allowed to grow up to + * a specified maximum size. After the maximum size is reached then + * the least-recently-used element is discarded to make room for the + * new. The most-recently-returned value is always left at the + * beginning of the list after retrieval. + * + * In the current implementation the cache is traversed by a linear + * search from most-recent to least-recent. This linear search + * probably limits the usefulness of this implementation to cache + * sizes of a few tens of elements. + */ + +#include "gdcache.h" + +/*********************************************************/ +/* implementation */ +/*********************************************************/ + +/* create a new cache */ +gdCache_head_t *gdCacheCreate(int size, + gdCacheTestFn_t gdCacheTest, + gdCacheFetchFn_t gdCacheFetch, + gdCacheReleaseFn_t gdCacheRelease) +{ + gdCache_head_t *head; + + head = (gdCache_head_t *)gdMalloc(sizeof(gdCache_head_t)); + if(!head) { + return NULL; + } + + head->mru = NULL; + head->size = size; + head->gdCacheTest = gdCacheTest; + head->gdCacheFetch = gdCacheFetch; + head->gdCacheRelease = gdCacheRelease; + + return head; +} + +void gdCacheDelete(gdCache_head_t *head) +{ + gdCache_element_t *elem, *prev; + + elem = head->mru; + while(elem) { + (*(head->gdCacheRelease))(elem->userdata); + prev = elem; + elem = elem->next; + gdFree((char *)prev); + } + + gdFree((char *)head); +} + +void * gdCacheGet(gdCache_head_t *head, void *keydata) +{ + int i = 0; + gdCache_element_t *elem, *prev = NULL, *prevprev = NULL; + void *userdata; + + elem = head->mru; + while(elem) { + if((*(head->gdCacheTest))(elem->userdata, keydata)) { + if(i) { + /* if not already most-recently-used */ + /* relink to top of list */ + prev->next = elem->next; + elem->next = head->mru; + head->mru = elem; + } + + return elem->userdata; + } + + prevprev = prev; + prev = elem; + elem = elem->next; + i++; + } + + userdata = (*(head->gdCacheFetch))(&(head->error), keydata); + if(!userdata) { + /* if there was an error in the fetch then don't cache */ + return NULL; + } + + if(i < head->size) { + /* cache still growing - add new elem */ + elem = (gdCache_element_t *)gdMalloc(sizeof(gdCache_element_t)); + if(!elem) { + (*(head->gdCacheRelease)) (userdata); + return NULL; + } + } else { + /* cache full - replace least-recently-used */ + /* preveprev becomes new end of list */ + prevprev->next = NULL; + elem = prev; + (*(head->gdCacheRelease))(elem->userdata); + } + + /* relink to top of list */ + elem->next = head->mru; + head->mru = elem; + elem->userdata = userdata; + + return userdata; +} + +/*********************************************************/ +/* test stub */ +/*********************************************************/ + +#ifdef TEST + +#include <stdio.h> + +typedef struct { + int key; + int value; +} +key_value_t; + +static int cacheTest(void *map, void *key) +{ + return (((key_value_t *)map)->key == *(int *)key); +} + +static void *cacheFetch(char **error, void *key) +{ + key_value_t *map; + + map = (key_value_t *)gdMalloc(sizeof(key_value_t)); + if (!map) { + *error = "gdMalloc failed"; + return NULL; + } + map->key = *(int *)key; + map->value = 3; + + *error = NULL; + + return (void *)map; +} + +static void cacheRelease(void *map) +{ + gdFree((char *)map); +} + +int main(char *argv[], int argc) +{ + gdCache_head_t *cacheTable; + int elem, key; + + cacheTable = gdCacheCreate(3, cacheTest, cacheFetch, cacheRelease); + if(!cacheTable) { + exit(1); + } + + key = 20; + elem = *(int *)gdCacheGet(cacheTable, &key); + key = 30; + elem = *(int *)gdCacheGet(cacheTable, &key); + key = 40; + elem = *(int *)gdCacheGet(cacheTable, &key); + key = 50; + elem = *(int *)gdCacheGet(cacheTable, &key); + key = 30; + elem = *(int *)gdCacheGet(cacheTable, &key); + key = 30; + elem = *(int *)gdCacheGet(cacheTable, &key); + + gdCacheDelete(cacheTable); + + return 0; +} + +#endif /* TEST */ +#endif /* NEED_CACHE */ |