perfhlib.cpp 2.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
  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 PatternHasher::init(int _NumEntry, int _EntryLen, int _SetSize, char _SetMin, int _NumVert)
  22. {
  23. /* These parameters are stored in statics so as to obviate the need for
  24. passing all these (or defererencing pointers) for every call to hash()
  25. */
  26. NumEntry = _NumEntry;
  27. EntryLen = _EntryLen;
  28. SetSize = _SetSize;
  29. SetMin = _SetMin;
  30. NumVert = _NumVert;
  31. /* Allocate the variable sized tables etc */
  32. T1base = new uint16_t [EntryLen * SetSize];
  33. T2base = new uint16_t [EntryLen * SetSize];
  34. graphNode = new int [NumEntry*2 + 1];
  35. graphNext = new int [NumEntry*2 + 1];
  36. graphFirst = new int [NumVert + 1];
  37. g = new short [NumVert + 1];
  38. // visited = new bool [NumVert + 1];
  39. return;
  40. }
  41. void PatternHasher::cleanup(void)
  42. {
  43. /* Free the storage for variable sized tables etc */
  44. delete [] T1base;
  45. delete [] T2base;
  46. delete [] graphNode;
  47. delete [] graphNext;
  48. delete [] graphFirst;
  49. delete [] g;
  50. // delete [] visited;
  51. }
  52. int PatternHasher::hash(uint8_t *string)
  53. {
  54. uint16_t u, v;
  55. int j;
  56. u = 0;
  57. for (j=0; j < EntryLen; j++)
  58. {
  59. T1 = T1base + j * SetSize;
  60. u += T1[string[j] - SetMin];
  61. }
  62. u %= NumVert;
  63. v = 0;
  64. for (j=0; j < EntryLen; j++)
  65. {
  66. T2 = T2base + j * SetSize;
  67. v += T2[string[j] - SetMin];
  68. }
  69. v %= NumVert;
  70. return (g[u] + g[v]) % NumEntry;
  71. }
  72. uint16_t * PatternHasher::readT1(void)
  73. {
  74. return T1base;
  75. }
  76. uint16_t *PatternHasher::readT2(void)
  77. {
  78. return T2base;
  79. }
  80. uint16_t * PatternHasher::readG(void)
  81. {
  82. return (uint16_t *)g;
  83. }