[PATCH libxkbcommon v2 1/2] makekeys: use GNU gperf to generate perfect hashtables
David Herrmann
dh.herrmann at googlemail.com
Tue Oct 2 10:51:53 PDT 2012
Instead of using a home-brew hashtable generator, we should instead use
the gperf program which is known to work.
This removes the "makekeys" programs and instead replaces it by a file
that can generate input files for gperf. Gperf then generates hashtables
for all of these input files and writes them concatenated into
ks_tables.h which then can be used from keysym.c
Unfortunately, gperf does not support integer keys but only strings or
binary data. Therefore, we have to make the keysym->name lookup
little-endian to avoid errors during cross compilation.
Signed-off-by: David Herrmann <dh.herrmann at googlemail.com>
---
.gitignore | 1 +
Makefile.am | 24 +-
configure.ac | 6 +-
makekeys/Makefile.am | 10 -
makekeys/makekeys.c | 616 ++++++++++++++++++++++++++++-----------------------
src/keysym.c | 86 ++-----
6 files changed, 383 insertions(+), 360 deletions(-)
delete mode 100644 makekeys/Makefile.am
diff --git a/.gitignore b/.gitignore
index 22b4465..5a309a5 100644
--- a/.gitignore
+++ b/.gitignore
@@ -81,3 +81,4 @@ core
cscope.out
test-suite.log
test-driver
+*.gperf
diff --git a/Makefile.am b/Makefile.am
index 26646fb..763e1bc 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -1,7 +1,5 @@
ACLOCAL_AMFLAGS = -I m4
-SUBDIRS = makekeys
-
pkgconfigdir = $(libdir)/pkgconfig
pkgconfig_DATA = xkbcommon.pc
@@ -92,11 +90,25 @@ src/xkbcomp/parser.c: $(top_builddir)/src/$(am__dirstamp) $(top_builddir)/src/xk
src/xkbcomp/parser.h: $(top_builddir)/src/$(am__dirstamp) $(top_builddir)/src/xkbcomp/$(am__dirstamp)
src/xkbcomp/scanner.c: $(top_builddir)/src/$(am__dirstamp) $(top_builddir)/src/xkbcomp/$(am__dirstamp)
-src/ks_tables.h: $(top_builddir)/makekeys/makekeys$(EXEEXT)
- $(AM_V_GEN)$(top_builddir)/makekeys/makekeys $(top_srcdir)/xkbcommon/xkbcommon-keysyms.h > $@
+# makekeys program and src/ks_tables.h file
+
+noinst_PROGRAMS = makekeys/makekeys
+makekeys_makekeys_SOURCES = makekeys/makekeys.c
+CLEANFILES += \
+ makekeys/name2key.gperf \
+ makekeys/key2name.gperf
+
+src/ks_tables.h: \
+ $(top_builddir)/makekeys/name2key.gperf \
+ $(top_builddir)/makekeys/key2name.gperf
+ $(AM_V_GEN)$(GPERF) --language="ANSI-C" $(top_builddir)/makekeys/name2key.gperf > $@
+ $(AM_V_GEN)$(GPERF) --language="ANSI-C" $(top_builddir)/makekeys/key2name.gperf >> $@
+
+$(top_builddir)/makekeys/name2key.gperf: $(top_builddir)/makekeys/makekeys$(EXEEXT)
+ $(AM_V_GEN)$< --name2key $(top_srcdir)/xkbcommon/xkbcommon-keysyms.h > $@
-$(top_builddir)/makekeys/makekeys$(EXEEXT): $(top_srcdir)/makekeys/makekeys.c
- $(MAKE) -C makekeys
+$(top_builddir)/makekeys/key2name.gperf: $(top_builddir)/makekeys/makekeys$(EXEEXT)
+ $(AM_V_GEN)$< --key2name $(top_srcdir)/xkbcommon/xkbcommon-keysyms.h > $@
# Documentation
diff --git a/configure.ac b/configure.ac
index df8a99e..4200118 100644
--- a/configure.ac
+++ b/configure.ac
@@ -62,6 +62,11 @@ if test ! -f "src/xkbcomp/parser.c"; then
fi
fi
+AC_PATH_PROG([GPERF], "gperf", "")
+if test -z "$GPERF"; then
+ AC_MSG_ERROR([gperf not found - enable to create src/ks_tables.h])
+fi
+
# Checks for library functions.
AC_CHECK_FUNCS([strcasecmp strncasecmp])
if test "x$ac_cv_func_strcasecmp" = xno || \
@@ -121,7 +126,6 @@ AC_DEFINE_UNQUOTED([DEFAULT_XKB_LAYOUT], ["$DEFAULT_XKB_LAYOUT"],
AC_CONFIG_FILES([
Makefile
- makekeys/Makefile
xkbcommon-uninstalled.pc
xkbcommon.pc
doc/Doxyfile
diff --git a/makekeys/Makefile.am b/makekeys/Makefile.am
deleted file mode 100644
index 5d9a441..0000000
--- a/makekeys/Makefile.am
+++ /dev/null
@@ -1,10 +0,0 @@
-AM_CFLAGS = $(BASE_CFLAGS) -I$(top_srcdir)
-
-# need to use build-native compiler
-
-CC = $(CC_FOR_BUILD)
-CPPFLAGS = $(CPPFLAGS_FOR_BUILD)
-CFLAGS = $(CFLAGS_FOR_BUILD)
-LDFLAGS = $(LDFLAGS_FOR_BUILD)
-noinst_PROGRAMS = makekeys
-
diff --git a/makekeys/makekeys.c b/makekeys/makekeys.c
index 62d7255..22ece2f 100644
--- a/makekeys/makekeys.c
+++ b/makekeys/makekeys.c
@@ -1,302 +1,362 @@
/*
+ * Copyright (c) 2012 David Herrmann <dh.herrmann at googlemail.com>
*
- * Copyright 1990, 1998 The Open Group
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
*
- * Permission to use, copy, modify, distribute, and sell this software and its
- * documentation for any purpose is hereby granted without fee, provided that
- * the above copyright notice appear in all copies and that both that
- * copyright notice and this permission notice appear in supporting
- * documentation.
- *
- * The above copyright notice and this permission notice shall be included
- * in all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
- * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
- * IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
- * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
- * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
- * OTHER DEALINGS IN THE SOFTWARE.
- *
- * Except as contained in this notice, the name of The Open Group shall
- * not be used in advertising or otherwise to promote the sale, use or
- * other dealings in this Software without prior written authorization
- * from The Open Group.
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
*
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
*/
/*
- * Constructs hash tables for xkb_keysym_to_string and
- * xkb_string_from_keysym.
+ * Prepare source files for "gperf" which generates perfect hash-tables for
+ * xkb_keysym_get_name() and xkb_keysym_from_name().
*/
-#include "xkbcommon/xkbcommon.h"
-
+#include <endian.h>
#include <inttypes.h>
+#include <stdbool.h>
+#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+#include "xkbcommon/xkbcommon.h"
+
+/* maximum length of a keysym name including XKB_KEY_* */
+#define MAX_KEYSYM_LEN 127
+
+/* stringification of constants */
+#define xstr(x) #x
+#define str(x) xstr(x)
+
+/*
+ * Parse one line that was read as input from a keysym-defintion. @buf contains
+ * the line and is zero-terminated. @key is a buffer that can hold any keysym of
+ * maximum length MAX_KEYSYM_LEN.
+ * Returns true if a keysym has been parsed and stores the symbol in @key and
+ * the value in @val.
+ */
+static bool parse_line(const char *buf, char *key, uint32_t *val)
+{
+ unsigned int i;
+
+ i = sscanf(buf, "#define %" str(MAX_KEYSYM_LEN) "s 0x%" SCNx32,
+ key, val);
+ if (i == 2 && !strncmp(key, "XKB_KEY_", 8)) {
+ memmove(key, &key[8], strlen(&key[8]) + 1);
+ return true;
+ }
+
+ return false;
+}
+
+/* If we already have a keysym named @old in our list and a new keysym named
+ * @new is added, this function returns true if @new should overwrite @old.
+ * The caller must go sure that strcasecmp(@new, @old) returns "equal" before
+ * calling this.
+ *
+ * In general, we want lower-case letters to overwrite upper-case letters. As we
+ * generally not know which keysym-name is upper-case and which one is
+ * lower-case, we use a little hack:
+ * We simply sum up the ASCII values of both strings and use the greater
+ * value. This works because we know that the names of keysyms are written in
+ * upper-case letters if it is an upper case keysym. And upper-case letters
+ * have lower ASCII values than their respective lower-case letters. */
+static bool should_overwrite(const char *new, const char *old)
+{
+ unsigned int sum1, sum2, i;
+ const unsigned char *newu, *oldu;
+
+ newu = (const void*)new;
+ oldu = (const void*)old;
+ sum1 = 0;
+ sum2 = 0;
+ for (i = 0; new[i] && old[i]; ++i) {
+ sum1 += newu[i];
+ sum2 += oldu[i];
+ }
+
+ if (newu > oldu)
+ return true;
+
+ return false;
+}
+
+/*
+ * Flags for the gperf generator
+ *
+ * IGNORE_CASE causes the generator to create a case-insensitive hash-map and
+ * skips all duplicates. If a keysym is available as lower-case and upper-case
+ * keysym, then the lower-case keysym is taken.
+ *
+ * USE_NULL_STRINGS causes the hashtable to use NULL instead of "" for empty
+ * entries. This reduces memory space but causes a little performance-penalty.
+ *
+ * COMPARE_LENGTHS causes the hashtable to compare legths before doing a lookup.
+ * This causes a separate length-map to be added but can reduce performance for
+ * lookup-misses.
+ *
+ * REVERSE generates a reversed table, that is, the value is used as key and the
+ * name is returned. We simply convert the 4-byte keysym into a raw binary
+ * string and escape it correctly so gperf can read it.
+ */
+#define FLAG_IGNORE_CASE 0x01
+#define FLAG_USE_NULL_STRINGS 0x02
+#define FLAG_COMPARE_LENGTHS 0x04
+#define FLAG_REVERSE 0x08
+
+struct entry {
+ char name[MAX_KEYSYM_LEN + 1];
+ uint32_t value;
+};
+
+struct entry *entries;
+unsigned int ent_used;
+unsigned int ent_size;
+
+/* Pushes one keysym+value entry into the global list. Depending on @flags this
+ * might first check whether this entry wasn't added before. */
+static bool push_entry(const char *name, uint32_t value, unsigned int flags)
+{
+ struct entry *tmp;
+ unsigned int nsize, i;
+
+ if (strlen(name) > MAX_KEYSYM_LEN) {
+ fprintf(stderr, "keysym name is too long: %s\n", name);
+ return false;
+ }
+
+ if (ent_used == ent_size) {
+ nsize = ent_size * 2;
+ if (!nsize)
+ nsize = 1024;
+
+ tmp = realloc(entries, sizeof(struct entry) * nsize);
+ if (!tmp) {
+ fprintf(stderr, "cannot allocate enough memory\n");
+ return false;
+ }
-typedef uint32_t Signature;
+ entries = tmp;
+ ent_size = nsize;
+ }
-#define KTNUM 4000
+ if (flags & FLAG_IGNORE_CASE) {
+ for (i = 0; i < ent_used; ++i) {
+ tmp = &entries[i];
+ if (!strcasecmp(tmp->name, name)) {
+ if (should_overwrite(name, tmp->name))
+ break;
+ else
+ return true;
+ }
+ }
+ } else if (flags & FLAG_REVERSE) {
+ /* if two symbols resolve to the same value, we prefer the first
+ * value for backwards compatibility. */
+ for (i = 0; i < ent_used; ++i) {
+ tmp = &entries[i];
+ if (tmp->value == value)
+ return true;
+ }
+ } else {
+ i = ent_used;
+ }
-static struct info {
- char *name;
- xkb_keysym_t val;
-} info[KTNUM];
+ strcpy(entries[i].name, name);
+ entries[i].value = value;
-#define MIN_REHASH 15
-#define MATCHES 10
+ if (i == ent_used)
+ ++ent_used;
-static char tab[KTNUM];
-static unsigned short offsets[KTNUM];
-static unsigned short indexes[KTNUM];
-static xkb_keysym_t values[KTNUM];
-static int ksnum = 0;
+ return true;
+}
+
+/*
+ * This parses all files that are given on the command-line and pushes the
+ * symbols into the global symbol list. Command-line arguments starting with "-"
+ * are ignored. If your file starts with "-", then use "./-<file>".
+ */
+static bool parse_all(unsigned int flags, int argc, char **argv)
+{
+ unsigned int i;
+ FILE *f;
+ char buf[1024], key[128];
+ uint32_t val;
+
+ for (i = 1; i < argc; ++i) {
+ if (argv[i][0] == '-')
+ continue;
+
+ f = fopen(argv[i], "rb");
+ if (!f) {
+ fprintf(stderr, "cannot open input file %s\n", argv[i]);
+ return false;
+ }
+
+ while (fgets(buf, sizeof(buf), f)) {
+ if (!parse_line(buf, key, &val))
+ continue;
+
+ if (!push_entry(key, val, flags)) {
+ fprintf(stderr, "cannot save entry %s\n", key);
+ return false;
+ }
+ }
+
+ if (!feof(f)) {
+ fprintf(stderr, "error while reading input file %s\n",
+ argv[i]);
+ return false;
+ }
+
+ fclose(f);
+ }
+
+ return true;
+}
+
+static void write_header(FILE *out, const char *prefix, unsigned int flags)
+{
+ fprintf(out, "%%struct-type\n"
+ "%%readonly-tables\n"
+ "%%enum\n"
+ "%%pic\n");
+
+ if (flags & FLAG_USE_NULL_STRINGS)
+ fprintf(out, "%%null-strings\n");
+ if (flags & (FLAG_COMPARE_LENGTHS | FLAG_REVERSE))
+ fprintf(out, "%%compare-lengths\n");
+ if (flags & FLAG_IGNORE_CASE)
+ fprintf(out, "%%ignore-case\n");
+
+ fprintf(out, "%%define hash-function-name %1$shash\n"
+ "%%define lookup-function-name %1$slookup\n"
+ "%%define string-pool-name %1$sstringpool\n"
+ "%%define word-array-name %1$swordarray\n"
+ "%%define length-table-name %1$slengthtable\n",
+ prefix);
+
+ if (flags & FLAG_REVERSE)
+ fprintf(out, "struct %1$sentry {\n"
+ " int name;\n"
+ " const char *value;\n"
+ "};\n"
+ "%%%%\n", prefix);
+ else
+ fprintf(out, "struct %1$sentry {\n"
+ " int name;\n"
+ " uint32_t value;\n"
+ "};\n"
+ "%%%%\n", prefix);
+}
-static int
-parse_line(const char *buf, char *key, xkb_keysym_t *val, char *prefix)
+static void write_footer(FILE *out)
{
- int i;
- char alias[128];
-
- /* See if we can catch a straight XK_foo 0x1234-style definition first;
- * the trickery around tmp is to account for prefices. */
- i = sscanf(buf, "#define %127s 0x%" SCNx32, key, val);
- if (i == 2 && strncmp(key, "XKB_KEY_", 8) == 0) {
- prefix[0] = '\0';
- memmove(key, key + 8, strlen(key + 8) + 1);
- return 1;
- }
-
- i = sscanf(buf, "#define %127s %127s", key, alias);
- if (i == 2)
- fprintf(stderr, "can't parse keysym definition: %s", buf);
-
- return 0;
+ fprintf(out, "%%%%\n");
+}
+
+/*
+ * Creates a single gperf configuration file with the given function prefix
+ * @prefix, the options @flags and the files given in @argv.
+ * Output is written to @out.
+ */
+static bool create_file(FILE *out, const char *prefix, unsigned int flags,
+ int argc, char **argv)
+{
+ unsigned int i;
+ uint32_t val;
+ const char *name;
+ uint8_t *ptr;
+
+ if (!parse_all(flags, argc, argv))
+ return false;
+
+ write_header(out, prefix, flags);
+
+ for (i = 0; i < ent_used; ++i) {
+ name = entries[i].name;
+ val = entries[i].value;
+
+ if (flags & FLAG_REVERSE) {
+ /* For reversed lookup we make the keys little-endian
+ * to guarantee that the resulting gperf file can be
+ * cross-compiled.
+ * This adds a small performance-penalty to the runtime
+ * lookup function, but this is neglectable. */
+ val = htole32(val);
+ ptr = (uint8_t*)&val;
+ fprintf(out, "\"\\x%" PRIx8 "\\x%" PRIx8,
+ ptr[0], ptr[1]);
+ fprintf(out, "\\x%" PRIx8 "\\x%" PRIx8 "\"",
+ ptr[2], ptr[3]);
+ fprintf(out, ", ");
+ fprintf(out, "\"%s\"", name);
+ } else {
+ fprintf(out, "\"%s\"", name);
+ fprintf(out, ", ");
+ fprintf(out, "%" PRIu32, val);
+ }
+ fprintf(out, "\n");
+ }
+
+ write_footer(out);
+
+ return true;
}
-int
-main(int argc, char *argv[])
+/*
+ * Main Entry
+ * This checks the argument-list for one of --name2key and --key2name. All other
+ * arguments are taken as file-list that should be parsed. The generated gperf
+ * input is written to STDOUT.
+ */
+int main(int argc, char **argv)
{
- FILE *fptr;
- int max_rehash;
- Signature sig;
- int i, j, k, l, z;
- char *name;
- char c;
- int first;
- int best_max_rehash;
- int best_z = 0;
- int num_found;
- xkb_keysym_t val;
- char key[128], prefix[128];
- char buf[1024];
-
- for (l = 1; l < argc; l++) {
- fptr = fopen(argv[l], "r");
- if (!fptr) {
- fprintf(stderr, "couldn't open %s\n", argv[l]);
- continue;
- }
-
- while (fgets(buf, sizeof(buf), fptr)) {
- if (!parse_line(buf, key, &val, prefix))
- continue;
-
- if (val == XKB_KEY_VoidSymbol)
- val = 0;
- if (val > 0x1fffffff) {
- fprintf(stderr, "ignoring illegal keysym (%s, %" PRIx32 ")\n",
- key,
- val);
- continue;
- }
-
- name = malloc(strlen(prefix) + strlen(key) + 1);
- if (!name) {
- fprintf(stderr, "makekeys: out of memory!\n");
- exit(1);
- }
- sprintf(name, "%s%s", prefix, key);
- info[ksnum].name = name;
- info[ksnum].val = val;
- ksnum++;
- if (ksnum == KTNUM) {
- fprintf(stderr, "makekeys: too many keysyms!\n");
- exit(1);
- }
- }
-
- fclose(fptr);
- }
-
- printf("/* This file is generated from keysymdef.h. */\n");
- printf("/* Do not edit. */\n");
- printf("\n");
-
- best_max_rehash = ksnum;
- num_found = 0;
- for (z = ksnum; z < KTNUM; z++) {
- max_rehash = 0;
- for (name = tab, i = z; --i >= 0; )
- *name++ = 0;
- for (i = 0; i < ksnum; i++) {
- name = info[i].name;
- sig = 0;
- while ((c = *name++))
- sig = (sig << 1) + c;
- first = j = sig % z;
- for (k = 0; tab[j]; k++) {
- j += first + 1;
- if (j >= z)
- j -= z;
- if (j == first)
- goto next1;
- }
- tab[j] = 1;
- if (k > max_rehash)
- max_rehash = k;
- }
- if (max_rehash < MIN_REHASH) {
- if (max_rehash < best_max_rehash) {
- best_max_rehash = max_rehash;
- best_z = z;
- }
- num_found++;
- if (num_found >= MATCHES)
- break;
- }
-next1:;
- }
-
- z = best_z;
- printf("#ifndef KS_TABLES_H\n");
- printf("#define KS_TABLES_H\n\n");
- printf("static const unsigned char _XkeyTable[] = {\n");
- if (z == 0) {
- fprintf(stderr, "makekeys: failed to find small enough hash!\n"
- "Try increasing KTNUM in makekeys.c\n");
- exit(1);
- }
- printf("0,\n");
- k = 1;
- for (i = 0; i < ksnum; i++) {
- name = info[i].name;
- sig = 0;
- while ((c = *name++))
- sig = (sig << 1) + c;
- first = j = sig % z;
- while (offsets[j]) {
- j += first + 1;
- if (j >= z)
- j -= z;
- }
- offsets[j] = k;
- indexes[i] = k;
- val = info[i].val;
- printf("0x%.2" PRIx32 ", 0x%.2" PRIx32 ", 0x%.2" PRIx32 ", "
- "0x%.2" PRIx32 ", 0x%.2" PRIx32 ", 0x%.2" PRIx32 ", ",
- (sig >> 8) & 0xff, sig & 0xff, (val >> 24) & 0xff,
- (val >> 16) & 0xff, (val >> 8) & 0xff, val & 0xff);
- for (name = info[i].name, k += 7; (c = *name++); k++)
- printf("'%c',", c);
- printf((i == (ksnum - 1)) ? "0\n" : "0,\n");
- }
- printf("};\n");
- printf("\n");
- printf("#define KTABLESIZE %d\n", z);
- printf("#define KMAXHASH %d\n", best_max_rehash + 1);
- printf("\n");
- printf("static const unsigned short hashString[KTABLESIZE] = {\n");
- for (i = 0; i < z; ) {
- printf("0x%.4x", offsets[i]);
- i++;
- if (i == z)
- break;
- printf((i & 7) ? ", " : ",\n");
- }
- printf("\n");
- printf("};\n");
-
- best_max_rehash = ksnum;
- num_found = 0;
- for (z = ksnum; z < KTNUM; z++) {
- max_rehash = 0;
- for (name = tab, i = z; --i >= 0; )
- *name++ = 0;
- for (i = 0; i < ksnum; i++) {
- val = info[i].val;
- first = j = val % z;
- for (k = 0; tab[j]; k++) {
- if (values[j] == val)
- goto skip1;
- j += first + 1;
- if (j >= z)
- j -= z;
- if (j == first)
- goto next2;
- }
- tab[j] = 1;
- values[j] = val;
- if (k > max_rehash)
- max_rehash = k;
-skip1:;
- }
- if (max_rehash < MIN_REHASH) {
- if (max_rehash < best_max_rehash) {
- best_max_rehash = max_rehash;
- best_z = z;
- }
- num_found++;
- if (num_found >= MATCHES)
- break;
- }
-next2:;
- }
-
- z = best_z;
- if (z == 0) {
- fprintf(stderr, "makekeys: failed to find small enough hash!\n"
- "Try increasing KTNUM in makekeys.c\n");
- exit(1);
- }
- for (i = z; --i >= 0; )
- offsets[i] = 0;
- for (i = 0; i < ksnum; i++) {
- val = info[i].val;
- first = j = val % z;
- while (offsets[j]) {
- if (values[j] == val)
- goto skip2;
- j += first + 1;
- if (j >= z)
- j -= z;
- }
- offsets[j] = indexes[i] + 2;
- values[j] = val;
-skip2:;
- }
- printf("\n");
- printf("#define VTABLESIZE %d\n", z);
- printf("#define VMAXHASH %d\n", best_max_rehash + 1);
- printf("\n");
- printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n");
- for (i = 0; i < z; ) {
- printf("0x%.4x", offsets[i]);
- i++;
- if (i == z)
- break;
- printf((i & 7) ? ", " : ",\n");
- }
- printf("\n");
- printf("};\n");
- printf("\n#endif /* KS_TABLES_H */\n");
-
- for (i = 0; i < ksnum; i++)
- free(info[i].name);
-
- exit(0);
+ unsigned int i, flags;
+ const char *prefix;
+ bool res;
+
+ prefix = NULL;
+ for (i = 1; i < argc; ++i) {
+ if (!strcmp(argv[i], "--name2key")) {
+ prefix = "name2key_";
+ flags = FLAG_USE_NULL_STRINGS;
+ flags |= FLAG_COMPARE_LENGTHS;
+ } else if (!strcmp(argv[i], "--key2name")) {
+ prefix = "key2name_";
+ flags = FLAG_USE_NULL_STRINGS;
+ flags |= FLAG_COMPARE_LENGTHS;
+ flags |= FLAG_REVERSE;
+ } else if (argv[i][0] == '-') {
+ fprintf(stderr, "invalid option %s\n", argv[i]);
+ return EXIT_FAILURE;
+ }
+ }
+
+ if (!prefix) {
+ fprintf(stderr, "none of --name2key and --key2name specified\n");
+ return EXIT_FAILURE;
+ }
+
+ res = create_file(stdout, prefix, flags, argc, argv);
+ if (!res) {
+ fprintf(stderr, "cannot create gperf file\n");
+ return EXIT_FAILURE;
+ }
+
+ return EXIT_SUCCESS;
}
diff --git a/src/keysym.c b/src/keysym.c
index d659354..3ee0499 100644
--- a/src/keysym.c
+++ b/src/keysym.c
@@ -47,49 +47,35 @@
* DEALINGS IN THE SOFTWARE.
*/
+#include <endian.h>
+#include <inttypes.h>
+#include <string.h>
#include "xkbcommon/xkbcommon.h"
#include "utils.h"
-#include "ks_tables.h"
#include "keysym.h"
+const struct name2key_entry *name2key_lookup(register const char *str,
+ register unsigned int len);
+const struct key2name_entry *key2name_lookup(register const char *str,
+ register unsigned int len);
+
+#include "ks_tables.h"
+
XKB_EXPORT int
xkb_keysym_get_name(xkb_keysym_t ks, char *buffer, size_t size)
{
- int i, n, h, idx;
- const unsigned char *entry;
- unsigned char val1, val2, val3, val4;
+ const struct key2name_entry *e;
+ uint32_t val;
if ((ks & ((unsigned long) ~0x1fffffff)) != 0) {
snprintf(buffer, size, "Invalid");
return -1;
}
- /* Try to find it in our hash table. */
- if (ks <= 0x1fffffff) {
- val1 = ks >> 24;
- val2 = (ks >> 16) & 0xff;
- val3 = (ks >> 8) & 0xff;
- val4 = ks & 0xff;
- i = ks % VTABLESIZE;
- h = i + 1;
- n = VMAXHASH;
-
- while ((idx = hashKeysym[i])) {
- entry = &_XkeyTable[idx];
-
- if ((entry[0] == val1) && (entry[1] == val2) &&
- (entry[2] == val3) && (entry[3] == val4)) {
- return snprintf(buffer, size, "%s", entry + 4);
- }
-
- if (!--n)
- break;
-
- i += h;
- if (i >= VTABLESIZE)
- i -= VTABLESIZE;
- }
- }
+ val = htole32(ks);
+ e = key2name_lookup((void*)&val, sizeof(val));
+ if (e)
+ return snprintf(buffer, size, "%s", e->value);
if (ks >= 0x01000100 && ks <= 0x0110ffff)
/* Unnamed Unicode codepoint. */
@@ -102,42 +88,13 @@ xkb_keysym_get_name(xkb_keysym_t ks, char *buffer, size_t size)
XKB_EXPORT xkb_keysym_t
xkb_keysym_from_name(const char *s)
{
- int i, n, h, c, idx;
- uint32_t sig = 0;
- const char *p = s;
+ const struct name2key_entry *e;
char *tmp;
- const unsigned char *entry;
- unsigned char sig1, sig2;
- xkb_keysym_t val;
-
- while ((c = *p++))
- sig = (sig << 1) + c;
-
- i = sig % KTABLESIZE;
- h = i + 1;
- sig1 = (sig >> 8) & 0xff;
- sig2 = sig & 0xff;
- n = KMAXHASH;
-
- while ((idx = hashString[i])) {
- entry = &_XkeyTable[idx];
+ xkb_keysym_t val, ret;
- if ((entry[0] == sig1) && (entry[1] == sig2) &&
- streq(s, (const char *) entry + 6)) {
- val = (entry[2] << 24) | (entry[3] << 16) |
- (entry[4] << 8) | entry[5];
- if (!val)
- val = XKB_KEY_VoidSymbol;
- return val;
- }
-
- if (!--n)
- break;
-
- i += h;
- if (i >= KTABLESIZE)
- i -= KTABLESIZE;
- }
+ e = name2key_lookup(s, strlen(s));
+ if (e)
+ return e->value;
if (*s == 'U') {
val = strtoul(&s[1], &tmp, 16);
@@ -164,7 +121,6 @@ xkb_keysym_from_name(const char *s)
* no separating underscore, while some XF86* syms in the latter did.
* As a last ditch effort, try without. */
if (strncmp(s, "XF86_", 5) == 0) {
- xkb_keysym_t ret;
tmp = strdup(s);
if (!tmp)
return XKB_KEY_NoSymbol;
--
1.7.12.2
More information about the wayland-devel
mailing list