开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 编译器/解释器 > 查看源码
kwhash.c
资源名称：parse.tar.Z　[点击查看]
上传用户：hbdengju
上传日期：2007-01-06
资源大小：11k
文件大小：3k
源码类别：

编译器/解释器

开发平台：

C/C++

kwhash.c：源码内容
  2. /* this is a C program */
  4. #include <stdio.h>
  6. static char *keywords[] =
  7.     {
  8.     "asm",
  9.     "auto",
  10.     "break",
  11.     "case",
  12.     "char",
  13.     "class",
  14.     "const",
  15.     "continue",
  16.     "default",
  17.     "delete",
  18.     "do",
  19.     "double",
  20.     "else",
  21.     "enum",
  22.     "extern",
  23.     "float",
  24.     "for",
  25.     "friend",
  26.     "goto",
  27.     "if",
  28.     "inline",
  29.     "int",
  30.     "long",
  31.     "new",
  32.     "operator",
  33.     "overload",
  34.     "private",
  35.     "protected",
  36.     "public",
  37.     "register",
  38.     "return",
  39.     "short",
  40.     "signed",
  41.     "sizeof",
  42.     "static",
  43.     "struct",
  44.     "switch",
  45.     "this",
  46.     "typedef",
  47.     "union",
  48.     "unsigned",
  49.     "virtual",
  50.     "volatile",
  51.     "void",
  52.     "while"
  53.     };
  55. #define KW_NUMKEYS (sizeof(keywords)/sizeof(*keywords))
  57. unsigned int hashsize = 137;
  58. char** kwhash;
  59. typedef unsigned short u_short;
  61. u_short
  62. hash(cp, len, a, b, c)
  63.     unsigned char* cp;
  64.     u_short len;
  65.     u_short a, b, c;
  66.     {
  67.     return (((u_short)cp[0]         ) ^
  68.             ((u_short)cp[1]     << a) ^
  69.             ((u_short)cp[len-1] << b) ^
  70.              (len               << c)  ) % hashsize;
  71.     }
  73. int
  74. insert(cp, a, b, c)
  75.     char *cp;
  76.     u_short a, b, c;
  77.     {
  78.     short h;
  80.     h = hash(cp, strlen(cp), a, b, c);
  81.     if (kwhash[h] != NULL)
  82.         {
  83. /*
  84.         printf("Keyword hash collision: %s, %sn", kwhash[h], cp);
  85. */
  86.         return 0;
  87.         }
  88.     else
  89.         kwhash[h] = cp;
  90.     return 1;
  91.     }
  93. int
  94. try(a, b, c)
  95.     short a, b, c;
  96.     {
  97.     short int i;
  98.     int collisions;
  100.     collisions = 0;
  101.     for (i = 0; i < hashsize; ++i)
  102.         kwhash[i] = NULL;
  103.     for (i = 0; i < KW_NUMKEYS; ++i)
  104.         if (!insert(keywords[i], a, b, c))
  105.             ++collisions;
  106.     return collisions;
  107.     }
  109. main(argc, argv)
  110.     int argc;
  111.     char **argv;
  112.     {
  113.     int min_collisions;
  114.     int min_abc = 0;
  115.     short a, b, c;
  117.     if (argc > 1) hashsize = atoi(argv[1]);
  118.     else
  119.         {
  120.         printf("usage: %s <hash_size>nt<hash_size> should be prime.n",
  121.                 argv[0]);
  122.         exit(-1);
  123.         }
  125.     if (hashsize < KW_NUMKEYS)
  126.         {
  127.         printf("Hash table is too small.n");
  128.         exit(-1);
  129.         }
  131.     kwhash = (char**) malloc(hashsize * sizeof(char*));
  132.     min_collisions = hashsize + 1;
  133.     for (a = 0; a <= 10; ++a)
  134.         {
  135.         for (b = 0; b <= 10; ++b)
  136.             {
  137.             for (c = 0; c <= 10; ++c)
  138.                 {
  139.                 int collisions;
  141.                 collisions = try(a, b, c);
  142.                 if (collisions <= min_collisions)
  143.                     {
  144.                     printf("abc: %03x  Collisions: %2d ",
  145.                            ((a<<8)|(b<<4)|c), collisions);
  146.                     min_collisions = collisions;
  147.                     if (collisions == 0) putchar('*');
  148.                     putchar('n');
  149.                     }
  150.                 }
  151.             }
  152.         }
  153.     }