Branch data Line data Source code
1 : : #include<stdio.h>
2 : : #include<stdlib.h>
3 : : #include<string.h>
4 : : #include<math.h>
5 : : #include<time.h>
6 : : #include<assert.h>
7 : : #include<limits.h>
8 : : #include<errno.h>
9 : :
10 : : #include "cmph_structs.h"
11 : : #include "chd_structs_ph.h"
12 : : #include "chd_ph.h"
13 : : #include"miller_rabin.h"
14 : : #include"bitbool.h"
15 : :
16 : :
17 : : //#define DEBUG
18 : : #include "debug.h"
19 : :
20 : : // NO_ELEMENT is equivalent to null pointer
21 : : #ifndef NO_ELEMENT
22 : : #define NO_ELEMENT UINT_MAX
23 : : #endif
24 : :
25 : : // struct used to represent items at mapping, ordering and searching phases
26 : : struct _chd_ph_item_t
27 : : {
28 : : cmph_uint32 f;
29 : : cmph_uint32 h;
30 : : };
31 : : typedef struct _chd_ph_item_t chd_ph_item_t;
32 : :
33 : : // struct to represent the items at mapping phase only.
34 : : struct _chd_ph_map_item_t
35 : : {
36 : : cmph_uint32 f;
37 : : cmph_uint32 h;
38 : : cmph_uint32 bucket_num;
39 : : };
40 : : typedef struct _chd_ph_map_item_t chd_ph_map_item_t;
41 : :
42 : : // struct to represent a bucket
43 : : struct _chd_ph_bucket_t
44 : : {
45 : : cmph_uint32 items_list; // offset
46 : : union
47 : : {
48 : : cmph_uint32 size;
49 : : cmph_uint32 bucket_id;
50 : : };
51 : : };
52 : :
53 : : typedef struct _chd_ph_bucket_t chd_ph_bucket_t;
54 : :
55 : : struct _chd_ph_sorted_list_t
56 : : {
57 : : cmph_uint32 buckets_list;
58 : : cmph_uint32 size;
59 : : };
60 : :
61 : : typedef struct _chd_ph_sorted_list_t chd_ph_sorted_list_t;
62 : :
63 : :
64 : : static inline chd_ph_bucket_t * chd_ph_bucket_new(cmph_uint32 nbuckets);
65 : : static inline void chd_ph_bucket_clean(chd_ph_bucket_t * buckets, cmph_uint32 nbuckets);
66 : : static inline void chd_ph_bucket_destroy(chd_ph_bucket_t * buckets);
67 : :
68 : 0 : chd_ph_bucket_t * chd_ph_bucket_new(cmph_uint32 nbuckets)
69 : : {
70 : 0 : chd_ph_bucket_t * buckets = (chd_ph_bucket_t *) calloc(nbuckets, sizeof(chd_ph_bucket_t));
71 : 0 : return buckets;
72 : : }
73 : :
74 : 0 : void chd_ph_bucket_clean(chd_ph_bucket_t * buckets, cmph_uint32 nbuckets)
75 : : {
76 : 0 : register cmph_uint32 i = 0;
77 : 0 : assert(buckets);
78 : 0 : for(i = 0; i < nbuckets; i++)
79 : 0 : buckets[i].size = 0;
80 : 0 : }
81 : 0 : static cmph_uint8 chd_ph_bucket_insert(chd_ph_bucket_t * buckets,chd_ph_map_item_t * map_items, chd_ph_item_t * items,
82 : : cmph_uint32 nbuckets,cmph_uint32 item_idx)
83 : : {
84 : 0 : register cmph_uint32 i = 0;
85 : : register chd_ph_item_t * tmp_item;
86 : 0 : register chd_ph_map_item_t * tmp_map_item = map_items + item_idx;
87 : 0 : register chd_ph_bucket_t * bucket = buckets + tmp_map_item->bucket_num;
88 : 0 : tmp_item = items + bucket->items_list;
89 : :
90 : 0 : for(i = 0; i < bucket->size; i++)
91 : : {
92 : 0 : if(tmp_item->f == tmp_map_item->f && tmp_item->h == tmp_map_item->h)
93 : : {
94 : : DEBUGP("Item not added\n");
95 : 0 : return 0;
96 : : };
97 : 0 : tmp_item++;
98 : : };
99 : 0 : tmp_item->f = tmp_map_item->f;
100 : 0 : tmp_item->h = tmp_map_item->h;
101 : 0 : bucket->size++;
102 : 0 : return 1;
103 : : };
104 : 0 : void chd_ph_bucket_destroy(chd_ph_bucket_t * buckets)
105 : : {
106 : 0 : free(buckets);
107 : 0 : }
108 : :
109 : : static inline cmph_uint8 chd_ph_mapping(cmph_config_t *mph, chd_ph_bucket_t * buckets, chd_ph_item_t * items,
110 : : cmph_uint32 *max_bucket_size);
111 : :
112 : : static chd_ph_sorted_list_t * chd_ph_ordering(chd_ph_bucket_t ** _buckets,chd_ph_item_t ** items,
113 : : cmph_uint32 nbuckets,cmph_uint32 nitems, cmph_uint32 max_bucket_size);
114 : :
115 : : static cmph_uint8 chd_ph_searching(chd_ph_config_data_t *chd_ph, chd_ph_bucket_t *buckets, chd_ph_item_t *items ,
116 : : cmph_uint32 max_bucket_size, chd_ph_sorted_list_t *sorted_lists, cmph_uint32 max_probes, cmph_uint32 * disp_table);
117 : :
118 : 0 : static inline double chd_ph_space_lower_bound(cmph_uint32 _n, cmph_uint32 _r)
119 : : {
120 : 0 : double r = _r, n = _n;
121 : 0 : return (1 + (r/n - 1.0 + 1.0/(2.0*n))*log(1 - n/r))/log(2);
122 : : };
123 : :
124 : : /* computes the entropy of non empty buckets.*/
125 : : static inline double chd_ph_get_entropy(cmph_uint32 * disp_table, cmph_uint32 n, cmph_uint32 max_probes)
126 : : {
127 : : register cmph_uint32 * probe_counts = (cmph_uint32 *) calloc(max_probes, sizeof(cmph_uint32));
128 : : register cmph_uint32 i;
129 : : register double entropy = 0;
130 : :
131 : : for(i = 0; i < n; i++)
132 : : {
133 : : probe_counts[disp_table[i]]++;
134 : : };
135 : :
136 : : for(i = 0; i < max_probes; i++)
137 : : {
138 : : if(probe_counts[i] > 0)
139 : : entropy -= probe_counts[i]*log((double)probe_counts[i]/(double)n)/log(2);
140 : : };
141 : : free(probe_counts);
142 : : return entropy;
143 : : };
144 : :
145 : 0 : chd_ph_config_data_t *chd_ph_config_new(void)
146 : : {
147 : : chd_ph_config_data_t *chd_ph;
148 : 0 : chd_ph = (chd_ph_config_data_t *)malloc(sizeof(chd_ph_config_data_t));
149 : 0 : assert(chd_ph);
150 : 0 : memset(chd_ph, 0, sizeof(chd_ph_config_data_t));
151 : :
152 : 0 : chd_ph->hashfunc = CMPH_HASH_JENKINS;
153 : 0 : chd_ph->cs = NULL;
154 : 0 : chd_ph->nbuckets = 0;
155 : 0 : chd_ph->n = 0;
156 : 0 : chd_ph->hl = NULL;
157 : :
158 : 0 : chd_ph->m = 0;
159 : 0 : chd_ph->use_h = 1;
160 : 0 : chd_ph->keys_per_bin = 1;
161 : 0 : chd_ph->keys_per_bucket = 4;
162 : 0 : chd_ph->occup_table = 0;
163 : :
164 : 0 : return chd_ph;
165 : : }
166 : :
167 : 0 : void chd_ph_config_destroy(cmph_config_t *mph)
168 : : {
169 : 0 : chd_ph_config_data_t *data = (chd_ph_config_data_t *) mph->data;
170 : : DEBUGP("Destroying algorithm dependent data\n");
171 : 0 : if(data->occup_table)
172 : : {
173 : 0 : free(data->occup_table);
174 : 0 : data->occup_table = NULL;
175 : : }
176 : 0 : free(data);
177 : 0 : }
178 : :
179 : :
180 : 0 : void chd_ph_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs)
181 : : {
182 : 0 : chd_ph_config_data_t *chd_ph = (chd_ph_config_data_t *)mph->data;
183 : 0 : CMPH_HASH *hashptr = hashfuncs;
184 : 0 : cmph_uint32 i = 0;
185 : 0 : while(*hashptr != CMPH_HASH_COUNT)
186 : : {
187 : 0 : if (i >= 1) break; //chd_ph only uses one linear hash function
188 : 0 : chd_ph->hashfunc = *hashptr;
189 : 0 : ++i, ++hashptr;
190 : : }
191 : 0 : }
192 : :
193 : :
194 : 0 : void chd_ph_config_set_b(cmph_config_t *mph, cmph_uint32 keys_per_bucket)
195 : : {
196 : : chd_ph_config_data_t *chd_ph;
197 : 0 : assert(mph);
198 : 0 : chd_ph = (chd_ph_config_data_t *)mph->data;
199 : 0 : if(keys_per_bucket < 1 || keys_per_bucket >= 15)
200 : : {
201 : 0 : keys_per_bucket = 4;
202 : : }
203 : 0 : chd_ph->keys_per_bucket = keys_per_bucket;
204 : 0 : }
205 : :
206 : :
207 : 0 : void chd_ph_config_set_keys_per_bin(cmph_config_t *mph, cmph_uint32 keys_per_bin)
208 : : {
209 : : chd_ph_config_data_t *chd_ph;
210 : 0 : assert(mph);
211 : 0 : chd_ph = (chd_ph_config_data_t *)mph->data;
212 : 0 : if(keys_per_bin <= 1 || keys_per_bin >= 128)
213 : : {
214 : 0 : keys_per_bin = 1;
215 : : }
216 : 0 : chd_ph->keys_per_bin = keys_per_bin;
217 : 0 : }
218 : :
219 : 0 : cmph_uint8 chd_ph_mapping(cmph_config_t *mph, chd_ph_bucket_t * buckets, chd_ph_item_t * items, cmph_uint32 *max_bucket_size)
220 : : {
221 : 0 : register cmph_uint32 i = 0, g = 0;
222 : : cmph_uint32 hl[3];
223 : 0 : chd_ph_config_data_t *chd_ph = (chd_ph_config_data_t *)mph->data;
224 : 0 : char * key = NULL;
225 : 0 : cmph_uint32 keylen = 0;
226 : : chd_ph_map_item_t * map_item;
227 : 0 : chd_ph_map_item_t * map_items = malloc(chd_ph->m*sizeof(chd_ph_map_item_t));
228 : 0 : register cmph_uint32 mapping_iterations = 1000;
229 : 0 : *max_bucket_size = 0;
230 : : while(1)
231 : : {
232 : 0 : mapping_iterations--;
233 : 0 : if (chd_ph->hl) hash_state_destroy(chd_ph->hl);
234 : 0 : chd_ph->hl = hash_state_new(chd_ph->hashfunc, chd_ph->m);
235 : :
236 : 0 : chd_ph_bucket_clean(buckets, chd_ph->nbuckets);
237 : :
238 : 0 : mph->key_source->rewind(mph->key_source->data);
239 : :
240 : 0 : for(i = 0; i < chd_ph->m; i++)
241 : : {
242 : 0 : mph->key_source->read(mph->key_source->data, &key, &keylen);
243 : 0 : hash_vector(chd_ph->hl, key, keylen, hl);
244 : :
245 : 0 : map_item = (map_items + i);
246 : :
247 : 0 : g = hl[0] % chd_ph->nbuckets;
248 : 0 : map_item->f = hl[1] % chd_ph->n;
249 : 0 : map_item->h = hl[2] % (chd_ph->n - 1) + 1;
250 : 0 : map_item->bucket_num=g;
251 : 0 : mph->key_source->dispose(mph->key_source->data, key, keylen);
252 : : // if(buckets[g].size == (chd_ph->keys_per_bucket << 2))
253 : : // {
254 : : // DEBUGP("BUCKET = %u -- SIZE = %u -- MAXIMUM SIZE = %u\n", g, buckets[g].size, (chd_ph->keys_per_bucket << 2));
255 : : // goto error;
256 : : // }
257 : 0 : buckets[g].size++;
258 : 0 : if(buckets[g].size > *max_bucket_size)
259 : : {
260 : 0 : *max_bucket_size = buckets[g].size;
261 : : }
262 : : }
263 : 0 : buckets[0].items_list = 0;
264 : 0 : for(i = 1; i < chd_ph->nbuckets; i++)
265 : : {
266 : 0 : buckets[i].items_list = buckets[i-1].items_list + buckets[i - 1].size;
267 : 0 : buckets[i - 1].size = 0;
268 : : };
269 : 0 : buckets[i - 1].size = 0;
270 : 0 : for(i = 0; i < chd_ph->m; i++)
271 : : {
272 : 0 : map_item = (map_items + i);
273 : 0 : if(!chd_ph_bucket_insert(buckets, map_items, items, chd_ph->nbuckets, i))
274 : 0 : break;
275 : : }
276 : 0 : if(i == chd_ph->m)
277 : : {
278 : 0 : free(map_items);
279 : 0 : return 1; // SUCCESS
280 : : }
281 : :
282 : 0 : if(mapping_iterations == 0)
283 : : {
284 : 0 : goto error;
285 : : }
286 : : }
287 : 0 : error:
288 : 0 : free(map_items);
289 : 0 : hash_state_destroy(chd_ph->hl);
290 : 0 : chd_ph->hl = NULL;
291 : 0 : return 0; // FAILURE
292 : : }
293 : :
294 : 0 : chd_ph_sorted_list_t * chd_ph_ordering(chd_ph_bucket_t ** _buckets, chd_ph_item_t ** _items,
295 : : cmph_uint32 nbuckets, cmph_uint32 nitems, cmph_uint32 max_bucket_size)
296 : : {
297 : 0 : chd_ph_sorted_list_t * sorted_lists = (chd_ph_sorted_list_t *) calloc(max_bucket_size + 1, sizeof(chd_ph_sorted_list_t));
298 : :
299 : 0 : chd_ph_bucket_t * input_buckets = (*_buckets);
300 : : chd_ph_bucket_t * output_buckets;
301 : 0 : chd_ph_item_t * input_items = (*_items);
302 : : chd_ph_item_t * output_items;
303 : : register cmph_uint32 i, j, bucket_size, position, position2;
304 : : // cmph_uint32 non_empty_buckets;
305 : : DEBUGP("MAX BUCKET SIZE = %u\n", max_bucket_size);
306 : : // Determine size of each list of buckets
307 : 0 : for(i = 0; i < nbuckets; i++)
308 : : {
309 : 0 : bucket_size = input_buckets[i].size;
310 : 0 : if(bucket_size == 0)
311 : 0 : continue;
312 : 0 : sorted_lists[bucket_size].size++;
313 : : };
314 : 0 : sorted_lists[1].buckets_list = 0;
315 : : // Determine final position of list of buckets into the contiguous array that will store all the buckets
316 : 0 : for(i = 2; i <= max_bucket_size; i++)
317 : : {
318 : 0 : sorted_lists[i].buckets_list = sorted_lists[i-1].buckets_list + sorted_lists[i-1].size;
319 : 0 : sorted_lists[i-1].size = 0;
320 : : };
321 : 0 : sorted_lists[i-1].size = 0;
322 : : // Store the buckets in a new array which is sorted by bucket sizes
323 : 0 : output_buckets = calloc(nbuckets, sizeof(chd_ph_bucket_t)); // everything is initialized with zero
324 : : // non_empty_buckets = nbuckets;
325 : :
326 : 0 : for(i = 0; i < nbuckets; i++)
327 : : {
328 : 0 : bucket_size = input_buckets[i].size;
329 : 0 : if(bucket_size == 0)
330 : : {
331 : : // non_empty_buckets--;
332 : 0 : continue;
333 : : };
334 : 0 : position = sorted_lists[bucket_size].buckets_list + sorted_lists[bucket_size].size;
335 : 0 : output_buckets[position].bucket_id = i;
336 : 0 : output_buckets[position].items_list = input_buckets[i].items_list;
337 : 0 : sorted_lists[bucket_size].size++;
338 : : };
339 : : /* for(i = non_empty_buckets; i < nbuckets; i++)
340 : : output_buckets[i].size=0;*/
341 : : // Return the buckets sorted in new order and free the old buckets sorted in old order
342 : 0 : free(input_buckets);
343 : 0 : (*_buckets) = output_buckets;
344 : :
345 : :
346 : : // Store the items according to the new order of buckets.
347 : 0 : output_items = (chd_ph_item_t*)calloc(nitems, sizeof(chd_ph_item_t));
348 : 0 : position = 0;
349 : 0 : i = 0;
350 : 0 : for(bucket_size = 1; bucket_size <= max_bucket_size; bucket_size++)
351 : : {
352 : 0 : for(i = sorted_lists[bucket_size].buckets_list; i < sorted_lists[bucket_size].size + sorted_lists[bucket_size].buckets_list; i++)
353 : : {
354 : 0 : position2 = output_buckets[i].items_list;
355 : 0 : output_buckets[i].items_list = position;
356 : 0 : for(j = 0; j < bucket_size; j++)
357 : : {
358 : 0 : output_items[position].f = input_items[position2].f;
359 : 0 : output_items[position].h = input_items[position2].h;
360 : 0 : position++;
361 : 0 : position2++;
362 : : };
363 : : };
364 : : };
365 : : //Return the items sorted in new order and free the old items sorted in old order
366 : 0 : free(input_items);
367 : 0 : (*_items) = output_items;
368 : 0 : return sorted_lists;
369 : : };
370 : :
371 : 0 : static inline cmph_uint8 place_bucket_probe(chd_ph_config_data_t *chd_ph, chd_ph_bucket_t *buckets,
372 : : chd_ph_item_t *items, cmph_uint32 probe0_num, cmph_uint32 probe1_num,
373 : : cmph_uint32 bucket_num, cmph_uint32 size)
374 : : {
375 : : register cmph_uint32 i;
376 : : register chd_ph_item_t * item;
377 : : register cmph_uint32 position;
378 : :
379 : 0 : item = items + buckets[bucket_num].items_list;
380 : : // try place bucket with probe_num
381 : 0 : if(chd_ph->keys_per_bin > 1)
382 : : {
383 : 0 : for(i = 0; i < size; i++) // placement
384 : : {
385 : 0 : position = (cmph_uint32)((item->f + ((cmph_uint64)item->h)*probe0_num + probe1_num) % chd_ph->n);
386 : 0 : if(chd_ph->occup_table[position] >= chd_ph->keys_per_bin)
387 : : {
388 : 0 : break;
389 : : }
390 : 0 : (chd_ph->occup_table[position])++;
391 : 0 : item++;
392 : : };
393 : : } else
394 : : {
395 : 0 : for(i = 0; i < size; i++) // placement
396 : : {
397 : 0 : position = (cmph_uint32)((item->f + ((cmph_uint64)item->h)*probe0_num + probe1_num) % chd_ph->n);
398 : 0 : if(GETBIT32(((cmph_uint32 *)chd_ph->occup_table), position))
399 : : {
400 : 0 : break;
401 : : }
402 : 0 : SETBIT32(((cmph_uint32*)chd_ph->occup_table), position);
403 : 0 : item++;
404 : : };
405 : : };
406 : 0 : if(i != size) // Undo the placement
407 : : {
408 : 0 : item = items + buckets[bucket_num].items_list;
409 : 0 : if(chd_ph->keys_per_bin > 1)
410 : : {
411 : : while(1)
412 : : {
413 : 0 : if(i == 0)
414 : : {
415 : 0 : break;
416 : : }
417 : 0 : position = (cmph_uint32)((item->f + ((cmph_uint64 )item->h) * probe0_num + probe1_num) % chd_ph->n);
418 : 0 : (chd_ph->occup_table[position])--;
419 : 0 : item++;
420 : 0 : i--;
421 : : };
422 : : } else
423 : : {
424 : : while(1)
425 : : {
426 : 0 : if(i == 0)
427 : : {
428 : 0 : break;
429 : : }
430 : 0 : position = (cmph_uint32)((item->f + ((cmph_uint64 )item->h) * probe0_num + probe1_num) % chd_ph->n);
431 : 0 : UNSETBIT32(((cmph_uint32*)chd_ph->occup_table), position);
432 : :
433 : : // ([position/32]^=(1<<(position%32));
434 : 0 : item++;
435 : 0 : i--;
436 : : };
437 : : };
438 : 0 : return 0;
439 : : }
440 : 0 : return 1;
441 : : };
442 : :
443 : 0 : static inline cmph_uint8 place_bucket(chd_ph_config_data_t *chd_ph, chd_ph_bucket_t *buckets, chd_ph_item_t * items, cmph_uint32 max_probes,
444 : : cmph_uint32 * disp_table, cmph_uint32 bucket_num, cmph_uint32 size)
445 : :
446 : : {
447 : : register cmph_uint32 probe0_num, probe1_num, probe_num;
448 : 0 : probe0_num = 0;
449 : 0 : probe1_num = 0;
450 : 0 : probe_num = 0;
451 : :
452 : : while(1)
453 : : {
454 : 0 : if(place_bucket_probe(chd_ph, buckets, items, probe0_num, probe1_num, bucket_num,size))
455 : : {
456 : 0 : disp_table[buckets[bucket_num].bucket_id] = probe0_num + probe1_num * chd_ph->n;
457 : 0 : return 1;
458 : : }
459 : 0 : probe0_num++;
460 : 0 : if(probe0_num >= chd_ph->n)
461 : : {
462 : 0 : probe0_num -= chd_ph->n;
463 : 0 : probe1_num++;
464 : : };
465 : 0 : probe_num++;
466 : 0 : if(probe_num >= max_probes || probe1_num >= chd_ph->n)
467 : : {
468 : 0 : return 0;
469 : : };
470 : : };
471 : : return 0;
472 : : };
473 : :
474 : 0 : static inline cmph_uint8 place_buckets1(chd_ph_config_data_t *chd_ph, chd_ph_bucket_t * buckets, chd_ph_item_t *items,
475 : : cmph_uint32 max_bucket_size, chd_ph_sorted_list_t *sorted_lists, cmph_uint32 max_probes,
476 : : cmph_uint32 * disp_table)
477 : : {
478 : 0 : register cmph_uint32 i = 0;
479 : 0 : register cmph_uint32 curr_bucket = 0;
480 : :
481 : 0 : for(i = max_bucket_size; i > 0; i--)
482 : : {
483 : 0 : curr_bucket = sorted_lists[i].buckets_list;
484 : 0 : while(curr_bucket < sorted_lists[i].size + sorted_lists[i].buckets_list)
485 : : {
486 : 0 : if(!place_bucket(chd_ph, buckets, items, max_probes, disp_table, curr_bucket, i))
487 : : {
488 : 0 : return 0;
489 : : }
490 : 0 : curr_bucket++;
491 : : };
492 : : };
493 : 0 : return 1;
494 : : };
495 : :
496 : 0 : static inline cmph_uint8 place_buckets2(chd_ph_config_data_t *chd_ph, chd_ph_bucket_t *buckets, chd_ph_item_t * items,
497 : : cmph_uint32 max_bucket_size, chd_ph_sorted_list_t *sorted_lists, cmph_uint32 max_probes,
498 : : cmph_uint32 * disp_table)
499 : : {
500 : : register cmph_uint32 i,j, non_placed_bucket;
501 : : register cmph_uint32 curr_bucket;
502 : : register cmph_uint32 probe_num, probe0_num, probe1_num;
503 : : cmph_uint32 sorted_list_size;
504 : : #ifdef DEBUG
505 : : cmph_uint32 items_list;
506 : : cmph_uint32 bucket_id;
507 : : #endif
508 : : DEBUGP("USING HEURISTIC TO PLACE BUCKETS\n");
509 : 0 : for(i = max_bucket_size; i > 0; i--)
510 : : {
511 : 0 : probe_num = 0;
512 : 0 : probe0_num = 0;
513 : 0 : probe1_num = 0;
514 : 0 : sorted_list_size = sorted_lists[i].size;
515 : 0 : while(sorted_lists[i].size != 0)
516 : : {
517 : 0 : curr_bucket = sorted_lists[i].buckets_list;
518 : 0 : for(j = 0, non_placed_bucket = 0; j < sorted_lists[i].size; j++)
519 : : {
520 : : // if bucket is successfully placed remove it from list
521 : 0 : if(place_bucket_probe(chd_ph, buckets, items, probe0_num, probe1_num, curr_bucket, i))
522 : : {
523 : 0 : disp_table[buckets[curr_bucket].bucket_id] = probe0_num + probe1_num * chd_ph->n;
524 : : // DEBUGP("BUCKET %u PLACED --- DISPLACEMENT = %u\n", curr_bucket, disp_table[curr_bucket]);
525 : : }
526 : : else
527 : : {
528 : : // DEBUGP("BUCKET %u NOT PLACED\n", curr_bucket);
529 : : #ifdef DEBUG
530 : : items_list = buckets[non_placed_bucket + sorted_lists[i].buckets_list].items_list;
531 : : bucket_id = buckets[non_placed_bucket + sorted_lists[i].buckets_list].bucket_id;
532 : : #endif
533 : 0 : buckets[non_placed_bucket + sorted_lists[i].buckets_list].items_list = buckets[curr_bucket].items_list;
534 : 0 : buckets[non_placed_bucket + sorted_lists[i].buckets_list].bucket_id = buckets[curr_bucket].bucket_id;
535 : : #ifdef DEBUG
536 : : buckets[curr_bucket].items_list=items_list;
537 : : buckets[curr_bucket].bucket_id=bucket_id;
538 : : #endif
539 : 0 : non_placed_bucket++;
540 : : }
541 : 0 : curr_bucket++;
542 : : };
543 : 0 : sorted_lists[i].size = non_placed_bucket;
544 : 0 : probe0_num++;
545 : 0 : if(probe0_num >= chd_ph->n)
546 : : {
547 : 0 : probe0_num -= chd_ph->n;
548 : 0 : probe1_num++;
549 : : };
550 : 0 : probe_num++;
551 : 0 : if(probe_num >= max_probes || probe1_num >= chd_ph->n)
552 : : {
553 : 0 : sorted_lists[i].size = sorted_list_size;
554 : 0 : return 0;
555 : : };
556 : : };
557 : 0 : sorted_lists[i].size = sorted_list_size;
558 : : };
559 : 0 : return 1;
560 : : };
561 : :
562 : 0 : cmph_uint8 chd_ph_searching(chd_ph_config_data_t *chd_ph, chd_ph_bucket_t *buckets, chd_ph_item_t *items ,
563 : : cmph_uint32 max_bucket_size, chd_ph_sorted_list_t *sorted_lists, cmph_uint32 max_probes,
564 : : cmph_uint32 * disp_table)
565 : : {
566 : 0 : if(chd_ph->use_h)
567 : : {
568 : 0 : return place_buckets2(chd_ph, buckets, items, max_bucket_size, sorted_lists, max_probes, disp_table);
569 : : }
570 : : else
571 : : {
572 : 0 : return place_buckets1(chd_ph, buckets, items, max_bucket_size, sorted_lists, max_probes, disp_table);
573 : : }
574 : :
575 : : }
576 : :
577 : : static inline cmph_uint8 chd_ph_check_bin_hashing(chd_ph_config_data_t *chd_ph, chd_ph_bucket_t *buckets, chd_ph_item_t *items,
578 : : cmph_uint32 * disp_table, chd_ph_sorted_list_t * sorted_lists,cmph_uint32 max_bucket_size)
579 : : {
580 : : register cmph_uint32 bucket_size, i, j;
581 : : register cmph_uint32 position, probe0_num, probe1_num;
582 : : G_GNUC_UNUSED register cmph_uint32 m = 0;
583 : : register chd_ph_item_t * item;
584 : : if(chd_ph->keys_per_bin > 1)
585 : : memset(chd_ph->occup_table, 0, chd_ph->n);
586 : : else
587 : : memset(chd_ph->occup_table, 0, ((chd_ph->n + 31)/32) * sizeof(cmph_uint32));
588 : :
589 : : for(bucket_size = 1; bucket_size <= max_bucket_size; bucket_size++)
590 : : for(i = sorted_lists[bucket_size].buckets_list; i < sorted_lists[bucket_size].size +
591 : : sorted_lists[bucket_size].buckets_list; i++)
592 : : {
593 : : j = bucket_size;
594 : : item = items + buckets[i].items_list;
595 : : probe0_num = disp_table[buckets[i].bucket_id] % chd_ph->n;
596 : : probe1_num = disp_table[buckets[i].bucket_id] / chd_ph->n;
597 : : for(; j > 0; j--)
598 : : {
599 : : #ifdef DEBUG
600 : : m++;
601 : : #endif
602 : : position = (cmph_uint32)((item->f + ((cmph_uint64 )item->h) * probe0_num + probe1_num) % chd_ph->n);
603 : : if(chd_ph->keys_per_bin > 1)
604 : : {
605 : : if(chd_ph->occup_table[position] >= chd_ph->keys_per_bin)
606 : : {
607 : : return 0;
608 : : }
609 : : (chd_ph->occup_table[position])++;
610 : : }
611 : : else
612 : : {
613 : : if(GETBIT32(((cmph_uint32*)chd_ph->occup_table), position))
614 : : {
615 : : return 0;
616 : : }
617 : : SETBIT32(((cmph_uint32*)chd_ph->occup_table), position);
618 : : };
619 : : item++;
620 : : };
621 : : };
622 : : DEBUGP("We were able to place m = %u keys\n", m);
623 : : return 1;
624 : : };
625 : :
626 : :
627 : 0 : cmph_t *chd_ph_new(cmph_config_t *mph, double c)
628 : : {
629 : 0 : cmph_t *mphf = NULL;
630 : 0 : chd_ph_data_t *chd_phf = NULL;
631 : 0 : chd_ph_config_data_t *chd_ph = (chd_ph_config_data_t *)mph->data;
632 : :
633 : 0 : register double load_factor = c;
634 : 0 : register cmph_uint8 searching_success = 0;
635 : 0 : register cmph_uint32 max_probes = 1 << 20; // default value for max_probes
636 : 0 : register cmph_uint32 iterations = 100;
637 : 0 : chd_ph_bucket_t * buckets = NULL;
638 : 0 : chd_ph_item_t * items = NULL;
639 : 0 : register cmph_uint8 failure = 0;
640 : 0 : cmph_uint32 max_bucket_size = 0;
641 : 0 : chd_ph_sorted_list_t * sorted_lists = NULL;
642 : 0 : cmph_uint32 * disp_table = NULL;
643 : 0 : register double space_lower_bound = 0;
644 : : #ifdef CMPH_TIMING
645 : : double construction_time_begin = 0.0;
646 : : double construction_time = 0.0;
647 : : ELAPSED_TIME_IN_SECONDS(&construction_time_begin);
648 : : #endif
649 : :
650 : :
651 : 0 : chd_ph->m = mph->key_source->nkeys;
652 : : DEBUGP("m = %u\n", chd_ph->m);
653 : :
654 : 0 : chd_ph->nbuckets = (cmph_uint32)(chd_ph->m/chd_ph->keys_per_bucket) + 1;
655 : : DEBUGP("nbuckets = %u\n", chd_ph->nbuckets);
656 : :
657 : 0 : if(load_factor < 0.5 )
658 : : {
659 : 0 : load_factor = 0.5;
660 : : }
661 : :
662 : 0 : if(load_factor >= 0.99)
663 : : {
664 : 0 : load_factor = 0.99;
665 : : }
666 : :
667 : : DEBUGP("load_factor = %.3f\n", load_factor);
668 : :
669 : 0 : chd_ph->n = (cmph_uint32)(chd_ph->m/(chd_ph->keys_per_bin * load_factor)) + 1;
670 : :
671 : : //Round the number of bins to the prime immediately above
672 : 0 : if(chd_ph->n % 2 == 0) chd_ph->n++;
673 : : for(;;)
674 : : {
675 : 0 : if(check_primality(chd_ph->n) == 1)
676 : 0 : break;
677 : 0 : chd_ph->n += 2; // just odd numbers can be primes for n > 2
678 : :
679 : : };
680 : :
681 : : DEBUGP("n = %u \n", chd_ph->n);
682 : 0 : if(chd_ph->keys_per_bin == 1)
683 : : {
684 : 0 : space_lower_bound = chd_ph_space_lower_bound(chd_ph->m, chd_ph->n);
685 : : }
686 : :
687 : 0 : if(mph->verbosity)
688 : : {
689 : 0 : fprintf(stderr, "space lower bound is %.3f bits per key\n", space_lower_bound);
690 : : }
691 : :
692 : : // We allocate the working tables
693 : 0 : buckets = chd_ph_bucket_new(chd_ph->nbuckets);
694 : 0 : items = (chd_ph_item_t *) calloc(chd_ph->m, sizeof(chd_ph_item_t));
695 : :
696 : 0 : max_probes = (cmph_uint32)(((log(chd_ph->m)/log(2))/20) * max_probes);
697 : :
698 : 0 : if(chd_ph->keys_per_bin == 1)
699 : 0 : chd_ph->occup_table = (cmph_uint8 *) calloc(((chd_ph->n + 31)/32), sizeof(cmph_uint32));
700 : : else
701 : 0 : chd_ph->occup_table = (cmph_uint8 *) calloc(chd_ph->n, sizeof(cmph_uint8));
702 : :
703 : 0 : disp_table = (cmph_uint32 *) calloc(chd_ph->nbuckets, sizeof(cmph_uint32));
704 : : //
705 : : // init_genrand(time(0));
706 : :
707 : : while(1)
708 : : {
709 : 0 : iterations --;
710 : 0 : if (mph->verbosity)
711 : : {
712 : 0 : fprintf(stderr, "Starting mapping step for mph creation of %u keys with %u bins\n", chd_ph->m, chd_ph->n);
713 : : }
714 : :
715 : 0 : if(!chd_ph_mapping(mph, buckets, items, &max_bucket_size))
716 : : {
717 : 0 : if (mph->verbosity)
718 : : {
719 : 0 : fprintf(stderr, "Failure in mapping step\n");
720 : : }
721 : 0 : failure = 1;
722 : 0 : goto cleanup;
723 : : }
724 : :
725 : 0 : if (mph->verbosity)
726 : : {
727 : 0 : fprintf(stderr, "Starting ordering step\n");
728 : : }
729 : 0 : if(sorted_lists)
730 : : {
731 : 0 : free(sorted_lists);
732 : : }
733 : :
734 : 0 : sorted_lists = chd_ph_ordering(&buckets, &items, chd_ph->nbuckets, chd_ph->m, max_bucket_size);
735 : :
736 : 0 : if (mph->verbosity)
737 : : {
738 : 0 : fprintf(stderr, "Starting searching step\n");
739 : : }
740 : :
741 : 0 : searching_success = chd_ph_searching(chd_ph, buckets, items, max_bucket_size, sorted_lists, max_probes, disp_table);
742 : 0 : if(searching_success) break;
743 : :
744 : : // reset occup_table
745 : 0 : if(chd_ph->keys_per_bin > 1)
746 : 0 : memset(chd_ph->occup_table, 0, chd_ph->n);
747 : : else
748 : 0 : memset(chd_ph->occup_table, 0, ((chd_ph->n + 31)/32) * sizeof(cmph_uint32));
749 : 0 : if(iterations == 0)
750 : : {
751 : : // Cleanup memory
752 : 0 : if (mph->verbosity)
753 : : {
754 : 0 : fprintf(stderr, "Failure because the max trials was exceeded\n");
755 : : }
756 : 0 : failure = 1;
757 : 0 : goto cleanup;
758 : : };
759 : : }
760 : :
761 : : #ifdef DEBUG
762 : : {
763 : : if(!chd_ph_check_bin_hashing(chd_ph, buckets, items, disp_table,sorted_lists,max_bucket_size))
764 : : {
765 : :
766 : : DEBUGP("Error for bin packing generation");
767 : : failure = 1;
768 : : goto cleanup;
769 : : }
770 : : }
771 : : #endif
772 : :
773 : 0 : if (mph->verbosity)
774 : : {
775 : 0 : fprintf(stderr, "Starting compressing step\n");
776 : : }
777 : :
778 : 0 : if(chd_ph->cs)
779 : : {
780 : 0 : free(chd_ph->cs);
781 : : }
782 : 0 : chd_ph->cs = (compressed_seq_t *) calloc(1, sizeof(compressed_seq_t));
783 : 0 : compressed_seq_init(chd_ph->cs);
784 : 0 : compressed_seq_generate(chd_ph->cs, disp_table, chd_ph->nbuckets);
785 : :
786 : : #ifdef CMPH_TIMING
787 : : ELAPSED_TIME_IN_SECONDS(&construction_time);
788 : : register double entropy = chd_ph_get_entropy(disp_table, chd_ph->nbuckets, max_probes);
789 : : DEBUGP("Entropy = %.4f\n", entropy/chd_ph->m);
790 : : #endif
791 : :
792 : 0 : cleanup:
793 : 0 : chd_ph_bucket_destroy(buckets);
794 : 0 : free(items);
795 : 0 : free(sorted_lists);
796 : 0 : free(disp_table);
797 : 0 : if(failure)
798 : : {
799 : 0 : if(chd_ph->hl)
800 : : {
801 : 0 : hash_state_destroy(chd_ph->hl);
802 : : }
803 : 0 : chd_ph->hl = NULL;
804 : 0 : return NULL;
805 : : }
806 : :
807 : 0 : mphf = (cmph_t *)malloc(sizeof(cmph_t));
808 : 0 : mphf->algo = mph->algo;
809 : 0 : chd_phf = (chd_ph_data_t *)malloc(sizeof(chd_ph_data_t));
810 : :
811 : 0 : chd_phf->cs = chd_ph->cs;
812 : 0 : chd_ph->cs = NULL; //transfer memory ownership
813 : 0 : chd_phf->hl = chd_ph->hl;
814 : 0 : chd_ph->hl = NULL; //transfer memory ownership
815 : 0 : chd_phf->n = chd_ph->n;
816 : 0 : chd_phf->nbuckets = chd_ph->nbuckets;
817 : :
818 : 0 : mphf->data = chd_phf;
819 : 0 : mphf->size = chd_ph->n;
820 : :
821 : : DEBUGP("Successfully generated minimal perfect hash\n");
822 : 0 : if (mph->verbosity)
823 : : {
824 : 0 : fprintf(stderr, "Successfully generated minimal perfect hash function\n");
825 : : }
826 : :
827 : : #ifdef CMPH_TIMING
828 : : register cmph_uint32 space_usage = chd_ph_packed_size(mphf)*8;
829 : : construction_time = construction_time - construction_time_begin;
830 : : fprintf(stdout, "%u\t%.2f\t%u\t%.4f\t%.4f\t%.4f\t%.4f\n", chd_ph->m, load_factor, chd_ph->keys_per_bucket, construction_time, space_usage/(double)chd_ph->m, space_lower_bound, entropy/chd_ph->m);
831 : : #endif
832 : :
833 : 0 : return mphf;
834 : : }
835 : :
836 : :
837 : :
838 : 0 : void chd_ph_load(FILE *fd, cmph_t *mphf)
839 : : {
840 : 0 : char *buf = NULL;
841 : : cmph_uint32 buflen;
842 : : register size_t nbytes;
843 : 0 : chd_ph_data_t *chd_ph = (chd_ph_data_t *)malloc(sizeof(chd_ph_data_t));
844 : :
845 : : DEBUGP("Loading chd_ph mphf\n");
846 : 0 : mphf->data = chd_ph;
847 : :
848 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
849 : : DEBUGP("Hash state has %u bytes\n", buflen);
850 : 0 : buf = (char *)malloc((size_t)buflen);
851 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, fd);
852 : 0 : chd_ph->hl = hash_state_load(buf, buflen);
853 : 0 : free(buf);
854 : :
855 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
856 : : DEBUGP("Compressed sequence structure has %u bytes\n", buflen);
857 : 0 : buf = (char *)malloc((size_t)buflen);
858 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, fd);
859 : 0 : chd_ph->cs = (compressed_seq_t *) calloc(1, sizeof(compressed_seq_t));
860 : 0 : compressed_seq_load(chd_ph->cs, buf, buflen);
861 : 0 : free(buf);
862 : :
863 : : // loading n and nbuckets
864 : : DEBUGP("Reading n and nbuckets\n");
865 : 0 : nbytes = fread(&(chd_ph->n), sizeof(cmph_uint32), (size_t)1, fd);
866 : 0 : nbytes = fread(&(chd_ph->nbuckets), sizeof(cmph_uint32), (size_t)1, fd);
867 : 0 : if (nbytes == 0 && ferror(fd)) {
868 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
869 : : }
870 : :
871 : 0 : }
872 : :
873 : 0 : int chd_ph_dump(cmph_t *mphf, FILE *fd)
874 : : {
875 : 0 : char *buf = NULL;
876 : : cmph_uint32 buflen;
877 : : register size_t nbytes;
878 : 0 : chd_ph_data_t *data = (chd_ph_data_t *)mphf->data;
879 : :
880 : 0 : __cmph_dump(mphf, fd);
881 : :
882 : 0 : hash_state_dump(data->hl, &buf, &buflen);
883 : : DEBUGP("Dumping hash state with %u bytes to disk\n", buflen);
884 : 0 : nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
885 : 0 : nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
886 : 0 : free(buf);
887 : :
888 : 0 : compressed_seq_dump(data->cs, &buf, &buflen);
889 : : DEBUGP("Dumping compressed sequence structure with %u bytes to disk\n", buflen);
890 : 0 : nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
891 : 0 : nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
892 : 0 : free(buf);
893 : :
894 : : // dumping n and nbuckets
895 : 0 : nbytes = fwrite(&(data->n), sizeof(cmph_uint32), (size_t)1, fd);
896 : 0 : nbytes = fwrite(&(data->nbuckets), sizeof(cmph_uint32), (size_t)1, fd);
897 : 0 : if (nbytes == 0 && ferror(fd)) {
898 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
899 : 0 : return 0;
900 : : }
901 : 0 : return 1;
902 : : }
903 : :
904 : 0 : void chd_ph_destroy(cmph_t *mphf)
905 : : {
906 : 0 : chd_ph_data_t *data = (chd_ph_data_t *)mphf->data;
907 : 0 : compressed_seq_destroy(data->cs);
908 : 0 : free(data->cs);
909 : 0 : hash_state_destroy(data->hl);
910 : 0 : free(data);
911 : 0 : free(mphf);
912 : :
913 : 0 : }
914 : :
915 : 0 : cmph_uint32 chd_ph_search(cmph_t *mphf, const char *key, cmph_uint32 keylen)
916 : : {
917 : 0 : register chd_ph_data_t * chd_ph = mphf->data;
918 : : cmph_uint32 hl[3];
919 : : register cmph_uint32 disp,position;
920 : : register cmph_uint32 probe0_num,probe1_num;
921 : : register cmph_uint32 f,g,h;
922 : 0 : hash_vector(chd_ph->hl, key, keylen, hl);
923 : 0 : g = hl[0] % chd_ph->nbuckets;
924 : 0 : f = hl[1] % chd_ph->n;
925 : 0 : h = hl[2] % (chd_ph->n-1) + 1;
926 : :
927 : 0 : disp = compressed_seq_query(chd_ph->cs, g);
928 : 0 : probe0_num = disp % chd_ph->n;
929 : 0 : probe1_num = disp/chd_ph->n;
930 : 0 : position = (cmph_uint32)((f + ((cmph_uint64 )h)*probe0_num + probe1_num) % chd_ph->n);
931 : 0 : return position;
932 : : }
933 : :
934 : 0 : void chd_ph_pack(cmph_t *mphf, void *packed_mphf)
935 : : {
936 : 0 : chd_ph_data_t *data = (chd_ph_data_t *)mphf->data;
937 : 0 : cmph_uint8 * ptr = packed_mphf;
938 : :
939 : : // packing hl type
940 : 0 : CMPH_HASH hl_type = hash_get_type(data->hl);
941 : 0 : *((cmph_uint32 *) ptr) = hl_type;
942 : 0 : ptr += sizeof(cmph_uint32);
943 : :
944 : : // packing hl
945 : 0 : hash_state_pack(data->hl, ptr);
946 : 0 : ptr += hash_state_packed_size(hl_type);
947 : :
948 : : // packing n
949 : 0 : *((cmph_uint32 *) ptr) = data->n;
950 : 0 : ptr += sizeof(data->n);
951 : :
952 : : // packing nbuckets
953 : 0 : *((cmph_uint32 *) ptr) = data->nbuckets;
954 : 0 : ptr += sizeof(data->nbuckets);
955 : :
956 : : // packing cs
957 : 0 : compressed_seq_pack(data->cs, ptr);
958 : : //ptr += compressed_seq_packed_size(data->cs);
959 : :
960 : 0 : }
961 : :
962 : 0 : cmph_uint32 chd_ph_packed_size(cmph_t *mphf)
963 : : {
964 : 0 : register chd_ph_data_t *data = (chd_ph_data_t *)mphf->data;
965 : 0 : register CMPH_HASH hl_type = hash_get_type(data->hl);
966 : 0 : register cmph_uint32 hash_state_pack_size = hash_state_packed_size(hl_type);
967 : 0 : register cmph_uint32 cs_pack_size = compressed_seq_packed_size(data->cs);
968 : :
969 : 0 : return (cmph_uint32)(sizeof(CMPH_ALGO) + hash_state_pack_size + cs_pack_size + 3*sizeof(cmph_uint32));
970 : :
971 : : }
972 : :
973 : 0 : cmph_uint32 chd_ph_search_packed(void *packed_mphf, const char *key, cmph_uint32 keylen)
974 : : {
975 : 0 : register CMPH_HASH hl_type = *(cmph_uint32 *)packed_mphf;
976 : 0 : register cmph_uint8 *hl_ptr = (cmph_uint8 *)(packed_mphf) + 4;
977 : :
978 : 0 : register cmph_uint32 * ptr = (cmph_uint32 *)(hl_ptr + hash_state_packed_size(hl_type));
979 : 0 : register cmph_uint32 n = *ptr++;
980 : 0 : register cmph_uint32 nbuckets = *ptr++;
981 : : cmph_uint32 hl[3];
982 : :
983 : : register cmph_uint32 disp,position;
984 : : register cmph_uint32 probe0_num,probe1_num;
985 : : register cmph_uint32 f,g,h;
986 : :
987 : 0 : hash_vector_packed(hl_ptr, hl_type, key, keylen, hl);
988 : :
989 : 0 : g = hl[0] % nbuckets;
990 : 0 : f = hl[1] % n;
991 : 0 : h = hl[2] % (n-1) + 1;
992 : :
993 : 0 : disp = compressed_seq_query_packed(ptr, g);
994 : 0 : probe0_num = disp % n;
995 : 0 : probe1_num = disp/n;
996 : 0 : position = (cmph_uint32)((f + ((cmph_uint64 )h)*probe0_num + probe1_num) % n);
997 : 0 : return position;
998 : : }
999 : :
1000 : :
1001 : :
|
