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