Add svgtiny_list and convert gradient plotting to use it.

svn path=/trunk/libsvgtiny/; revision=4062

4 files changed, 187 insertions, 35 deletions

diff --git a/makefile b/makefile
index 817f906..582a93b 100644
--- a/makefile
+++ b/makefile
@@ -5,7 +5,7 @@
 # Copyright 2008 James Bursa <james@semichrome.net>
 #
 
-SOURCE = svgtiny.c svgtiny_gradient.c colors.c
+SOURCE = svgtiny.c svgtiny_gradient.c svgtiny_list.c colors.c
 HDRS = svgtiny.h svgtiny_internal.h
 
 CFLAGS = -std=c99 -W -Wall -Wundef -Wpointer-arith -Wcast-qual \
@@ -18,8 +18,8 @@ INSTALL = install
 ifeq ($(TARGET),riscos)
 GCCSDK_INSTALL_CROSSBIN ?= /home/riscos/cross/bin
 GCCSDK_INSTALL_ENV ?= /home/riscos/env
-CC ?= $(GCCSDK_INSTALL_CROSSBIN)/gcc
-AR ?= $(GCCSDK_INSTALL_CROSSBIN)/ar
+CC = $(GCCSDK_INSTALL_CROSSBIN)/gcc
+AR = $(GCCSDK_INSTALL_CROSSBIN)/ar
 CFLAGS += -Driscos -mpoke-function-name -I$(GCCSDK_INSTALL_ENV)/include \
 	-I$(GCCSDK_INSTALL_ENV)/include/libxml2
 LIBS = -L$(GCCSDK_INSTALL_ENV)/lib -lxml2 -lz
diff --git a/svgtiny_gradient.c b/svgtiny_gradient.c
index 31dba1e..be4f256 100644
--- a/svgtiny_gradient.c
+++ b/svgtiny_gradient.c
@@ -288,10 +288,10 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 	struct grad_point {
 		float x, y, r;
 	};
-	struct grad_point *pts = malloc(n * steps * sizeof pts[0]);
+	struct svgtiny_list *pts = svgtiny_list_create(
+			sizeof (struct grad_point));
 	if (!pts)
 		return svgtiny_OUT_OF_MEMORY;
-	unsigned int pts_count = 0;
 	float min_r = 1000;
 	unsigned int min_pt = 0;
 	for (unsigned int j = 0; j != n; ) {
@@ -314,14 +314,18 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 		r0 = ((x0_trans - gradient_x0) * gradient_dx +
 				(y0_trans - gradient_y0) * gradient_dy) /
 				gradient_norm_squared;
-		pts[pts_count].x = x0;
-		pts[pts_count].y = y0;
-		pts[pts_count].r = r0;
+		struct grad_point *point = svgtiny_list_push(pts);
+		if (!point) {
+			svgtiny_list_free(pts);
+			return svgtiny_OUT_OF_MEMORY;
+		}
+		point->x = x0;
+		point->y = y0;
+		point->r = r0;
 		if (r0 < min_r) {
 			min_r = r0;
-			min_pt = pts_count;
+			min_pt = svgtiny_list_size(pts) - 1;
 		}
-		pts_count++;
 
 		/* end point (x1, y1) */
 		if (segment_type == svgtiny_PATH_LINE) {
@@ -377,14 +381,18 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 					(y_trans - gradient_y0) * gradient_dy) /
 					gradient_norm_squared;
 			fprintf(stderr, "(%g %g [%g]) ", x, y, r);
-			pts[pts_count].x = x;
-			pts[pts_count].y = y;
-			pts[pts_count].r = r;
+			struct grad_point *point = svgtiny_list_push(pts);
+			if (!point) {
+				svgtiny_list_free(pts);
+				return svgtiny_OUT_OF_MEMORY;
+			}
+			point->x = x;
+			point->y = y;
+			point->r = r;
 			if (r < min_r) {
 				min_r = r;
-				min_pt = pts_count;
+				min_pt = svgtiny_list_size(pts) - 1;
 			}
-			pts_count++;
 		}
 		fprintf(stderr, "\n");
 
@@ -392,8 +400,8 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 		x0 = x1;
 		y0 = y1;
 	}
-	fprintf(stderr, "pts_count %i, min_pt %i, min_r %.3f\n",
-			pts_count, min_pt, min_r);
+	fprintf(stderr, "pts size %i, min_pt %i, min_r %.3f\n",
+			svgtiny_list_size(pts), min_pt, min_r);
 
 	/* render triangles */
 	unsigned int stop_count = state->linear_gradient_stop_count;
