| 1 |
#ifdef WIN32 |
| 2 |
#include "wingetopt.h" |
| 3 |
#else |
| 4 |
#include <getopt.h> |
| 5 |
#endif |
| 6 |
#include <stdio.h> |
| 7 |
#include <stdlib.h> |
| 8 |
#include <errno.h> |
| 9 |
#include <string.h> |
| 10 |
#include <time.h> |
| 11 |
#include <limits.h> |
| 12 |
#include <assert.h> |
| 13 |
#include "cmph.h" |
| 14 |
#include "hash.h" |
| 15 |
|
| 16 |
#ifdef WIN32 |
| 17 |
#define VERSION "0.8" |
| 18 |
#else |
| 19 |
#include "config.h" |
| 20 |
#endif |
| 21 |
|
| 22 |
|
| 23 |
void usage(const char *prg) |
| 24 |
{ |
| 25 |
fprintf(stderr, "usage: %s [-v] [-h] [-V] [-k nkeys] [-f hash_function] [-g [-c algorithm_dependent_value][-s seed] ] [-a algorithm] [-M memory_in_MB] [-b algorithm_dependent_value] [-t keys_per_bin] [-d tmp_dir] [-m file.mph] keysfile\n", prg); |
| 26 |
} |
| 27 |
void usage_long(const char *prg) |
| 28 |
{ |
| 29 |
cmph_uint32 i; |
| 30 |
fprintf(stderr, "usage: %s [-v] [-h] [-V] [-k nkeys] [-f hash_function] [-g [-c algorithm_dependent_value][-s seed] ] [-a algorithm] [-M memory_in_MB] [-b algorithm_dependent_value] [-t keys_per_bin] [-d tmp_dir] [-m file.mph] keysfile\n", prg); |
| 31 |
fprintf(stderr, "Minimum perfect hashing tool\n\n"); |
| 32 |
fprintf(stderr, " -h\t print this help message\n"); |
| 33 |
fprintf(stderr, " -c\t c value determines:\n"); |
| 34 |
fprintf(stderr, " \t * the number of vertices in the graph for the algorithms BMZ and CHM\n"); |
| 35 |
fprintf(stderr, " \t * the number of bits per key required in the FCH algorithm\n"); |
| 36 |
fprintf(stderr, " \t * the load factor in the CHD_PH algorithm\n"); |
| 37 |
fprintf(stderr, " -a\t algorithm - valid values are\n"); |
| 38 |
for (i = 0; i < CMPH_COUNT; ++i) fprintf(stderr, " \t * %s\n", cmph_names[i]); |
| 39 |
fprintf(stderr, " -f\t hash function (may be used multiple times) - valid values are\n"); |
| 40 |
for (i = 0; i < CMPH_HASH_COUNT; ++i) fprintf(stderr, " \t * %s\n", cmph_hash_names[i]); |
| 41 |
fprintf(stderr, " -V\t print version number and exit\n"); |
| 42 |
fprintf(stderr, " -v\t increase verbosity (may be used multiple times)\n"); |
| 43 |
fprintf(stderr, " -k\t number of keys\n"); |
| 44 |
fprintf(stderr, " -g\t generation mode\n"); |
| 45 |
fprintf(stderr, " -s\t random seed\n"); |
| 46 |
fprintf(stderr, " -m\t minimum perfect hash function file \n"); |
| 47 |
fprintf(stderr, " -M\t main memory availability (in MB) used in BRZ algorithm \n"); |
| 48 |
fprintf(stderr, " -d\t temporary directory used in BRZ algorithm \n"); |
| 49 |
fprintf(stderr, " -b\t the meaning of this parameter depends on the algorithm selected in the -a option:\n"); |
| 50 |
fprintf(stderr, " \t * For BRZ it is used to make the maximal number of keys in a bucket lower than 256.\n"); |
| 51 |
fprintf(stderr, " \t In this case its value should be an integer in the range [64,175]. Default is 128.\n\n"); |
| 52 |
fprintf(stderr, " \t * For BDZ it is used to determine the size of some precomputed rank\n"); |
| 53 |
fprintf(stderr, " \t information and its value should be an integer in the range [3,10]. Default\n"); |
| 54 |
fprintf(stderr, " \t is 7. The larger is this value, the more compact are the resulting functions\n"); |
| 55 |
fprintf(stderr, " \t and the slower are them at evaluation time.\n\n"); |
| 56 |
fprintf(stderr, " \t * For CHD and CHD_PH it is used to set the average number of keys per bucket\n"); |
| 57 |
fprintf(stderr, " \t and its value should be an integer in the range [1,32]. Default is 4. The\n"); |
| 58 |
fprintf(stderr, " \t larger is this value, the slower is the construction of the functions.\n"); |
| 59 |
fprintf(stderr, " \t This parameter has no effect for other algorithms.\n\n"); |
| 60 |
fprintf(stderr, " -t\t set the number of keys per bin for a t-perfect hashing function. A t-perfect\n"); |
| 61 |
fprintf(stderr, " \t hash function allows at most t collisions in a given bin. This parameter applies\n"); |
| 62 |
fprintf(stderr, " \t only to the CHD and CHD_PH algorithms. Its value should be an integer in the\n"); |
| 63 |
fprintf(stderr, " \t range [1,128]. Defaul is 1\n"); |
| 64 |
fprintf(stderr, " keysfile\t line separated file with keys\n"); |
| 65 |
} |
| 66 |
|
| 67 |
int main(int argc, char **argv) |
| 68 |
{ |
| 69 |
cmph_uint32 verbosity = 0; |
| 70 |
char generate = 0; |
| 71 |
char *mphf_file = NULL; |
| 72 |
FILE *mphf_fd = stdout; |
| 73 |
const char *keys_file = NULL; |
| 74 |
FILE *keys_fd; |
| 75 |
cmph_uint32 nkeys = UINT_MAX; |
| 76 |
cmph_uint32 seed = UINT_MAX; |
| 77 |
CMPH_HASH *hashes = NULL; |
| 78 |
cmph_uint32 nhashes = 0; |
| 79 |
cmph_uint32 i; |
| 80 |
CMPH_ALGO mph_algo = CMPH_CHM; |
| 81 |
double c = 0; |
| 82 |
cmph_config_t *config = NULL; |
| 83 |
cmph_t *mphf = NULL; |
| 84 |
char * tmp_dir = NULL; |
| 85 |
cmph_io_adapter_t *source; |
| 86 |
cmph_uint32 memory_availability = 0; |
| 87 |
cmph_uint32 b = 0; |
| 88 |
cmph_uint32 keys_per_bin = 1; |
| 89 |
while (1) |
| 90 |
{ |
| 91 |
char ch = (char)getopt(argc, argv, "hVvgc:k:a:M:b:t:f:m:d:s:"); |
| 92 |
if (ch == -1) break; |
| 93 |
switch (ch) |
| 94 |
{ |
| 95 |
case 's': |
| 96 |
{ |
| 97 |
char *cptr; |
| 98 |
seed = (cmph_uint32)strtoul(optarg, &cptr, 10); |
| 99 |
if(*cptr != 0) { |
| 100 |
fprintf(stderr, "Invalid seed %s\n", optarg); |
| 101 |
exit(1); |
| 102 |
} |
| 103 |
} |
| 104 |
break; |
| 105 |
case 'c': |
| 106 |
{ |
| 107 |
char *endptr; |
| 108 |
c = strtod(optarg, &endptr); |
| 109 |
if(*endptr != 0) { |
| 110 |
fprintf(stderr, "Invalid c value %s\n", optarg); |
| 111 |
exit(1); |
| 112 |
} |
| 113 |
} |
| 114 |
break; |
| 115 |
case 'g': |
| 116 |
generate = 1; |
| 117 |
break; |
| 118 |
case 'k': |
| 119 |
{ |
| 120 |
char *endptr; |
| 121 |
nkeys = (cmph_uint32)strtoul(optarg, &endptr, 10); |
| 122 |
if(*endptr != 0) { |
| 123 |
fprintf(stderr, "Invalid number of keys %s\n", optarg); |
| 124 |
exit(1); |
| 125 |
} |
| 126 |
} |
| 127 |
break; |
| 128 |
case 'm': |
| 129 |
mphf_file = strdup(optarg); |
| 130 |
break; |
| 131 |
case 'd': |
| 132 |
tmp_dir = strdup(optarg); |
| 133 |
break; |
| 134 |
case 'M': |
| 135 |
{ |
| 136 |
char *cptr; |
| 137 |
memory_availability = (cmph_uint32)strtoul(optarg, &cptr, 10); |
| 138 |
if(*cptr != 0) { |
| 139 |
fprintf(stderr, "Invalid memory availability %s\n", optarg); |
| 140 |
exit(1); |
| 141 |
} |
| 142 |
} |
| 143 |
break; |
| 144 |
case 'b': |
| 145 |
{ |
| 146 |
char *cptr; |
| 147 |
b = (cmph_uint32)strtoul(optarg, &cptr, 10); |
| 148 |
if(*cptr != 0) { |
| 149 |
fprintf(stderr, "Parameter b was not found: %s\n", optarg); |
| 150 |
exit(1); |
| 151 |
} |
| 152 |
} |
| 153 |
break; |
| 154 |
case 't': |
| 155 |
{ |
| 156 |
char *cptr; |
| 157 |
keys_per_bin = (cmph_uint32)strtoul(optarg, &cptr, 10); |
| 158 |
if(*cptr != 0) { |
| 159 |
fprintf(stderr, "Parameter t was not found: %s\n", optarg); |
| 160 |
exit(1); |
| 161 |
} |
| 162 |
} |
| 163 |
break; |
| 164 |
case 'v': |
| 165 |
++verbosity; |
| 166 |
break; |
| 167 |
case 'V': |
| 168 |
printf("%s\n", VERSION); |
| 169 |
return 0; |
| 170 |
case 'h': |
| 171 |
usage_long(argv[0]); |
| 172 |
return 0; |
| 173 |
case 'a': |
| 174 |
{ |
| 175 |
char valid = 0; |
| 176 |
for (i = 0; i < CMPH_COUNT; ++i) |
| 177 |
{ |
| 178 |
if (strcmp(cmph_names[i], optarg) == 0) |
| 179 |
{ |
| 180 |
mph_algo = i; |
| 181 |
valid = 1; |
| 182 |
break; |
| 183 |
} |
| 184 |
} |
| 185 |
if (!valid) |
| 186 |
{ |
| 187 |
fprintf(stderr, "Invalid mph algorithm: %s. It is not available in version %s\n", optarg, VERSION); |
| 188 |
return -1; |
| 189 |
} |
| 190 |
} |
| 191 |
break; |
| 192 |
case 'f': |
| 193 |
{ |
| 194 |
char valid = 0; |
| 195 |
for (i = 0; i < CMPH_HASH_COUNT; ++i) |
| 196 |
{ |
| 197 |
if (strcmp(cmph_hash_names[i], optarg) == 0) |
| 198 |
{ |
| 199 |
hashes = (CMPH_HASH *)realloc(hashes, sizeof(CMPH_HASH) * ( nhashes + 2 )); |
| 200 |
hashes[nhashes] = i; |
| 201 |
hashes[nhashes + 1] = CMPH_HASH_COUNT; |
| 202 |
++nhashes; |
| 203 |
valid = 1; |
| 204 |
break; |
| 205 |
} |
| 206 |
} |
| 207 |
if (!valid) |
| 208 |
{ |
| 209 |
fprintf(stderr, "Invalid hash function: %s\n", optarg); |
| 210 |
return -1; |
| 211 |
} |
| 212 |
} |
| 213 |
break; |
| 214 |
default: |
| 215 |
usage(argv[0]); |
| 216 |
return 1; |
| 217 |
} |
| 218 |
} |
| 219 |
|
| 220 |
if (optind != argc - 1) |
| 221 |
{ |
| 222 |
usage(argv[0]); |
| 223 |
return 1; |
| 224 |
} |
| 225 |
keys_file = argv[optind]; |
| 226 |
|
| 227 |
if (seed == UINT_MAX) seed = (cmph_uint32)time(NULL); |
| 228 |
srand(seed); |
| 229 |
int ret = 0; |
| 230 |
if (mphf_file == NULL) |
| 231 |
{ |
| 232 |
mphf_file = (char *)malloc(strlen(keys_file) + 5); |
| 233 |
memcpy(mphf_file, keys_file, strlen(keys_file)); |
| 234 |
memcpy(mphf_file + strlen(keys_file), ".mph\0", (size_t)5); |
| 235 |
} |
| 236 |
|
| 237 |
keys_fd = fopen(keys_file, "r"); |
| 238 |
|
| 239 |
if (keys_fd == NULL) |
| 240 |
{ |
| 241 |
fprintf(stderr, "Unable to open file %s: %s\n", keys_file, strerror(errno)); |
| 242 |
return -1; |
| 243 |
} |
| 244 |
|
| 245 |
if (seed == UINT_MAX) seed = (cmph_uint32)time(NULL); |
| 246 |
if(nkeys == UINT_MAX) source = cmph_io_nlfile_adapter(keys_fd); |
| 247 |
else source = cmph_io_nlnkfile_adapter(keys_fd, nkeys); |
| 248 |
if (generate) |
| 249 |
{ |
| 250 |
//Create mphf |
| 251 |
mphf_fd = fopen(mphf_file, "w"); |
| 252 |
config = cmph_config_new(source); |
| 253 |
cmph_config_set_algo(config, mph_algo); |
| 254 |
if (nhashes) cmph_config_set_hashfuncs(config, hashes); |
| 255 |
cmph_config_set_verbosity(config, verbosity); |
| 256 |
cmph_config_set_tmp_dir(config, (cmph_uint8 *) tmp_dir); |
| 257 |
cmph_config_set_mphf_fd(config, mphf_fd); |
| 258 |
cmph_config_set_memory_availability(config, memory_availability); |
| 259 |
cmph_config_set_b(config, b); |
| 260 |
cmph_config_set_keys_per_bin(config, keys_per_bin); |
| 261 |
|
| 262 |
//if((mph_algo == CMPH_BMZ || mph_algo == CMPH_BRZ) && c >= 2.0) c=1.15; |
| 263 |
if(mph_algo == CMPH_BMZ && c >= 2.0) c=1.15; |
| 264 |
if (c != 0) cmph_config_set_graphsize(config, c); |
| 265 |
mphf = cmph_new(config); |
| 266 |
|
| 267 |
cmph_config_destroy(config); |
| 268 |
if (mphf == NULL) |
| 269 |
{ |
| 270 |
fprintf(stderr, "Unable to create minimum perfect hashing function\n"); |
| 271 |
//cmph_config_destroy(config); |
| 272 |
free(mphf_file); |
| 273 |
return -1; |
| 274 |
} |
| 275 |
|
| 276 |
if (mphf_fd == NULL) |
| 277 |
{ |
| 278 |
fprintf(stderr, "Unable to open output file %s: %s\n", mphf_file, strerror(errno)); |
| 279 |
free(mphf_file); |
| 280 |
return -1; |
| 281 |
} |
| 282 |
cmph_dump(mphf, mphf_fd); |
| 283 |
cmph_destroy(mphf); |
| 284 |
fclose(mphf_fd); |
| 285 |
} |
| 286 |
else |
| 287 |
{ |
| 288 |
cmph_uint8 * hashtable = NULL; |
| 289 |
mphf_fd = fopen(mphf_file, "r"); |
| 290 |
if (mphf_fd == NULL) |
| 291 |
{ |
| 292 |
fprintf(stderr, "Unable to open input file %s: %s\n", mphf_file, strerror(errno)); |
| 293 |
free(mphf_file); |
| 294 |
return -1; |
| 295 |
} |
| 296 |
mphf = cmph_load(mphf_fd); |
| 297 |
fclose(mphf_fd); |
| 298 |
if (!mphf) |
| 299 |
{ |
| 300 |
fprintf(stderr, "Unable to parser input file %s\n", mphf_file); |
| 301 |
free(mphf_file); |
| 302 |
return -1; |
| 303 |
} |
| 304 |
cmph_uint32 siz = cmph_size(mphf); |
| 305 |
hashtable = (cmph_uint8*)calloc(siz, sizeof(cmph_uint8)); |
| 306 |
memset(hashtable, 0,(size_t) siz); |
| 307 |
//check all keys |
| 308 |
for (i = 0; i < source->nkeys; ++i) |
| 309 |
{ |
| 310 |
cmph_uint32 h; |
| 311 |
char *buf; |
| 312 |
cmph_uint32 buflen = 0; |
| 313 |
source->read(source->data, &buf, &buflen); |
| 314 |
h = cmph_search(mphf, buf, buflen); |
| 315 |
if (!(h < siz)) |
| 316 |
{ |
| 317 |
fprintf(stderr, "Unknown key %*s in the input.\n", buflen, buf); |
| 318 |
ret = 1; |
| 319 |
} else if(hashtable[h] >= keys_per_bin) |
| 320 |
{ |
| 321 |
fprintf(stderr, "More than %u keys were mapped to bin %u\n", keys_per_bin, h); |
| 322 |
fprintf(stderr, "Duplicated or unknown key %*s in the input\n", buflen, buf); |
| 323 |
ret = 1; |
| 324 |
} else hashtable[h]++; |
| 325 |
|
| 326 |
if (verbosity) |
| 327 |
{ |
| 328 |
printf("%s -> %u\n", buf, h); |
| 329 |
} |
| 330 |
source->dispose(source->data, buf, buflen); |
| 331 |
} |
| 332 |
|
| 333 |
cmph_destroy(mphf); |
| 334 |
free(hashtable); |
| 335 |
} |
| 336 |
fclose(keys_fd); |
| 337 |
free(mphf_file); |
| 338 |
free(tmp_dir); |
| 339 |
cmph_io_nlfile_adapter_destroy(source); |
| 340 |
return ret; |
| 341 |
|
| 342 |
} |