Xlib: Fixes for util/makekeys

[Bernardo Innocenti]

Daniel Stone wrote:

> This was one of the branches on my now-stolen laptop that I forgot
> about.  Still, might be worth making KTNUM a dynamic variable and
> calculating something optimal?

If only I could go back in time and warn myself not to attempt it I
would have saved a couple of hours of my time.

Next time makekeys needs changing, I'd suggest rewriting it in Perl
or Python right from the start.


>From dd3ea3a9604c806ae4a545b0a3334ce53fd8af32 Mon Sep 17 00:00:00 2001
From: Bernardo Innocenti <bernie at codewiz.org>
Date: Thu, 23 Aug 2007 23:39:50 -0400
Subject: [PATCH] makekeys: Remove hardcoded hashtable size.

In an attempt to avoid infinite loops with this naive collision resolution
strategy, the table size is now a prime number at least twice as large as
the number of entries.

The hashing algorithm could use a good rewrite, as it causes lots of
collisions even for a reasonable table size to entries ratio.
---
 src/util/makekeys.c |   74 +++++++++++++++++++++++++++++++++++----------------
 1 files changed, 51 insertions(+), 23 deletions(-)

diff --git a/src/util/makekeys.c b/src/util/makekeys.c
index 214ea5c..0d66a1a 100644
--- a/src/util/makekeys.c
+++ b/src/util/makekeys.c
@@ -36,32 +36,43 @@ from The Open Group.
 #include <X11/keysymdef.h>
 #include <stdio.h>
 #include <stdlib.h>
-#if defined(macII) && !defined(__STDC__)  /* stdlib.h fails to define these */
-char *malloc();
-#endif /* macII */
 
 typedef unsigned long Signature;
 
-#define KTNUM 3000
-
-static struct info {
+struct info {
     char	*name;
     KeySym	val;
-} info[KTNUM];
+};
 
 #define MIN_REHASH 15
 #define MATCHES 10
 
-char tab[KTNUM];
-unsigned short offsets[KTNUM];
-unsigned short indexes[KTNUM];
-KeySym values[KTNUM];
-char buf[1024];
+/* Silly, but simple algorithm for computing the next prime number */
+static size_t next_prime(size_t prime)
+{
+    size_t n, end;
+    do {
+        prime += 1;
+        end = (prime / 2) + 1;
+        for (n = 2; n < end; n += 1) {
+            if ((prime % n) == 0)
+                break;
+        }
+    }
+    while (n < end);
+
+    return prime;
+}
 
 int
 main(int argc, char *argv[])
 {
-    int ksnum = 0;
+    int ksnum = 0, ksalloc = 0;
+    struct info *info = NULL;
+    KeySym val, *values;
+    char *tab;
+    unsigned short *offsets;
+    unsigned short *indexes;
     int max_rehash;
     Signature sig;
     register int i, j, k, z;
@@ -71,12 +82,23 @@ main(int argc, char *argv[])
     int best_max_rehash;
     int best_z = 0;
     int num_found;
-    KeySym val;
     char key[128];
     char alias[128];
+    char buf[1024];
 
 
     while (fgets(buf, sizeof(buf), stdin)) {
+	/* Extend info vector if needed */
+	if (ksnum >= ksalloc / 2)
+	{
+	    ksalloc = next_prime(ksalloc);
+	    info = (struct info *)realloc(info, ksalloc * sizeof(*info));
+	    if (!info) {
+		fprintf(stderr, "makekeys: out of memory!\n");
+		exit(1);
+	    }
+	}
+
 	i = sscanf(buf, "#define XK_%127s 0x%lx", key, &info[ksnum].val);
 	if (i != 2) {
 	    i = sscanf(buf, "#define XK_%127s XK_%127s", key, alias);
@@ -103,19 +125,24 @@ main(int argc, char *argv[])
 		    key);
 	    continue;
 	}
-	name = malloc((unsigned)strlen(key)+1);
-	if (!name) {
+
+	info[ksnum].name = strdup(key);
+	if (!info[ksnum].name) {
 	    fprintf(stderr, "makekeys: out of memory!\n");
 	    exit(1);
 	}
-	(void)strcpy(name, key);
-	info[ksnum].name = name;
 	ksnum++;
-	if (ksnum == KTNUM) {
-	    fprintf(stderr, "makekeys: too many keysyms!\n");
+    }
+
+    /* Allocate auxiliary vectors */
+    values  = (KeySym *) calloc(ksalloc, sizeof(KeySym));
+    tab     = (char *) calloc(ksalloc, sizeof(char));
+    offsets = (unsigned short *) calloc(ksalloc, sizeof(unsigned short));
+    indexes = (unsigned short *) calloc(ksalloc, sizeof(unsigned short));
+	if (!(values && tab && offsets && indexes)) {
+	    fprintf(stderr, "makekeys: out of memory!\n");
 	    exit(1);
 	}
-    }
 
     printf("/* This file is generated from keysymdef.h. */\n");
     printf("/* Do not edit. */\n");
@@ -123,7 +150,7 @@ main(int argc, char *argv[])
 
     best_max_rehash = ksnum;
     num_found = 0;
-    for (z = ksnum; z < KTNUM; z++) {
+    for (z = ksnum; z < ksalloc; z++) {
 	max_rehash = 0;
 	for (name = tab, i = z; --i >= 0;)
 		*name++ = 0;
@@ -157,6 +184,7 @@ next1:	;
     }
 
     z = best_z;
+    //z = ksalloc;
     printf("#ifdef NEEDKTABLE\n");
     printf("const unsigned char _XkeyTable[] = {\n");
     printf("0,\n");
@@ -202,7 +230,7 @@ next1:	;
 
     best_max_rehash = ksnum;
     num_found = 0;
-    for (z = ksnum; z < KTNUM; z++) {
+    for (z = ksnum; z < ksalloc; z++) {
 	max_rehash = 0;
 	for (name = tab, i = z; --i >= 0;)
 		*name++ = 0;
-- 
1.5.2.4



-- 
   // Bernardo Innocenti
 \X/  http://www.codewiz.org/