Keywords are now collected using a B-tree rather than an array with

heapsort. This makes the code much simpler for a start, but the main
reason is so that we can spot duplicate keywords as we go along
rather than having to wait until the end of input processing.

[originally from svn r1489]

4 files changed, 43 insertions, 82 deletions

diff --git a/buttress.h b/buttress.h
index 19e6cf8..6646a81 100644
--- a/buttress.h
+++ b/buttress.h
@@ -206,6 +206,7 @@ enum {
     err_macroexists,		       /* this macro already exists */
     err_sectjump,		       /* jump a heading level, eg \C -> \S */
     err_winhelp_ctxclash,	       /* WinHelp context ID hash clash */
+    err_multikw,		       /* keyword clash in sections */
     err_whatever                       /* random error of another type */
 };
 
@@ -321,7 +322,7 @@ paragraph *read_input(input *in, indexdata *idx);
 struct keywordlist_Tag {
     int nkeywords;
     int size;
-    keyword **keys;
+    tree234 *keys;		       /* sorted by `key' field */
     word **looseends;		       /* non-keyword list element numbers */
     int nlooseends;
     int looseendssize;
diff --git a/error.c b/error.c
index d115073..4f7524c 100644
--- a/error.c
+++ b/error.c
@@ -18,7 +18,7 @@ static void do_error(int code, va_list ap) {
     char auxbuf[256];
     char *sp, *sp2;
     wchar_t *wsp;
-    filepos fpos;
+    filepos fpos, fpos2;
     int flags;
 
     switch(code) {
@@ -175,6 +175,15 @@ static void do_error(int code, va_list ap) {
 		"previously defined `%.200s'", sp, sp2);
 	flags = FILEPOS;
 	break;
+      case err_multikw:
+	fpos = *va_arg(ap, filepos *);
+	fpos2 = *va_arg(ap, filepos *);
+	wsp = va_arg(ap, wchar_t *);
+	sp = ustrtoa(wsp, auxbuf, sizeof(auxbuf));
+	sprintf(error, "paragraph keyword `%.200s' already defined at ", sp);
+	sprintf(error + strlen(error), "%s:%d", fpos2.filename, fpos2.line);
+	flags = FILEPOS;
+	break;
       case err_whatever:
 	sp = va_arg(ap, char *);
         vsprintf(error, sp, ap);
diff --git a/keywords.c b/keywords.c
index 638ff29..1fc6f5e 100644
--- a/keywords.c
+++ b/keywords.c
@@ -7,76 +7,22 @@
 #include <assert.h>
 #include "buttress.h"
 
-#define heapparent(x) (((x)+1)/2-1)
-#define heaplchild(x) (2*(x)+1)
-#define heaprchild(x) (2*(x)+2)
-
-#define key(x) ( kl->keys[(x)] )
-
-#define greater(x,y) ( ustrcmp(key(x)->key, key(y)->key) > 0 )
-#define swap(x,y) do { keyword *t=key(x); key(x)=key(y); key(y)=t; } while(0)
-
-static void heap_add(keywordlist *kl, keyword *key) {
-    int p;
-    if (kl->nkeywords >= kl->size) {
-	kl->size = kl->nkeywords + 128;
-	kl->keys = resize(kl->keys, kl->size);
-    }
-    p = kl->nkeywords++;
-    kl->keys[p] = key;
-    while (heapparent(p) >= 0 && greater(p, heapparent(p))) {
-	swap(p, heapparent(p));
-	p = heapparent(p);
-    }
+static int kwcmp(void *av, void *bv)
+{
+    const keyword *a = (const keyword *)av;
+    const keyword *b = (const keyword *)bv;
+    return ustrcmp(a->key, b->key);
 }
 
-static void heap_sort(keywordlist *kl) {
-    int i, j;
-
-    kl->size = kl->nkeywords;
-    kl->keys = resize(kl->keys, kl->size);
-
-    i = kl->nkeywords;
-    while (i > 1) {
-	i--;
-	swap(0, i);		       /* put greatest at end */
-	j = 0;
-	while (1) {
-	    int left = heaplchild(j), right = heaprchild(j);
-	    if (left >= i || !greater(left, j))
-		left = -1;
-	    if (right >= i || !greater(right, j))
-		right = -1;
-	    if (left >= 0 && right >= 0) {
-		if (greater(left, right))
-		    right = -1;
-		else
-		    left = -1;
-	    }
-	    if (left >= 0) { swap(j, left); j = left; }
-	    else if (right >= 0) { swap(j, right); j = right; }
-	    else break;
-	}
-    }
-    /* FIXME: check for duplicate keys; do what about them? */
+static int kwfind(void *av, void *bv)
+{
+    wchar_t *a = (wchar_t *)av;
+    const keyword *b = (const keyword *)bv;
+    return ustrcmp(a, b->key);
 }
 
 keyword *kw_lookup(keywordlist *kl, wchar_t *str) {
-    int i, j, k, cmp;
-
-    i = -1;
-    j = kl->nkeywords;
-    while (j-i > 1) {
-	k = (i+j)/2;
-	cmp = ustrcmp(str, kl->keys[k]->key);
-	if (cmp < 0)
-	    j = k;
-	else if (cmp > 0)
-	    i = k;
-	else
-	    return kl->keys[k];
-    }
-    return NULL;
+    return find234(kl->keys, str, kwfind);
 }
 
 /*
@@ -93,9 +39,8 @@ keywordlist *get_keywords(paragraph *source) {
 
     number_cfg(n, source);
 
-    kl->nkeywords = 0;
     kl->size = 0;
-    kl->keys = NULL;
+    kl->keys = newtree234(kwcmp);
     kl->nlooseends = kl->looseendssize = 0;
     kl->looseends = NULL;
     for (; source; source = source->next) {
@@ -122,11 +67,18 @@ keywordlist *get_keywords(paragraph *source) {
 
 	if (p && *p) {
 	    if (source->kwtext || source->type == para_Biblio) {
-		keyword *kw = mknew(keyword);
+		keyword *kw, *ret;
+
+		kw = mknew(keyword);
 		kw->key = p;
 		kw->text = source->kwtext;
 		kw->para = source;
-		heap_add(kl, kw);
+		ret = add234(kl->keys, kw);
+		if (ret != kw) {
+		    error(err_multikw, &source->fpos, &ret->para->fpos, p);
+		    sfree(kw);
+		    /* FIXME: what happens to kw->text? Does it leak? */
+		}
 	    }
 	} else {
 	    if (kl->nlooseends >= kl->looseendssize) {
@@ -144,22 +96,20 @@ keywordlist *get_keywords(paragraph *source) {
 	return NULL;
     }
 
-    heap_sort(kl);
-
     return kl;
 }
 
 void free_keywords(keywordlist *kl) {
-    int i;
+    keyword *kw;
     while (kl->nlooseends)
 	free_word_list(kl->looseends[--kl->nlooseends]);
     sfree(kl->looseends);
-    for (i = 0; i < kl->nkeywords; i++) {
-	if (kl->keys[i])
-	    free_word_list(kl->keys[i]->text);
-	sfree(kl->keys[i]);
+    while ( (kw = index234(kl->keys, 0)) != NULL) {
+        delpos234(kl->keys, 0);
+	free_word_list(kw->text);
+	sfree(kw);
     }
-    sfree(kl->keys);
+    freetree234(kl->keys);
     sfree(kl);
 }
 
diff --git a/main.c b/main.c
index 8202bca..a86399a 100644
--- a/main.c
+++ b/main.c
@@ -259,11 +259,12 @@ static void dbg_prtkws(keywordlist *kws) {
      */
 
     int i;
+    keyword *kw;
 
-    for (i = 0; i < kws->nkeywords; i++) {
+    for (i = 0; (kw = index234(kws->keys, i)) != NULL; i++) {
 	wchar_t *wp;
 	printf("keyword ");
-	wp = kws->keys[i]->key;
+	wp = kw->key;
 	while (*wp) {
 	    putchar('\"');
 	    for (; *wp; wp++)
@@ -273,7 +274,7 @@ static void dbg_prtkws(keywordlist *kws) {
 		printf(", ");
 	}
 	printf(" {\n");
-	dbg_prtwordlist(1, kws->keys[i]->text);
+	dbg_prtwordlist(1, kw->text);
 	printf("}\n");
     }
 }