kwhash.c

一个基于C++的语法分析类

/* this is a C program */

#include <stdio.h>

static char *keywords[] =
    {
    "asm",
    "auto",
    "break",
    "case",
    "char",
    "class",
    "const",
    "continue",
    "default",
    "delete",
    "do",
    "double",
    "else",
    "enum",
    "extern",
    "float",
    "for",
    "friend",
    "goto",
    "if",
    "inline",
    "int",
    "long",
    "new",
    "operator",
    "overload",
    "private",
    "protected",
    "public",
    "register",
    "return",
    "short",
    "signed",
    "sizeof",
    "static",
    "struct",
    "switch",
    "this",
    "typedef",
    "union",
    "unsigned",
    "virtual",
    "volatile",
    "void",
    "while"
    };

#define KW_NUMKEYS (sizeof(keywords)/sizeof(*keywords))

unsigned int hashsize = 137;
char** kwhash;
typedef unsigned short u_short;

u_short
hash(cp, len, a, b, c)
    unsigned char* cp;
    u_short len;
    u_short a, b, c;
    {
    return (((u_short)cp[0]         ) ^
            ((u_short)cp[1]     << a) ^
            ((u_short)cp[len-1] << b) ^
             (len               << c)  ) % hashsize;
    }

int
insert(cp, a, b, c)
    char *cp;
    u_short a, b, c;
    {
    short h;

    h = hash(cp, strlen(cp), a, b, c);
    if (kwhash[h] != NULL)
        {
/*
        printf("Keyword hash collision: %s, %s\n", kwhash[h], cp);
*/
        return 0;
        }
    else
        kwhash[h] = cp;
    return 1;
    }

int
try(a, b, c)
    short a, b, c;
    {
    short int i;
    int collisions;

    collisions = 0;
    for (i = 0; i < hashsize; ++i)
        kwhash[i] = NULL;
    for (i = 0; i < KW_NUMKEYS; ++i)
        if (!insert(keywords[i], a, b, c))
            ++collisions;
    return collisions;
    }

main(argc, argv)
    int argc;
    char **argv;
    {
    int min_collisions;
    int min_abc = 0;
    short a, b, c;

    if (argc > 1) hashsize = atoi(argv[1]);
    else
        {
        printf("usage: %s <hash_size>\n\t<hash_size> should be prime.\n",
                argv[0]);
        exit(-1);
        }

    if (hashsize < KW_NUMKEYS)
        {
        printf("Hash table is too small.\n");
        exit(-1);
        }

    kwhash = (char**) malloc(hashsize * sizeof(char*));
    min_collisions = hashsize + 1;
    for (a = 0; a <= 10; ++a)
        {
        for (b = 0; b <= 10; ++b)
            {
            for (c = 0; c <= 10; ++c)
                {
                int collisions;

                collisions = try(a, b, c);
                if (collisions <= min_collisions)
                    {
                    printf("abc: %03x  Collisions: %2d ",
                           ((a<<8)|(b<<4)|c), collisions);
                    min_collisions = collisions;
                    if (collisions == 0) putchar('*');
                    putchar('\n');
                    }
                }
            }
        }
    }