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