Source

gd-libgd / src / gdcache.c

pierre b0243fe 
mattias 0ee6355 
pierre b0243fe 

pierre 22d55c5 


pierre 6223ff8 
mattias 0ee6355 
pierre 22d55c5 

mattias 0ee6355 
pierre 22d55c5 



pierre 6223ff8 
pierrejoye e20413b 
pierre 6223ff8 

pierrejoye e20413b 

pierre 6223ff8 

pierre 871d0d8 
pierre 6223ff8 

pierre 1cdea74 
pierre 6223ff8 







pierrejoye e20413b 


pierre 6223ff8 
pierre 1cdea74 
pierre 6223ff8 



pierrejoye e20413b 

pierre 6223ff8 














mattias 0ee6355 
pierrejoye e20413b 


pierre 6223ff8 
mattias 0ee6355 
pierre 1cdea74 
mattias 0ee6355 

pajoye 1dbbe05 


mattias 0ee6355 






pierre 6223ff8 

mattias 0ee6355 
pierre 6223ff8 
mattias 0ee6355 










pierre 6223ff8 

mattias 0ee6355 
pierre 6223ff8 
mattias 0ee6355 



























pierre 6223ff8 

mattias 0ee6355 





pierrejoye e20413b 
mattias 0ee6355 






pierre 6223ff8 
mattias 0ee6355 






pierre 6223ff8 








pierrejoye e20413b 
mattias 0ee6355 

pierre 1cdea74 

pierre 6223ff8 
mattias 0ee6355 
pierre 6223ff8 
mattias 0ee6355 
pierre 6223ff8 

mattias 0ee6355 
pierre 6223ff8 
mattias 0ee6355 


tabe 04bcbd5 



mattias 0ee6355 

pierre 6223ff8 
mattias 0ee6355 
pierre 6223ff8 
mattias 0ee6355 
pierre 6223ff8 

mattias 0ee6355 
pierre 6223ff8 
mattias 0ee6355 
pierre 6223ff8 

mattias 0ee6355 
pierre 6223ff8 
mattias 0ee6355 

pierre 1cdea74 
mattias 0ee6355 

pajoye 1dbbe05 

pierre 1cdea74 
mattias 0ee6355 















pierre 6223ff8 


tabe 3316a4d 
#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 */