@@ -407,10 +415,13 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 	blue0 = blue1 = svgtiny_BLUE(state->gradient_stop[0].color);
 	unsigned int t, a, b;
 	t = min_pt;
-	a = (min_pt + 1) % pts_count;
-	b = min_pt == 0 ? pts_count - 1 : min_pt - 1;
+	a = (min_pt + 1) % svgtiny_list_size(pts);
+	b = min_pt == 0 ? svgtiny_list_size(pts) - 1 : min_pt - 1;
 	while (a != b) {
-		float mean_r = (pts[t].r + pts[a].r + pts[b].r) / 3;
+		struct grad_point *point_t = svgtiny_list_get(pts, t);
+		struct grad_point *point_a = svgtiny_list_get(pts, a);
+		struct grad_point *point_b = svgtiny_list_get(pts, b);
+		float mean_r = (point_t->r + point_a->r + point_b->r) / 3;
 		/*fprintf(stderr, "triangle: t %i %.3f a %i %.3f b %i %.3f "
 				"mean_r %.3f\n",
 				t, pts[t].r, a, pts[a].r, b, pts[b].r,
@@ -436,14 +447,14 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 		if (!p)
 			return svgtiny_OUT_OF_MEMORY;
 		p[0] = svgtiny_PATH_MOVE;
-		p[1] = pts[t].x;
-		p[2] = pts[t].y;
+		p[1] = point_t->x;
+		p[2] = point_t->y;
 		p[3] = svgtiny_PATH_LINE;
-		p[4] = pts[a].x;
-		p[5] = pts[a].y;
+		p[4] = point_a->x;
+		p[5] = point_a->y;
 		p[6] = svgtiny_PATH_LINE;
-		p[7] = pts[b].x;
-		p[8] = pts[b].y;
+		p[7] = point_b->x;
+		p[8] = point_b->y;
 		p[9] = svgtiny_PATH_CLOSE;
 		svgtiny_transform_path(p, 10, state);
 		struct svgtiny_shape *shape = svgtiny_add_shape(state);
@@ -472,12 +483,12 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 		shape->stroke = svgtiny_RGB(0, 0, 0xff);
 		#endif
 		state->diagram->shape_count++;
-		if (pts[a].r < pts[b].r) {
+		if (point_a->r < point_b->r) {
 			t = a;
-			a = (a + 1) % pts_count;
+			a = (a + 1) % svgtiny_list_size(pts);
 		} else {
 			t = b;
-			b = b == 0 ? pts_count - 1 : b - 1;
+			b = b == 0 ? svgtiny_list_size(pts) - 1 : b - 1;
 		}
 	}
 
@@ -510,19 +521,20 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 
 	/* render triangle vertices with r values for debugging */
 	#ifdef GRADIENT_DEBUG
-	for (unsigned int i = 0; i != pts_count; i++) {
+	for (unsigned int i = 0; i != pts->size; i++) {
+		struct grad_point *point = svgtiny_list_get(pts, i);
 		struct svgtiny_shape *shape = svgtiny_add_shape(state);
 		if (!shape)
 			return svgtiny_OUT_OF_MEMORY;
 		char *text = malloc(20);
 		if (!text)
 			return svgtiny_OUT_OF_MEMORY;
-		sprintf(text, "%i=%.3f", i, pts[i].r);
+		sprintf(text, "%i=%.3f", i, point->r);
 		shape->text = text;
-		shape->text_x = state->ctm.a * pts[i].x +
-				state->ctm.c * pts[i].y + state->ctm.e;
-		shape->text_y = state->ctm.b * pts[i].x +
-				state->ctm.d * pts[i].y + state->ctm.f;
+		shape->text_x = state->ctm.a * point->x +
+				state->ctm.c * point->y + state->ctm.e;
+		shape->text_y = state->ctm.b * point->x +
+				state->ctm.d * point->y + state->ctm.f;
 		shape->fill = svgtiny_RGB(0, 0, 0);
 		shape->stroke = svgtiny_TRANSPARENT;
 		state->diagram->shape_count++;
@@ -542,8 +554,12 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 		shape->path_length = n;
 		shape->fill = svgtiny_TRANSPARENT;
 		state->diagram->shape_count++;
+	} else {
+		free(p);
 	}
 
+	svgtiny_list_free(pts);
+
 	return svgtiny_OK;
 }
 
diff --git a/svgtiny_internal.h b/svgtiny_internal.h
index a729f25..f07f430 100644
--- a/svgtiny_internal.h
+++ b/svgtiny_internal.h
@@ -47,6 +47,7 @@ struct svgtiny_parse_state {
 	} gradient_transform;
 };
 
