hash.c 2.0 KB

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