summaryrefslogtreecommitdiff
path: root/Build/source/libs/gd/libgd-src/src/gdcache.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/gd/libgd-src/src/gdcache.c')
-rw-r--r--Build/source/libs/gd/libgd-src/src/gdcache.c224
1 files changed, 224 insertions, 0 deletions
diff --git a/Build/source/libs/gd/libgd-src/src/gdcache.c b/Build/source/libs/gd/libgd-src/src/gdcache.c
new file mode 100644
index 00000000000..b264d6ef859
--- /dev/null
+++ b/Build/source/libs/gd/libgd-src/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 */