ncurses 5.7 - patch 20090808
authorThomas E. Dickey <dickey@invisible-island.net>
Sat, 8 Aug 2009 23:45:56 +0000 (23:45 +0000)
committerThomas E. Dickey <dickey@invisible-island.net>
Sat, 8 Aug 2009 23:45:56 +0000 (23:45 +0000)
+ separate _nc_find_entry() and _nc_find_type_entry() from
  implementation details of hash function.

MANIFEST
NEWS
dist.mk
include/tic.h
ncurses/Makefile.in
ncurses/tinfo/MKcaptab.sh
ncurses/tinfo/comp_hash.c
ncurses/tinfo/make_hash.c [new file with mode: 0644]

index b1e1b556c9c750c1f8cba3a69fe9ae6b7cd213e7..cee2cd0b5fd15d177aec88ada848dcd522706b11 100644 (file)
--- a/MANIFEST
+++ b/MANIFEST
 ./ncurses/tinfo/lib_tparm.c
 ./ncurses/tinfo/lib_tputs.c
 ./ncurses/tinfo/lib_ttyflags.c
+./ncurses/tinfo/make_hash.c
 ./ncurses/tinfo/make_keys.c
 ./ncurses/tinfo/name_match.c
 ./ncurses/tinfo/parse_entry.c
diff --git a/NEWS b/NEWS
index f2ac7a86a8d99591695c53787c5d139032880926..3a8cc4769553f8bc0768dfbd6516ac769f6d5f84 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -25,7 +25,7 @@
 -- sale, use or other dealings in this Software without prior written        --
 -- authorization.                                                            --
 -------------------------------------------------------------------------------
--- $Id: NEWS,v 1.1416 2009/08/04 00:45:58 tom Exp $
+-- $Id: NEWS,v 1.1417 2009/08/08 18:08:44 tom Exp $
 -------------------------------------------------------------------------------
 
 This is a log of changes that ncurses has gone through since Zeyd started
@@ -45,6 +45,10 @@ See the AUTHORS file for the corresponding full names.
 Changes through 1.9.9e did not credit all contributions;
 it is not possible to add this information.
 
+20090808
+       + separate _nc_find_entry() and _nc_find_type_entry() from
+         implementation details of hash function.
+
 20090803
        + add tabs.1 to man/man_db.renames
        + modify lib_addch.c to compensate for removal of wide-character test
diff --git a/dist.mk b/dist.mk
index d7e04fc7709f18aac3998f9ab6ed958884b301a8..56d5f24379f0554bcab49db11154ca1b6eb82eed 100644 (file)
--- a/dist.mk
+++ b/dist.mk
@@ -25,7 +25,7 @@
 # use or other dealings in this Software without prior written               #
 # authorization.                                                             #
 ##############################################################################
-# $Id: dist.mk,v 1.713 2009/08/03 21:10:47 tom Exp $
+# $Id: dist.mk,v 1.714 2009/08/08 15:23:25 tom Exp $
 # Makefile for creating ncurses distributions.
 #
 # This only needs to be used directly as a makefile by developers, but
@@ -37,7 +37,7 @@ SHELL = /bin/sh
 # These define the major/minor/patch versions of ncurses.
 NCURSES_MAJOR = 5
 NCURSES_MINOR = 7
-NCURSES_PATCH = 20090803
+NCURSES_PATCH = 20090808
 
 # We don't append the patch to the version, since this only applies to releases
 VERSION = $(NCURSES_MAJOR).$(NCURSES_MINOR)
index f91d771d7bf1c21c61e02c082a900f9e3f9ded82..4f3a21c22b3fbdaed94ded0ab63721f85c3c91c4 100644 (file)
@@ -33,7 +33,7 @@
  ****************************************************************************/
 
 /*
- * $Id: tic.h,v 1.63 2009/07/11 18:11:15 tom Exp $
+ * $Id: tic.h,v 1.65 2009/08/08 17:52:46 tom Exp $
  *     tic.h - Global variables and structures for the terminfo
  *                     compiler.
  */
@@ -183,6 +183,8 @@ extern NCURSES_EXPORT_VAR(const struct tinfo_fkeys) _nc_tinfo_fkeys[];
 
 #endif
 
+typedef short HashValue;
+
        /*
         * The file comp_captab.c contains an array of these structures, one
         * per possible capability.  These are indexed by a hash table array of
@@ -193,10 +195,21 @@ struct name_table_entry
 {
        const char *nte_name;   /* name to hash on */
        int     nte_type;       /* BOOLEAN, NUMBER or STRING */
