Annotation of embedaddon/php/ext/gd/gdcache.c, revision 1.1
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 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>