perfhlib.cpp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448
  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 int NumEntry; /* Number of entries in the hash table (# keys) */
  12. static int EntryLen; /* Size (bytes) of each entry (size of keys) */
  13. static int SetSize; /* Size of the char set */
  14. static char SetMin; /* First char in the set */
  15. static int NumVert; /* c times NumEntry */
  16. static word *T1base, *T2base; /* Pointers to start of T1, T2 */
  17. static word *T1, *T2; /* Pointers to T1[i], T2[i] */
  18. static int *graphNode; /* The array of edges */
  19. static int *graphNext; /* Linked list of edges */
  20. static int *graphFirst;/* First edge at a vertex */
  21. static short *g; /* g[] */
  22. static int numEdges; /* An edge counter */
  23. static bool *visited; /* Array of bools: whether visited */
  24. /* Private prototypes */
  25. static void initGraph(void);
  26. static void addToGraph(int e, int v1, int v2);
  27. static bool isCycle(void);
  28. static void duplicateKeys(int v1, int v2);
  29. void
  30. hashParams(int _NumEntry, int _EntryLen, int _SetSize, char _SetMin,
  31. int _NumVert)
  32. {
  33. /* These parameters are stored in statics so as to obviate the need for
  34. passing all these (or defererencing pointers) for every call to hash()
  35. */
  36. NumEntry = _NumEntry;
  37. EntryLen = _EntryLen;
  38. SetSize = _SetSize;
  39. SetMin = _SetMin;
  40. NumVert = _NumVert;
  41. /* Allocate the variable sized tables etc */
  42. if ((T1base = (word *)malloc(EntryLen * SetSize * sizeof(word))) == 0)
  43. {
  44. goto BadAlloc;
  45. }
  46. if ((T2base = (word *)malloc(EntryLen * SetSize * sizeof(word))) == 0)
  47. {
  48. goto BadAlloc;
  49. }
  50. if ((graphNode = (int *)malloc((NumEntry*2 + 1) * sizeof(int))) == 0)
  51. {
  52. goto BadAlloc;
  53. }
  54. if ((graphNext = (int *)malloc((NumEntry*2 + 1) * sizeof(int))) == 0)
  55. {
  56. goto BadAlloc;
  57. }
  58. if ((graphFirst = (int *)malloc((NumVert + 1) * sizeof(int))) == 0)
  59. {
  60. goto BadAlloc;
  61. }
  62. if ((g = (short *)malloc((NumVert+1) * sizeof(short))) == 0)
  63. {
  64. goto BadAlloc;
  65. }
  66. if ((visited = (bool *)malloc((NumVert+1) * sizeof(bool))) == 0)
  67. {
  68. goto BadAlloc;
  69. }
  70. return;
  71. BadAlloc:
  72. printf("Could not allocate memory\n");
  73. hashCleanup();
  74. exit(1);
  75. }
  76. void
  77. hashCleanup(void)
  78. {
  79. /* Free the storage for variable sized tables etc */
  80. if (T1base) free(T1base);
  81. if (T2base) free(T2base);
  82. if (graphNode) free(graphNode);
  83. if (graphNext) free(graphNext);
  84. if (graphFirst) free(graphFirst);
  85. if (g) free(g);
  86. }
  87. void
  88. map(void)
  89. {
  90. int i, j, c;
  91. word f1, f2;
  92. bool cycle;
  93. byte *keys;
  94. c = 0;
  95. do
  96. {
  97. initGraph();
  98. cycle = FALSE;
  99. /* Randomly generate T1 and T2 */
  100. for (i=0; i < SetSize*EntryLen; i++)
  101. {
  102. T1base[i] = rand() % NumVert;
  103. T2base[i] = rand() % NumVert;
  104. }
  105. for (i=0; i < NumEntry; i++)
  106. {
  107. f1 = 0; f2 = 0;
  108. getKey(i, &keys);
  109. for (j=0; j < EntryLen; j++)
  110. {
  111. T1 = T1base + j * SetSize;
  112. T2 = T2base + j * SetSize;
  113. f1 += T1[keys[j] - SetMin];
  114. f2 += T2[keys[j] - SetMin];
  115. }
  116. f1 %= (word)NumVert;
  117. f2 %= (word)NumVert;
  118. if (f1 == f2)
  119. {
  120. /* A self loop. Reject! */
  121. printf("Self loop on vertex %d!\n", f1);
  122. cycle = TRUE;
  123. break;
  124. }
  125. addToGraph(numEdges++, f1, f2);
  126. }
  127. if (cycle || (cycle = isCycle())) /* OK - is there a cycle? */
  128. {
  129. printf("Iteration %d\n", ++c);
  130. }
  131. else
  132. {
  133. break;
  134. }
  135. }
  136. while (/* there is a cycle */ 1);
  137. }
  138. /* Initialise the graph */
  139. static void
  140. initGraph(void)
  141. {
  142. int i;
  143. for (i=1; i <= NumVert; i++)
  144. {
  145. graphFirst[i] = 0;
  146. }
  147. for (i= -NumEntry; i <= NumEntry; i++)
  148. {
  149. /* No need to init graphNode[] as they will all be filled by successive
  150. calls to addToGraph() */
  151. graphNext[NumEntry+i] = 0;
  152. }
  153. numEdges = 0;
  154. }
  155. /* Add an edge e between vertices v1 and v2 */
  156. /* e, v1, v2 are 0 based */
  157. static void
  158. addToGraph(int e, int v1, int v2)
  159. {
  160. e++; v1++; v2++; /* So much more convenient */
  161. graphNode[NumEntry+e] = v2; /* Insert the edge information */
  162. graphNode[NumEntry-e] = v1;
  163. graphNext[NumEntry+e] = graphFirst[v1]; /* Insert v1 to list of alphas */
  164. graphFirst[v1]= e;
  165. graphNext[NumEntry-e] = graphFirst[v2]; /* Insert v2 to list of omegas */
  166. graphFirst[v2]= -e;
  167. }
  168. bool DFS(int parentE, int v)
  169. {
  170. int e, w;
  171. /* Depth first search of the graph, starting at vertex v, looking for
  172. cycles. parent and v are origin 1. Note parent is an EDGE,
  173. not a vertex */
  174. visited[v] = TRUE;
  175. /* For each e incident with v .. */
  176. for (e = graphFirst[v]; e; e = graphNext[NumEntry+e])
  177. {
  178. byte *key1;
  179. getKey(abs(e)-1, &key1);
  180. if (*(long *)key1 == 0)
  181. {
  182. /* A deleted key. Just ignore it */
  183. continue;
  184. }
  185. w = graphNode[NumEntry+e];
  186. if (visited[w])
  187. {
  188. /* Did we just come through this edge? If so, ignore it. */
  189. if (abs(e) != abs(parentE))
  190. {
  191. /* There is a cycle in the graph. There is some subtle code here
  192. to work around the distinct possibility that there may be
  193. duplicate keys. Duplicate keys will always cause unit
  194. cycles, since f1 and f2 (used to select v and w) will be the
  195. same for both. The edges (representing an index into the
  196. array of keys) are distinct, but the key values are not.
  197. The logic is as follows: for the candidate edge e, check to
  198. see if it terminates in the parent vertex. If so, we test
  199. the keys associated with e and the parent, and if they are
  200. the same, we can safely ignore e for the purposes of cycle
  201. detection, since edge e adds nothing to the cycle. Cycles
  202. involving v, w, and e0 will still be found. The parent
  203. edge was not similarly eliminated because at the time when
  204. it was a candidate, v was not yet visited.
  205. We still have to remove the key from further consideration,
  206. since each edge is visited twice, but with a different
  207. parent edge each time.
  208. */
  209. /* We save some stack space by calculating the parent vertex
  210. for these relatively few cases where it is needed */
  211. int parentV = graphNode[NumEntry-parentE];
  212. if (w == parentV)
  213. {
  214. byte *key2;
  215. getKey(abs(parentE)-1, &key2);
  216. if (memcmp(key1, key2, EntryLen) == 0)
  217. {
  218. printf("Duplicate keys with edges %d and %d (",
  219. e, parentE);
  220. dispKey(abs(e)-1);
  221. printf(" & ");
  222. dispKey(abs(parentE)-1);
  223. printf(")\n");
  224. /* *(long *)key1 = 0; /* Wipe the key */
  225. memset(key1, 0, EntryLen);
  226. }
  227. else
  228. {
  229. /* A genuine (unit) cycle. */
  230. printf("There is a unit cycle involving vertex %d and edge %d\n", v, e);
  231. return TRUE;
  232. }
  233. }
  234. else
  235. {
  236. /* We have reached a previously visited vertex not the
  237. parent. Therefore, we have uncovered a genuine cycle */
  238. printf("There is a cycle involving vertex %d and edge %d\n", v, e);
  239. return TRUE;
  240. }
  241. }
  242. }
  243. else /* Not yet seen. Traverse it */
  244. {
  245. if (DFS(e, w))
  246. {
  247. /* Cycle found deeper down. Exit */
  248. return TRUE;
  249. }
  250. }
  251. }
  252. return FALSE;
  253. }
  254. static bool
  255. isCycle(void)
  256. {
  257. int v;
  258. for (v=1; v <= NumVert; v++)
  259. {
  260. visited[v] = FALSE;
  261. }
  262. for (v=1; v <= NumVert; v++)
  263. {
  264. if (!visited[v])
  265. {
  266. if (DFS(-32767, v))
  267. {
  268. return TRUE;
  269. }
  270. }
  271. }
  272. return FALSE;
  273. }
  274. void
  275. traverse(int u)
  276. {
  277. int w, e;
  278. visited[u] = TRUE;
  279. /* Find w, the neighbours of u, by searching the edges e associated with u */
  280. e = graphFirst[1+u];
  281. while (e)
  282. {
  283. w = graphNode[NumEntry+e]-1;
  284. if (!visited[w])
  285. {
  286. g[w] = (abs(e)-1 - g[u]) % NumEntry;
  287. if (g[w] < 0) g[w] += NumEntry; /* Keep these positive */
  288. traverse(w);
  289. }
  290. e = graphNext[NumEntry+e];
  291. }
  292. }
  293. void
  294. assign(void)
  295. {
  296. int v;
  297. for (v=0; v < NumVert; v++)
  298. {
  299. g[v] = 0; /* g is sparse; leave the gaps 0 */
  300. visited[v] = FALSE;
  301. }
  302. for (v=0; v < NumVert; v++)
  303. {
  304. if (!visited[v])
  305. {
  306. g[v] = 0;
  307. traverse(v);
  308. }
  309. }
  310. }
  311. int
  312. hash(byte *string)
  313. {
  314. word u, v;
  315. int j;
  316. u = 0;
  317. for (j=0; j < EntryLen; j++)
  318. {
  319. T1 = T1base + j * SetSize;
  320. u += T1[string[j] - SetMin];
  321. }
  322. u %= NumVert;
  323. v = 0;
  324. for (j=0; j < EntryLen; j++)
  325. {
  326. T2 = T2base + j * SetSize;
  327. v += T2[string[j] - SetMin];
  328. }
  329. v %= NumVert;
  330. return (g[u] + g[v]) % NumEntry;
  331. }
  332. word *
  333. readT1(void)
  334. {
  335. return T1base;
  336. }
  337. word *
  338. readT2(void)
  339. {
  340. return T2base;
  341. }
  342. word *
  343. readG(void)
  344. {
  345. return (word *)g;
  346. }
  347. #if 0
  348. void dispRecord(int i);
  349. void
  350. duplicateKeys(int v1, int v2)
  351. {
  352. int i, j;
  353. byte *keys;
  354. int u, v;
  355. v1--; v2--; /* These guys are origin 1 */
  356. printf("Duplicate keys:\n");
  357. for (i=0; i < NumEntry; i++)
  358. {
  359. getKey(i, &keys);
  360. u = 0;
  361. for (j=0; j < EntryLen; j++)
  362. {
  363. T1 = T1base + j * SetSize;
  364. u += T1[keys[j] - SetMin];
  365. }
  366. u %= NumVert;
  367. if ((u != v1) && (u != v2)) continue;
  368. v = 0;
  369. for (j=0; j < EntryLen; j++)
  370. {
  371. T2 = T2base + j * SetSize;
  372. v += T2[keys[j] - SetMin];
  373. }
  374. v %= NumVert;
  375. if ((v == v2) || (v == v1))
  376. {
  377. printf("Entry #%d key: ", i+1);
  378. for (j=0; j < EntryLen; j++) printf("%02X ", keys[j]);
  379. printf("\n");
  380. dispRecord(i+1);
  381. }
  382. }
  383. exit(1);
  384. }
  385. #endif