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.h"
12 : : #include "chd.h"
13 : : #include "bitbool.h"
14 : : //#define DEBUG
15 : : #include "debug.h"
16 : :
17 : 0 : chd_config_data_t *chd_config_new(cmph_config_t *mph)
18 : : {
19 : 0 : cmph_io_adapter_t *key_source = mph->key_source;
20 : : chd_config_data_t *chd;
21 : 0 : chd = (chd_config_data_t *)malloc(sizeof(chd_config_data_t));
22 : 0 : assert(chd);
23 : 0 : memset(chd, 0, sizeof(chd_config_data_t));
24 : :
25 : 0 : chd->chd_ph = cmph_config_new(key_source);
26 : 0 : cmph_config_set_algo(chd->chd_ph, CMPH_CHD_PH);
27 : :
28 : 0 : return chd;
29 : : }
30 : :
31 : 0 : void chd_config_destroy(cmph_config_t *mph)
32 : : {
33 : 0 : chd_config_data_t *data = (chd_config_data_t *) mph->data;
34 : : DEBUGP("Destroying algorithm dependent data\n");
35 : 0 : if(data->chd_ph)
36 : : {
37 : 0 : cmph_config_destroy(data->chd_ph);
38 : 0 : data->chd_ph = NULL;
39 : : }
40 : 0 : free(data);
41 : 0 : }
42 : :
43 : :
44 : 0 : void chd_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs)
45 : : {
46 : 0 : chd_config_data_t *data = (chd_config_data_t *) mph->data;
47 : 0 : cmph_config_set_hashfuncs(data->chd_ph, hashfuncs);
48 : 0 : }
49 : :
50 : :
51 : 0 : void chd_config_set_b(cmph_config_t *mph, cmph_uint32 keys_per_bucket)
52 : : {
53 : 0 : chd_config_data_t *data = (chd_config_data_t *) mph->data;
54 : 0 : cmph_config_set_b(data->chd_ph, keys_per_bucket);
55 : 0 : }
56 : :
57 : :
58 : 0 : void chd_config_set_keys_per_bin(cmph_config_t *mph, cmph_uint32 keys_per_bin)
59 : : {
60 : 0 : chd_config_data_t *data = (chd_config_data_t *) mph->data;
61 : 0 : cmph_config_set_keys_per_bin(data->chd_ph, keys_per_bin);
62 : 0 : }
63 : :
64 : :
65 : 0 : cmph_t *chd_new(cmph_config_t *mph, double c)
66 : : {
67 : 0 : cmph_t *mphf = NULL;
68 : 0 : chd_data_t *chdf = NULL;
69 : 0 : chd_config_data_t *chd = (chd_config_data_t *)mph->data;
70 : 0 : chd_ph_config_data_t * chd_ph = (chd_ph_config_data_t *)chd->chd_ph->data;
71 : : compressed_rank_t cr;
72 : :
73 : 0 : register cmph_t * chd_phf = NULL;
74 : 0 : register cmph_uint32 packed_chd_phf_size = 0;
75 : 0 : cmph_uint8 * packed_chd_phf = NULL;
76 : :
77 : 0 : register cmph_uint32 packed_cr_size = 0;
78 : 0 : cmph_uint8 * packed_cr = NULL;
79 : :
80 : : register cmph_uint32 i, idx, nkeys, nvals, nbins;
81 : 0 : cmph_uint32 * vals_table = NULL;
82 : 0 : register cmph_uint32 * occup_table = NULL;
83 : : #ifdef CMPH_TIMING
84 : : double construction_time_begin = 0.0;
85 : : double construction_time = 0.0;
86 : : ELAPSED_TIME_IN_SECONDS(&construction_time_begin);
87 : : #endif
88 : :
89 : 0 : cmph_config_set_verbosity(chd->chd_ph, mph->verbosity);
90 : 0 : cmph_config_set_graphsize(chd->chd_ph, c);
91 : :
92 : 0 : if (mph->verbosity)
93 : : {
94 : 0 : fprintf(stderr, "Generating a CHD_PH perfect hash function with a load factor equal to %.3f\n", c);
95 : : }
96 : :
97 : 0 : chd_phf = cmph_new(chd->chd_ph);
98 : :
99 : 0 : if(chd_phf == NULL)
100 : : {
101 : 0 : return NULL;
102 : : }
103 : :
104 : 0 : packed_chd_phf_size = cmph_packed_size(chd_phf);
105 : : DEBUGP("packed_chd_phf_size = %u\n", packed_chd_phf_size);
106 : :
107 : : /* Make sure that we have enough space to pack the mphf. */
108 : 0 : packed_chd_phf = calloc((size_t)packed_chd_phf_size,(size_t)1);
109 : :
110 : : /* Pack the mphf. */
111 : 0 : cmph_pack(chd_phf, packed_chd_phf);
112 : :
113 : 0 : cmph_destroy(chd_phf);
114 : :
115 : :
116 : 0 : if (mph->verbosity)
117 : : {
118 : 0 : fprintf(stderr, "Compressing the range of the resulting CHD_PH perfect hash function\n");
119 : : }
120 : :
121 : 0 : compressed_rank_init(&cr);
122 : 0 : nbins = chd_ph->n;
123 : 0 : nkeys = chd_ph->m;
124 : 0 : nvals = nbins - nkeys;
125 : :
126 : 0 : vals_table = (cmph_uint32 *)calloc(nvals, sizeof(cmph_uint32));
127 : 0 : occup_table = (cmph_uint32 *)chd_ph->occup_table;
128 : :
129 : 0 : for(i = 0, idx = 0; i < nbins; i++)
130 : : {
131 : 0 : if(!GETBIT32(occup_table, i))
132 : : {
133 : 0 : vals_table[idx++] = i;
134 : : }
135 : : }
136 : :
137 : 0 : compressed_rank_generate(&cr, vals_table, nvals);
138 : 0 : free(vals_table);
139 : :
140 : 0 : packed_cr_size = compressed_rank_packed_size(&cr);
141 : 0 : packed_cr = (cmph_uint8 *) calloc(packed_cr_size, sizeof(cmph_uint8));
142 : 0 : compressed_rank_pack(&cr, packed_cr);
143 : 0 : compressed_rank_destroy(&cr);
144 : :
145 : 0 : mphf = (cmph_t *)malloc(sizeof(cmph_t));
146 : 0 : mphf->algo = mph->algo;
147 : 0 : chdf = (chd_data_t *)malloc(sizeof(chd_data_t));
148 : :
149 : 0 : chdf->packed_cr = packed_cr;
150 : 0 : packed_cr = NULL; //transfer memory ownership
151 : :
152 : 0 : chdf->packed_chd_phf = packed_chd_phf;
153 : 0 : packed_chd_phf = NULL; //transfer memory ownership
154 : :
155 : 0 : chdf->packed_chd_phf_size = packed_chd_phf_size;
156 : 0 : chdf->packed_cr_size = packed_cr_size;
157 : :
158 : 0 : mphf->data = chdf;
159 : 0 : mphf->size = nkeys;
160 : :
161 : : DEBUGP("Successfully generated minimal perfect hash\n");
162 : 0 : if (mph->verbosity)
163 : : {
164 : 0 : fprintf(stderr, "Successfully generated minimal perfect hash function\n");
165 : : }
166 : : #ifdef CMPH_TIMING
167 : : ELAPSED_TIME_IN_SECONDS(&construction_time);
168 : : register cmph_uint32 space_usage = chd_packed_size(mphf)*8;
169 : : construction_time = construction_time - construction_time_begin;
170 : : fprintf(stdout, "%u\t%.2f\t%u\t%.4f\t%.4f\n", nkeys, c, chd_ph->keys_per_bucket, construction_time, space_usage/(double)nkeys);
171 : : #endif
172 : :
173 : 0 : return mphf;
174 : : }
175 : :
176 : 0 : void chd_load(FILE *fd, cmph_t *mphf)
177 : : {
178 : : register size_t nbytes;
179 : 0 : chd_data_t *chd = (chd_data_t *)malloc(sizeof(chd_data_t));
180 : :
181 : : DEBUGP("Loading chd mphf\n");
182 : 0 : mphf->data = chd;
183 : :
184 : 0 : nbytes = fread(&chd->packed_chd_phf_size, sizeof(cmph_uint32), (size_t)1, fd);
185 : : DEBUGP("Loading CHD_PH perfect hash function with %u bytes to disk\n", chd->packed_chd_phf_size);
186 : 0 : chd->packed_chd_phf = (cmph_uint8 *) calloc((size_t)chd->packed_chd_phf_size,(size_t)1);
187 : 0 : nbytes = fread(chd->packed_chd_phf, chd->packed_chd_phf_size, (size_t)1, fd);
188 : :
189 : 0 : nbytes = fread(&chd->packed_cr_size, sizeof(cmph_uint32), (size_t)1, fd);
190 : : DEBUGP("Loading Compressed rank structure, which has %u bytes\n", chd->packed_cr_size);
191 : 0 : chd->packed_cr = (cmph_uint8 *) calloc((size_t)chd->packed_cr_size, (size_t)1);
192 : 0 : nbytes = fread(chd->packed_cr, chd->packed_cr_size, (size_t)1, fd);
193 : 0 : if (nbytes == 0 && ferror(fd)) {
194 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
195 : : }
196 : :
197 : 0 : }
198 : :
199 : 0 : int chd_dump(cmph_t *mphf, FILE *fd)
200 : : {
201 : : register size_t nbytes;
202 : 0 : chd_data_t *data = (chd_data_t *)mphf->data;
203 : :
204 : 0 : __cmph_dump(mphf, fd);
205 : : // Dumping CHD_PH perfect hash function
206 : :
207 : : DEBUGP("Dumping CHD_PH perfect hash function with %u bytes to disk\n", data->packed_chd_phf_size);
208 : 0 : nbytes = fwrite(&data->packed_chd_phf_size, sizeof(cmph_uint32), (size_t)1, fd);
209 : 0 : nbytes = fwrite(data->packed_chd_phf, data->packed_chd_phf_size, (size_t)1, fd);
210 : :
211 : : DEBUGP("Dumping compressed rank structure with %u bytes to disk\n", data->packed_cr_size);
212 : 0 : nbytes = fwrite(&data->packed_cr_size, sizeof(cmph_uint32), (size_t)1, fd);
213 : 0 : nbytes = fwrite(data->packed_cr, data->packed_cr_size, (size_t)1, fd);
214 : 0 : if (nbytes == 0 && ferror(fd)) {
215 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
216 : 0 : return 0;
217 : : }
218 : :
219 : 0 : return 1;
220 : : }
221 : :
222 : 0 : void chd_destroy(cmph_t *mphf)
223 : : {
224 : 0 : chd_data_t *data = (chd_data_t *)mphf->data;
225 : 0 : free(data->packed_chd_phf);
226 : 0 : free(data->packed_cr);
227 : 0 : free(data);
228 : 0 : free(mphf);
229 : 0 : }
230 : :
231 : 0 : static inline cmph_uint32 _chd_search(void * packed_chd_phf, void * packed_cr, const char *key, cmph_uint32 keylen)
232 : : {
233 : 0 : register cmph_uint32 bin_idx = cmph_search_packed(packed_chd_phf, key, keylen);
234 : 0 : register cmph_uint32 rank = compressed_rank_query_packed(packed_cr, bin_idx);
235 : 0 : return bin_idx - rank;
236 : : }
237 : :
238 : 0 : cmph_uint32 chd_search(cmph_t *mphf, const char *key, cmph_uint32 keylen)
239 : : {
240 : 0 : register chd_data_t * chd = mphf->data;
241 : 0 : return _chd_search(chd->packed_chd_phf, chd->packed_cr, key, keylen);
242 : : }
243 : :
244 : 0 : void chd_pack(cmph_t *mphf, void *packed_mphf)
245 : : {
246 : 0 : chd_data_t *data = (chd_data_t *)mphf->data;
247 : 0 : cmph_uint32 * ptr = packed_mphf;
248 : : cmph_uint8 * ptr8;
249 : :
250 : : // packing packed_cr_size and packed_cr
251 : 0 : *ptr = data->packed_cr_size;
252 : 0 : ptr8 = (cmph_uint8 *) (ptr + 1);
253 : :
254 : 0 : memcpy(ptr8, data->packed_cr, data->packed_cr_size);
255 : 0 : ptr8 += data->packed_cr_size;
256 : :
257 : 0 : ptr = (cmph_uint32 *) ptr8;
258 : 0 : *ptr = data->packed_chd_phf_size;
259 : :
260 : 0 : ptr8 = (cmph_uint8 *) (ptr + 1);
261 : 0 : memcpy(ptr8, data->packed_chd_phf, data->packed_chd_phf_size);
262 : 0 : }
263 : :
264 : 0 : cmph_uint32 chd_packed_size(cmph_t *mphf)
265 : : {
266 : 0 : register chd_data_t *data = (chd_data_t *)mphf->data;
267 : 0 : return (cmph_uint32)(sizeof(CMPH_ALGO) + 2*sizeof(cmph_uint32) + data->packed_cr_size + data->packed_chd_phf_size);
268 : :
269 : : }
270 : :
271 : 0 : cmph_uint32 chd_search_packed(void *packed_mphf, const char *key, cmph_uint32 keylen)
272 : : {
273 : :
274 : 0 : register cmph_uint32 * ptr = packed_mphf;
275 : 0 : register cmph_uint32 packed_cr_size = *ptr++;
276 : 0 : register cmph_uint8 * packed_chd_phf = ((cmph_uint8 *) ptr) + packed_cr_size + sizeof(cmph_uint32);
277 : 0 : return _chd_search(packed_chd_phf, ptr, key, keylen);
278 : : }
279 : :
280 : :
|
