Branch data Line data Source code
1 : : #include "fch.h"
2 : : #include "cmph_structs.h"
3 : : #include "fch_structs.h"
4 : : #include "hash.h"
5 : : #include "bitbool.h"
6 : : #include "fch_buckets.h"
7 : : #include <math.h>
8 : : #include <stdlib.h>
9 : : #include <stdio.h>
10 : : #include <assert.h>
11 : : #include <string.h>
12 : : #include <errno.h>
13 : :
14 : : #define INDEX 0 /* alignment index within a bucket */
15 : : //#define DEBUG
16 : : #include "debug.h"
17 : :
18 : : static fch_buckets_t * mapping(cmph_config_t *mph);
19 : : static cmph_uint32 * ordering(fch_buckets_t * buckets);
20 : : static cmph_uint8 check_for_collisions_h2(fch_config_data_t *fch, fch_buckets_t * buckets, cmph_uint32 *sorted_indexes);
21 : : static void permut(cmph_uint32 * vector, cmph_uint32 n);
22 : : static cmph_uint8 searching(fch_config_data_t *fch, fch_buckets_t *buckets, cmph_uint32 *sorted_indexes);
23 : :
24 : 0 : fch_config_data_t *fch_config_new(void)
25 : : {
26 : : fch_config_data_t *fch;
27 : 0 : fch = (fch_config_data_t *)malloc(sizeof(fch_config_data_t));
28 [ # # ]: 0 : assert(fch);
29 : 0 : memset(fch, 0, sizeof(fch_config_data_t));
30 : 0 : fch->hashfuncs[0] = CMPH_HASH_JENKINS;
31 : 0 : fch->hashfuncs[1] = CMPH_HASH_JENKINS;
32 : 0 : fch->m = fch->b = 0;
33 : 0 : fch->c = fch->p1 = fch->p2 = 0.0;
34 : 0 : fch->g = NULL;
35 : 0 : fch->h1 = NULL;
36 : 0 : fch->h2 = NULL;
37 : 0 : return fch;
38 : : }
39 : :
40 : 0 : void fch_config_destroy(cmph_config_t *mph)
41 : : {
42 : 0 : fch_config_data_t *data = (fch_config_data_t *)mph->data;
43 : : //DEBUGP("Destroying algorithm dependent data\n");
44 : 0 : free(data);
45 : 0 : }
46 : :
47 : 0 : void fch_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs)
48 : : {
49 : 0 : fch_config_data_t *fch = (fch_config_data_t *)mph->data;
50 : 0 : CMPH_HASH *hashptr = hashfuncs;
51 : 0 : cmph_uint32 i = 0;
52 [ # # ]: 0 : while(*hashptr != CMPH_HASH_COUNT)
53 : : {
54 [ # # ]: 0 : if (i >= 2) break; //fch only uses two hash functions
55 : 0 : fch->hashfuncs[i] = *hashptr;
56 : 0 : ++i, ++hashptr;
57 : : }
58 : 0 : }
59 : :
60 : 0 : cmph_uint32 mixh10h11h12(cmph_uint32 b, double p1, double p2, cmph_uint32 initial_index)
61 : : {
62 : 0 : register cmph_uint32 int_p2 = (cmph_uint32)p2;
63 [ # # ]: 0 : if (initial_index < p1) initial_index %= int_p2; /* h11 o h10 */
64 : : else { /* h12 o h10 */
65 : 0 : initial_index %= b;
66 [ # # ]: 0 : if(initial_index < p2) initial_index += int_p2;
67 : : }
68 : 0 : return initial_index;
69 : : }
70 : :
71 : :
72 : 0 : cmph_uint32 fch_calc_b(double c, cmph_uint32 m)
73 : : {
74 : 0 : return (cmph_uint32)ceil((c*m)/(log((double)m)/log(2.0) + 1));
75 : : }
76 : :
77 : 0 : double fch_calc_p1(cmph_uint32 m)
78 : : {
79 : 0 : return ceil(0.55*m);
80 : : }
81 : :
82 : 0 : double fch_calc_p2(cmph_uint32 b)
83 : : {
84 : 0 : return ceil(0.3*b);
85 : : }
86 : :
87 : 0 : static fch_buckets_t * mapping(cmph_config_t *mph)
88 : : {
89 : 0 : cmph_uint32 i = 0;
90 : 0 : fch_buckets_t *buckets = NULL;
91 : 0 : fch_config_data_t *fch = (fch_config_data_t *)mph->data;
92 [ # # ]: 0 : if (fch->h1) hash_state_destroy(fch->h1);
93 : 0 : fch->h1 = hash_state_new(fch->hashfuncs[0], fch->m);
94 : 0 : fch->b = fch_calc_b(fch->c, fch->m);
95 : 0 : fch->p1 = fch_calc_p1(fch->m);
96 : 0 : fch->p2 = fch_calc_p2(fch->b);
97 : : //DEBUGP("b:%u p1:%f p2:%f\n", fch->b, fch->p1, fch->p2);
98 : 0 : buckets = fch_buckets_new(fch->b);
99 : :
100 : 0 : mph->key_source->rewind(mph->key_source->data);
101 [ # # ]: 0 : for(i = 0; i < fch->m; i++)
102 : : {
103 : : cmph_uint32 h1, keylen;
104 : 0 : char *key = NULL;
105 : 0 : mph->key_source->read(mph->key_source->data, &key, &keylen);
106 : 0 : h1 = hash(fch->h1, key, keylen) % fch->m;
107 : 0 : h1 = mixh10h11h12 (fch->b, fch->p1, fch->p2, h1);
108 : 0 : fch_buckets_insert(buckets, h1, key, keylen);
109 : 0 : key = NULL; // transger memory ownership
110 : :
111 : : }
112 : 0 : return buckets;
113 : : }
114 : :
115 : :
116 : : // returns the buckets indexes sorted by their sizes.
117 : 0 : static cmph_uint32 * ordering(fch_buckets_t * buckets)
118 : : {
119 : 0 : return fch_buckets_get_indexes_sorted_by_size(buckets);
120 : : }
121 : :
122 : : /* Check whether function h2 causes collisions among the keys of each bucket */
123 : 0 : static cmph_uint8 check_for_collisions_h2(fch_config_data_t *fch, fch_buckets_t * buckets, cmph_uint32 *sorted_indexes)
124 : : {
125 : : //cmph_uint32 max_size = fch_buckets_get_max_size(buckets);
126 : 0 : cmph_uint8 * hashtable = (cmph_uint8 *)calloc((size_t)fch->m, sizeof(cmph_uint8));
127 : 0 : cmph_uint32 nbuckets = fch_buckets_get_nbuckets(buckets);
128 : 0 : cmph_uint32 i = 0, index = 0, j =0;
129 [ # # ]: 0 : for (i = 0; i < nbuckets; i++)
130 : : {
131 : 0 : cmph_uint32 nkeys = fch_buckets_get_size(buckets, sorted_indexes[i]);
132 : 0 : memset(hashtable, 0, (size_t)fch->m);
133 : : //DEBUGP("bucket %u -- nkeys: %u\n", i, nkeys);
134 [ # # ]: 0 : for (j = 0; j < nkeys; j++)
135 : : {
136 : 0 : char * key = fch_buckets_get_key(buckets, sorted_indexes[i], j);
137 : 0 : cmph_uint32 keylen = fch_buckets_get_keylength(buckets, sorted_indexes[i], j);
138 : 0 : index = hash(fch->h2, key, keylen) % fch->m;
139 [ # # ]: 0 : if(hashtable[index]) { // collision detected
140 : 0 : free(hashtable);
141 : 0 : return 1;
142 : : }
143 : 0 : hashtable[index] = 1;
144 : : }
145 : : }
146 : 0 : free(hashtable);
147 : 0 : return 0;
148 : : }
149 : :
150 : 0 : static void permut(cmph_uint32 * vector, cmph_uint32 n)
151 : : {
152 : : cmph_uint32 i, j, b;
153 [ # # ]: 0 : for (i = 0; i < n; i++) {
154 : 0 : j = (cmph_uint32) rand() % n;
155 : 0 : b = vector[i];
156 : 0 : vector[i] = vector[j];
157 : 0 : vector[j] = b;
158 : : }
159 : 0 : }
160 : :
161 : 0 : static cmph_uint8 searching(fch_config_data_t *fch, fch_buckets_t *buckets, cmph_uint32 *sorted_indexes)
162 : : {
163 : 0 : cmph_uint32 * random_table = (cmph_uint32 *) calloc((size_t)fch->m, sizeof(cmph_uint32));
164 : 0 : cmph_uint32 * map_table = (cmph_uint32 *) calloc((size_t)fch->m, sizeof(cmph_uint32));
165 : 0 : cmph_uint32 iteration_to_generate_h2 = 0;
166 : 0 : cmph_uint32 searching_iterations = 0;
167 : 0 : cmph_uint8 restart = 0;
168 : 0 : cmph_uint32 nbuckets = fch_buckets_get_nbuckets(buckets);
169 : 0 : cmph_uint32 i, j, z, counter = 0, filled_count = 0;
170 [ # # ]: 0 : if (fch->g) free (fch->g);
171 : 0 : fch->g = (cmph_uint32 *) calloc((size_t)fch->b, sizeof(cmph_uint32));
172 : :
173 : : //DEBUGP("max bucket size: %u\n", fch_buckets_get_max_size(buckets));
174 : :
175 [ # # ]: 0 : for(i = 0; i < fch->m; i++)
176 : : {
177 : 0 : random_table[i] = i;
178 : : }
179 : 0 : permut(random_table, fch->m);
180 [ # # ]: 0 : for(i = 0; i < fch->m; i++)
181 : : {
182 : 0 : map_table[random_table[i]] = i;
183 : : }
184 : : do {
185 [ # # ]: 0 : if (fch->h2) hash_state_destroy(fch->h2);
186 : 0 : fch->h2 = hash_state_new(fch->hashfuncs[1], fch->m);
187 : 0 : restart = check_for_collisions_h2(fch, buckets, sorted_indexes);
188 : 0 : filled_count = 0;
189 [ # # ]: 0 : if (!restart)
190 : : {
191 : 0 : searching_iterations++; iteration_to_generate_h2 = 0;
192 : : //DEBUGP("searching_iterations: %u\n", searching_iterations);
193 : : }
194 : : else {
195 : 0 : iteration_to_generate_h2++;
196 : : //DEBUGP("iteration_to_generate_h2: %u\n", iteration_to_generate_h2);
197 : : }
198 [ # # # # ]: 0 : for(i = 0; (i < nbuckets) && !restart; i++) {
199 : 0 : cmph_uint32 bucketsize = fch_buckets_get_size(buckets, sorted_indexes[i]);
200 [ # # ]: 0 : if (bucketsize == 0)
201 : : {
202 : 0 : restart = 0; // false
203 : 0 : break;
204 : : }
205 : 0 : else restart = 1; // true
206 [ # # # # ]: 0 : for(z = 0; (z < (fch->m - filled_count)) && restart; z++) {
207 : 0 : char * key = fch_buckets_get_key(buckets, sorted_indexes[i], INDEX);
208 : 0 : cmph_uint32 keylen = fch_buckets_get_keylength(buckets, sorted_indexes[i], INDEX);
209 : 0 : cmph_uint32 h2 = hash(fch->h2, key, keylen) % fch->m;
210 : 0 : counter = 0;
211 : 0 : restart = 0; // false
212 : 0 : fch->g[sorted_indexes[i]] = (fch->m + random_table[filled_count + z] - h2) % fch->m;
213 : : //DEBUGP("g[%u]: %u\n", sorted_indexes[i], fch->g[sorted_indexes[i]]);
214 : 0 : j = INDEX;
215 : : do {
216 : 0 : cmph_uint32 index = 0;
217 : 0 : key = fch_buckets_get_key(buckets, sorted_indexes[i], j);
218 : 0 : keylen = fch_buckets_get_keylength(buckets, sorted_indexes[i], j);
219 : 0 : h2 = hash(fch->h2, key, keylen) % fch->m;
220 : 0 : index = (h2 + fch->g[sorted_indexes[i]]) % fch->m;
221 : : //DEBUGP("key:%s keylen:%u index: %u h2:%u bucketsize:%u\n", key, keylen, index, h2, bucketsize);
222 [ # # ]: 0 : if (map_table[index] >= filled_count) {
223 : 0 : cmph_uint32 y = map_table[index];
224 : 0 : cmph_uint32 ry = random_table[y];
225 : 0 : random_table[y] = random_table[filled_count];
226 : 0 : random_table[filled_count] = ry;
227 : 0 : map_table[random_table[y]] = y;
228 : 0 : map_table[random_table[filled_count]] = filled_count;
229 : 0 : filled_count++;
230 : 0 : counter ++;
231 : : }
232 : : else {
233 : 0 : restart = 1; // true
234 : 0 : filled_count = filled_count - counter;
235 : 0 : counter = 0;
236 : 0 : break;
237 : : }
238 : 0 : j = (j + 1) % bucketsize;
239 [ # # ]: 0 : } while(j % bucketsize != INDEX);
240 : : }
241 : : //getchar();
242 : : }
243 [ # # # # : 0 : } while(restart && (searching_iterations < 10) && (iteration_to_generate_h2 < 1000));
# # ]
244 : 0 : free(map_table);
245 : 0 : free(random_table);
246 : 0 : return restart;
247 : : }
248 : :
249 : :
250 : :
251 : 0 : cmph_t *fch_new(cmph_config_t *mph, double c)
252 : : {
253 : 0 : cmph_t *mphf = NULL;
254 : 0 : fch_data_t *fchf = NULL;
255 : 0 : cmph_uint32 iterations = 100;
256 : 0 : cmph_uint8 restart_mapping = 0;
257 : 0 : fch_buckets_t * buckets = NULL;
258 : 0 : cmph_uint32 * sorted_indexes = NULL;
259 : 0 : fch_config_data_t *fch = (fch_config_data_t *)mph->data;
260 : 0 : fch->m = mph->key_source->nkeys;
261 : : //DEBUGP("m: %f\n", fch->m);
262 [ # # ]: 0 : if (c <= 2) c = 2.6; // validating restrictions over parameter c.
263 : 0 : fch->c = c;
264 : : //DEBUGP("c: %f\n", fch->c);
265 : 0 : fch->h1 = NULL;
266 : 0 : fch->h2 = NULL;
267 : 0 : fch->g = NULL;
268 : : do
269 : : {
270 [ # # ]: 0 : if (mph->verbosity)
271 : : {
272 : 0 : fprintf(stderr, "Entering mapping step for mph creation of %u keys\n", fch->m);
273 : : }
274 [ # # ]: 0 : if (buckets) fch_buckets_destroy(buckets);
275 : 0 : buckets = mapping(mph);
276 [ # # ]: 0 : if (mph->verbosity)
277 : : {
278 : 0 : fprintf(stderr, "Starting ordering step\n");
279 : : }
280 [ # # ]: 0 : if (sorted_indexes) free (sorted_indexes);
281 : 0 : sorted_indexes = ordering(buckets);
282 [ # # ]: 0 : if (mph->verbosity)
283 : : {
284 : 0 : fprintf(stderr, "Starting searching step.\n");
285 : : }
286 : 0 : restart_mapping = searching(fch, buckets, sorted_indexes);
287 : 0 : iterations--;
288 : :
289 [ # # # # ]: 0 : } while(restart_mapping && iterations > 0);
290 [ # # ]: 0 : if (buckets) fch_buckets_destroy(buckets);
291 [ # # ]: 0 : if (sorted_indexes) free (sorted_indexes);
292 [ # # ]: 0 : if (iterations == 0) return NULL;
293 : 0 : mphf = (cmph_t *)malloc(sizeof(cmph_t));
294 : 0 : mphf->algo = mph->algo;
295 : 0 : fchf = (fch_data_t *)malloc(sizeof(fch_data_t));
296 : 0 : fchf->g = fch->g;
297 : 0 : fch->g = NULL; //transfer memory ownership
298 : 0 : fchf->h1 = fch->h1;
299 : 0 : fch->h1 = NULL; //transfer memory ownership
300 : 0 : fchf->h2 = fch->h2;
301 : 0 : fch->h2 = NULL; //transfer memory ownership
302 : 0 : fchf->p2 = fch->p2;
303 : 0 : fchf->p1 = fch->p1;
304 : 0 : fchf->b = fch->b;
305 : 0 : fchf->c = fch->c;
306 : 0 : fchf->m = fch->m;
307 : 0 : mphf->data = fchf;
308 : 0 : mphf->size = fch->m;
309 : : //DEBUGP("Successfully generated minimal perfect hash\n");
310 [ # # ]: 0 : if (mph->verbosity)
311 : : {
312 : 0 : fprintf(stderr, "Successfully generated minimal perfect hash function\n");
313 : : }
314 : 0 : return mphf;
315 : : }
316 : :
317 : 0 : int fch_dump(cmph_t *mphf, FILE *fd)
318 : : {
319 : 0 : char *buf = NULL;
320 : : cmph_uint32 buflen;
321 : : register size_t nbytes;
322 : :
323 : 0 : fch_data_t *data = (fch_data_t *)mphf->data;
324 : :
325 : : #ifdef DEBUG
326 : : cmph_uint32 i;
327 : : #endif
328 : 0 : __cmph_dump(mphf, fd);
329 : :
330 : 0 : hash_state_dump(data->h1, &buf, &buflen);
331 : : //DEBUGP("Dumping hash state with %u bytes to disk\n", buflen);
332 : 0 : nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
333 : 0 : nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
334 : 0 : free(buf);
335 : :
336 : 0 : hash_state_dump(data->h2, &buf, &buflen);
337 : : //DEBUGP("Dumping hash state with %u bytes to disk\n", buflen);
338 : 0 : nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
339 : 0 : nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
340 : 0 : free(buf);
341 : :
342 : 0 : nbytes = fwrite(&(data->m), sizeof(cmph_uint32), (size_t)1, fd);
343 : 0 : nbytes = fwrite(&(data->c), sizeof(double), (size_t)1, fd);
344 : 0 : nbytes = fwrite(&(data->b), sizeof(cmph_uint32), (size_t)1, fd);
345 : 0 : nbytes = fwrite(&(data->p1), sizeof(double), (size_t)1, fd);
346 : 0 : nbytes = fwrite(&(data->p2), sizeof(double), (size_t)1, fd);
347 : 0 : nbytes = fwrite(data->g, sizeof(cmph_uint32)*(data->b), (size_t)1, fd);
348 [ # # # # ]: 0 : if (nbytes == 0 && ferror(fd)) {
349 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
350 : 0 : return 0;
351 : : }
352 : : #ifdef DEBUG
353 : : fprintf(stderr, "G: ");
354 : : for (i = 0; i < data->b; ++i) fprintf(stderr, "%u ", data->g[i]);
355 : : fprintf(stderr, "\n");
356 : : #endif
357 : 0 : return 1;
358 : : }
359 : :
360 : 0 : void fch_load(FILE *f, cmph_t *mphf)
361 : : {
362 : 0 : char *buf = NULL;
363 : : cmph_uint32 buflen;
364 : : register size_t nbytes;
365 : 0 : fch_data_t *fch = (fch_data_t *)malloc(sizeof(fch_data_t));
366 : : #ifdef DEBUG
367 : : cmph_uint32 i;
368 : : #endif
369 : :
370 : : //DEBUGP("Loading fch mphf\n");
371 : 0 : mphf->data = fch;
372 : : //DEBUGP("Reading h1\n");
373 : 0 : fch->h1 = NULL;
374 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, f);
375 : : //DEBUGP("Hash state of h1 has %u bytes\n", buflen);
376 : 0 : buf = (char *)malloc((size_t)buflen);
377 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, f);
378 : 0 : fch->h1 = hash_state_load(buf, buflen);
379 : 0 : free(buf);
380 : :
381 : : //DEBUGP("Loading fch mphf\n");
382 : 0 : mphf->data = fch;
383 : : //DEBUGP("Reading h2\n");
384 : 0 : fch->h2 = NULL;
385 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, f);
386 : : //DEBUGP("Hash state of h2 has %u bytes\n", buflen);
387 : 0 : buf = (char *)malloc((size_t)buflen);
388 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, f);
389 : 0 : fch->h2 = hash_state_load(buf, buflen);
390 : 0 : free(buf);
391 : :
392 : :
393 : : //DEBUGP("Reading m and n\n");
394 : 0 : nbytes = fread(&(fch->m), sizeof(cmph_uint32), (size_t)1, f);
395 : 0 : nbytes = fread(&(fch->c), sizeof(double), (size_t)1, f);
396 : 0 : nbytes = fread(&(fch->b), sizeof(cmph_uint32), (size_t)1, f);
397 : 0 : nbytes = fread(&(fch->p1), sizeof(double), (size_t)1, f);
398 : 0 : nbytes = fread(&(fch->p2), sizeof(double), (size_t)1, f);
399 : :
400 : 0 : fch->g = (cmph_uint32 *)malloc(sizeof(cmph_uint32)*fch->b);
401 : 0 : nbytes = fread(fch->g, fch->b*sizeof(cmph_uint32), (size_t)1, f);
402 [ # # # # ]: 0 : if (nbytes == 0 && ferror(f)) {
403 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
404 : 0 : return;
405 : : }
406 : :
407 : : #ifdef DEBUG
408 : : fprintf(stderr, "G: ");
409 : : for (i = 0; i < fch->b; ++i) fprintf(stderr, "%u ", fch->g[i]);
410 : : fprintf(stderr, "\n");
411 : : #endif
412 : 0 : return;
413 : : }
414 : :
415 : 0 : cmph_uint32 fch_search(cmph_t *mphf, const char *key, cmph_uint32 keylen)
416 : : {
417 : 0 : fch_data_t *fch = mphf->data;
418 : 0 : cmph_uint32 h1 = hash(fch->h1, key, keylen) % fch->m;
419 : 0 : cmph_uint32 h2 = hash(fch->h2, key, keylen) % fch->m;
420 : 0 : h1 = mixh10h11h12 (fch->b, fch->p1, fch->p2, h1);
421 : : //DEBUGP("key: %s h1: %u h2: %u g[h1]: %u\n", key, h1, h2, fch->g[h1]);
422 : 0 : return (h2 + fch->g[h1]) % fch->m;
423 : : }
424 : 0 : void fch_destroy(cmph_t *mphf)
425 : : {
426 : 0 : fch_data_t *data = (fch_data_t *)mphf->data;
427 : 0 : free(data->g);
428 : 0 : hash_state_destroy(data->h1);
429 : 0 : hash_state_destroy(data->h2);
430 : 0 : free(data);
431 : 0 : free(mphf);
432 : 0 : }
433 : :
434 : : /** \fn void fch_pack(cmph_t *mphf, void *packed_mphf);
435 : : * \brief Support the ability to pack a perfect hash function into a preallocated contiguous memory space pointed by packed_mphf.
436 : : * \param mphf pointer to the resulting mphf
437 : : * \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()
438 : : */
439 : 0 : void fch_pack(cmph_t *mphf, void *packed_mphf)
440 : : {
441 : 0 : fch_data_t *data = (fch_data_t *)mphf->data;
442 : 0 : cmph_uint8 * ptr = packed_mphf;
443 : :
444 : : // packing h1 type
445 : 0 : CMPH_HASH h1_type = hash_get_type(data->h1);
446 : : CMPH_HASH h2_type;
447 : 0 : *((cmph_uint32 *) ptr) = h1_type;
448 : 0 : ptr += sizeof(cmph_uint32);
449 : :
450 : : // packing h1
451 : 0 : hash_state_pack(data->h1, ptr);
452 : 0 : ptr += hash_state_packed_size(h1_type);
453 : :
454 : : // packing h2 type
455 : 0 : h2_type = hash_get_type(data->h2);
456 : 0 : *((cmph_uint32 *) ptr) = h2_type;
457 : 0 : ptr += sizeof(cmph_uint32);
458 : :
459 : : // packing h2
460 : 0 : hash_state_pack(data->h2, ptr);
461 : 0 : ptr += hash_state_packed_size(h2_type);
462 : :
463 : : // packing m
464 : 0 : *((cmph_uint32 *) ptr) = data->m;
465 : 0 : ptr += sizeof(data->m);
466 : :
467 : : // packing b
468 : 0 : *((cmph_uint32 *) ptr) = data->b;
469 : 0 : ptr += sizeof(data->b);
470 : :
471 : : // packing p1
472 : 0 : *((cmph_uint64 *)ptr) = (cmph_uint64)data->p1;
473 : 0 : ptr += sizeof(data->p1);
474 : :
475 : : // packing p2
476 : 0 : *((cmph_uint64 *)ptr) = (cmph_uint64)data->p2;
477 : 0 : ptr += sizeof(data->p2);
478 : :
479 : : // packing g
480 : 0 : memcpy(ptr, data->g, sizeof(cmph_uint32)*(data->b));
481 : 0 : }
482 : :
483 : : /** \fn cmph_uint32 fch_packed_size(cmph_t *mphf);
484 : : * \brief Return the amount of space needed to pack mphf.
485 : : * \param mphf pointer to a mphf
486 : : * \return the size of the packed function or zero for failures
487 : : */
488 : 0 : cmph_uint32 fch_packed_size(cmph_t *mphf)
489 : : {
490 : 0 : fch_data_t *data = (fch_data_t *)mphf->data;
491 : 0 : CMPH_HASH h1_type = hash_get_type(data->h1);
492 : 0 : CMPH_HASH h2_type = hash_get_type(data->h2);
493 : :
494 : 0 : return (cmph_uint32)(sizeof(CMPH_ALGO) + hash_state_packed_size(h1_type) + hash_state_packed_size(h2_type) +
495 : 0 : 4*sizeof(cmph_uint32) + 2*sizeof(double) + sizeof(cmph_uint32)*(data->b));
496 : : }
497 : :
498 : :
499 : : /** cmph_uint32 fch_search(void *packed_mphf, const char *key, cmph_uint32 keylen);
500 : : * \brief Use the packed mphf to do a search.
501 : : * \param packed_mphf pointer to the packed mphf
502 : : * \param key key to be hashed
503 : : * \param keylen key length in bytes
504 : : * \return The mphf value
505 : : */
506 : 0 : cmph_uint32 fch_search_packed(void *packed_mphf, const char *key, cmph_uint32 keylen)
507 : : {
508 : 0 : register cmph_uint8 *h1_ptr = packed_mphf;
509 : 0 : register CMPH_HASH h1_type = *((cmph_uint32 *)h1_ptr);
510 : : register cmph_uint8 *h2_ptr;
511 : : register CMPH_HASH h2_type;
512 : : register cmph_uint32 *g_ptr;
513 : : register cmph_uint32 m, b, h1, h2;
514 : : register double p1, p2;
515 : :
516 : 0 : h1_ptr += 4;
517 : :
518 : 0 : h2_ptr = h1_ptr + hash_state_packed_size(h1_type);
519 : 0 : h2_type = *((cmph_uint32 *)h2_ptr);
520 : 0 : h2_ptr += 4;
521 : :
522 : 0 : g_ptr = (cmph_uint32 *)(h2_ptr + hash_state_packed_size(h2_type));
523 : :
524 : 0 : m = *g_ptr++;
525 : :
526 : 0 : b = *g_ptr++;
527 : :
528 : 0 : p1 = (double)(*((cmph_uint64 *)g_ptr));
529 : 0 : g_ptr += 2;
530 : :
531 : 0 : p2 = (double)(*((cmph_uint64 *)g_ptr));
532 : 0 : g_ptr += 2;
533 : :
534 : 0 : h1 = hash_packed(h1_ptr, h1_type, key, keylen) % m;
535 : 0 : h2 = hash_packed(h2_ptr, h2_type, key, keylen) % m;
536 : 0 : h1 = mixh10h11h12 (b, p1, p2, h1);
537 : 0 : return (h2 + g_ptr[h1]) % m;
538 : : }
539 : :
|
