perfhlib.h 1.5 KB

12345678910111213141516171819202122232425262728293031323334353637
  1. #include <stdint.h>
  2. /** Perfect hashing function library. Contains functions to generate perfect
  3. hashing functions */
  4. struct PatternCollector;
  5. struct PerfectHash {
  6. uint16_t *T1base;
  7. uint16_t *T2base; /* Pointers to start of T1, T2 */
  8. short *g; /* g[] */
  9. int NumEntry; /* Number of entries in the hash table (# keys) */
  10. int EntryLen; /* Size (bytes) of each entry (size of keys) */
  11. int SetSize; /* Size of the char set */
  12. char SetMin; /* First char in the set */
  13. int NumVert; /* c times NumEntry */
  14. /** Set the parameters for the hash table */
  15. void setHashParams(int _numEntry, int _entryLen, int _setSize, char _setMin, int _numVert);
  16. public:
  17. void map(PatternCollector * collector); /* Part 1 of creating the tables */
  18. void hashCleanup(); /* Frees memory allocated by setHashParams() */
  19. void assign(); /* Part 2 of creating the tables */
  20. int hash(uint8_t *string); /* Hash the string to an int 0 .. NUMENTRY-1 */
  21. const uint16_t *readT1(void) const { return T1base; }
  22. const uint16_t *readT2(void) const { return T2base; }
  23. const uint16_t *readG(void) const { return (uint16_t *)g; }
  24. uint16_t *readT1(void){ return T1base; }
  25. uint16_t *readT2(void){ return T2base; }
  26. uint16_t *readG(void) { return (uint16_t *)g; }
  27. private:
  28. void initGraph();
  29. void addToGraph(int e, int v1, int v2);
  30. bool isCycle();
  31. bool DFS(int parentE, int v);
  32. void traverse(int u);
  33. PatternCollector *m_collector; /* used to retrieve the keys */
  34. };