From b8a31a795a8ef4dad884a0bb9292cdc6d7f72cb6 Mon Sep 17 00:00:00 2001
From: Peter Wu <lekensteyn@gmail.com>
Date: Sat, 29 Sep 2012 00:11:31 +0200
Subject: xcbviewfs: use array instead of list

I know the number of colors on beforehand, no need to use pointers to a next
list item. Improves performance by almost twice.
---
 xcbviewfs.c | 40 +++++++++++++++++-----------------------
 1 file changed, 17 insertions(+), 23 deletions(-)

diff --git a/xcbviewfs.c b/xcbviewfs.c
index 2b1a928..74eb284 100644
--- a/xcbviewfs.c
+++ b/xcbviewfs.c
@@ -288,12 +288,10 @@ static void xpm_parse_color_line(char *line, uint8_t color[3]) {
 	print_once("No color found\n");
 }
 
-/* better use a RB tree instead of a linked list... */
-typedef struct _ColorList ColorList;
-struct _ColorList {
+typedef struct _ColorPair ColorPair;
+struct _ColorPair {
 	unsigned int key; /* assume that the key has less or equal bytes */
 	uint8_t color[3]; /* RGB */
-	ColorList *next;
 };
 
 static int load_xpm_image(char *filename, unsigned char **data,
@@ -332,21 +330,15 @@ static int load_xpm_image(char *filename, unsigned char **data,
 		bail(free_xpm, "Cannot allocate memory for image\n");
 	}
 
-	/* horrible performance, but ok... */
-	ColorList dummy_color = {0};
-	ColorList *colors = &dummy_color;
+	ColorPair *colors = malloc(ncolors * sizeof(ColorPair));
 	for (i=1; i<=ncolors; i++) {
 		char *line = xpm_data[i];
-		ColorList *color = malloc(sizeof(ColorList));
+		ColorPair *color = &colors[i - 1];
 		color->key = 0;
 		memcpy(&color->key, line, cpp);
 		/* skip color key */
 		xpm_parse_color_line(line + cpp, color->color);
-		colors->next = color;
-		colors = color;
 	}
-	colors->next = NULL;
-	colors = dummy_color.next;
 
 	/* fill data */
 	unsigned int x, y;
@@ -356,12 +348,19 @@ static int load_xpm_image(char *filename, unsigned char **data,
 		unsigned char *data_line = *data + 4 * y * w;
 		for (x=0; x<w; ++x) {
 			unsigned int key = 0;
-			ColorList *color = colors;
+			unsigned int remaining = ncolors;
+			uint8_t *c = NULL;
+			ColorPair *color = colors;
+
 			memcpy(&key, pixels + cpp * x, cpp);
-			while (color && color->key != key)
-				color = color->next;
-			if (color) {
-				uint8_t *c = color->color;
+			while (remaining--) {
+				if (color->key == key) {
+					c = color->color;
+					break;
+				}
+				++color;
+			}
+			if (c) {
 				unsigned char *p = data_line + 4 * x;
 				*(p++) = c[2]; /* b */
 				*(p++) = c[1]; /* g */
@@ -374,12 +373,7 @@ static int load_xpm_image(char *filename, unsigned char **data,
 
 	error = 1; /* success */
 
-	/* clean linked list of colors */
-	while (colors) {
-		ColorList *next = colors->next;
-		free(colors);
-		colors = next;
-	}
+	free(colors);
 free_xpm:
 	XpmFree(xpm_data);
 	return error;
-- 
cgit v1.2.1