perfhlib.cpp 2.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
  1. /*
  2. * Perfect hashing function library. Contains functions to generate perfect
  3. * hashing functions
  4. * (C) Mike van Emmerik
  5. */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include "perfhlib.h"
  10. /* Private data structures */
  11. static word *T1, *T2; /* Pointers to T1[i], T2[i] */
  12. static short *g; /* g[] */
  13. static int numEdges; /* An edge counter */
  14. //static bool *visited; /* Array of bools: whether visited */
  15. /* Private prototypes */
  16. static void initGraph(void);
  17. static void addToGraph(int e, int v1, int v2);
  18. static bool isCycle(void);
  19. static void duplicateKeys(int v1, int v2);
  20. PatternHasher g_pattern_hasher;
  21. void
  22. PatternHasher::init(int _NumEntry, int _EntryLen, int _SetSize, char _SetMin,
  23. int _NumVert)
  24. {
  25. /* These parameters are stored in statics so as to obviate the need for
  26. passing all these (or defererencing pointers) for every call to hash()
  27. */
  28. NumEntry = _NumEntry;
  29. EntryLen = _EntryLen;
  30. SetSize = _SetSize;
  31. SetMin = _SetMin;
  32. NumVert = _NumVert;
  33. /* Allocate the variable sized tables etc */
  34. T1base = new word [EntryLen * SetSize];
  35. T2base = new word [EntryLen * SetSize];
  36. graphNode = new int [NumEntry*2 + 1];
  37. graphNext = new int [NumEntry*2 + 1];
  38. graphFirst = new int [NumVert + 1];
  39. g = new short [NumVert + 1];
  40. // visited = new bool [NumVert + 1];
  41. return;
  42. BadAlloc:
  43. printf("Could not allocate memory\n");
  44. cleanup();
  45. exit(1);
  46. }
  47. void PatternHasher::cleanup(void)
  48. {
  49. /* Free the storage for variable sized tables etc */
  50. delete [] T1base;
  51. delete [] T2base;
  52. delete [] graphNode;
  53. delete [] graphNext;
  54. delete [] graphFirst;
  55. delete [] g;
  56. // delete [] visited;
  57. }
  58. int PatternHasher::hash(byte *string)
  59. {
  60. word u, v;
  61. int j;
  62. u = 0;
  63. for (j=0; j < EntryLen; j++)
  64. {
  65. T1 = T1base + j * SetSize;
  66. u += T1[string[j] - SetMin];
  67. }
  68. u %= NumVert;
  69. v = 0;
  70. for (j=0; j < EntryLen; j++)
  71. {
  72. T2 = T2base + j * SetSize;
  73. v += T2[string[j] - SetMin];
  74. }
  75. v %= NumVert;
  76. return (g[u] + g[v]) % NumEntry;
  77. }
  78. word * PatternHasher::readT1(void)
  79. {
  80. return T1base;
  81. }
  82. word *PatternHasher::readT2(void)
  83. {
  84. return T2base;
  85. }
  86. word * PatternHasher::readG(void)
  87. {
  88. return (word *)g;
  89. }