perfhlib.h 1.6 KB

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