Branch data Line data Source code
1 : : #include "graph.h"
2 : : #include "bmz8.h"
3 : : #include "cmph_structs.h"
4 : : #include "bmz8_structs.h"
5 : : #include "hash.h"
6 : : #include "vqueue.h"
7 : : #include "bitbool.h"
8 : : #include <math.h>
9 : : #include <stdlib.h>
10 : : #include <stdio.h>
11 : : #include <assert.h>
12 : : #include <string.h>
13 : : #include <errno.h>
14 : :
15 : : //#define DEBUG
16 : : #include "debug.h"
17 : :
18 : : static int bmz8_gen_edges(cmph_config_t *mph);
19 : : static cmph_uint8 bmz8_traverse_critical_nodes(bmz8_config_data_t *bmz8, cmph_uint32 v, cmph_uint8 * biggest_g_value, cmph_uint8 * biggest_edge_value, cmph_uint8 * used_edges, cmph_uint8 * visited);
20 : : static cmph_uint8 bmz8_traverse_critical_nodes_heuristic(bmz8_config_data_t *bmz8, cmph_uint32 v, cmph_uint8 * biggest_g_value, cmph_uint8 * biggest_edge_value, cmph_uint8 * used_edges, cmph_uint8 * visited);
21 : : static void bmz8_traverse_non_critical_nodes(bmz8_config_data_t *bmz8, cmph_uint8 * used_edges, cmph_uint8 * visited);
22 : :
23 : 0 : bmz8_config_data_t *bmz8_config_new(void)
24 : : {
25 : : bmz8_config_data_t *bmz8;
26 : 0 : bmz8 = (bmz8_config_data_t *)malloc(sizeof(bmz8_config_data_t));
27 : 0 : assert(bmz8);
28 : 0 : memset(bmz8, 0, sizeof(bmz8_config_data_t));
29 : 0 : bmz8->hashfuncs[0] = CMPH_HASH_JENKINS;
30 : 0 : bmz8->hashfuncs[1] = CMPH_HASH_JENKINS;
31 : 0 : bmz8->g = NULL;
32 : 0 : bmz8->graph = NULL;
33 : 0 : bmz8->hashes = NULL;
34 : 0 : return bmz8;
35 : : }
36 : :
37 : 0 : void bmz8_config_destroy(cmph_config_t *mph)
38 : : {
39 : 0 : bmz8_config_data_t *data = (bmz8_config_data_t *)mph->data;
40 : : DEBUGP("Destroying algorithm dependent data\n");
41 : 0 : free(data);
42 : 0 : }
43 : :
44 : 0 : void bmz8_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs)
45 : : {
46 : 0 : bmz8_config_data_t *bmz8 = (bmz8_config_data_t *)mph->data;
47 : 0 : CMPH_HASH *hashptr = hashfuncs;
48 : 0 : cmph_uint8 i = 0;
49 : 0 : while(*hashptr != CMPH_HASH_COUNT)
50 : : {
51 : 0 : if (i >= 2) break; //bmz8 only uses two hash functions
52 : 0 : bmz8->hashfuncs[i] = *hashptr;
53 : 0 : ++i, ++hashptr;
54 : : }
55 : 0 : }
56 : :
57 : 0 : cmph_t *bmz8_new(cmph_config_t *mph, double c)
58 : : {
59 : 0 : cmph_t *mphf = NULL;
60 : 0 : bmz8_data_t *bmz8f = NULL;
61 : : cmph_uint8 i;
62 : : cmph_uint8 iterations;
63 : 0 : cmph_uint8 iterations_map = 20;
64 : 0 : cmph_uint8 *used_edges = NULL;
65 : 0 : cmph_uint8 restart_mapping = 0;
66 : 0 : cmph_uint8 * visited = NULL;
67 : 0 : bmz8_config_data_t *bmz8 = (bmz8_config_data_t *)mph->data;
68 : :
69 : 0 : if (mph->key_source->nkeys >= 256)
70 : : {
71 : 0 : if (mph->verbosity) fprintf(stderr, "The number of keys in BMZ8 must be lower than 256.\n");
72 : 0 : return NULL;
73 : : }
74 : 0 : if (c == 0) c = 1.15; // validating restrictions over parameter c.
75 : : DEBUGP("c: %f\n", c);
76 : 0 : bmz8->m = (cmph_uint8) mph->key_source->nkeys;
77 : 0 : bmz8->n = (cmph_uint8) ceil(c * mph->key_source->nkeys);
78 : : DEBUGP("m (edges): %u n (vertices): %u c: %f\n", bmz8->m, bmz8->n, c);
79 : 0 : bmz8->graph = graph_new(bmz8->n, bmz8->m);
80 : : DEBUGP("Created graph\n");
81 : :
82 : 0 : bmz8->hashes = (hash_state_t **)malloc(sizeof(hash_state_t *)*3);
83 : 0 : for(i = 0; i < 3; ++i) bmz8->hashes[i] = NULL;
84 : :
85 : : do
86 : : {
87 : : // Mapping step
88 : 0 : cmph_uint8 biggest_g_value = 0;
89 : 0 : cmph_uint8 biggest_edge_value = 1;
90 : 0 : iterations = 100;
91 : 0 : if (mph->verbosity)
92 : : {
93 : 0 : fprintf(stderr, "Entering mapping step for mph creation of %u keys with graph sized %u\n", bmz8->m, bmz8->n);
94 : : }
95 : : while(1)
96 : 0 : {
97 : : int ok;
98 : : DEBUGP("hash function 1\n");
99 : 0 : bmz8->hashes[0] = hash_state_new(bmz8->hashfuncs[0], bmz8->n);
100 : : DEBUGP("hash function 2\n");
101 : 0 : bmz8->hashes[1] = hash_state_new(bmz8->hashfuncs[1], bmz8->n);
102 : : DEBUGP("Generating edges\n");
103 : 0 : ok = bmz8_gen_edges(mph);
104 : 0 : if (!ok)
105 : : {
106 : 0 : --iterations;
107 : 0 : hash_state_destroy(bmz8->hashes[0]);
108 : 0 : bmz8->hashes[0] = NULL;
109 : 0 : hash_state_destroy(bmz8->hashes[1]);
110 : 0 : bmz8->hashes[1] = NULL;
111 : : DEBUGP("%u iterations remaining\n", iterations);
112 : 0 : if (mph->verbosity)
113 : : {
114 : 0 : fprintf(stderr, "simple graph creation failure - %u iterations remaining\n", iterations);
115 : : }
116 : 0 : if (iterations == 0) break;
117 : : }
118 : 0 : else break;
119 : : }
120 : 0 : if (iterations == 0)
121 : : {
122 : 0 : graph_destroy(bmz8->graph);
123 : 0 : return NULL;
124 : : }
125 : :
126 : : // Ordering step
127 : 0 : if (mph->verbosity)
128 : : {
129 : 0 : fprintf(stderr, "Starting ordering step\n");
130 : : }
131 : :
132 : 0 : graph_obtain_critical_nodes(bmz8->graph);
133 : :
134 : : // Searching step
135 : 0 : if (mph->verbosity)
136 : : {
137 : 0 : fprintf(stderr, "Starting Searching step.\n");
138 : 0 : fprintf(stderr, "\tTraversing critical vertices.\n");
139 : : }
140 : : DEBUGP("Searching step\n");
141 : 0 : visited = (cmph_uint8 *)malloc((size_t)bmz8->n/8 + 1);
142 : 0 : memset(visited, 0, (size_t)bmz8->n/8 + 1);
143 : 0 : used_edges = (cmph_uint8 *)malloc((size_t)bmz8->m/8 + 1);
144 : 0 : memset(used_edges, 0, (size_t)bmz8->m/8 + 1);
145 : 0 : free(bmz8->g);
146 : 0 : bmz8->g = (cmph_uint8 *)calloc((size_t)bmz8->n, sizeof(cmph_uint8));
147 : 0 : assert(bmz8->g);
148 : 0 : for (i = 0; i < bmz8->n; ++i) // critical nodes
149 : : {
150 : 0 : if (graph_node_is_critical(bmz8->graph, i) && (!GETBIT(visited,i)))
151 : : {
152 : 0 : if(c > 1.14) restart_mapping = bmz8_traverse_critical_nodes(bmz8, i, &biggest_g_value, &biggest_edge_value, used_edges, visited);
153 : 0 : else restart_mapping = bmz8_traverse_critical_nodes_heuristic(bmz8, i, &biggest_g_value, &biggest_edge_value, used_edges, visited);
154 : 0 : if(restart_mapping) break;
155 : : }
156 : : }
157 : 0 : if(!restart_mapping)
158 : : {
159 : 0 : if (mph->verbosity)
160 : : {
161 : 0 : fprintf(stderr, "\tTraversing non critical vertices.\n");
162 : : }
163 : 0 : bmz8_traverse_non_critical_nodes(bmz8, used_edges, visited); // non_critical_nodes
164 : : }
165 : : else
166 : : {
167 : 0 : iterations_map--;
168 : 0 : if (mph->verbosity) fprintf(stderr, "Restarting mapping step. %u iterations remaining.\n", iterations_map);
169 : : }
170 : :
171 : 0 : free(used_edges);
172 : 0 : free(visited);
173 : :
174 : 0 : }while(restart_mapping && iterations_map > 0);
175 : 0 : graph_destroy(bmz8->graph);
176 : 0 : bmz8->graph = NULL;
177 : 0 : if (iterations_map == 0)
178 : : {
179 : 0 : return NULL;
180 : : }
181 : 0 : mphf = (cmph_t *)malloc(sizeof(cmph_t));
182 : 0 : mphf->algo = mph->algo;
183 : 0 : bmz8f = (bmz8_data_t *)malloc(sizeof(bmz8_data_t));
184 : 0 : bmz8f->g = bmz8->g;
185 : 0 : bmz8->g = NULL; //transfer memory ownership
186 : 0 : bmz8f->hashes = bmz8->hashes;
187 : 0 : bmz8->hashes = NULL; //transfer memory ownership
188 : 0 : bmz8f->n = bmz8->n;
189 : 0 : bmz8f->m = bmz8->m;
190 : 0 : mphf->data = bmz8f;
191 : 0 : mphf->size = bmz8->m;
192 : : DEBUGP("Successfully generated minimal perfect hash\n");
193 : 0 : if (mph->verbosity)
194 : : {
195 : 0 : fprintf(stderr, "Successfully generated minimal perfect hash function\n");
196 : : }
197 : 0 : return mphf;
198 : : }
199 : :
200 : 0 : static cmph_uint8 bmz8_traverse_critical_nodes(bmz8_config_data_t *bmz8, cmph_uint32 v, cmph_uint8 * biggest_g_value, cmph_uint8 * biggest_edge_value, cmph_uint8 * used_edges, cmph_uint8 * visited)
201 : : {
202 : : cmph_uint8 next_g;
203 : : cmph_uint32 u; /* Auxiliary vertex */
204 : : cmph_uint32 lav; /* lookahead vertex */
205 : : cmph_uint8 collision;
206 : 0 : vqueue_t * q = vqueue_new((cmph_uint32)(graph_ncritical_nodes(bmz8->graph)));
207 : : graph_iterator_t it, it1;
208 : :
209 : : DEBUGP("Labelling critical vertices\n");
210 : 0 : bmz8->g[v] = (cmph_uint8)(ceil ((double)(*biggest_edge_value)/2) - 1);
211 : 0 : SETBIT(visited, v);
212 : 0 : next_g = (cmph_uint8)floor((double)(*biggest_edge_value/2)); /* next_g is incremented in the do..while statement*/
213 : 0 : vqueue_insert(q, v);
214 : 0 : while(!vqueue_is_empty(q))
215 : : {
216 : 0 : v = vqueue_remove(q);
217 : 0 : it = graph_neighbors_it(bmz8->graph, v);
218 : 0 : while ((u = graph_next_neighbor(bmz8->graph, &it)) != GRAPH_NO_NEIGHBOR)
219 : : {
220 : 0 : if (graph_node_is_critical(bmz8->graph, u) && (!GETBIT(visited,u)))
221 : : {
222 : 0 : collision = 1;
223 : 0 : while(collision) // lookahead to resolve collisions
224 : : {
225 : 0 : next_g = (cmph_uint8)(*biggest_g_value + 1);
226 : 0 : it1 = graph_neighbors_it(bmz8->graph, u);
227 : 0 : collision = 0;
228 : 0 : while((lav = graph_next_neighbor(bmz8->graph, &it1)) != GRAPH_NO_NEIGHBOR)
229 : : {
230 : 0 : if (graph_node_is_critical(bmz8->graph, lav) && GETBIT(visited,lav))
231 : : {
232 : 0 : if(next_g + bmz8->g[lav] >= bmz8->m)
233 : : {
234 : 0 : vqueue_destroy(q);
235 : 0 : return 1; // restart mapping step.
236 : : }
237 : 0 : if (GETBIT(used_edges, (next_g + bmz8->g[lav])))
238 : : {
239 : 0 : collision = 1;
240 : 0 : break;
241 : : }
242 : : }
243 : : }
244 : 0 : if (next_g > *biggest_g_value) *biggest_g_value = next_g;
245 : : }
246 : : // Marking used edges...
247 : 0 : it1 = graph_neighbors_it(bmz8->graph, u);
248 : 0 : while((lav = graph_next_neighbor(bmz8->graph, &it1)) != GRAPH_NO_NEIGHBOR)
249 : : {
250 : 0 : if (graph_node_is_critical(bmz8->graph, lav) && GETBIT(visited, lav))
251 : : {
252 : 0 : SETBIT(used_edges,(next_g + bmz8->g[lav]));
253 : :
254 : 0 : if(next_g + bmz8->g[lav] > *biggest_edge_value)
255 : 0 : *biggest_edge_value = (cmph_uint8)(next_g + bmz8->g[lav]);
256 : : }
257 : : }
258 : 0 : bmz8->g[u] = next_g; // Labelling vertex u.
259 : 0 : SETBIT(visited,u);
260 : 0 : vqueue_insert(q, u);
261 : : }
262 : : }
263 : :
264 : : }
265 : 0 : vqueue_destroy(q);
266 : 0 : return 0;
267 : : }
268 : :
269 : 0 : static cmph_uint8 bmz8_traverse_critical_nodes_heuristic(bmz8_config_data_t *bmz8, cmph_uint32 v, cmph_uint8 * biggest_g_value, cmph_uint8 * biggest_edge_value, cmph_uint8 * used_edges, cmph_uint8 * visited)
270 : : {
271 : : cmph_uint8 next_g;
272 : : cmph_uint32 u;
273 : : cmph_uint32 lav;
274 : : cmph_uint8 collision;
275 : 0 : cmph_uint8 * unused_g_values = NULL;
276 : 0 : cmph_uint8 unused_g_values_capacity = 0;
277 : 0 : cmph_uint8 nunused_g_values = 0;
278 : 0 : vqueue_t * q = vqueue_new((cmph_uint32)(graph_ncritical_nodes(bmz8->graph)));
279 : : graph_iterator_t it, it1;
280 : :
281 : : DEBUGP("Labelling critical vertices\n");
282 : 0 : bmz8->g[v] = (cmph_uint8)(ceil ((double)(*biggest_edge_value)/2) - 1);
283 : 0 : SETBIT(visited, v);
284 : 0 : next_g = (cmph_uint8)floor((double)(*biggest_edge_value/2));
285 : 0 : vqueue_insert(q, v);
286 : 0 : while(!vqueue_is_empty(q))
287 : : {
288 : 0 : v = vqueue_remove(q);
289 : 0 : it = graph_neighbors_it(bmz8->graph, v);
290 : 0 : while ((u = graph_next_neighbor(bmz8->graph, &it)) != GRAPH_NO_NEIGHBOR)
291 : : {
292 : 0 : if (graph_node_is_critical(bmz8->graph, u) && (!GETBIT(visited,u)))
293 : : {
294 : 0 : cmph_uint8 next_g_index = 0;
295 : 0 : collision = 1;
296 : 0 : while(collision) // lookahead to resolve collisions
297 : : {
298 : 0 : if (next_g_index < nunused_g_values)
299 : : {
300 : 0 : next_g = unused_g_values[next_g_index++];
301 : : }
302 : : else
303 : : {
304 : 0 : next_g = (cmph_uint8)(*biggest_g_value + 1);
305 : 0 : next_g_index = 255;//UINT_MAX;
306 : : }
307 : 0 : it1 = graph_neighbors_it(bmz8->graph, u);
308 : 0 : collision = 0;
309 : 0 : while((lav = graph_next_neighbor(bmz8->graph, &it1)) != GRAPH_NO_NEIGHBOR)
310 : : {
311 : 0 : if (graph_node_is_critical(bmz8->graph, lav) && GETBIT(visited,lav))
312 : : {
313 : 0 : if(next_g + bmz8->g[lav] >= bmz8->m)
314 : : {
315 : 0 : vqueue_destroy(q);
316 : 0 : free(unused_g_values);
317 : 0 : return 1; // restart mapping step.
318 : : }
319 : 0 : if (GETBIT(used_edges, (next_g + bmz8->g[lav])))
320 : : {
321 : 0 : collision = 1;
322 : 0 : break;
323 : : }
324 : : }
325 : : }
326 : 0 : if(collision && (next_g > *biggest_g_value)) // saving the current g value stored in next_g.
327 : : {
328 : 0 : if(nunused_g_values == unused_g_values_capacity)
329 : : {
330 : 0 : unused_g_values = (cmph_uint8*)realloc(unused_g_values, ((size_t)(unused_g_values_capacity + BUFSIZ))*sizeof(cmph_uint8));
331 : 0 : unused_g_values_capacity += (cmph_uint8)BUFSIZ;
332 : : }
333 : 0 : unused_g_values[nunused_g_values++] = next_g;
334 : :
335 : : }
336 : 0 : if (next_g > *biggest_g_value) *biggest_g_value = next_g;
337 : : }
338 : :
339 : 0 : next_g_index--;
340 : 0 : if (next_g_index < nunused_g_values) unused_g_values[next_g_index] = unused_g_values[--nunused_g_values];
341 : :
342 : : // Marking used edges...
343 : 0 : it1 = graph_neighbors_it(bmz8->graph, u);
344 : 0 : while((lav = graph_next_neighbor(bmz8->graph, &it1)) != GRAPH_NO_NEIGHBOR)
345 : : {
346 : 0 : if (graph_node_is_critical(bmz8->graph, lav) && GETBIT(visited, lav))
347 : : {
348 : 0 : SETBIT(used_edges,(next_g + bmz8->g[lav]));
349 : 0 : if(next_g + bmz8->g[lav] > *biggest_edge_value)
350 : 0 : *biggest_edge_value = (cmph_uint8)(next_g + bmz8->g[lav]);
351 : : }
352 : : }
353 : :
354 : 0 : bmz8->g[u] = next_g; // Labelling vertex u.
355 : 0 : SETBIT(visited, u);
356 : 0 : vqueue_insert(q, u);
357 : :
358 : : }
359 : : }
360 : :
361 : : }
362 : 0 : vqueue_destroy(q);
363 : 0 : free(unused_g_values);
364 : 0 : return 0;
365 : : }
366 : :
367 : 0 : static cmph_uint8 next_unused_edge(bmz8_config_data_t *bmz8, cmph_uint8 * used_edges, cmph_uint32 unused_edge_index)
368 : : {
369 : : while(1)
370 : : {
371 : 0 : assert(unused_edge_index < bmz8->m);
372 : 0 : if(GETBIT(used_edges, unused_edge_index)) unused_edge_index ++;
373 : 0 : else break;
374 : : }
375 : 0 : return (cmph_uint8)unused_edge_index;
376 : : }
377 : :
378 : 0 : static void bmz8_traverse(bmz8_config_data_t *bmz8, cmph_uint8 * used_edges, cmph_uint32 v, cmph_uint8 * unused_edge_index, cmph_uint8 * visited)
379 : : {
380 : 0 : graph_iterator_t it = graph_neighbors_it(bmz8->graph, v);
381 : 0 : cmph_uint32 neighbor = 0;
382 : 0 : while((neighbor = graph_next_neighbor(bmz8->graph, &it)) != GRAPH_NO_NEIGHBOR)
383 : : {
384 : 0 : if(GETBIT(visited,neighbor)) continue;
385 : : //DEBUGP("Visiting neighbor %u\n", neighbor);
386 : 0 : *unused_edge_index = next_unused_edge(bmz8, used_edges, *unused_edge_index);
387 : 0 : bmz8->g[neighbor] = (cmph_uint8)(*unused_edge_index - bmz8->g[v]);
388 : : //if (bmz8->g[neighbor] >= bmz8->m) bmz8->g[neighbor] += bmz8->m;
389 : 0 : SETBIT(visited, neighbor);
390 : 0 : (*unused_edge_index)++;
391 : 0 : bmz8_traverse(bmz8, used_edges, neighbor, unused_edge_index, visited);
392 : :
393 : : }
394 : 0 : }
395 : :
396 : 0 : static void bmz8_traverse_non_critical_nodes(bmz8_config_data_t *bmz8, cmph_uint8 * used_edges, cmph_uint8 * visited)
397 : : {
398 : :
399 : 0 : cmph_uint8 i, v1, v2, unused_edge_index = 0;
400 : : DEBUGP("Labelling non critical vertices\n");
401 : 0 : for(i = 0; i < bmz8->m; i++)
402 : : {
403 : 0 : v1 = (cmph_uint8)graph_vertex_id(bmz8->graph, i, 0);
404 : 0 : v2 = (cmph_uint8)graph_vertex_id(bmz8->graph, i, 1);
405 : 0 : if((GETBIT(visited,v1) && GETBIT(visited,v2)) || (!GETBIT(visited,v1) && !GETBIT(visited,v2))) continue;
406 : 0 : if(GETBIT(visited,v1)) bmz8_traverse(bmz8, used_edges, v1, &unused_edge_index, visited);
407 : 0 : else bmz8_traverse(bmz8, used_edges, v2, &unused_edge_index, visited);
408 : :
409 : : }
410 : :
411 : 0 : for(i = 0; i < bmz8->n; i++)
412 : : {
413 : 0 : if(!GETBIT(visited,i))
414 : : {
415 : 0 : bmz8->g[i] = 0;
416 : 0 : SETBIT(visited, i);
417 : 0 : bmz8_traverse(bmz8, used_edges, i, &unused_edge_index, visited);
418 : : }
419 : : }
420 : :
421 : 0 : }
422 : :
423 : 0 : static int bmz8_gen_edges(cmph_config_t *mph)
424 : : {
425 : : cmph_uint8 e;
426 : 0 : bmz8_config_data_t *bmz8 = (bmz8_config_data_t *)mph->data;
427 : 0 : cmph_uint8 multiple_edges = 0;
428 : : DEBUGP("Generating edges for %u vertices\n", bmz8->n);
429 : 0 : graph_clear_edges(bmz8->graph);
430 : 0 : mph->key_source->rewind(mph->key_source->data);
431 : 0 : for (e = 0; e < mph->key_source->nkeys; ++e)
432 : : {
433 : : cmph_uint8 h1, h2;
434 : : cmph_uint32 keylen;
435 : 0 : char *key = NULL;
436 : 0 : mph->key_source->read(mph->key_source->data, &key, &keylen);
437 : :
438 : : // if (key == NULL)fprintf(stderr, "key = %s -- read BMZ\n", key);
439 : 0 : h1 = (cmph_uint8)(hash(bmz8->hashes[0], key, keylen) % bmz8->n);
440 : 0 : h2 = (cmph_uint8)(hash(bmz8->hashes[1], key, keylen) % bmz8->n);
441 : 0 : if (h1 == h2) if (++h2 >= bmz8->n) h2 = 0;
442 : 0 : if (h1 == h2)
443 : : {
444 : 0 : if (mph->verbosity) fprintf(stderr, "Self loop for key %u\n", e);
445 : 0 : mph->key_source->dispose(mph->key_source->data, key, keylen);
446 : 0 : return 0;
447 : : }
448 : : //DEBUGP("Adding edge: %u -> %u for key %s\n", h1, h2, key);
449 : 0 : mph->key_source->dispose(mph->key_source->data, key, keylen);
450 : : // fprintf(stderr, "key = %s -- dispose BMZ\n", key);
451 : 0 : multiple_edges = graph_contains_edge(bmz8->graph, h1, h2);
452 : 0 : if (mph->verbosity && multiple_edges) fprintf(stderr, "A non simple graph was generated\n");
453 : 0 : if (multiple_edges) return 0; // checking multiple edge restriction.
454 : 0 : graph_add_edge(bmz8->graph, h1, h2);
455 : : }
456 : 0 : return !multiple_edges;
457 : : }
458 : :
459 : 0 : int bmz8_dump(cmph_t *mphf, FILE *fd)
460 : : {
461 : 0 : char *buf = NULL;
462 : : cmph_uint32 buflen;
463 : 0 : cmph_uint8 two = 2; //number of hash functions
464 : 0 : bmz8_data_t *data = (bmz8_data_t *)mphf->data;
465 : : register size_t nbytes;
466 : 0 : __cmph_dump(mphf, fd);
467 : :
468 : 0 : nbytes = fwrite(&two, sizeof(cmph_uint8), (size_t)1, fd);
469 : :
470 : 0 : hash_state_dump(data->hashes[0], &buf, &buflen);
471 : : DEBUGP("Dumping hash state with %u bytes to disk\n", buflen);
472 : 0 : nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
473 : 0 : nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
474 : 0 : free(buf);
475 : :
476 : 0 : hash_state_dump(data->hashes[1], &buf, &buflen);
477 : : DEBUGP("Dumping hash state with %u bytes to disk\n", buflen);
478 : 0 : nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
479 : 0 : nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
480 : 0 : free(buf);
481 : :
482 : 0 : nbytes = fwrite(&(data->n), sizeof(cmph_uint8), (size_t)1, fd);
483 : 0 : nbytes = fwrite(&(data->m), sizeof(cmph_uint8), (size_t)1, fd);
484 : :
485 : 0 : nbytes = fwrite(data->g, sizeof(cmph_uint8)*(data->n), (size_t)1, fd);
486 : 0 : if (nbytes == 0 && ferror(fd)) {
487 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
488 : 0 : return 0;
489 : : }
490 : : /* #ifdef DEBUG
491 : : fprintf(stderr, "G: ");
492 : : for (i = 0; i < data->n; ++i) fprintf(stderr, "%u ", data->g[i]);
493 : : fprintf(stderr, "\n");
494 : : #endif*/
495 : 0 : return 1;
496 : : }
497 : :
498 : 0 : void bmz8_load(FILE *f, cmph_t *mphf)
499 : : {
500 : : cmph_uint8 nhashes;
501 : 0 : char *buf = NULL;
502 : : cmph_uint32 buflen;
503 : : cmph_uint8 i;
504 : : register size_t nbytes;
505 : 0 : bmz8_data_t *bmz8 = (bmz8_data_t *)malloc(sizeof(bmz8_data_t));
506 : :
507 : : DEBUGP("Loading bmz8 mphf\n");
508 : 0 : mphf->data = bmz8;
509 : 0 : nbytes = fread(&nhashes, sizeof(cmph_uint8), (size_t)1, f);
510 : 0 : bmz8->hashes = (hash_state_t **)malloc(sizeof(hash_state_t *)*(size_t)(nhashes + 1));
511 : 0 : bmz8->hashes[nhashes] = NULL;
512 : : DEBUGP("Reading %u hashes\n", nhashes);
513 : 0 : for (i = 0; i < nhashes; ++i)
514 : : {
515 : 0 : hash_state_t *state = NULL;
516 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, f);
517 : : DEBUGP("Hash state has %u bytes\n", buflen);
518 : 0 : buf = (char *)malloc((size_t)buflen);
519 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, f);
520 : 0 : state = hash_state_load(buf, buflen);
521 : 0 : bmz8->hashes[i] = state;
522 : 0 : free(buf);
523 : : }
524 : :
525 : : DEBUGP("Reading m and n\n");
526 : 0 : nbytes = fread(&(bmz8->n), sizeof(cmph_uint8), (size_t)1, f);
527 : 0 : nbytes = fread(&(bmz8->m), sizeof(cmph_uint8), (size_t)1, f);
528 : :
529 : 0 : bmz8->g = (cmph_uint8 *)malloc(sizeof(cmph_uint8)*bmz8->n);
530 : 0 : nbytes = fread(bmz8->g, bmz8->n*sizeof(cmph_uint8), (size_t)1, f);
531 : 0 : if (nbytes == 0 && ferror(f)) {
532 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
533 : 0 : return;
534 : : }
535 : :
536 : : #ifdef DEBUG
537 : : fprintf(stderr, "G: ");
538 : : for (i = 0; i < bmz8->n; ++i) fprintf(stderr, "%u ", bmz8->g[i]);
539 : : fprintf(stderr, "\n");
540 : : #endif
541 : 0 : return;
542 : : }
543 : :
544 : :
545 : 0 : cmph_uint8 bmz8_search(cmph_t *mphf, const char *key, cmph_uint32 keylen)
546 : : {
547 : 0 : bmz8_data_t *bmz8 = mphf->data;
548 : 0 : cmph_uint8 h1 = (cmph_uint8)(hash(bmz8->hashes[0], key, keylen) % bmz8->n);
549 : 0 : cmph_uint8 h2 = (cmph_uint8)(hash(bmz8->hashes[1], key, keylen) % bmz8->n);
550 : : DEBUGP("key: %s h1: %u h2: %u\n", key, h1, h2);
551 : 0 : if (h1 == h2 && ++h2 > bmz8->n) h2 = 0;
552 : : DEBUGP("key: %s g[h1]: %u g[h2]: %u edges: %u\n", key, bmz8->g[h1], bmz8->g[h2], bmz8->m);
553 : 0 : return (cmph_uint8)(bmz8->g[h1] + bmz8->g[h2]);
554 : : }
555 : 0 : void bmz8_destroy(cmph_t *mphf)
556 : : {
557 : 0 : bmz8_data_t *data = (bmz8_data_t *)mphf->data;
558 : 0 : free(data->g);
559 : 0 : hash_state_destroy(data->hashes[0]);
560 : 0 : hash_state_destroy(data->hashes[1]);
561 : 0 : free(data->hashes);
562 : 0 : free(data);
563 : 0 : free(mphf);
564 : 0 : }
565 : :
566 : : /** \fn void bmz8_pack(cmph_t *mphf, void *packed_mphf);
567 : : * \brief Support the ability to pack a perfect hash function into a preallocated contiguous memory space pointed by packed_mphf.
568 : : * \param mphf pointer to the resulting mphf
569 : : * \param packed_mphf pointer to the contiguous memory area used to store the resulting mphf. The size of packed_mphf must be at least cmph_packed_size()
570 : : */
571 : 0 : void bmz8_pack(cmph_t *mphf, void *packed_mphf)
572 : : {
573 : 0 : bmz8_data_t *data = (bmz8_data_t *)mphf->data;
574 : 0 : cmph_uint8 * ptr = packed_mphf;
575 : : CMPH_HASH h2_type;
576 : :
577 : : // packing h1 type
578 : 0 : CMPH_HASH h1_type = hash_get_type(data->hashes[0]);
579 : 0 : *((cmph_uint32 *) ptr) = h1_type;
580 : 0 : ptr += sizeof(cmph_uint32);
581 : :
582 : : // packing h1
583 : 0 : hash_state_pack(data->hashes[0], ptr);
584 : 0 : ptr += hash_state_packed_size(h1_type);
585 : :
586 : : // packing h2 type
587 : 0 : h2_type = hash_get_type(data->hashes[1]);
588 : 0 : *((cmph_uint32 *) ptr) = h2_type;
589 : 0 : ptr += sizeof(cmph_uint32);
590 : :
591 : : // packing h2
592 : 0 : hash_state_pack(data->hashes[1], ptr);
593 : 0 : ptr += hash_state_packed_size(h2_type);
594 : :
595 : : // packing n
596 : 0 : *ptr++ = data->n;
597 : :
598 : : // packing g
599 : 0 : memcpy(ptr, data->g, sizeof(cmph_uint8)*data->n);
600 : 0 : }
601 : :
602 : : /** \fn cmph_uint32 bmz8_packed_size(cmph_t *mphf);
603 : : * \brief Return the amount of space needed to pack mphf.
604 : : * \param mphf pointer to a mphf
605 : : * \return the size of the packed function or zero for failures
606 : : */
607 : 0 : cmph_uint32 bmz8_packed_size(cmph_t *mphf)
608 : : {
609 : 0 : bmz8_data_t *data = (bmz8_data_t *)mphf->data;
610 : 0 : CMPH_HASH h1_type = hash_get_type(data->hashes[0]);
611 : 0 : CMPH_HASH h2_type = hash_get_type(data->hashes[1]);
612 : :
613 : 0 : return (cmph_uint32)(sizeof(CMPH_ALGO) + hash_state_packed_size(h1_type) + hash_state_packed_size(h2_type) +
614 : 0 : 2*sizeof(cmph_uint32) + sizeof(cmph_uint8) + sizeof(cmph_uint8)*data->n);
615 : : }
616 : :
617 : : /** cmph_uint8 bmz8_search(void *packed_mphf, const char *key, cmph_uint32 keylen);
618 : : * \brief Use the packed mphf to do a search.
619 : : * \param packed_mphf pointer to the packed mphf
620 : : * \param key key to be hashed
621 : : * \param keylen key length in bytes
622 : : * \return The mphf value
623 : : */
624 : 0 : cmph_uint8 bmz8_search_packed(void *packed_mphf, const char *key, cmph_uint32 keylen)
625 : : {
626 : 0 : register cmph_uint8 *h1_ptr = packed_mphf;
627 : 0 : register CMPH_HASH h1_type = *((cmph_uint32 *)h1_ptr);
628 : : register cmph_uint8 *h2_ptr;
629 : : register CMPH_HASH h2_type;
630 : : register cmph_uint8 *g_ptr, n, h1, h2;
631 : :
632 : 0 : h1_ptr += 4;
633 : :
634 : 0 : h2_ptr = h1_ptr + hash_state_packed_size(h1_type);
635 : 0 : h2_type = *((cmph_uint32 *)h2_ptr);
636 : 0 : h2_ptr += 4;
637 : :
638 : 0 : g_ptr = h2_ptr + hash_state_packed_size(h2_type);
639 : :
640 : 0 : n = *g_ptr++;
641 : :
642 : 0 : h1 = (cmph_uint8)(hash_packed(h1_ptr, h1_type, key, keylen) % n);
643 : 0 : h2 = (cmph_uint8)(hash_packed(h2_ptr, h2_type, key, keylen) % n);
644 : : DEBUGP("key: %s h1: %u h2: %u\n", key, h1, h2);
645 : 0 : if (h1 == h2 && ++h2 > n) h2 = 0;
646 : 0 : return (cmph_uint8)(g_ptr[h1] + g_ptr[h2]);
647 : : }
|
