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