-       short   nte_index;      /* index of associated variable in its array */
-       short   nte_link;       /* index in table of next hash, or -1 */
+       HashValue nte_index;    /* index of associated variable in its array */
+       HashValue nte_link;     /* index in table of next hash, or -1 */
 };
 
+       /*
+        * Use this structure to hide differences between terminfo and termcap
+        * tables.
+        */
+typedef struct {
+       unsigned table_size;
+       const HashValue *table_data;
+       HashValue (*hash_of)(const char *);
+       int (*compare_names)(const char *, const char *);
+} HashData;
+
 struct alias
 {
        const char      *from;
@@ -205,7 +218,8 @@ struct alias
 };
 
 extern NCURSES_EXPORT(const struct name_table_entry *) _nc_get_table (bool);
-extern NCURSES_EXPORT(const short *) _nc_get_hash_table (bool);
+extern NCURSES_EXPORT(const HashData *) _nc_get_hash_info (bool);
+extern NCURSES_EXPORT(const HashValue *) _nc_get_hash_table (bool);
 extern NCURSES_EXPORT(const struct alias *) _nc_get_alias_table (bool);
 
 #define NOTFOUND       ((struct name_table_entry *) 0)
@@ -244,7 +258,7 @@ extern NCURSES_EXPORT(char *) _nc_rootname (char *);
 
 /* comp_hash.c: name lookup */
 extern NCURSES_EXPORT(struct name_table_entry const *) _nc_find_entry
-       (const char *, const short *);
+       (const char *, const HashValue *);
 extern NCURSES_EXPORT(struct name_table_entry const *) _nc_find_type_entry
        (const char *, int, bool);
 
index 0f94e4337650bdff7a4b26938b90700134751c36..a46c3291dffc7472785a90c9813f40f9e1696242 100644 (file)
@@ -1,4 +1,4 @@
-# $Id: Makefile.in,v 1.117 2009/07/04 16:36:11 tom Exp $
+# $Id: Makefile.in,v 1.118 2009/08/08 17:42:06 tom Exp $
 ##############################################################################
 # Copyright (c) 1998-2007,2009 Free Software Foundation, Inc.                #
 #                                                                            #
@@ -202,9 +202,9 @@ make_keys$(BUILD_EXEEXT) : \
        $(BUILD_CC) -o $@ $(BUILD_CCFLAGS) $(tinfo)/make_keys.c $(BUILD_LDFLAGS) $(BUILD_LIBS)
 
 make_hash$(BUILD_EXEEXT) : \
-               $(tinfo)/comp_hash.c \
+               $(tinfo)/make_hash.c \
                ../include/hashsize.h
-       $(BUILD_CC) -o $@ $(BUILD_CCFLAGS) -DMAIN_PROGRAM $(tinfo)/comp_hash.c $(BUILD_LDFLAGS) $(BUILD_LIBS)
+       $(BUILD_CC) -o $@ $(BUILD_CCFLAGS) $(tinfo)/make_hash.c $(BUILD_LDFLAGS) $(BUILD_LIBS)
 
 ./expanded.c : curses.priv.h $(serial)/MKexpanded.sh
        sh -e $(serial)/MKexpanded.sh "$(CPP)" $(CPPFLAGS) > $@
index 98c04e884309d240376988506f6d14d64a8ac2d3..d333301a0b377eeded747bb76f80f8c3fcec4b92 100755 (executable)
@@ -1,6 +1,6 @@
 #!/bin/sh
 ##############################################################################
-# Copyright (c) 2007 Free Software Foundation, Inc.                          #
+# Copyright (c) 2007,2009 Free Software Foundation, Inc.                     #
 #                                                                            #
 # Permission is hereby granted, free of charge, to any person obtaining a    #
 # copy of this software and associated documentation files (the "Software"), #
 # use or other dealings in this Software without prior written               #
 # authorization.                                                             #
 ##############################################################################
-# $Id: MKcaptab.sh,v 1.8 2007/08/12 13:13:51 tom Exp $
+# $Id: MKcaptab.sh,v 1.10 2009/08/08 17:19:25 tom Exp $
 AWK=${1-awk}
 OPT1=${2-0}
 OPT2=${3-tinfo/MKcaptab.awk}
 DATA=${4-../include/Caps}
 
