| 1 |
#include "graph.h" |
| 2 |
#include "hashtree.h" |
| 3 |
#include "cmph_structs.h" |
| 4 |
#include "hastree_structs.h" |
| 5 |
#include "hash.h" |
| 6 |
#include "bitbool.h" |
| 7 |
|
| 8 |
#include <math.h> |
| 9 |
#include <stdlib.h> |
| 10 |
#include <stdio.h> |
| 11 |
#include <assert.h> |
| 12 |
#include <string.h> |
| 13 |
|
| 14 |
//#define DEBUG |
| 15 |
#include "debug.h" |
| 16 |
|
| 17 |
hashtree_config_data_t *hashtree_config_new() |
| 18 |
{ |
| 19 |
hashtree_config_data_t *hashtree; |
| 20 |
hashtree = (hashtree_config_data_t *)malloc(sizeof(hashtree_config_data_t)); |
| 21 |
if (!hashtree) return NULL; |
| 22 |
memset(hashtree, 0, sizeof(hashtree_config_data_t)); |
| 23 |
hashtree->hashfuncs[0] = CMPH_HASH_JENKINS; |
| 24 |
hashtree->hashfuncs[1] = CMPH_HASH_JENKINS; |
| 25 |
hashtree->hashfuncs[2] = CMPH_HASH_JENKINS; |
| 26 |
hashtree->memory = 32 * 1024 * 1024; |
| 27 |
return hashtree; |
| 28 |
} |
| 29 |
void hashtree_config_destroy(cmph_config_t *mph) |
| 30 |
{ |
| 31 |
hashtree_config_data_t *data = (hashtree_config_data_t *)mph->data; |
| 32 |
DEBUGP("Destroying algorithm dependent data\n"); |
| 33 |
free(data); |
| 34 |
} |
| 35 |
|
| 36 |
void hashtree_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs) |
| 37 |
{ |
| 38 |
hashtree_config_data_t *hashtree = (hashtree_config_data_t *)mph->data; |
| 39 |
CMPH_HASH *hashptr = hashfuncs; |
| 40 |
cmph_uint32 i = 0; |
| 41 |
while(*hashptr != CMPH_HASH_COUNT) |
| 42 |
{ |
| 43 |
if (i >= 3) break; //hashtree only uses three hash functions |
| 44 |
hashtree->hashfuncs[i] = *hashptr; |
| 45 |
++i, ++hashptr; |
| 46 |
} |
| 47 |
} |
| 48 |
|
| 49 |
cmph_t *hashtree_new(cmph_config_t *mph, double c) |
| 50 |
{ |
| 51 |
cmph_t *mphf = NULL; |
| 52 |
hashtree_data_t *hashtreef = NULL; |
| 53 |
|
| 54 |
cmph_uint32 i; |
| 55 |
cmph_uint32 iterations = 20; |
| 56 |
cmph_uint8 *visited = NULL; |
| 57 |
hashtree_config_data_t *hashtree = (hashtree_config_data_t *)mph->data; |
| 58 |
hashtree->m = mph->key_source->nkeys; |
| 59 |
hashtree->n = ceil(c * mph->key_source->nkeys); |
| 60 |
DEBUGP("m (edges): %u n (vertices): %u c: %f\n", hashtree->m, hashtree->n, c); |
| 61 |
hashtree->graph = graph_new(hashtree->n, hashtree->m); |
| 62 |
DEBUGP("Created graph\n"); |
| 63 |
|
| 64 |
hashtree->hashes = (hash_state_t **)malloc(sizeof(hash_state_t *)*3); |
| 65 |
for(i = 0; i < 3; ++i) hashtree->hashes[i] = NULL; |
| 66 |
//Mapping step |
| 67 |
if (mph->verbosity) |
| 68 |
{ |
| 69 |
fprintf(stderr, "Entering mapping step for mph creation of %u keys with graph sized %u\n", hashtree->m, hashtree->n); |
| 70 |
} |
| 71 |
while(1) |
| 72 |
{ |
| 73 |
int ok; |
| 74 |
hashtree->hashes[0] = hash_state_new(hashtree->hashfuncs[0], hashtree->n); |
| 75 |
hashtree->hashes[1] = hash_state_new(hashtree->hashfuncs[1], hashtree->n); |
| 76 |
ok = hashtree_gen_edges(mph); |
| 77 |
if (!ok) |
| 78 |
{ |
| 79 |
--iterations; |
| 80 |
hash_state_destroy(hashtree->hashes[0]); |
| 81 |
hashtree->hashes[0] = NULL; |
| 82 |
hash_state_destroy(hashtree->hashes[1]); |
| 83 |
hashtree->hashes[1] = NULL; |
| 84 |
DEBUGP("%u iterations remaining\n", iterations); |
| 85 |
if (mph->verbosity) |
| 86 |
{ |
| 87 |
fprintf(stderr, "Acyclic graph creation failure - %u iterations remaining\n", iterations); |
| 88 |
} |
| 89 |
if (iterations == 0) break; |
| 90 |
} |
| 91 |
else break; |
| 92 |
} |
| 93 |
if (iterations == 0) |
| 94 |
{ |
| 95 |
graph_destroy(hashtree->graph); |
| 96 |
return NULL; |
| 97 |
} |
| 98 |
|
| 99 |
//Assignment step |
| 100 |
if (mph->verbosity) |
| 101 |
{ |
| 102 |
fprintf(stderr, "Starting assignment step\n"); |
| 103 |
} |
| 104 |
DEBUGP("Assignment step\n"); |
| 105 |
visited = (char *)malloc(hashtree->n/8 + 1); |
| 106 |
memset(visited, 0, hashtree->n/8 + 1); |
| 107 |
free(hashtree->g); |
| 108 |
hashtree->g = (cmph_uint32 *)malloc(hashtree->n * sizeof(cmph_uint32)); |
| 109 |
assert(hashtree->g); |
| 110 |
for (i = 0; i < hashtree->n; ++i) |
| 111 |
{ |
| 112 |
if (!GETBIT(visited,i)) |
| 113 |
{ |
| 114 |
hashtree->g[i] = 0; |
| 115 |
hashtree_traverse(hashtree, visited, i); |
| 116 |
} |
| 117 |
} |
| 118 |
graph_destroy(hashtree->graph); |
| 119 |
free(visited); |
| 120 |
hashtree->graph = NULL; |
| 121 |
|
| 122 |
mphf = (cmph_t *)malloc(sizeof(cmph_t)); |
| 123 |
mphf->algo = mph->algo; |
| 124 |
hashtreef = (hashtree_data_t *)malloc(sizeof(hashtree_data_t)); |
| 125 |
hashtreef->g = hashtree->g; |
| 126 |
hashtree->g = NULL; //transfer memory ownership |
| 127 |
hashtreef->hashes = hashtree->hashes; |
| 128 |
hashtree->hashes = NULL; //transfer memory ownership |
| 129 |
hashtreef->n = hashtree->n; |
| 130 |
hashtreef->m = hashtree->m; |
| 131 |
mphf->data = hashtreef; |
| 132 |
mphf->size = hashtree->m; |
| 133 |
DEBUGP("Successfully generated minimal perfect hash\n"); |
| 134 |
if (mph->verbosity) |
| 135 |
{ |
| 136 |
fprintf(stderr, "Successfully generated minimal perfect hash function\n"); |
| 137 |
} |
| 138 |
return mphf; |
| 139 |
} |
| 140 |
|
| 141 |
static void hashtree_traverse(hashtree_config_data_t *hashtree, cmph_uint8 *visited, cmph_uint32 v) |
| 142 |
{ |
| 143 |
|
| 144 |
graph_iterator_t it = graph_neighbors_it(hashtree->graph, v); |
| 145 |
cmph_uint32 neighbor = 0; |
| 146 |
SETBIT(visited,v); |
| 147 |
|
| 148 |
DEBUGP("Visiting vertex %u\n", v); |
| 149 |
while((neighbor = graph_next_neighbor(hashtree->graph, &it)) != GRAPH_NO_NEIGHBOR) |
| 150 |
{ |
| 151 |
DEBUGP("Visiting neighbor %u\n", neighbor); |
| 152 |
if(GETBIT(visited,neighbor)) continue; |
| 153 |
DEBUGP("Visiting neighbor %u\n", neighbor); |
| 154 |
DEBUGP("Visiting edge %u->%u with id %u\n", v, neighbor, graph_edge_id(hashtree->graph, v, neighbor)); |
| 155 |
hashtree->g[neighbor] = graph_edge_id(hashtree->graph, v, neighbor) - hashtree->g[v]; |
| 156 |
DEBUGP("g is %u (%u - %u mod %u)\n", hashtree->g[neighbor], graph_edge_id(hashtree->graph, v, neighbor), hashtree->g[v], hashtree->m); |
| 157 |
hashtree_traverse(hashtree, visited, neighbor); |
| 158 |
} |
| 159 |
} |
| 160 |
|
| 161 |
static int hashtree_gen_edges(cmph_config_t *mph) |
| 162 |
{ |
| 163 |
cmph_uint32 e; |
| 164 |
hashtree_config_data_t *hashtree = (hashtree_config_data_t *)mph->data; |
| 165 |
int cycles = 0; |
| 166 |
|
| 167 |
DEBUGP("Generating edges for %u vertices with hash functions %s and %s\n", hashtree->n, cmph_hash_names[hashtree->hashfuncs[0]], cmph_hash_names[hashtree->hashfuncs[1]]); |
| 168 |
graph_clear_edges(hashtree->graph); |
| 169 |
mph->key_source->rewind(mph->key_source->data); |
| 170 |
for (e = 0; e < mph->key_source->nkeys; ++e) |
| 171 |
{ |
| 172 |
cmph_uint32 h1, h2; |
| 173 |
cmph_uint32 keylen; |
| 174 |
char *key; |
| 175 |
mph->key_source->read(mph->key_source->data, &key, &keylen); |
| 176 |
h1 = hash(hashtree->hashes[0], key, keylen) % hashtree->n; |
| 177 |
h2 = hash(hashtree->hashes[1], key, keylen) % hashtree->n; |
| 178 |
if (h1 == h2) if (++h2 >= hashtree->n) h2 = 0; |
| 179 |
if (h1 == h2) |
| 180 |
{ |
| 181 |
if (mph->verbosity) fprintf(stderr, "Self loop for key %u\n", e); |
| 182 |
mph->key_source->dispose(mph->key_source->data, key, keylen); |
| 183 |
return 0; |
| 184 |
} |
| 185 |
DEBUGP("Adding edge: %u -> %u for key %s\n", h1, h2, key); |
| 186 |
mph->key_source->dispose(mph->key_source->data, key, keylen); |
| 187 |
graph_add_edge(hashtree->graph, h1, h2); |
| 188 |
} |
| 189 |
cycles = graph_is_cyclic(hashtree->graph); |
| 190 |
if (mph->verbosity && cycles) fprintf(stderr, "Cyclic graph generated\n"); |
| 191 |
DEBUGP("Looking for cycles: %u\n", cycles); |
| 192 |
|
| 193 |
return ! cycles; |
| 194 |
} |
| 195 |
|
| 196 |
int hashtree_dump(cmph_t *mphf, FILE *fd) |
| 197 |
{ |
| 198 |
char *buf = NULL; |
| 199 |
cmph_uint32 buflen; |
| 200 |
cmph_uint32 two = 2; //number of hash functions |
| 201 |
hashtree_data_t *data = (hashtree_data_t *)mphf->data; |
| 202 |
__cmph_dump(mphf, fd); |
| 203 |
|
| 204 |
fwrite(&two, sizeof(cmph_uint32), 1, fd); |
| 205 |
hash_state_dump(data->hashes[0], &buf, &buflen); |
| 206 |
DEBUGP("Dumping hash state with %u bytes to disk\n", buflen); |
| 207 |
fwrite(&buflen, sizeof(cmph_uint32), 1, fd); |
| 208 |
fwrite(buf, buflen, 1, fd); |
| 209 |
free(buf); |
| 210 |
|
| 211 |
hash_state_dump(data->hashes[1], &buf, &buflen); |
| 212 |
DEBUGP("Dumping hash state with %u bytes to disk\n", buflen); |
| 213 |
fwrite(&buflen, sizeof(cmph_uint32), 1, fd); |
| 214 |
fwrite(buf, buflen, 1, fd); |
| 215 |
free(buf); |
| 216 |
|
| 217 |
fwrite(&(data->n), sizeof(cmph_uint32), 1, fd); |
| 218 |
fwrite(&(data->m), sizeof(cmph_uint32), 1, fd); |
| 219 |
|
| 220 |
fwrite(data->g, sizeof(cmph_uint32)*data->n, 1, fd); |
| 221 |
#ifdef DEBUG |
| 222 |
fprintf(stderr, "G: "); |
| 223 |
for (i = 0; i < data->n; ++i) fprintf(stderr, "%u ", data->g[i]); |
| 224 |
fprintf(stderr, "\n"); |
| 225 |
#endif |
| 226 |
return 1; |
| 227 |
} |
| 228 |
|
| 229 |
void hashtree_load(FILE *f, cmph_t *mphf) |
| 230 |
{ |
| 231 |
cmph_uint32 nhashes; |
| 232 |
char *buf = NULL; |
| 233 |
cmph_uint32 buflen; |
| 234 |
cmph_uint32 i; |
| 235 |
hashtree_data_t *hashtree = (hashtree_data_t *)malloc(sizeof(hashtree_data_t)); |
| 236 |
|
| 237 |
DEBUGP("Loading hashtree mphf\n"); |
| 238 |
mphf->data = hashtree; |
| 239 |
fread(&nhashes, sizeof(cmph_uint32), 1, f); |
| 240 |
hashtree->hashes = (hash_state_t **)malloc(sizeof(hash_state_t *)*(nhashes + 1)); |
| 241 |
hashtree->hashes[nhashes] = NULL; |
| 242 |
DEBUGP("Reading %u hashes\n", nhashes); |
| 243 |
for (i = 0; i < nhashes; ++i) |
| 244 |
{ |
| 245 |
hash_state_t *state = NULL; |
| 246 |
fread(&buflen, sizeof(cmph_uint32), 1, f); |
| 247 |
DEBUGP("Hash state has %u bytes\n", buflen); |
| 248 |
buf = (char *)malloc(buflen); |
| 249 |
fread(buf, buflen, 1, f); |
| 250 |
state = hash_state_load(buf, buflen); |
| 251 |
hashtree->hashes[i] = state; |
| 252 |
free(buf); |
| 253 |
} |
| 254 |
|
| 255 |
DEBUGP("Reading m and n\n"); |
| 256 |
fread(&(hashtree->n), sizeof(cmph_uint32), 1, f); |
| 257 |
fread(&(hashtree->m), sizeof(cmph_uint32), 1, f); |
| 258 |
|
| 259 |
hashtree->g = (cmph_uint32 *)malloc(sizeof(cmph_uint32)*hashtree->n); |
| 260 |
fread(hashtree->g, hashtree->n*sizeof(cmph_uint32), 1, f); |
| 261 |
#ifdef DEBUG |
| 262 |
fprintf(stderr, "G: "); |
| 263 |
for (i = 0; i < hashtree->n; ++i) fprintf(stderr, "%u ", hashtree->g[i]); |
| 264 |
fprintf(stderr, "\n"); |
| 265 |
#endif |
| 266 |
return; |
| 267 |
} |
| 268 |
|
| 269 |
|
| 270 |
cmph_uint32 hashtree_search(cmph_t *mphf, const char *key, cmph_uint32 keylen) |
| 271 |
{ |
| 272 |
hashtree_data_t *hashtree = mphf->data; |
| 273 |
cmph_uint32 h1 = hash(hashtree->hashes[0], key, keylen) % hashtree->n; |
| 274 |
cmph_uint32 h2 = hash(hashtree->hashes[1], key, keylen) % hashtree->n; |
| 275 |
DEBUGP("key: %s h1: %u h2: %u\n", key, h1, h2); |
| 276 |
if (h1 == h2 && ++h2 >= hashtree->n) h2 = 0; |
| 277 |
DEBUGP("key: %s g[h1]: %u g[h2]: %u edges: %u\n", key, hashtree->g[h1], hashtree->g[h2], hashtree->m); |
| 278 |
return (hashtree->g[h1] + hashtree->g[h2]) % hashtree->m; |
| 279 |
} |
| 280 |
void hashtree_destroy(cmph_t *mphf) |
| 281 |
{ |
| 282 |
hashtree_data_t *data = (hashtree_data_t *)mphf->data; |
| 283 |
free(data->g); |
| 284 |
hash_state_destroy(data->hashes[0]); |
| 285 |
hash_state_destroy(data->hashes[1]); |
| 286 |
free(data->hashes); |
| 287 |
free(data); |
| 288 |
free(mphf); |
| 289 |
} |