Branch data Line data Source code
1 : : #include "graph.h"
2 : : #include "fch.h"
3 : : #include "fch_structs.h"
4 : : #include "bmz8.h"
5 : : #include "bmz8_structs.h"
6 : : #include "brz.h"
7 : : #include "cmph_structs.h"
8 : : #include "brz_structs.h"
9 : : #include "buffer_manager.h"
10 : : #include "cmph.h"
11 : : #include "hash.h"
12 : : #include "bitbool.h"
13 : : #include <math.h>
14 : : #include <stdlib.h>
15 : : #include <stdint.h>
16 : : #include <stdio.h>
17 : : #include <assert.h>
18 : : #include <string.h>
19 : : #include <errno.h>
20 : : #define MAX_BUCKET_SIZE 255
21 : : //#define DEBUG
22 : : #include "debug.h"
23 : :
24 : :
25 : : static int brz_gen_mphf(cmph_config_t *mph);
26 : : static cmph_uint32 brz_min_index(cmph_uint32 * vector, cmph_uint32 n);
27 : : static void brz_destroy_keys_vd(cmph_uint8 ** keys_vd, cmph_uint32 nkeys);
28 : : static char * brz_copy_partial_fch_mphf(brz_config_data_t *brz, fch_data_t * fchf, cmph_uint32 index, cmph_uint32 *buflen);
29 : : static char * brz_copy_partial_bmz8_mphf(brz_config_data_t *brz, bmz8_data_t * bmzf, cmph_uint32 index, cmph_uint32 *buflen);
30 : 0 : brz_config_data_t *brz_config_new(void)
31 : : {
32 : 0 : brz_config_data_t *brz = NULL;
33 : 0 : brz = (brz_config_data_t *)malloc(sizeof(brz_config_data_t));
34 : 0 : brz->algo = CMPH_FCH;
35 : 0 : brz->b = 128;
36 : 0 : brz->hashfuncs[0] = CMPH_HASH_JENKINS;
37 : 0 : brz->hashfuncs[1] = CMPH_HASH_JENKINS;
38 : 0 : brz->hashfuncs[2] = CMPH_HASH_JENKINS;
39 : 0 : brz->size = NULL;
40 : 0 : brz->offset = NULL;
41 : 0 : brz->g = NULL;
42 : 0 : brz->h1 = NULL;
43 : 0 : brz->h2 = NULL;
44 : 0 : brz->h0 = NULL;
45 : 0 : brz->memory_availability = 1024*1024;
46 : 0 : brz->tmp_dir = (cmph_uint8 *)calloc((size_t)10, sizeof(cmph_uint8));
47 : 0 : brz->mphf_fd = NULL;
48 : 0 : strcpy((char *)(brz->tmp_dir), "/var/tmp/");
49 [ # # ]: 0 : assert(brz);
50 : 0 : return brz;
51 : : }
52 : :
53 : 0 : void brz_config_destroy(cmph_config_t *mph)
54 : : {
55 : 0 : brz_config_data_t *data = (brz_config_data_t *)mph->data;
56 : 0 : free(data->tmp_dir);
57 : : DEBUGP("Destroying algorithm dependent data\n");
58 : 0 : free(data);
59 : 0 : }
60 : :
61 : 0 : void brz_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs)
62 : : {
63 : 0 : brz_config_data_t *brz = (brz_config_data_t *)mph->data;
64 : 0 : CMPH_HASH *hashptr = hashfuncs;
65 : 0 : cmph_uint32 i = 0;
66 [ # # ]: 0 : while(*hashptr != CMPH_HASH_COUNT)
67 : : {
68 [ # # ]: 0 : if (i >= 3) break; //brz only uses three hash functions
69 : 0 : brz->hashfuncs[i] = *hashptr;
70 : 0 : ++i, ++hashptr;
71 : : }
72 : 0 : }
73 : :
74 : 0 : void brz_config_set_memory_availability(cmph_config_t *mph, cmph_uint32 memory_availability)
75 : : {
76 : 0 : brz_config_data_t *brz = (brz_config_data_t *)mph->data;
77 [ # # ]: 0 : if(memory_availability > 0) brz->memory_availability = memory_availability*1024*1024;
78 : 0 : }
79 : :
80 : 0 : void brz_config_set_tmp_dir(cmph_config_t *mph, cmph_uint8 *tmp_dir)
81 : : {
82 : 0 : brz_config_data_t *brz = (brz_config_data_t *)mph->data;
83 [ # # ]: 0 : if(tmp_dir)
84 : : {
85 : 0 : size_t len = strlen((char *)tmp_dir);
86 : 0 : free(brz->tmp_dir);
87 [ # # ]: 0 : if(tmp_dir[len-1] != '/')
88 : : {
89 : 0 : brz->tmp_dir = (cmph_uint8 *)calloc((size_t)len+2, sizeof(cmph_uint8));
90 : 0 : sprintf((char *)(brz->tmp_dir), "%s/", (char *)tmp_dir);
91 : : }
92 : : else
93 : : {
94 : 0 : brz->tmp_dir = (cmph_uint8 *)calloc((size_t)len+1, sizeof(cmph_uint8));
95 : 0 : sprintf((char *)(brz->tmp_dir), "%s", (char *)tmp_dir);
96 : : }
97 : :
98 : : }
99 : 0 : }
100 : :
101 : 0 : void brz_config_set_mphf_fd(cmph_config_t *mph, FILE *mphf_fd)
102 : : {
103 : 0 : brz_config_data_t *brz = (brz_config_data_t *)mph->data;
104 : 0 : brz->mphf_fd = mphf_fd;
105 [ # # ]: 0 : assert(brz->mphf_fd);
106 : 0 : }
107 : :
108 : 0 : void brz_config_set_b(cmph_config_t *mph, cmph_uint32 b)
109 : : {
110 : 0 : brz_config_data_t *brz = (brz_config_data_t *)mph->data;
111 [ # # # # ]: 0 : if(b <= 64 || b >= 175)
112 : : {
113 : 0 : b = 128;
114 : : }
115 : 0 : brz->b = (cmph_uint8)b;
116 : 0 : }
117 : :
118 : 0 : void brz_config_set_algo(cmph_config_t *mph, CMPH_ALGO algo)
119 : : {
120 [ # # # # ]: 0 : if (algo == CMPH_BMZ8 || algo == CMPH_FCH) // supported algorithms
121 : : {
122 : 0 : brz_config_data_t *brz = (brz_config_data_t *)mph->data;
123 : 0 : brz->algo = algo;
124 : : }
125 : 0 : }
126 : :
127 : 0 : cmph_t *brz_new(cmph_config_t *mph, double c)
128 : : {
129 : 0 : cmph_t *mphf = NULL;
130 : 0 : brz_data_t *brzf = NULL;
131 : : cmph_uint32 i;
132 : 0 : cmph_uint32 iterations = 20;
133 : : brz_config_data_t *brz;
134 : :
135 : : DEBUGP("c: %f\n", c);
136 : 0 : brz = (brz_config_data_t *)mph->data;
137 [ # # # ]: 0 : switch(brz->algo) // validating restrictions over parameter c.
138 : : {
139 : 0 : case CMPH_BMZ8:
140 [ # # # # ]: 0 : if (c == 0 || c >= 2.0) c = 1;
141 : 0 : break;
142 : 0 : case CMPH_FCH:
143 [ # # ]: 0 : if (c <= 2.0) c = 2.6;
144 : 0 : break;
145 : 0 : default:
146 : 0 : assert(0);
147 : : }
148 : 0 : brz->c = c;
149 : 0 : brz->m = mph->key_source->nkeys;
150 : : DEBUGP("m: %u\n", brz->m);
151 : 0 : brz->k = (cmph_uint32)ceil(brz->m/((double)brz->b));
152 : : DEBUGP("k: %u\n", brz->k);
153 : 0 : brz->size = (cmph_uint8 *) calloc((size_t)brz->k, sizeof(cmph_uint8));
154 : :
155 : : // Clustering the keys by graph id.
156 [ # # ]: 0 : if (mph->verbosity)
157 : : {
158 : 0 : fprintf(stderr, "Partitioning the set of keys.\n");
159 : : }
160 : :
161 : : while(1)
162 : 0 : {
163 : : int ok;
164 : : DEBUGP("hash function 3\n");
165 : 0 : brz->h0 = hash_state_new(brz->hashfuncs[2], brz->k);
166 : : DEBUGP("Generating graphs\n");
167 : 0 : ok = brz_gen_mphf(mph);
168 [ # # ]: 0 : if (!ok)
169 : : {
170 : 0 : --iterations;
171 : 0 : hash_state_destroy(brz->h0);
172 : 0 : brz->h0 = NULL;
173 : : DEBUGP("%u iterations remaining to create the graphs in a external file\n", iterations);
174 [ # # ]: 0 : if (mph->verbosity)
175 : : {
176 : 0 : fprintf(stderr, "Failure: A graph with more than 255 keys was created - %u iterations remaining\n", iterations);
177 : : }
178 [ # # ]: 0 : if (iterations == 0) break;
179 : : }
180 : 0 : else break;
181 : : }
182 [ # # ]: 0 : if (iterations == 0)
183 : : {
184 : : DEBUGP("Graphs with more than 255 keys were created in all 20 iterations\n");
185 : 0 : free(brz->size);
186 : 0 : return NULL;
187 : : }
188 : : DEBUGP("Graphs generated\n");
189 : :
190 : 0 : brz->offset = (cmph_uint32 *)calloc((size_t)brz->k, sizeof(cmph_uint32));
191 [ # # ]: 0 : for (i = 1; i < brz->k; ++i)
192 : : {
193 : 0 : brz->offset[i] = brz->size[i-1] + brz->offset[i-1];
194 : : }
195 : : // Generating a mphf
196 : 0 : mphf = (cmph_t *)malloc(sizeof(cmph_t));
197 : 0 : mphf->algo = mph->algo;
198 : 0 : brzf = (brz_data_t *)malloc(sizeof(brz_data_t));
199 : 0 : brzf->g = brz->g;
200 : 0 : brz->g = NULL; //transfer memory ownership
201 : 0 : brzf->h1 = brz->h1;
202 : 0 : brz->h1 = NULL; //transfer memory ownership
203 : 0 : brzf->h2 = brz->h2;
204 : 0 : brz->h2 = NULL; //transfer memory ownership
205 : 0 : brzf->h0 = brz->h0;
206 : 0 : brz->h0 = NULL; //transfer memory ownership
207 : 0 : brzf->size = brz->size;
208 : 0 : brz->size = NULL; //transfer memory ownership
209 : 0 : brzf->offset = brz->offset;
210 : 0 : brz->offset = NULL; //transfer memory ownership
211 : 0 : brzf->k = brz->k;
212 : 0 : brzf->c = brz->c;
213 : 0 : brzf->m = brz->m;
214 : 0 : brzf->algo = brz->algo;
215 : 0 : mphf->data = brzf;
216 : 0 : mphf->size = brz->m;
217 : : DEBUGP("Successfully generated minimal perfect hash\n");
218 [ # # ]: 0 : if (mph->verbosity)
219 : : {
220 : 0 : fprintf(stderr, "Successfully generated minimal perfect hash function\n");
221 : : }
222 : 0 : return mphf;
223 : : }
224 : :
225 : 0 : static int brz_gen_mphf(cmph_config_t *mph)
226 : : {
227 : : cmph_uint32 i, e, error;
228 : 0 : brz_config_data_t *brz = (brz_config_data_t *)mph->data;
229 : 0 : cmph_uint32 memory_usage = 0;
230 : 0 : cmph_uint32 nkeys_in_buffer = 0;
231 : 0 : cmph_uint8 *buffer = (cmph_uint8 *)malloc((size_t)brz->memory_availability);
232 : 0 : cmph_uint32 *buckets_size = (cmph_uint32 *)calloc((size_t)brz->k, sizeof(cmph_uint32));
233 : 0 : cmph_uint32 *keys_index = NULL;
234 : 0 : cmph_uint8 **buffer_merge = NULL;
235 : 0 : cmph_uint32 *buffer_h0 = NULL;
236 : 0 : cmph_uint32 nflushes = 0;
237 : : cmph_uint32 h0;
238 : : register size_t nbytes;
239 : 0 : FILE * tmp_fd = NULL;
240 : 0 : buffer_manager_t * buff_manager = NULL;
241 : 0 : char *filename = NULL;
242 : 0 : char *key = NULL;
243 : : cmph_uint32 keylen;
244 : 0 : cmph_uint32 cur_bucket = 0;
245 : 0 : cmph_uint8 nkeys_vd = 0;
246 : 0 : cmph_uint8 ** keys_vd = NULL;
247 : :
248 : 0 : mph->key_source->rewind(mph->key_source->data);
249 : : DEBUGP("Generating graphs from %u keys\n", brz->m);
250 : : // Partitioning
251 [ # # ]: 0 : for (e = 0; e < brz->m; ++e)
252 : : {
253 : 0 : mph->key_source->read(mph->key_source->data, &key, &keylen);
254 : :
255 : : /* Buffers management */
256 [ # # ]: 0 : if (memory_usage + keylen + sizeof(keylen) > brz->memory_availability) // flush buffers
257 : : {
258 : : cmph_uint32 value, sum, keylen1;
259 [ # # ]: 0 : if(mph->verbosity)
260 : : {
261 : 0 : fprintf(stderr, "Flushing %u\n", nkeys_in_buffer);
262 : : }
263 : 0 : value = buckets_size[0];
264 : 0 : sum = 0;
265 : 0 : keylen1 = 0;
266 : 0 : buckets_size[0] = 0;
267 [ # # ]: 0 : for(i = 1; i < brz->k; i++)
268 : : {
269 [ # # ]: 0 : if(buckets_size[i] == 0) continue;
270 : 0 : sum += value;
271 : 0 : value = buckets_size[i];
272 : 0 : buckets_size[i] = sum;
273 : :
274 : : }
275 : 0 : memory_usage = 0;
276 : 0 : keys_index = (cmph_uint32 *)calloc((size_t)nkeys_in_buffer, sizeof(cmph_uint32));
277 [ # # ]: 0 : for(i = 0; i < nkeys_in_buffer; i++)
278 : : {
279 : 0 : memcpy(&keylen1, buffer + memory_usage, sizeof(keylen1));
280 : 0 : h0 = hash(brz->h0, (char *)(buffer + memory_usage + sizeof(keylen1)), keylen1) % brz->k;
281 : 0 : keys_index[buckets_size[h0]] = memory_usage;
282 : 0 : buckets_size[h0]++;
283 : 0 : memory_usage += keylen1 + (cmph_uint32)sizeof(keylen1);
284 : : }
285 : 0 : filename = (char *)calloc(strlen((char *)(brz->tmp_dir)) + 11, sizeof(char));
286 : 0 : sprintf(filename, "%s%u.cmph",brz->tmp_dir, nflushes);
287 : 0 : tmp_fd = fopen(filename, "wb");
288 : 0 : free(filename);
289 : 0 : filename = NULL;
290 [ # # ]: 0 : for(i = 0; i < nkeys_in_buffer; i++)
291 : : {
292 : 0 : memcpy(&keylen1, buffer + keys_index[i], sizeof(keylen1));
293 : 0 : nbytes = fwrite(buffer + keys_index[i], (size_t)1, keylen1 + sizeof(keylen1), tmp_fd);
294 : : }
295 : 0 : nkeys_in_buffer = 0;
296 : 0 : memory_usage = 0;
297 : 0 : memset((void *)buckets_size, 0, brz->k*sizeof(cmph_uint32));
298 : 0 : nflushes++;
299 : 0 : free(keys_index);
300 : 0 : fclose(tmp_fd);
301 : : }
302 : 0 : memcpy(buffer + memory_usage, &keylen, sizeof(keylen));
303 : 0 : memcpy(buffer + memory_usage + sizeof(keylen), key, (size_t)keylen);
304 : 0 : memory_usage += keylen + (cmph_uint32)sizeof(keylen);
305 : 0 : h0 = hash(brz->h0, key, keylen) % brz->k;
306 : :
307 [ # # # # : 0 : if ((brz->size[h0] == MAX_BUCKET_SIZE) || (brz->algo == CMPH_BMZ8 && ((brz->c >= 1.0) && (cmph_uint8)(brz->c * brz->size[h0]) < brz->size[h0])))
# # # # ]
308 : : {
309 : 0 : free(buffer);
310 : 0 : free(buckets_size);
311 : 0 : return 0;
312 : : }
313 : 0 : brz->size[h0] = (cmph_uint8)(brz->size[h0] + 1U);
314 : 0 : buckets_size[h0] ++;
315 : 0 : nkeys_in_buffer++;
316 : 0 : mph->key_source->dispose(mph->key_source->data, key, keylen);
317 : : }
318 [ # # ]: 0 : if (memory_usage != 0) // flush buffers
319 : : {
320 : : cmph_uint32 value;
321 : : cmph_uint32 sum, keylen1;
322 [ # # ]: 0 : if(mph->verbosity)
323 : : {
324 : 0 : fprintf(stderr, "Flushing %u\n", nkeys_in_buffer);
325 : : }
326 : 0 : value = buckets_size[0];
327 : 0 : sum = 0;
328 : 0 : keylen1 = 0;
329 : 0 : buckets_size[0] = 0;
330 [ # # ]: 0 : for(i = 1; i < brz->k; i++)
331 : : {
332 [ # # ]: 0 : if(buckets_size[i] == 0) continue;
333 : 0 : sum += value;
334 : 0 : value = buckets_size[i];
335 : 0 : buckets_size[i] = sum;
336 : : }
337 : 0 : memory_usage = 0;
338 : 0 : keys_index = (cmph_uint32 *)calloc((size_t)nkeys_in_buffer, sizeof(cmph_uint32));
339 [ # # ]: 0 : for(i = 0; i < nkeys_in_buffer; i++)
340 : : {
341 : 0 : memcpy(&keylen1, buffer + memory_usage, sizeof(keylen1));
342 : 0 : h0 = hash(brz->h0, (char *)(buffer + memory_usage + sizeof(keylen1)), keylen1) % brz->k;
343 : 0 : keys_index[buckets_size[h0]] = memory_usage;
344 : 0 : buckets_size[h0]++;
345 : 0 : memory_usage += keylen1 + (cmph_uint32)sizeof(keylen1);
346 : : }
347 : 0 : filename = (char *)calloc(strlen((char *)(brz->tmp_dir)) + 11, sizeof(char));
348 : 0 : sprintf(filename, "%s%u.cmph",brz->tmp_dir, nflushes);
349 : 0 : tmp_fd = fopen(filename, "wb");
350 : 0 : free(filename);
351 : 0 : filename = NULL;
352 [ # # ]: 0 : for(i = 0; i < nkeys_in_buffer; i++)
353 : : {
354 : 0 : memcpy(&keylen1, buffer + keys_index[i], sizeof(keylen1));
355 : 0 : nbytes = fwrite(buffer + keys_index[i], (size_t)1, keylen1 + sizeof(keylen1), tmp_fd);
356 : : }
357 : 0 : nkeys_in_buffer = 0;
358 : 0 : memory_usage = 0;
359 : 0 : memset((void *)buckets_size, 0, brz->k*sizeof(cmph_uint32));
360 : 0 : nflushes++;
361 : 0 : free(keys_index);
362 : 0 : fclose(tmp_fd);
363 : : }
364 : :
365 : 0 : free(buffer);
366 : 0 : free(buckets_size);
367 [ # # ]: 0 : if(nflushes > 1024) return 0; // Too many files generated.
368 : : // mphf generation
369 [ # # ]: 0 : if(mph->verbosity)
370 : : {
371 : 0 : fprintf(stderr, "\nMPHF generation \n");
372 : : }
373 : : /* Starting to dump to disk the resultant MPHF: __cmph_dump function */
374 : 0 : nbytes = fwrite(cmph_names[CMPH_BRZ], (size_t)(strlen(cmph_names[CMPH_BRZ]) + 1), (size_t)1, brz->mphf_fd);
375 : 0 : nbytes = fwrite(&(brz->m), sizeof(brz->m), (size_t)1, brz->mphf_fd);
376 : 0 : nbytes = fwrite(&(brz->c), sizeof(double), (size_t)1, brz->mphf_fd);
377 : 0 : nbytes = fwrite(&(brz->algo), sizeof(brz->algo), (size_t)1, brz->mphf_fd);
378 : 0 : nbytes = fwrite(&(brz->k), sizeof(cmph_uint32), (size_t)1, brz->mphf_fd); // number of MPHFs
379 : 0 : nbytes = fwrite(brz->size, sizeof(cmph_uint8)*(brz->k), (size_t)1, brz->mphf_fd);
380 [ # # # # ]: 0 : if (nbytes == 0 && ferror(brz->mphf_fd)) {
381 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
382 : 0 : return 0;
383 : : }
384 : :
385 : : //tmp_fds = (FILE **)calloc(nflushes, sizeof(FILE *));
386 : 0 : buff_manager = buffer_manager_new(brz->memory_availability, nflushes);
387 : 0 : buffer_merge = (cmph_uint8 **)calloc((size_t)nflushes, sizeof(cmph_uint8 *));
388 : 0 : buffer_h0 = (cmph_uint32 *)calloc((size_t)nflushes, sizeof(cmph_uint32));
389 : :
390 : 0 : memory_usage = 0;
391 [ # # ]: 0 : for(i = 0; i < nflushes; i++)
392 : : {
393 : 0 : filename = (char *)calloc(strlen((char *)(brz->tmp_dir)) + 11, sizeof(char));
394 : 0 : sprintf(filename, "%s%u.cmph",brz->tmp_dir, i);
395 : 0 : buffer_manager_open(buff_manager, i, filename);
396 : 0 : free(filename);
397 : 0 : filename = NULL;
398 : 0 : key = (char *)buffer_manager_read_key(buff_manager, i, &keylen);
399 : 0 : h0 = hash(brz->h0, key+sizeof(keylen), keylen) % brz->k;
400 : 0 : buffer_h0[i] = h0;
401 : 0 : buffer_merge[i] = (cmph_uint8 *)key;
402 : 0 : key = NULL; //transfer memory ownership
403 : : }
404 : 0 : e = 0;
405 : 0 : keys_vd = (cmph_uint8 **)calloc((size_t)MAX_BUCKET_SIZE, sizeof(cmph_uint8 *));
406 : 0 : nkeys_vd = 0;
407 : 0 : error = 0;
408 [ # # ]: 0 : while(e < brz->m)
409 : : {
410 : 0 : i = brz_min_index(buffer_h0, nflushes);
411 : 0 : cur_bucket = buffer_h0[i];
412 : 0 : key = (char *)buffer_manager_read_key(buff_manager, i, &keylen);
413 [ # # ]: 0 : if(key)
414 : : {
415 [ # # ]: 0 : while(key)
416 : : {
417 : : //keylen = strlen(key);
418 : 0 : h0 = hash(brz->h0, key+sizeof(keylen), keylen) % brz->k;
419 [ # # ]: 0 : if (h0 != buffer_h0[i]) break;
420 : 0 : keys_vd[nkeys_vd++] = (cmph_uint8 *)key;
421 : 0 : key = NULL; //transfer memory ownership
422 : 0 : e++;
423 : 0 : key = (char *)buffer_manager_read_key(buff_manager, i, &keylen);
424 : : }
425 [ # # ]: 0 : if (key)
426 : : {
427 [ # # ]: 0 : assert(nkeys_vd < brz->size[cur_bucket]);
428 : 0 : keys_vd[nkeys_vd++] = buffer_merge[i];
429 : 0 : buffer_merge[i] = NULL; //transfer memory ownership
430 : 0 : e++;
431 : 0 : buffer_h0[i] = h0;
432 : 0 : buffer_merge[i] = (cmph_uint8 *)key;
433 : : }
434 : : }
435 [ # # ]: 0 : if(!key)
436 : : {
437 [ # # ]: 0 : assert(nkeys_vd < brz->size[cur_bucket]);
438 : 0 : keys_vd[nkeys_vd++] = buffer_merge[i];
439 : 0 : buffer_merge[i] = NULL; //transfer memory ownership
440 : 0 : e++;
441 : 0 : buffer_h0[i] = UINT_MAX;
442 : : }
443 : :
444 [ # # ]: 0 : if(nkeys_vd == brz->size[cur_bucket]) // Generating mphf for each bucket.
445 : : {
446 : 0 : cmph_io_adapter_t *source = NULL;
447 : 0 : cmph_config_t *config = NULL;
448 : 0 : cmph_t *mphf_tmp = NULL;
449 : 0 : char *bufmphf = NULL;
450 : 0 : cmph_uint32 buflenmphf = 0;
451 : : // Source of keys
452 : 0 : source = cmph_io_byte_vector_adapter(keys_vd, (cmph_uint32)nkeys_vd);
453 : 0 : config = cmph_config_new(source);
454 : 0 : cmph_config_set_algo(config, brz->algo);
455 : : //cmph_config_set_algo(config, CMPH_BMZ8);
456 : 0 : cmph_config_set_graphsize(config, brz->c);
457 : 0 : mphf_tmp = cmph_new(config);
458 [ # # ]: 0 : if (mphf_tmp == NULL)
459 : : {
460 [ # # ]: 0 : if(mph->verbosity) fprintf(stderr, "ERROR: Can't generate MPHF for bucket %u out of %u\n", cur_bucket + 1, brz->k);
461 : 0 : error = 1;
462 : 0 : cmph_config_destroy(config);
463 : 0 : brz_destroy_keys_vd(keys_vd, nkeys_vd);
464 : 0 : cmph_io_byte_vector_adapter_destroy(source);
465 : 0 : break;
466 : : }
467 [ # # ]: 0 : if(mph->verbosity)
468 : : {
469 [ # # ]: 0 : if (cur_bucket % 1000 == 0)
470 : : {
471 : 0 : fprintf(stderr, "MPHF for bucket %u out of %u was generated.\n", cur_bucket + 1, brz->k);
472 : : }
473 : : }
474 [ # # # ]: 0 : switch(brz->algo)
475 : : {
476 : 0 : case CMPH_FCH:
477 : : {
478 : 0 : fch_data_t * fchf = NULL;
479 : 0 : fchf = (fch_data_t *)mphf_tmp->data;
480 : 0 : bufmphf = brz_copy_partial_fch_mphf(brz, fchf, cur_bucket, &buflenmphf);
481 : : }
482 : 0 : break;
483 : 0 : case CMPH_BMZ8:
484 : : {
485 : 0 : bmz8_data_t * bmzf = NULL;
486 : 0 : bmzf = (bmz8_data_t *)mphf_tmp->data;
487 : 0 : bufmphf = brz_copy_partial_bmz8_mphf(brz, bmzf, cur_bucket, &buflenmphf);
488 : : }
489 : 0 : break;
490 : 0 : default: assert(0);
491 : : }
492 : 0 : nbytes = fwrite(bufmphf, (size_t)buflenmphf, (size_t)1, brz->mphf_fd);
493 : 0 : free(bufmphf);
494 : 0 : bufmphf = NULL;
495 : 0 : cmph_config_destroy(config);
496 : 0 : brz_destroy_keys_vd(keys_vd, nkeys_vd);
497 : 0 : cmph_destroy(mphf_tmp);
498 : 0 : cmph_io_byte_vector_adapter_destroy(source);
499 : 0 : nkeys_vd = 0;
500 : : }
501 : : }
502 : 0 : buffer_manager_destroy(buff_manager);
503 : 0 : free(keys_vd);
504 : 0 : free(buffer_merge);
505 : 0 : free(buffer_h0);
506 [ # # ]: 0 : if (error) return 0;
507 : 0 : return 1;
508 : : }
509 : :
510 : 0 : static cmph_uint32 brz_min_index(cmph_uint32 * vector, cmph_uint32 n)
511 : : {
512 : 0 : cmph_uint32 i, min_index = 0;
513 [ # # ]: 0 : for(i = 1; i < n; i++)
514 : : {
515 [ # # ]: 0 : if(vector[i] < vector[min_index]) min_index = i;
516 : : }
517 : 0 : return min_index;
518 : : }
519 : :
520 : 0 : static void brz_destroy_keys_vd(cmph_uint8 ** keys_vd, cmph_uint32 nkeys)
521 : : {
522 : : cmph_uint8 i;
523 [ # # ]: 0 : for(i = 0; i < nkeys; i++) { free(keys_vd[i]); keys_vd[i] = NULL;}
524 : 0 : }
525 : :
526 : 0 : static char * brz_copy_partial_fch_mphf(brz_config_data_t *brz, fch_data_t * fchf, cmph_uint32 index, cmph_uint32 *buflen)
527 : : {
528 : 0 : cmph_uint32 i = 0;
529 : 0 : cmph_uint32 buflenh1 = 0;
530 : 0 : cmph_uint32 buflenh2 = 0;
531 : 0 : char * bufh1 = NULL;
532 : 0 : char * bufh2 = NULL;
533 : 0 : char * buf = NULL;
534 : 0 : cmph_uint32 n = fchf->b;//brz->size[index];
535 : 0 : hash_state_dump(fchf->h1, &bufh1, &buflenh1);
536 : 0 : hash_state_dump(fchf->h2, &bufh2, &buflenh2);
537 : 0 : *buflen = buflenh1 + buflenh2 + n + 2U * (cmph_uint32)sizeof(cmph_uint32);
538 : 0 : buf = (char *)malloc((size_t)(*buflen));
539 : 0 : memcpy(buf, &buflenh1, sizeof(cmph_uint32));
540 : 0 : memcpy(buf+sizeof(cmph_uint32), bufh1, (size_t)buflenh1);
541 : 0 : memcpy(buf+sizeof(cmph_uint32)+buflenh1, &buflenh2, sizeof(cmph_uint32));
542 : 0 : memcpy(buf+2*sizeof(cmph_uint32)+buflenh1, bufh2, (size_t)buflenh2);
543 [ # # ]: 0 : for (i = 0; i < n; i++) memcpy(buf+2*sizeof(cmph_uint32)+buflenh1+buflenh2+i,(fchf->g + i), (size_t)1);
544 : 0 : free(bufh1);
545 : 0 : free(bufh2);
546 : 0 : return buf;
547 : : }
548 : 0 : static char * brz_copy_partial_bmz8_mphf(brz_config_data_t *brz, bmz8_data_t * bmzf, cmph_uint32 index, cmph_uint32 *buflen)
549 : : {
550 : 0 : cmph_uint32 buflenh1 = 0;
551 : 0 : cmph_uint32 buflenh2 = 0;
552 : 0 : char * bufh1 = NULL;
553 : 0 : char * bufh2 = NULL;
554 : 0 : char * buf = NULL;
555 : 0 : cmph_uint32 n = (cmph_uint32)ceil(brz->c * brz->size[index]);
556 : 0 : hash_state_dump(bmzf->hashes[0], &bufh1, &buflenh1);
557 : 0 : hash_state_dump(bmzf->hashes[1], &bufh2, &buflenh2);
558 : 0 : *buflen = buflenh1 + buflenh2 + n + 2U * (cmph_uint32)sizeof(cmph_uint32);
559 : 0 : buf = (char *)malloc((size_t)(*buflen));
560 : 0 : memcpy(buf, &buflenh1, sizeof(cmph_uint32));
561 : 0 : memcpy(buf+sizeof(cmph_uint32), bufh1, (size_t)buflenh1);
562 : 0 : memcpy(buf+sizeof(cmph_uint32)+buflenh1, &buflenh2, sizeof(cmph_uint32));
563 : 0 : memcpy(buf+2*sizeof(cmph_uint32)+buflenh1, bufh2, (size_t)buflenh2);
564 : 0 : memcpy(buf+2*sizeof(cmph_uint32)+buflenh1+buflenh2,bmzf->g, (size_t)n);
565 : 0 : free(bufh1);
566 : 0 : free(bufh2);
567 : 0 : return buf;
568 : : }
569 : :
570 : :
571 : 0 : int brz_dump(cmph_t *mphf, FILE *fd)
572 : : {
573 : 0 : brz_data_t *data = (brz_data_t *)mphf->data;
574 : 0 : char *buf = NULL;
575 : : cmph_uint32 buflen;
576 : : register size_t nbytes;
577 : : DEBUGP("Dumping brzf\n");
578 : : // The initial part of the MPHF have already been dumped to disk during construction
579 : : // Dumping h0
580 : 0 : hash_state_dump(data->h0, &buf, &buflen);
581 : : DEBUGP("Dumping hash state with %u bytes to disk\n", buflen);
582 : 0 : nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
583 : 0 : nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
584 : 0 : free(buf);
585 : : // Dumping m and the vector offset.
586 : 0 : nbytes = fwrite(&(data->m), sizeof(cmph_uint32), (size_t)1, fd);
587 : 0 : nbytes = fwrite(data->offset, sizeof(cmph_uint32)*(data->k), (size_t)1, fd);
588 [ # # # # ]: 0 : if (nbytes == 0 && ferror(fd)) {
589 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
590 : 0 : return 0;
591 : : }
592 : 0 : return 1;
593 : : }
594 : :
595 : 0 : void brz_load(FILE *f, cmph_t *mphf)
596 : : {
597 : 0 : char *buf = NULL;
598 : : cmph_uint32 buflen;
599 : : register size_t nbytes;
600 : : cmph_uint32 i, n;
601 : 0 : brz_data_t *brz = (brz_data_t *)malloc(sizeof(brz_data_t));
602 : :
603 : : DEBUGP("Loading brz mphf\n");
604 : 0 : mphf->data = brz;
605 : 0 : nbytes = fread(&(brz->c), sizeof(double), (size_t)1, f);
606 : 0 : nbytes = fread(&(brz->algo), sizeof(brz->algo), (size_t)1, f); // Reading algo.
607 : 0 : nbytes = fread(&(brz->k), sizeof(cmph_uint32), (size_t)1, f);
608 : 0 : brz->size = (cmph_uint8 *) malloc(sizeof(cmph_uint8)*brz->k);
609 : 0 : nbytes = fread(brz->size, sizeof(cmph_uint8)*(brz->k), (size_t)1, f);
610 : 0 : brz->h1 = (hash_state_t **)malloc(sizeof(hash_state_t *)*brz->k);
611 : 0 : brz->h2 = (hash_state_t **)malloc(sizeof(hash_state_t *)*brz->k);
612 : 0 : brz->g = (cmph_uint8 **) calloc((size_t)brz->k, sizeof(cmph_uint8 *));
613 : : DEBUGP("Reading c = %f k = %u algo = %u \n", brz->c, brz->k, brz->algo);
614 : : //loading h_i1, h_i2 and g_i.
615 [ # # ]: 0 : for(i = 0; i < brz->k; i++)
616 : : {
617 : : // h1
618 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, f);
619 : : DEBUGP("Hash state 1 has %u bytes\n", buflen);
620 : 0 : buf = (char *)malloc((size_t)buflen);
621 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, f);
622 : 0 : brz->h1[i] = hash_state_load(buf, buflen);
623 : 0 : free(buf);
624 : : //h2
625 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, f);
626 : : DEBUGP("Hash state 2 has %u bytes\n", buflen);
627 : 0 : buf = (char *)malloc((size_t)buflen);
628 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, f);
629 : 0 : brz->h2[i] = hash_state_load(buf, buflen);
630 : 0 : free(buf);
631 [ # # # ]: 0 : switch(brz->algo)
632 : : {
633 : 0 : case CMPH_FCH:
634 : 0 : n = fch_calc_b(brz->c, brz->size[i]);
635 : 0 : break;
636 : 0 : case CMPH_BMZ8:
637 : 0 : n = (cmph_uint32)ceil(brz->c * brz->size[i]);
638 : 0 : break;
639 : 0 : default: assert(0);
640 : : }
641 : : DEBUGP("g_i has %u bytes\n", n);
642 : 0 : brz->g[i] = (cmph_uint8 *)calloc((size_t)n, sizeof(cmph_uint8));
643 : 0 : nbytes = fread(brz->g[i], sizeof(cmph_uint8)*n, (size_t)1, f);
644 : : }
645 : : //loading h0
646 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, f);
647 : : DEBUGP("Hash state has %u bytes\n", buflen);
648 : 0 : buf = (char *)malloc((size_t)buflen);
649 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, f);
650 : 0 : brz->h0 = hash_state_load(buf, buflen);
651 : 0 : free(buf);
652 : :
653 : : //loading c, m, and the vector offset.
654 : 0 : nbytes = fread(&(brz->m), sizeof(cmph_uint32), (size_t)1, f);
655 : 0 : brz->offset = (cmph_uint32 *)malloc(sizeof(cmph_uint32)*brz->k);
656 : 0 : nbytes = fread(brz->offset, sizeof(cmph_uint32)*(brz->k), (size_t)1, f);
657 [ # # # # ]: 0 : if (nbytes == 0 && ferror(f)) {
658 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
659 : : }
660 : :
661 : 0 : return;
662 : : }
663 : :
664 : 0 : static cmph_uint32 brz_bmz8_search(brz_data_t *brz, const char *key, cmph_uint32 keylen, cmph_uint32 * fingerprint)
665 : : {
666 : : register cmph_uint32 h0;
667 : : register cmph_uint32 m, n, h1, h2;
668 : : register cmph_uint8 mphf_bucket;
669 : :
670 : 0 : hash_vector(brz->h0, key, keylen, fingerprint);
671 : 0 : h0 = fingerprint[2] % brz->k;
672 : :
673 : 0 : m = brz->size[h0];
674 : 0 : n = (cmph_uint32)ceil(brz->c * m);
675 : 0 : h1 = hash(brz->h1[h0], key, keylen) % n;
676 : 0 : h2 = hash(brz->h2[h0], key, keylen) % n;
677 : :
678 [ # # # # ]: 0 : if (h1 == h2 && ++h2 >= n) h2 = 0;
679 : 0 : mphf_bucket = (cmph_uint8)(brz->g[h0][h1] + brz->g[h0][h2]);
680 : : DEBUGP("key: %s h1: %u h2: %u h0: %u\n", key, h1, h2, h0);
681 : : DEBUGP("key: %s g[h1]: %u g[h2]: %u offset[h0]: %u edges: %u\n", key, brz->g[h0][h1], brz->g[h0][h2], brz->offset[h0], brz->m);
682 : : DEBUGP("Address: %u\n", mphf_bucket + brz->offset[h0]);
683 : 0 : return (mphf_bucket + brz->offset[h0]);
684 : : }
685 : :
686 : 0 : static cmph_uint32 brz_fch_search(brz_data_t *brz, const char *key, cmph_uint32 keylen, cmph_uint32 * fingerprint)
687 : : {
688 : : register cmph_uint32 h0;
689 : : register cmph_uint32 m, b, h1, h2;
690 : : register double p1, p2;
691 : : register cmph_uint8 mphf_bucket;
692 : :
693 : 0 : hash_vector(brz->h0, key, keylen, fingerprint);
694 : 0 : h0 = fingerprint[2] % brz->k;
695 : :
696 : 0 : m = brz->size[h0];
697 : 0 : b = fch_calc_b(brz->c, m);
698 : 0 : p1 = fch_calc_p1(m);
699 : 0 : p2 = fch_calc_p2(b);
700 : 0 : h1 = hash(brz->h1[h0], key, keylen) % m;
701 : 0 : h2 = hash(brz->h2[h0], key, keylen) % m;
702 : 0 : mphf_bucket = 0;
703 : 0 : h1 = mixh10h11h12(b, p1, p2, h1);
704 : 0 : mphf_bucket = (cmph_uint8)((h2 + brz->g[h0][h1]) % m);
705 : 0 : return (mphf_bucket + brz->offset[h0]);
706 : : }
707 : :
708 : 0 : cmph_uint32 brz_search(cmph_t *mphf, const char *key, cmph_uint32 keylen)
709 : : {
710 : 0 : brz_data_t *brz = mphf->data;
711 : : cmph_uint32 fingerprint[3];
712 [ # # # ]: 0 : switch(brz->algo)
713 : : {
714 : 0 : case CMPH_FCH:
715 : 0 : return brz_fch_search(brz, key, keylen, fingerprint);
716 : 0 : case CMPH_BMZ8:
717 : 0 : return brz_bmz8_search(brz, key, keylen, fingerprint);
718 : 0 : default: assert(0);
719 : : }
720 : : return 0;
721 : : }
722 : 0 : void brz_destroy(cmph_t *mphf)
723 : : {
724 : : cmph_uint32 i;
725 : 0 : brz_data_t *data = (brz_data_t *)mphf->data;
726 [ # # ]: 0 : if(data->g)
727 : : {
728 [ # # ]: 0 : for(i = 0; i < data->k; i++)
729 : : {
730 : 0 : free(data->g[i]);
731 : 0 : hash_state_destroy(data->h1[i]);
732 : 0 : hash_state_destroy(data->h2[i]);
733 : : }
734 : 0 : free(data->g);
735 : 0 : free(data->h1);
736 : 0 : free(data->h2);
737 : : }
738 : 0 : hash_state_destroy(data->h0);
739 : 0 : free(data->size);
740 : 0 : free(data->offset);
741 : 0 : free(data);
742 : 0 : free(mphf);
743 : 0 : }
744 : :
745 : : /** \fn void brz_pack(cmph_t *mphf, void *packed_mphf);
746 : : * \brief Support the ability to pack a perfect hash function into a preallocated contiguous memory space pointed by packed_mphf.
747 : : * \param mphf pointer to the resulting mphf
748 : : * \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()
749 : : */
750 : 0 : void brz_pack(cmph_t *mphf, void *packed_mphf)
751 : : {
752 : 0 : brz_data_t *data = (brz_data_t *)mphf->data;
753 : 0 : cmph_uint8 * ptr = packed_mphf;
754 : : cmph_uint32 i,n;
755 : : CMPH_HASH h0_type, h1_type, h2_type;
756 : : uintptr_t *g_is_ptr;
757 : : cmph_uint8 * g_i;
758 : :
759 : : // packing internal algo type
760 : 0 : memcpy(ptr, &(data->algo), sizeof(data->algo));
761 : 0 : ptr += sizeof(data->algo);
762 : :
763 : : // packing h0 type
764 : 0 : h0_type = hash_get_type(data->h0);
765 : 0 : memcpy(ptr, &h0_type, sizeof(h0_type));
766 : 0 : ptr += sizeof(h0_type);
767 : :
768 : : // packing h0
769 : 0 : hash_state_pack(data->h0, ptr);
770 : 0 : ptr += hash_state_packed_size(h0_type);
771 : :
772 : : // packing k
773 : 0 : memcpy(ptr, &(data->k), sizeof(data->k));
774 : 0 : ptr += sizeof(data->k);
775 : :
776 : : // packing c
777 : 0 : *((cmph_uint64 *)ptr) = (cmph_uint64)data->c;
778 : 0 : ptr += sizeof(data->c);
779 : :
780 : : // packing h1 type
781 : 0 : h1_type = hash_get_type(data->h1[0]);
782 : 0 : memcpy(ptr, &h1_type, sizeof(h1_type));
783 : 0 : ptr += sizeof(h1_type);
784 : :
785 : : // packing h2 type
786 : 0 : h2_type = hash_get_type(data->h2[0]);
787 : 0 : memcpy(ptr, &h2_type, sizeof(h2_type));
788 : 0 : ptr += sizeof(h2_type);
789 : :
790 : : // packing size
791 : 0 : memcpy(ptr, data->size, sizeof(cmph_uint8)*data->k);
792 : 0 : ptr += data->k;
793 : :
794 : : // packing offset
795 : 0 : memcpy(ptr, data->offset, sizeof(cmph_uint32)*data->k);
796 : 0 : ptr += sizeof(cmph_uint32)*data->k;
797 : :
798 : 0 : g_is_ptr = (uintptr_t *)ptr;
799 : :
800 : 0 : g_i = (cmph_uint8 *) (g_is_ptr + data->k);
801 : :
802 [ # # ]: 0 : for(i = 0; i < data->k; i++)
803 : : {
804 : 0 : *g_is_ptr++ = (uintptr_t)g_i;
805 : : // packing h1[i]
806 : 0 : hash_state_pack(data->h1[i], g_i);
807 : 0 : g_i += hash_state_packed_size(h1_type);
808 : :
809 : : // packing h2[i]
810 : 0 : hash_state_pack(data->h2[i], g_i);
811 : 0 : g_i += hash_state_packed_size(h2_type);
812 : :
813 : : // packing g_i
814 [ # # # ]: 0 : switch(data->algo)
815 : : {
816 : 0 : case CMPH_FCH:
817 : 0 : n = fch_calc_b(data->c, data->size[i]);
818 : 0 : break;
819 : 0 : case CMPH_BMZ8:
820 : 0 : n = (cmph_uint32)ceil(data->c * data->size[i]);
821 : 0 : break;
822 : 0 : default: assert(0);
823 : : }
824 : 0 : memcpy(g_i, data->g[i], sizeof(cmph_uint8)*n);
825 : 0 : g_i += n;
826 : :
827 : : }
828 : :
829 : 0 : }
830 : :
831 : : /** \fn cmph_uint32 brz_packed_size(cmph_t *mphf);
832 : : * \brief Return the amount of space needed to pack mphf.
833 : : * \param mphf pointer to a mphf
834 : : * \return the size of the packed function or zero for failures
835 : : */
836 : 0 : cmph_uint32 brz_packed_size(cmph_t *mphf)
837 : : {
838 : : cmph_uint32 i;
839 : 0 : cmph_uint32 size = 0;
840 : 0 : brz_data_t *data = (brz_data_t *)mphf->data;
841 : 0 : CMPH_HASH h0_type = hash_get_type(data->h0);
842 : 0 : CMPH_HASH h1_type = hash_get_type(data->h1[0]);
843 : 0 : CMPH_HASH h2_type = hash_get_type(data->h2[0]);
844 : : cmph_uint32 n;
845 : 0 : size = (cmph_uint32)(2*sizeof(CMPH_ALGO) + 3*sizeof(CMPH_HASH) + hash_state_packed_size(h0_type) + sizeof(cmph_uint32) +
846 : 0 : sizeof(double) + sizeof(cmph_uint8)*data->k + sizeof(cmph_uint32)*data->k);
847 : : // pointers to g_is
848 : 0 : size += (cmph_uint32) sizeof(uintptr_t) * data->k;
849 : 0 : size += hash_state_packed_size(h1_type) * data->k;
850 : 0 : size += hash_state_packed_size(h2_type) * data->k;
851 : :
852 : 0 : n = 0;
853 [ # # ]: 0 : for(i = 0; i < data->k; i++)
854 : : {
855 [ # # # ]: 0 : switch(data->algo)
856 : : {
857 : 0 : case CMPH_FCH:
858 : 0 : n = fch_calc_b(data->c, data->size[i]);
859 : 0 : break;
860 : 0 : case CMPH_BMZ8:
861 : 0 : n = (cmph_uint32)ceil(data->c * data->size[i]);
862 : 0 : break;
863 : 0 : default: assert(0);
864 : : }
865 : 0 : size += n;
866 : : }
867 : 0 : return size;
868 : : }
869 : :
870 : :
871 : :
872 : 0 : static cmph_uint32 brz_bmz8_search_packed(cmph_uint32 *packed_mphf, const char *key, cmph_uint32 keylen, cmph_uint32 * fingerprint)
873 : : {
874 : 0 : register CMPH_HASH h0_type = *packed_mphf++;
875 : 0 : register cmph_uint32 *h0_ptr = packed_mphf;
876 : : register cmph_uint32 k, h0, m, n, h1, h2;
877 : : register cmph_uint32 *offset;
878 : : register double c;
879 : : register CMPH_HASH h1_type, h2_type;
880 : : register cmph_uint8 * size;
881 : : register uintptr_t *g_is_ptr;
882 : : register cmph_uint8 *h1_ptr, *h2_ptr, *g;
883 : : register cmph_uint8 mphf_bucket;
884 : :
885 : 0 : packed_mphf = (cmph_uint32 *)(((cmph_uint8 *)packed_mphf) + hash_state_packed_size(h0_type));
886 : :
887 : 0 : k = *packed_mphf++;
888 : :
889 : 0 : c = (double)(*((cmph_uint64*)packed_mphf));
890 : 0 : packed_mphf += 2;
891 : :
892 : 0 : h1_type = *packed_mphf++;
893 : :
894 : 0 : h2_type = *packed_mphf++;
895 : :
896 : 0 : size = (cmph_uint8 *) packed_mphf;
897 : 0 : packed_mphf = (cmph_uint32 *)(size + k);
898 : :
899 : 0 : offset = packed_mphf;
900 : 0 : packed_mphf += k;
901 : :
902 : :
903 : 0 : hash_vector_packed(h0_ptr, h0_type, key, keylen, fingerprint);
904 : 0 : h0 = fingerprint[2] % k;
905 : :
906 : 0 : m = size[h0];
907 : 0 : n = (cmph_uint32)ceil(c * m);
908 : :
909 : 0 : g_is_ptr = (uintptr_t *)packed_mphf;
910 : :
911 : 0 : h1_ptr = (cmph_uint8 *) g_is_ptr[h0];
912 : :
913 : 0 : h2_ptr = h1_ptr + hash_state_packed_size(h1_type);
914 : :
915 : 0 : g = h2_ptr + hash_state_packed_size(h2_type);
916 : :
917 : 0 : h1 = hash_packed(h1_ptr, h1_type, key, keylen) % n;
918 : 0 : h2 = hash_packed(h2_ptr, h2_type, key, keylen) % n;
919 : :
920 [ # # # # ]: 0 : if (h1 == h2 && ++h2 >= n) h2 = 0;
921 : 0 : mphf_bucket = (cmph_uint8)(g[h1] + g[h2]);
922 : : DEBUGP("key: %s h1: %u h2: %u h0: %u\n", key, h1, h2, h0);
923 : : DEBUGP("Address: %u\n", mphf_bucket + offset[h0]);
924 : 0 : return (mphf_bucket + offset[h0]);
925 : : }
926 : :
927 : 0 : static cmph_uint32 brz_fch_search_packed(cmph_uint32 *packed_mphf, const char *key, cmph_uint32 keylen, cmph_uint32 * fingerprint)
928 : : {
929 : 0 : register CMPH_HASH h0_type = *packed_mphf++;
930 : :
931 : 0 : register cmph_uint32 *h0_ptr = packed_mphf;
932 : : register cmph_uint32 k, h0, m, b, h1, h2;
933 : : register double c, p1, p2;
934 : : register CMPH_HASH h1_type, h2_type;
935 : : register cmph_uint8 *size, *h1_ptr, *h2_ptr, *g;
936 : : register cmph_uint32 *offset;
937 : : register uintptr_t *g_is_ptr;
938 : : register cmph_uint8 mphf_bucket;
939 : :
940 : 0 : packed_mphf = (cmph_uint32 *)(((cmph_uint8 *)packed_mphf) + hash_state_packed_size(h0_type));
941 : :
942 : 0 : k = *packed_mphf++;
943 : :
944 : 0 : c = (double)(*((cmph_uint64*)packed_mphf));
945 : 0 : packed_mphf += 2;
946 : :
947 : 0 : h1_type = *packed_mphf++;
948 : :
949 : 0 : h2_type = *packed_mphf++;
950 : :
951 : 0 : size = (cmph_uint8 *) packed_mphf;
952 : 0 : packed_mphf = (cmph_uint32 *)(size + k);
953 : :
954 : 0 : offset = packed_mphf;
955 : 0 : packed_mphf += k;
956 : :
957 : 0 : hash_vector_packed(h0_ptr, h0_type, key, keylen, fingerprint);
958 : 0 : h0 = fingerprint[2] % k;
959 : :
960 : 0 : m = size[h0];
961 : 0 : b = fch_calc_b(c, m);
962 : 0 : p1 = fch_calc_p1(m);
963 : 0 : p2 = fch_calc_p2(b);
964 : :
965 : 0 : g_is_ptr = (uintptr_t *)packed_mphf;
966 : :
967 : 0 : h1_ptr = (cmph_uint8 *) g_is_ptr[h0];
968 : :
969 : 0 : h2_ptr = h1_ptr + hash_state_packed_size(h1_type);
970 : :
971 : 0 : g = h2_ptr + hash_state_packed_size(h2_type);
972 : :
973 : 0 : h1 = hash_packed(h1_ptr, h1_type, key, keylen) % m;
974 : 0 : h2 = hash_packed(h2_ptr, h2_type, key, keylen) % m;
975 : :
976 : 0 : mphf_bucket = 0;
977 : 0 : h1 = mixh10h11h12(b, p1, p2, h1);
978 : 0 : mphf_bucket = (cmph_uint8)((h2 + g[h1]) % m);
979 : 0 : return (mphf_bucket + offset[h0]);
980 : : }
981 : :
982 : : /** cmph_uint32 brz_search(void *packed_mphf, const char *key, cmph_uint32 keylen);
983 : : * \brief Use the packed mphf to do a search.
984 : : * \param packed_mphf pointer to the packed mphf
985 : : * \param key key to be hashed
986 : : * \param keylen key length in bytes
987 : : * \return The mphf value
988 : : */
989 : 0 : cmph_uint32 brz_search_packed(void *packed_mphf, const char *key, cmph_uint32 keylen)
990 : : {
991 : 0 : register cmph_uint32 *ptr = (cmph_uint32 *)packed_mphf;
992 : 0 : register CMPH_ALGO algo = *ptr++;
993 : : cmph_uint32 fingerprint[3];
994 [ # # # ]: 0 : switch(algo)
995 : : {
996 : 0 : case CMPH_FCH:
997 : 0 : return brz_fch_search_packed(ptr, key, keylen, fingerprint);
998 : 0 : case CMPH_BMZ8:
999 : 0 : return brz_bmz8_search_packed(ptr, key, keylen, fingerprint);
1000 : 0 : default:
1001 : 0 : assert(0);
1002 : : return 0; /* To avoid warnings that value must be returned */
1003 : : }
1004 : : }
1005 : :
|