+cat <<EOF
+/*
+ * generated by $0
+ */
+
+EOF
+
 cat <<'EOF'
 /*
  *     comp_captab.c -- The names of the capabilities indexed via a hash
@@ -58,7 +65,7 @@ cat <<EOF
 static void
 next_string(const char *strings, unsigned *offset)
 {
-       *offset += strlen(strings + *offset) + 1;
+    *offset += strlen(strings + *offset) + 1;
 }
 
 static const struct name_table_entry *
@@ -66,21 +73,21 @@ _nc_build_names(struct name_table_entry **actual,
                const name_table_data *source,
                const char *strings)
 {
-       if (*actual == 0) {
-               *actual = typeCalloc(struct name_table_entry, CAPTABSIZE);
-               if (*actual != 0) {
-                       unsigned n;
-                       unsigned len = 0;
-                       for (n = 0; n < CAPTABSIZE; ++n) {
-                               (*actual)[n].nte_name = strings + len;
-                               (*actual)[n].nte_type = source[n].nte_type;
-                               (*actual)[n].nte_index = source[n].nte_index;
-                               (*actual)[n].nte_link = source[n].nte_link;
-                               next_string(strings, &len);
-                       }
-               }
+    if (*actual == 0) {
+       *actual = typeCalloc(struct name_table_entry, CAPTABSIZE);
+       if (*actual != 0) {
+           unsigned n;
+           unsigned len = 0;
+           for (n = 0; n < CAPTABSIZE; ++n) {
+               (*actual)[n].nte_name = strings + len;
+               (*actual)[n].nte_type = source[n].nte_type;
+               (*actual)[n].nte_index = source[n].nte_index;
+               (*actual)[n].nte_link = source[n].nte_link;
+               next_string(strings, &len);
+           }
        }
-       return *actual;
+    }
+    return *actual;
 }
 
 #define add_alias(field) \\
@@ -94,18 +101,18 @@ _nc_build_alias(struct alias **actual,
                const char *strings,
                unsigned tablesize)
 {
-       if (*actual == 0) {
-               *actual = typeCalloc(struct alias, tablesize + 1);
-               if (*actual != 0) {
-                       unsigned n;
-                       for (n = 0; n < tablesize; ++n) {
-                               add_alias(from);
-                               add_alias(to);
-                               add_alias(source);
-                       }
-               }
+    if (*actual == 0) {
+       *actual = typeCalloc(struct alias, tablesize + 1);
+       if (*actual != 0) {
+           unsigned n;
+           for (n = 0; n < tablesize; ++n) {
+               add_alias(from);
+               add_alias(to);
+               add_alias(source);
+           }
        }
-       return *actual;
+    }
+    return *actual;
 }
 
 #define build_names(root) _nc_build_names(&_nc_##root##_table, \\
@@ -122,27 +129,65 @@ _nc_build_alias(struct alias **actual,
 
 NCURSES_EXPORT(const struct name_table_entry *) _nc_get_table (bool termcap)
 {
-       return termcap ? build_names(cap) : build_names(info) ;
+    return termcap ? build_names(cap) : build_names(info) ;
 }
 
-NCURSES_EXPORT(const short *) _nc_get_hash_table (bool termcap)
+/* entrypoint used by tack (do not alter) */
+NCURSES_EXPORT(const HashValue *) _nc_get_hash_table (bool termcap)
 {
-       return termcap ? _nc_cap_hash_table: _nc_info_hash_table ;
+    return termcap ? _nc_cap_hash_table: _nc_info_hash_table ;
 }
 
 NCURSES_EXPORT(const struct alias *) _nc_get_alias_table (bool termcap)
 {
-       return termcap ? build_alias(cap) : build_alias(info) ;
+    return termcap ? build_alias(cap) : build_alias(info) ;
+}
+
+static HashValue
+hash_function(const char *string)
+{
+    long sum = 0;
+
+    DEBUG(9, ("hashing %s", string));
+    while (*string) {
+       sum += (long) (*string + (*(string + 1) << 8));
+       string++;
+    }
+
+    DEBUG(9, ("sum is %ld", sum));
+    return (HashValue) (sum % HASHTABSIZE);
+}
+
+static int
+compare_cap_names(const char *a, const char *b)
+{
+    return !strncmp(a, b, 2);
+}
+
+static int
+compare_info_names(const char *a, const char *b)
+{
+    return !strcmp(a, b);
+}
+
+static const HashData hash_data[2] = {
+    { HASHTABSIZE, _nc_info_hash_table, hash_function, compare_info_names },
+    { HASHTABSIZE, _nc_cap_hash_table, hash_function, compare_cap_names }
+};
+
+NCURSES_EXPORT(const HashData *) _nc_get_hash_info (bool termcap)
+{
+    return &hash_data[(termcap != FALSE)];
 }
 
 #if NO_LEAKS
 NCURSES_EXPORT(void) _nc_comp_captab_leaks(void)
 {
 #if $OPT1
-       FreeIfNeeded(_nc_cap_table);
-       FreeIfNeeded(_nc_info_table);
-       FreeIfNeeded(_nc_capalias_table);
-       FreeIfNeeded(_nc_infoalias_table);
+    FreeIfNeeded(_nc_cap_table);
+    FreeIfNeeded(_nc_info_table);
+    FreeIfNeeded(_nc_capalias_table);
+    FreeIfNeeded(_nc_infoalias_table);
 #endif
 }
 #endif /* NO_LEAKS */
