hash.c 2.0 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
  1. /* $Id$ */
  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 <stdlib.h>
  12. #include <stdio.h>
  13. #include "misc.h"
  14. struct hlist { /* linear list of pattern numbers */
  15. int h_patno;
  16. struct hlist *h_next;
  17. };
  18. static struct hlist *hashtable[129]; /* an array of ptr's to these lists,
  19. * the index in the array is the
  20. * result of hashing
  21. */
  22. static unsigned
  23. hash(string) char *string; {
  24. register char *p;
  25. register unsigned i,sum;
  26. if (strcmp(string,"ANY") == 0) return 128;
  27. for (sum=i=0,p=string;*p;i += 3)
  28. sum += (*p++)<<(i&03);
  29. return sum % 128;
  30. }
  31. addtohashtable(s,n) char *s; {
  32. /*
  33. * Add a new pattern number to the hashtable.
  34. * s is the key, n the pattern number
  35. */
  36. unsigned hval;
  37. register struct hlist *p;
  38. hval = hash(s);
  39. p = (struct hlist *) malloc(sizeof *p);
  40. p->h_patno = n;
  41. /*
  42. * Now insert in front of the list
  43. * This way, the list will be sorted from high to low, which is the
  44. * wrong way around, but easy
  45. */
  46. p->h_next = hashtable[hval];
  47. hashtable[hval] = p;
  48. }
  49. static
  50. prhlist(p) struct hlist *p; {
  51. /*
  52. * Print a list in reversed order (see comment above)
  53. */
  54. if (p) {
  55. prhlist(p->h_next);
  56. fprintf(genc,"%d, ",p->h_patno - 1);
  57. }
  58. }
  59. printhashtable() {
  60. /*
  61. * Print the linear lists, and also output an array of
  62. * pointers to them
  63. */
  64. register i;
  65. register struct hlist *p;
  66. for (i = 1; i <= 128; i++) {
  67. fprintf(genc,"int hash%d[] = { ",i);
  68. prhlist(hashtable[i-1]);
  69. fputs("-1};\n",genc);
  70. }
  71. fputs("int hashany[] = { ", genc);
  72. prhlist(hashtable[128]);
  73. fputs("-1 };\n",genc);
  74. fputs("int *hashtab[] = {\n",genc);
  75. for (i = 1; i <= 128; i++) fprintf(genc,"\thash%d,\n",i);
  76. fputs("\thashany\n};\n",genc);
  77. }