From 01993102e9121faf14ff518b72e72fcc276ddf91 Mon Sep 17 00:00:00 2001
From: Peter Wu <lekensteyn@gmail.com>
Date: Sat, 29 Sep 2012 00:26:22 +0200
Subject: xcbviewfs: further improve performance by searching a sorted array

Sort the list of colors (which is almost instant for 256 colors). Then use a
binary search to cut the time with a factor 6.
---
 xcbviewfs.c | 29 +++++++++++++++--------------
 1 file changed, 15 insertions(+), 14 deletions(-)

(limited to 'xcbviewfs.c')

diff --git a/xcbviewfs.c b/xcbviewfs.c
index 74eb284..cb8f548 100644
--- a/xcbviewfs.c
+++ b/xcbviewfs.c
@@ -293,6 +293,10 @@ struct _ColorPair {
 	unsigned int key; /* assume that the key has less or equal bytes */
 	uint8_t color[3]; /* RGB */
 };
+int colorpaircmp(const void *a, const void *b) {
+	const ColorPair *left = a, *right = b;
+	return left->key - right->key;
+}
 
 static int load_xpm_image(char *filename, unsigned char **data,
 	unsigned int *len, unsigned int *width, unsigned int *height) {
@@ -339,6 +343,7 @@ static int load_xpm_image(char *filename, unsigned char **data,
 		/* skip color key */
 		xpm_parse_color_line(line + cpp, color->color);
 	}
+	qsort(colors, ncolors, sizeof(ColorPair), colorpaircmp);
 
 	/* fill data */
 	unsigned int x, y;
@@ -347,20 +352,16 @@ static int load_xpm_image(char *filename, unsigned char **data,
 		char *pixels = all_pixels[y];
 		unsigned char *data_line = *data + 4 * y * w;
 		for (x=0; x<w; ++x) {
-			unsigned int key = 0;
-			unsigned int remaining = ncolors;
-			uint8_t *c = NULL;
-			ColorPair *color = colors;
-
-			memcpy(&key, pixels + cpp * x, cpp);
-			while (remaining--) {
-				if (color->key == key) {
-					c = color->color;
-					break;
-				}
-				++color;
-			}
-			if (c) {
+			ColorPair key;
+			ColorPair *color;
+
+			key.key = 0;
+			memcpy(&key.key, pixels + cpp * x, cpp);
+			color = bsearch(&key, colors, ncolors,
+				sizeof(ColorPair), colorpaircmp);
+
+			if (color) {
+				uint8_t *c = color->color;
 				unsigned char *p = data_line + 4 * x;
 				*(p++) = c[2]; /* b */
 				*(p++) = c[1]; /* g */
-- 
cgit v1.2.1