index e120e3a7413fc0c30d13b087d8b7e676809a02ab..959c6e156431121f9ba652c84ef9f8c475212167 100644 (file)
 #include <tic.h>
 #include <hashsize.h>
 
-#ifdef MAIN_PROGRAM
-#include <ctype.h>
-#undef  DEBUG
-#define DEBUG(level, params)   /*nothing */
-#endif
-
-MODULE_ID("$Id: comp_hash.c,v 1.45 2009/07/18 20:30:21 tom Exp $")
-
-static int hash_function(const char *);
-
-/*
- *     _nc_make_hash_table()
- *
- *     Takes the entries in table[] and hashes them into hash_table[]
- *     by name.  There are CAPTABSIZE entries in table[] and HASHTABSIZE
- *     slots in hash_table[].
- *
- */
-
-#ifdef MAIN_PROGRAM
-
-#undef MODULE_ID
-#define MODULE_ID(id)          /*nothing */
-#include <tinfo/doalloc.c>
-
-static void
-_nc_make_hash_table(struct name_table_entry *table,
-                   short *hash_table)
-{
-    short i;
-    int hashvalue;
-    int collisions = 0;
-
-    for (i = 0; i < HASHTABSIZE; i++) {
-       hash_table[i] = -1;
-    }
-    for (i = 0; i < CAPTABSIZE; i++) {
-       hashvalue = hash_function(table[i].nte_name);
-
-       if (hash_table[hashvalue] >= 0)
-           collisions++;
-
-       if (hash_table[hashvalue] != 0)
-           table[i].nte_link = hash_table[hashvalue];
-       hash_table[hashvalue] = i;
-    }
-
-    printf("/* %d collisions out of %d entries */\n", collisions, CAPTABSIZE);
-}
-#endif
-
-/*
- *     int hash_function(string)
- *
- *     Computes the hashing function on the given string.
- *
- *     The current hash function is the sum of each consectutive pair
- *     of characters, taken as two-byte integers, mod HASHTABSIZE.
- *
- */
-
-static int
-hash_function(const char *string)
-{
-    long sum = 0;
-
-    DEBUG(9, ("hashing %s", string));
-    while (*string) {
-       sum += (long) (*string + (*(string + 1) << 8));
-       string++;
-    }
-
-    DEBUG(9, ("sum is %ld", sum));
-    return (int) (sum % HASHTABSIZE);
-}
-
-#ifndef MAIN_PROGRAM
-
-#define SameName(a,b,termcap) (termcap ? !strncmp(a,b,2) : !strcmp(a,b))
-#if 0
-static bool
-same_name(const char *a, const char *b, bool termcap)
-{
-    fprintf(stderr, "compare(%s,%s)\n", a, b);
-    return SameName(a, b, termcap);
-}
-#else
-#define same_name(a,b,termcap) SameName(a,b,termcap)
-#endif
+MODULE_ID("$Id: comp_hash.c,v 1.48 2009/08/08 17:36:21 tom Exp $")
 
 /*
  * Finds the entry for the given string in the hash table if present.
  * Returns a pointer to the entry in the table or 0 if not found.
  */
