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