perfhlib.cpp 2.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
  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 uint16_t *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 uint16_t [EntryLen * SetSize];
  35. T2base = new uint16_t [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. }
  43. void PatternHasher::cleanup(void)
  44. {
  45. /* Free the storage for variable sized tables etc */
  46. delete [] T1base;
  47. delete [] T2base;
  48. delete [] graphNode;
  49. delete [] graphNext;
  50. delete [] graphFirst;
  51. delete [] g;
  52. // delete [] visited;
  53. }
  54. int PatternHasher::hash(uint8_t *string)
  55. {
  56. uint16_t u, v;
  57. int j;
  58. u = 0;
  59. for (j=0; j < EntryLen; j++)
  60. {
  61. T1 = T1base + j * SetSize;
  62. u += T1[string[j] - SetMin];
  63. }
  64. u %= NumVert;
  65. v = 0;
  66. for (j=0; j < EntryLen; j++)
  67. {
  68. T2 = T2base + j * SetSize;
  69. v += T2[string[j] - SetMin];
  70. }
  71. v %= NumVert;
  72. return (g[u] + g[v]) % NumEntry;
  73. }
  74. uint16_t * PatternHasher::readT1(void)
  75. {
  76. return T1base;
  77. }
  78. uint16_t *PatternHasher::readT2(void)
  79. {
  80. return T2base;
  81. }
  82. uint16_t * PatternHasher::readG(void)
  83. {
  84. return (uint16_t *)g;
  85. }