build/genhash.c

   1 /*
   2  *      Generator of Word Recognition Hash Tables
   3  *      (a.k.a. simple gperf replacement)
   4  *
   5  *      (c) 1999 Martin Mares <mj@ucw.cz>
   6  */
   7
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11 #include <alloca.h>
  12
  13 struct word {
  14   struct word *next;
  15   char *w;
  16   char *extra;
  17 };
  18
  19 static unsigned int hash(char *c)
  20 {
  21   unsigned int h = 0;
  22   while (*c)
  23     h = (h * 37) + *c++;
  24   return h;
  25 }
  26
  27 static int                              /* Sequential search */
  28 fast_isprime(unsigned x)                /* We know x != 2 && x != 3 */
  29 {
  30   unsigned test = 5;
  31
  32   for(;;)
  33     {
  34       if (!(x % test))
  35         return 0;
  36       if (x / test <= test)
  37         return 1;
  38       test += 2;                        /* 6k+1 */
  39       if (!(x % test))
  40         return 0;
  41       if (x / test <= test)
  42         return 1;
  43       test += 4;                        /* 6k-1 */
  44     }
  45 }
  46
  47 static unsigned int
  48 nextprime(unsigned x)                   /* Returns some prime greater than X */
  49 {
  50   if (x <= 5)
  51     return 5;
  52   x += 5 - (x % 6);                     /* x is 6k-1 */
  53   for(;;)
  54     {
  55       if (fast_isprime(x))
  56         return x;
  57       x += 2;                           /* 6k+1 */
  58       if (fast_isprime(x))
  59         return x;
  60       x += 4;                           /* 6k-1 */
  61     }
  62 }
  63
  64 int main(int argc, char **argv)
  65 {
  66   FILE *fi, *fo;
  67   struct word *words = NULL;
  68   struct word *w, **ht;
  69   char buf[1024], *c, namebuf[256];
  70   int cnt = 0;
  71   int skip, i, size;
  72
  73   if (argc != 4)
  74     {
  75       fprintf(stderr, "Usage: genhash <input> <output> <func_name>\n");
  76       return 1;
  77     }
  78   fi = fopen(argv[1], "r");
  79   if (!fi) { fprintf(stderr, "Cannot open input file: %m\n"); return 1; }
  80   fo = fopen(argv[2], "w");
  81   if (!fo) { fprintf(stderr, "Cannot open output file: %m\n"); return 1; }
  82
  83   buf[0] = 0;
  84   fgets(buf, sizeof(buf)-1, fi);
  85   if (strncmp(buf, "%{", 2)) { fprintf(stderr, "Syntax error at <%s>\n", buf); return 1; }
  86   fputs(buf+2, fo);
  87   while (fgets(buf, sizeof(buf)-1, fi) && strcmp(buf, "%}\n"))
  88     fputs(buf, fo);
  89   fgets(namebuf, sizeof(namebuf)-1, fi);
  90   if (strncmp(namebuf, "struct ", 7) || !(c = strchr(namebuf+7, ' ')))
  91     { fprintf(stderr, "Syntax error at <%s>\n", namebuf); return 1; }
  92   *c = 0;
  93   while (fgets(buf, sizeof(buf)-1, fi) && strcmp(buf, "%%\n"))
  94     ;
  95   while (fgets(buf, sizeof(buf)-1, fi))
  96     {
  97       c = strchr(buf, '\n');
  98       if (c)
  99         *c = 0;
 100       c = strchr(buf, ',');
 101       w = alloca(sizeof(struct word));
 102       if (c)
 103         *c++ = 0;
 104       else
 105         { fprintf(stderr, "No comma?\n"); return 1; }
 106       w->w = alloca(strlen(buf)+1);
 107       strcpy(w->w, buf);
 108       w->extra = alloca(strlen(c)+1);
 109       strcpy(w->extra, c);
 110       w->next = words;
 111       words = w;
 112       cnt++;
 113     }
 114   cnt = cnt*12/10;
 115   size = 16;
 116   while (size < cnt)
 117     size += size;
 118   skip = nextprime(size*3/4);
 119
 120   ht = alloca(size * sizeof(struct word *));
 121   bzero(ht, size * sizeof(struct word *));
 122   for(w=words; w; w=w->next)
 123     {
 124       int h = hash(w->w) & (size - 1);
 125       while (ht[h])
 126         h = (h + skip) & (size - 1);
 127       ht[h] = w;
 128     }
 129
 130   fprintf(fo, "static %s htable[] = {\n", namebuf);
 131   for(i=0; i<size; i++)
 132     if (ht[i])
 133       fprintf(fo, "{ \"%s\", %s },\n", ht[i]->w, ht[i]->extra);
 134     else
 135       fprintf(fo, "{ NULL },\n");
 136   fprintf(fo, "};\n\nconst %s *%s(register const char *x, register unsigned int len)\n\
 137 {\n\
 138   const char *c = x;\n\
 139   unsigned int h = 0;\n\
 140   while (*c)\n\
 141     h = (h * 37) + *c++;\n\
 142   h = h & %d;\n\
 143   while (htable[h].name)\n\
 144     {\n\
 145       if (!strcmp(htable[h].name, x))\n\
 146         return &htable[h];\n\
 147       h = (h + %d) & %d;\n\
 148     }\n\
 149   return NULL;\n\
 150 }\n", namebuf, argv[3], size-1, skip, size-1);
 151
 152   return 0;
 153 }