+/* entrypoint used by tack (do not alter) */
 NCURSES_EXPORT(struct name_table_entry const *)
 _nc_find_entry(const char *string,
-              const short *hash_table)
+              const HashValue * hash_table)
 {
+    bool termcap = (hash_table != _nc_get_hash_table(FALSE));
+    const HashData *data = _nc_get_hash_info(termcap);
     int hashvalue;
     struct name_table_entry const *ptr = 0;
     struct name_table_entry const *real_table;
 
-    hashvalue = hash_function(string);
+    hashvalue = data->hash_of(string);
 
-    if (hash_table[hashvalue] >= 0) {
-       bool termcap = (hash_table != _nc_get_hash_table(FALSE));
+    if (data->table_data[hashvalue] >= 0) {
 
        real_table = _nc_get_table(termcap);
-       ptr = real_table + hash_table[hashvalue];
-       while (!same_name(ptr->nte_name, string, termcap)) {
+       ptr = real_table + data->table_data[hashvalue];
+       while (!data->compare_names(ptr->nte_name, string)) {
            if (ptr->nte_link < 0) {
                ptr = 0;
                break;
            }
-           ptr = real_table + (ptr->nte_link + hash_table[HASHTABSIZE]);
+           ptr = real_table + (ptr->nte_link
+                               + data->table_data[data->table_size]);
        }
     }
 
@@ -178,211 +93,22 @@ _nc_find_type_entry(const char *string,
                    bool termcap)
 {
     struct name_table_entry const *ptr = NULL;
-    const short *hash_table = _nc_get_hash_table(termcap);
-    int hashvalue = hash_function(string);
+    const HashData *data = _nc_get_hash_info(termcap);
+    int hashvalue = data->hash_of(string);
 
-    if (hash_table[hashvalue] >= 0) {
+    if (data->table_data[hashvalue] >= 0) {
        const struct name_table_entry *const table = _nc_get_table(termcap);
 
-       ptr = table + hash_table[hashvalue];
+       ptr = table + data->table_data[hashvalue];
        while (ptr->nte_type != type
-              || !same_name(ptr->nte_name, string, termcap)) {
+              || !data->compare_names(ptr->nte_name, string)) {
            if (ptr->nte_link < 0) {
                ptr = 0;
                break;
            }
-           ptr = table + (ptr->nte_link + hash_table[HASHTABSIZE]);
+           ptr = table + (ptr->nte_link + data->table_data[data->table_size]);
        }
     }
 
     return ptr;
 }
-#endif
-
-#ifdef MAIN_PROGRAM
-/*
- * This filter reads from standard input a list of tab-delimited columns,
- * (e.g., from Caps.filtered) computes the hash-value of a specified column and
- * writes the hashed tables to standard output.
- *
- * By compiling the hash table at build time, we're able to make the entire
- * set of terminfo and termcap tables readonly (and also provide some runtime
- * performance enhancement).
- */
-
-#define MAX_COLUMNS BUFSIZ     /* this _has_ to be worst-case */
-
-static char **
-parse_columns(char *buffer)
-{
-    static char **list;
-
-    int col = 0;
-
-    if (list == 0 && (list = typeCalloc(char *, MAX_COLUMNS)) == 0)
-         return (0);
-
-    if (*buffer != '#') {
-       while (*buffer != '\0') {
-           char *s;
-           for (s = buffer; (*s != '\0') && !isspace(UChar(*s)); s++)
-               /*EMPTY */ ;
-           if (s != buffer) {
-               char mark = *s;
-               *s = '\0';
-               if ((s - buffer) > 1
-                   && (*buffer == '"')
-                   && (s[-1] == '"')) {        /* strip the quotes */
-                   assert(s > buffer + 1);
-                   s[-1] = '\0';
-                   buffer++;
-               }
-               list[col] = buffer;
-               col++;
-               if (mark == '\0')
-                   break;
-               while (*++s && isspace(UChar(*s)))
-                   /*EMPTY */ ;
-               buffer = s;
-           } else
-               break;
-       }
-    }
-    return col ? list : 0;
-}
-
-int
-main(int argc, char **argv)
-{
-    struct name_table_entry *name_table = typeCalloc(struct
-                                                    name_table_entry, CAPTABSIZE);
-    short *hash_table = typeCalloc(short, HASHTABSIZE);
-    const char *root_name = "";
-    int column = 0;
-    int bigstring = 0;
-    int n;
-    char buffer[BUFSIZ];
-
-    static const char *typenames[] =
-    {"BOOLEAN", "NUMBER", "STRING"};
-
-    short BoolCount = 0;
-    short NumCount = 0;
-    short StrCount = 0;
-
-    /* The first argument is the column-number (starting with 0).
-     * The second is the root name of the tables to generate.
-     */
-    if (argc <= 3
-       || (column = atoi(argv[1])) <= 0
-       || (column >= MAX_COLUMNS)
-       || *(root_name = argv[2]) == 0
-       || (bigstring = atoi(argv[3])) < 0
-       || name_table == 0
-       || hash_table == 0) {
-       fprintf(stderr, "usage: make_hash column root_name bigstring\n");
-       exit(EXIT_FAILURE);
-    }
-
-    /*
-     * Read the table into our arrays.
-     */
-    for (n = 0; (n < CAPTABSIZE) && fgets(buffer, BUFSIZ, stdin);) {
-       char **list, *nlp = strchr(buffer, '\n');
-       if (nlp)
-           *nlp = '\0';
-       list = parse_columns(buffer);
-       if (list == 0)          /* blank or comment */
-           continue;
-       name_table[n].nte_link = -1;    /* end-of-hash */
-       name_table[n].nte_name = strdup(list[column]);
-       if (!strcmp(list[2], "bool")) {
-           name_table[n].nte_type = BOOLEAN;
-           name_table[n].nte_index = BoolCount++;
-       } else if (!strcmp(list[2], "num")) {
-           name_table[n].nte_type = NUMBER;
-           name_table[n].nte_index = NumCount++;
-       } else if (!strcmp(list[2], "str")) {
-           name_table[n].nte_type = STRING;
-           name_table[n].nte_index = StrCount++;
-       } else {
-           fprintf(stderr, "Unknown type: %s\n", list[2]);
-           exit(EXIT_FAILURE);
-       }
-       n++;
-    }
-    _nc_make_hash_table(name_table, hash_table);
-
-    /*
-     * Write the compiled tables to standard output
-     */
-    if (bigstring) {
-       int len = 0;
-       int nxt;
-
-       printf("static const char %s_names_text[] = \\\n", root_name);
-       for (n = 0; n < CAPTABSIZE; n++) {
-           nxt = (int) strlen(name_table[n].nte_name) + 5;
-           if (nxt + len > 72) {
-               printf("\\\n");
-               len = 0;
-           }
-           printf("\"%s\\0\" ", name_table[n].nte_name);
-           len += nxt;
-       }
-       printf(";\n\n");
-
-       len = 0;
-       printf("static name_table_data const %s_names_data[] =\n",
-              root_name);
-       printf("{\n");
-       for (n = 0; n < CAPTABSIZE; n++) {
-           printf("\t{ %15d,\t%10s,\t%3d, %3d }%c\n",
-                  len,
-                  typenames[name_table[n].nte_type],
-                  name_table[n].nte_index,
-                  name_table[n].nte_link,
-                  n < CAPTABSIZE - 1 ? ',' : ' ');
-           len += (int) strlen(name_table[n].nte_name) + 1;
-       }
-       printf("};\n\n");
-       printf("static struct name_table_entry *_nc_%s_table = 0;\n\n", root_name);
-    } else {
-
-       printf("static struct name_table_entry %s _nc_%s_table[] =\n",
-              bigstring ? "" : "const",
-              root_name);
-       printf("{\n");
-       for (n = 0; n < CAPTABSIZE; n++) {
-           sprintf(buffer, "\"%s\"",
-                   name_table[n].nte_name);
-           printf("\t{ %15s,\t%10s,\t%3d, %3d }%c\n",
-                  buffer,
-                  typenames[name_table[n].nte_type],
-                  name_table[n].nte_index,
-                  name_table[n].nte_link,
-                  n < CAPTABSIZE - 1 ? ',' : ' ');
-       }
-       printf("};\n\n");
-    }
-
-    printf("static const short _nc_%s_hash_table[%d] =\n",
-          root_name,
-          HASHTABSIZE + 1);
-    printf("{\n");
-    for (n = 0; n < HASHTABSIZE; n++) {
-       printf("\t%3d,\n", hash_table[n]);
-    }
-    printf("\t0\t/* base-of-table */\n");
-    printf("};\n\n");
-
-    printf("#if (BOOLCOUNT!=%d)||(NUMCOUNT!=%d)||(STRCOUNT!=%d)\n",
-          BoolCount, NumCount, StrCount);
-    printf("#error\t--> term.h and comp_captab.c disagree about the <--\n");
-    printf("#error\t--> numbers of booleans, numbers and/or strings <--\n");
-    printf("#endif\n\n");
-
-    free(hash_table);
-    return EXIT_SUCCESS;
-}
-#endif
diff --git a/ncurses/tinfo/make_hash.c b/ncurses/tinfo/make_hash.c
new file mode 100644 (file)
index 0000000..ffebe70
--- /dev/null
@@ -0,0 +1,294 @@
+/****************************************************************************
+ * Copyright (c) 1998-2008,2009 Free Software Foundation, Inc.              *
+ *                                                                          *
+ * 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, distribute with modifications, 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:                 *
+ *                                                                          *
+ * 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 ABOVE 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.                               *
+ *                                                                          *
+ * Except as contained in this notice, the name(s) of the above copyright   *
+ * holders shall not be used in advertising or otherwise to promote the     *
+ * sale, use or other dealings in this Software without prior written       *
+ * authorization.                                                           *
+ ****************************************************************************/
+
+/****************************************************************************
+ *  Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995               *
+ *     and: Eric S. Raymond <esr@snark.thyrsus.com>                         *
+ *     and: Thomas E. Dickey                        1996-on                 *
+ ****************************************************************************/
+
+/*
+ *     make_hash.c --- build-time program for constructing comp_captab.c
+ *
+ */
+
+#include <curses.priv.h>
+
+#include <tic.h>
+#include <hashsize.h>
+
+#include <ctype.h>
+
+MODULE_ID("$Id: make_hash.c,v 1.2 2009/08/08 17:42:41 tom Exp $")
+
+/*
+ *     _nc_make_hash_table()
+ *
+ *     Takes the entries in table[] and hashes them into hash_table[]
+ *     by name.  There are CAPTABSIZE entries in table[] and HASHTABSIZE
+ *     slots in hash_table[].
+ *
+ */
+
+#undef MODULE_ID
+#define MODULE_ID(id)          /*nothing */
+#include <tinfo/doalloc.c>
+
+/*
+ *     int hash_function(string)
+ *
+ *     Computes the hashing function on the given string.
+ *
+ *     The current hash function is the sum of each consectutive pair
+ *     of characters, taken as two-byte integers, mod HASHTABSIZE.
+ *
+ */
+
+static int
+hash_function(const char *string)
+{
+    long sum = 0;
+
+    while (*string) {
+       sum += (long) (*string + (*(string + 1) << 8));
+       string++;
+    }
+
+    return (int) (sum % HASHTABSIZE);
+}
+
+static void
+_nc_make_hash_table(struct name_table_entry *table,
+                   HashValue * hash_table)
+{
+    short i;
+    int hashvalue;
+    int collisions = 0;
+
+    for (i = 0; i < HASHTABSIZE; i++) {
+       hash_table[i] = -1;
+    }
+    for (i = 0; i < CAPTABSIZE; i++) {
+       hashvalue = hash_function(table[i].nte_name);
+
+       if (hash_table[hashvalue] >= 0)
+           collisions++;
+
+       if (hash_table[hashvalue] != 0)
+           table[i].nte_link = hash_table[hashvalue];
+       hash_table[hashvalue] = i;
+    }
+
+    printf("/* %d collisions out of %d entries */\n", collisions, CAPTABSIZE);
+}
+
+/*
+ * This filter reads from standard input a list of tab-delimited columns,
+ * (e.g., from Caps.filtered) computes the hash-value of a specified column and
+ * writes the hashed tables to standard output.
+ *
+ * By compiling the hash table at build time, we're able to make the entire
+ * set of terminfo and termcap tables readonly (and also provide some runtime
+ * performance enhancement).
+ */
+
+#define MAX_COLUMNS BUFSIZ     /* this _has_ to be worst-case */
+
+static char **
+parse_columns(char *buffer)
+{
+    static char **list;
+
+    int col = 0;
+
+    if (list == 0 && (list = typeCalloc(char *, MAX_COLUMNS)) == 0)
+         return (0);
+
+    if (*buffer != '#') {
+       while (*buffer != '\0') {
+           char *s;
+           for (s = buffer; (*s != '\0') && !isspace(UChar(*s)); s++)
+               /*EMPTY */ ;
+           if (s != buffer) {
+               char mark = *s;
+               *s = '\0';
+               if ((s - buffer) > 1
+                   && (*buffer == '"')
+                   && (s[-1] == '"')) {        /* strip the quotes */
+                   assert(s > buffer + 1);
+                   s[-1] = '\0';
+                   buffer++;
+               }
+               list[col] = buffer;
+               col++;
+               if (mark == '\0')
+                   break;
+               while (*++s && isspace(UChar(*s)))
+                   /*EMPTY */ ;
+               buffer = s;
+           } else
+               break;
+       }
+    }
+    return col ? list : 0;
+}
+
+int
+main(int argc, char **argv)
+{
+    struct name_table_entry *name_table = typeCalloc(struct
+                                                    name_table_entry, CAPTABSIZE);
+    HashValue *hash_table = typeCalloc(HashValue, HASHTABSIZE);
+    const char *root_name = "";
+    int column = 0;
+    int bigstring = 0;
+    int n;
+    char buffer[BUFSIZ];
+
+    static const char *typenames[] =
+    {"BOOLEAN", "NUMBER", "STRING"};
+
+    short BoolCount = 0;
+    short NumCount = 0;
+    short StrCount = 0;
+
+    /* The first argument is the column-number (starting with 0).
+     * The second is the root name of the tables to generate.
+     */
+    if (argc <= 3
+       || (column = atoi(argv[1])) <= 0
+       || (column >= MAX_COLUMNS)
+       || *(root_name = argv[2]) == 0
+       || (bigstring = atoi(argv[3])) < 0
+       || name_table == 0
+       || hash_table == 0) {
+       fprintf(stderr, "usage: make_hash column root_name bigstring\n");
+       exit(EXIT_FAILURE);
+    }
+
+    /*
+     * Read the table into our arrays.
+     */
+    for (n = 0; (n < CAPTABSIZE) && fgets(buffer, BUFSIZ, stdin);) {
+       char **list, *nlp = strchr(buffer, '\n');
+       if (nlp)
+           *nlp = '\0';
+       list = parse_columns(buffer);
+       if (list == 0)          /* blank or comment */
+           continue;
+       name_table[n].nte_link = -1;    /* end-of-hash */
+       name_table[n].nte_name = strdup(list[column]);
+       if (!strcmp(list[2], "bool")) {
+           name_table[n].nte_type = BOOLEAN;
+           name_table[n].nte_index = BoolCount++;
+       } else if (!strcmp(list[2], "num")) {
+           name_table[n].nte_type = NUMBER;
+           name_table[n].nte_index = NumCount++;
+       } else if (!strcmp(list[2], "str")) {
+           name_table[n].nte_type = STRING;
+           name_table[n].nte_index = StrCount++;
+       } else {
+           fprintf(stderr, "Unknown type: %s\n", list[2]);
+           exit(EXIT_FAILURE);
+       }
+       n++;
+    }
+    _nc_make_hash_table(name_table, hash_table);
+
+    /*
+     * Write the compiled tables to standard output
+     */
+    if (bigstring) {
+       int len = 0;
+       int nxt;
+
+       printf("static const char %s_names_text[] = \\\n", root_name);
+       for (n = 0; n < CAPTABSIZE; n++) {
+           nxt = (int) strlen(name_table[n].nte_name) + 5;
+           if (nxt + len > 72) {
+               printf("\\\n");
+               len = 0;
+           }
+           printf("\"%s\\0\" ", name_table[n].nte_name);
+           len += nxt;
+       }
+       printf(";\n\n");
+
+       len = 0;
+       printf("static name_table_data const %s_names_data[] =\n",
+              root_name);
+       printf("{\n");
+       for (n = 0; n < CAPTABSIZE; n++) {
+           printf("\t{ %15d,\t%10s,\t%3d, %3d }%c\n",
+                  len,
+                  typenames[name_table[n].nte_type],
+                  name_table[n].nte_index,
+                  name_table[n].nte_link,
+                  n < CAPTABSIZE - 1 ? ',' : ' ');
+           len += (int) strlen(name_table[n].nte_name) + 1;
+       }
+       printf("};\n\n");
+       printf("static struct name_table_entry *_nc_%s_table = 0;\n\n", root_name);
+    } else {
+
+       printf("static struct name_table_entry %s _nc_%s_table[] =\n",
+              bigstring ? "" : "const",
+              root_name);
+       printf("{\n");
+       for (n = 0; n < CAPTABSIZE; n++) {
+           sprintf(buffer, "\"%s\"",
+                   name_table[n].nte_name);
+           printf("\t{ %15s,\t%10s,\t%3d, %3d }%c\n",
+                  buffer,
+                  typenames[name_table[n].nte_type],
+                  name_table[n].nte_index,
+                  name_table[n].nte_link,
+                  n < CAPTABSIZE - 1 ? ',' : ' ');
+       }
+       printf("};\n\n");
+    }
+
+    printf("static const HashValue _nc_%s_hash_table[%d] =\n",
+          root_name,
+          HASHTABSIZE + 1);
+    printf("{\n");
+    for (n = 0; n < HASHTABSIZE; n++) {
+       printf("\t%3d,\n", hash_table[n]);
+    }
+    printf("\t0\t/* base-of-table */\n");
+    printf("};\n\n");
+
+    printf("#if (BOOLCOUNT!=%d)||(NUMCOUNT!=%d)||(STRCOUNT!=%d)\n",
+          BoolCount, NumCount, StrCount);
+    printf("#error\t--> term.h and comp_captab.c disagree about the <--\n");
+    printf("#error\t--> numbers of booleans, numbers and/or strings <--\n");
+    printf("#endif\n\n");
+
+    free(hash_table);
+    return EXIT_SUCCESS;
+}