+struct svgtiny_list;
 
 /* svgtiny.c */
 float svgtiny_parse_length(const char *s, int viewport_size,
@@ -65,6 +66,16 @@ svgtiny_code svgtiny_add_path_linear_gradient(float *p, unsigned int n,
 		struct svgtiny_parse_state *state);
 xmlNode *svgtiny_find_element_by_id(xmlNode *node, const char *id);
 
+/* svgtiny_list.c */
+struct svgtiny_list *svgtiny_list_create(size_t item_size);
+unsigned int svgtiny_list_size(struct svgtiny_list *list);
+svgtiny_code svgtiny_list_resize(struct svgtiny_list *list,
+		unsigned int new_size);
+void *svgtiny_list_get(struct svgtiny_list *list,
+		unsigned int i);
+void *svgtiny_list_push(struct svgtiny_list *list);
+void svgtiny_list_free(struct svgtiny_list *list);
+
 /* colors.gperf */
 const struct svgtiny_named_color *
 		svgtiny_color_lookup(register const char *str,
diff --git a/svgtiny_list.c b/svgtiny_list.c
new file mode 100644
index 0000000..53cfb34
--- /dev/null
+++ b/svgtiny_list.c
@@ -0,0 +1,125 @@
+/*
+ * This file is part of Libsvgtiny
+ * Licensed under the MIT License,
+ *                http://opensource.org/licenses/mit-license.php
+ * Copyright 2008 James Bursa <james@semichrome.net>
+ */
+
+/**
+ * A svgtiny_list is a managed array of objects. It grows in chunks to reduce
+ * calls to realloc(), but keeps wasted space low.
+ */
+
+#include <assert.h>
+#include "svgtiny.h"
+#include "svgtiny_internal.h"
+
+
+struct svgtiny_list {
+	unsigned int size;	/* number of slots used */
+	unsigned int allocated;	/* number of slots allocated (>= size) */
+	size_t item_size;	/* size of each slot / bytes */
+	char *items;		/* array of slots */
+};
+
+
+/**
+ * Create an empty svgtiny_list.
+ */
+
+struct svgtiny_list *svgtiny_list_create(size_t item_size)
+{
+	struct svgtiny_list *list = malloc(sizeof *list);
+	if (!list)
+		return 0;
+	list->size = 0;
+	list->allocated = 0;
+	list->item_size = item_size;
+	list->items = 0;
+	return list;
+}
+
+
+/**
+ * Return the number of objects in a list.
+ */
+
+unsigned int svgtiny_list_size(struct svgtiny_list *list)
+{
+	return list->size;
+}
+
+
+/**
+ * Set the number of objects in a list. If the size is increased, the new
+ * objects are not initialized in any way.
+ *
+ * The allocation size formula is taken from Python's list:
+ * http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup
+ *
+ * Objects may have moved after this call. Use svgtiny_list_get() to get new
+ * pointers.
+ */
+
+svgtiny_code svgtiny_list_resize(struct svgtiny_list *list,
+		unsigned int new_size)
+{
+	unsigned int new_allocated;
+	void *new_items;
+
+	if (new_size <= list->allocated) {
+		list->size = new_size;
+		return svgtiny_OK;
+	}
+
+	new_allocated = (new_size >> 3) + (new_size < 9 ? 3 : 6) + new_size;
+	if (new_size == 0)
+		new_allocated = 0;
+	new_items = realloc(list->items, new_allocated * list->item_size);
+	if (!new_items)
+		return svgtiny_OUT_OF_MEMORY;
+
+	list->size = new_size;
+	list->allocated = new_allocated;
+	list->items = new_items;
+
+	return svgtiny_OK;
+}
+
+
+/**
+ * Return a pointer to an object in a list.
+ */
+
+void *svgtiny_list_get(struct svgtiny_list *list,
+		unsigned int i)
+{
+	assert(i < list->size);
+	return (void *) (list->items + i * list->item_size);
+}
+
+
+/**
+ * Add space for one object to a list and return a pointer to it.
+ */
+
+void *svgtiny_list_push(struct svgtiny_list *list)
+{
+	svgtiny_code code;
+	code = svgtiny_list_resize(list, list->size + 1);
+	if (code != svgtiny_OK)
+		return 0;
+	return svgtiny_list_get(list, list->size - 1);
+}
+
+
+/**
+ * Free an entire list.
+ */
+
+void svgtiny_list_free(struct svgtiny_list *list)
+{
+	free(list->items);
+	free(list);
+}
+