util/topgen/hash.c

   1 /* $Id: hash.c,v 1.6 1994/06/24 10:42:06 ceriel Exp $ */
   2 /*
   3  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   4  * See the copyright notice in the ACK home directory, in the file "Copyright".
   5  */
   6 /* h a s h . c
   7  *
   8  * maintains the the lists of hashed patterns
   9  * Functions : addtohashtable() and printhashtable()
  10  */
  11 # include <stdio.h>
  12 # include "misc.h"
  13
  14 struct hlist {                  /* linear list of pattern numbers */
  15     int h_patno;
  16     struct hlist *h_next;
  17 };
  18
  19 static struct hlist *hashtable[129];    /* an array of ptr's to these lists,
  20                                          * the index in the array is the
  21                                          * result of hashing
  22                                          */
  23
  24 static unsigned
  25 hash(string) char *string; {
  26         register char *p;
  27         register unsigned i,sum;
  28
  29         if (strcmp(string,"ANY") == 0) return 128;
  30         for (sum=i=0,p=string;*p;i += 3)
  31                 sum += (*p++)<<(i&03);
  32         return sum % 128;
  33 }
  34
  35
  36 addtohashtable(s,n) char *s; {
  37     /*
  38      * Add a new pattern number to the hashtable.
  39      * s is the key, n the pattern number
  40      */
  41     unsigned hval;
  42     register struct hlist *p;
  43     char *malloc();
  44
  45     hval = hash(s);
  46     p = (struct hlist *) malloc(sizeof *p);
  47     p->h_patno = n;
  48     /*
  49      * Now insert in front of the list
  50      * This way, the list will be sorted from high to low, which is the
  51      * wrong way around, but easy
  52      */
  53     p->h_next = hashtable[hval];
  54     hashtable[hval] = p;
  55 }
  56
  57 static
  58 prhlist(p) struct hlist *p; {
  59     /*
  60      * Print a list in reversed order (see comment above)
  61      */
  62
  63     if (p) {
  64         prhlist(p->h_next);
  65         fprintf(genc,"%d, ",p->h_patno - 1);
  66     }
  67 }
  68
  69 printhashtable() {
  70     /*
  71      * Print the linear lists, and also output an array of
  72      * pointers to them
  73      */
  74     register i;
  75     register struct hlist *p;
  76
  77     for (i = 1; i <= 128; i++) {
  78         fprintf(genc,"int hash%d[] = { ",i);
  79         prhlist(hashtable[i-1]);
  80         fputs("-1};\n",genc);
  81     }
  82     fputs("int hashany[] = { ", genc);
  83     prhlist(hashtable[128]);
  84     fputs("-1 };\n",genc);
  85     fputs("int *hashtab[] = {\n",genc);
  86     for (i = 1; i <= 128; i++) fprintf(genc,"\thash%d,\n",i);
  87     fputs("\thashany\n};\n",genc);
  88 }