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