From 0bc46491d34af88de959e5f1b679a1a1f7206ab0 Mon Sep 17 00:00:00 2001
From: Ben Harris <bjh21@bjh21.me.uk>
Date: Sat, 28 Mar 2020 12:37:14 +0000
Subject: [PATCH] More efficient (but hacky) searching for glyphs by name

Now rather than linearly searching the list of glyphs, dolookup() can
do a binary search on a list of glyph names.  This is faster, but the
code is currently very ugly.
---
 bedstead.c | 62 ++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 48 insertions(+), 14 deletions(-)

diff --git a/bedstead.c b/bedstead.c
index 3acb5b8..e160c11 100644
--- a/bedstead.c
+++ b/bedstead.c
@@ -1667,7 +1667,10 @@ static struct glyph {
  {{037,021,021,021,021,021,037,000,000}, -1, ".notdef" },
 };
 
-static int const nglyphs = sizeof(glyphs) / sizeof(glyphs[0]);
+#define NGLYPHS (sizeof(glyphs) / sizeof(glyphs[0]))
+static int const nglyphs = NGLYPHS;
+
+static struct glyph const *glyphs_by_name[NGLYPHS];
 
 static void dolookups(struct glyph const *);
 
@@ -1715,6 +1718,29 @@ static char * fullname_to_fontname(char const *fullname)
 	return fontname;
 }
 
+static int
+compare_glyphs_by_name(const void *va, const void *vb)
+{
+	struct glyph const * const *ap = va, * const *bp = vb;
+	struct glyph const *a = *ap, *b = *bp;
+	char a_buf[10], b_buf[10];
+	char const *an, *bn;
+
+	if (a->name) {
+		an = a->name;
+	} else {
+		sprintf(a_buf, "uni%04X.", a->unicode);
+		an = a_buf;
+	}
+	if (b->name) {
+		bn = b->name;
+	} else {
+		sprintf(b_buf, "uni%04X.", b->unicode);
+		bn = b_buf;
+	}
+	return strcmp(an, bn);
+}
+
 int
 main(int argc, char **argv)
 {
@@ -1866,6 +1892,10 @@ main(int argc, char **argv)
 	    "['c2sc' ('latn' <'dflt'>)]\n");
 	printf("BeginChars: %d %d\n", 0x110000 + extraglyphs, nglyphs);
 	extraglyphs = 0;
+	for (i = 0; i < nglyphs; i++)
+		glyphs_by_name[i] = glyphs + i;
+	qsort(glyphs_by_name, nglyphs, sizeof(glyphs_by_name[0]),
+	      &compare_glyphs_by_name);
 	for (i = 0; i < nglyphs; i++) {
 		if (glyphs[i].name)
 			printf("\nStartChar: %s\n", glyphs[i].name);
@@ -2048,6 +2078,7 @@ static void
 dolookups(struct glyph const *g)
 {
 	char prefix[32];
+	struct glyph const **found;
 	size_t plen;
 	int i;
 
@@ -2058,24 +2089,27 @@ dolookups(struct glyph const *g)
 	assert(plen < 32);
 
 	/* Look for related glyphs */
-	for (i = 0; i < nglyphs; i++) {
-		if (glyphs[i].name &&
-		    strncmp(prefix, glyphs[i].name, plen) == 0) {
-			if (strcmp(glyphs[i].name + plen, "saa5051") == 0)
+	found = bsearch(&g, glyphs_by_name, nglyphs, sizeof(glyphs_by_name[0]),
+		&compare_glyphs_by_name);
+	assert(found != NULL);
+	for (found++; found < glyphs_by_name + nglyphs; found++) {
+		if ((*found)->name &&
+		    strncmp(prefix, (*found)->name, plen) == 0) {
+			if (strcmp((*found)->name + plen, "saa5051") == 0)
 				printf("Substitution2: \"ss01\" %s\n",
-				       glyphs[i].name);
-			if (strcmp(glyphs[i].name + plen, "saa5052") == 0)
+				       (*found)->name);
+			if (strcmp((*found)->name + plen, "saa5052") == 0)
 				printf("Substitution2: \"ss02\" %s\n",
-				       glyphs[i].name);
-			if (strcmp(glyphs[i].name + plen, "saa5054") == 0)
+				       (*found)->name);
+			if (strcmp((*found)->name + plen, "saa5054") == 0)
 				printf("Substitution2: \"ss04\" %s\n",
-				       glyphs[i].name);
-			if (strcmp(glyphs[i].name + plen, "sc") == 0)
+				       (*found)->name);
+			if (strcmp((*found)->name + plen, "sc") == 0)
 				printf("Substitution2: \"smcp\" %s\n",
-				       glyphs[i].name);
+				       (*found)->name);
 			printf("AlternateSubs2: \"aalt\" %s\n",
-			       glyphs[i].name);
-		}
+			       (*found)->name);
+		} else break;
 	}
 	if ((g->flags & SC))
 		printf("Substitution2: \"%s\" %c%ssc\n", "c2sc",
-- 
2.30.2