diff options
Diffstat (limited to 'girepository/cmph/chd.c')
-rw-r--r-- | girepository/cmph/chd.c | 271 |
1 files changed, 271 insertions, 0 deletions
diff --git a/girepository/cmph/chd.c b/girepository/cmph/chd.c new file mode 100644 index 00000000..7fb3b8bb --- /dev/null +++ b/girepository/cmph/chd.c @@ -0,0 +1,271 @@ +#include<stdio.h> +#include<stdlib.h> +#include<string.h> +#include<math.h> +#include<time.h> +#include<assert.h> +#include<limits.h> + +#include "cmph_structs.h" +#include "chd_structs.h" +#include "chd.h" +#include "bitbool.h" +//#define DEBUG +#include "debug.h" + +chd_config_data_t *chd_config_new(cmph_config_t *mph) +{ + cmph_io_adapter_t *key_source = mph->key_source; + chd_config_data_t *chd; + chd = (chd_config_data_t *)malloc(sizeof(chd_config_data_t)); + assert(chd); + memset(chd, 0, sizeof(chd_config_data_t)); + + chd->chd_ph = cmph_config_new(key_source); + cmph_config_set_algo(chd->chd_ph, CMPH_CHD_PH); + + return chd; +} + +void chd_config_destroy(cmph_config_t *mph) +{ + chd_config_data_t *data = (chd_config_data_t *) mph->data; + DEBUGP("Destroying algorithm dependent data\n"); + if(data->chd_ph) + { + cmph_config_destroy(data->chd_ph); + data->chd_ph = NULL; + } + free(data); +} + + +void chd_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs) +{ + chd_config_data_t *data = (chd_config_data_t *) mph->data; + cmph_config_set_hashfuncs(data->chd_ph, hashfuncs); +} + + +void chd_config_set_b(cmph_config_t *mph, cmph_uint32 keys_per_bucket) +{ + chd_config_data_t *data = (chd_config_data_t *) mph->data; + cmph_config_set_b(data->chd_ph, keys_per_bucket); +} + + +void chd_config_set_keys_per_bin(cmph_config_t *mph, cmph_uint32 keys_per_bin) +{ + chd_config_data_t *data = (chd_config_data_t *) mph->data; + cmph_config_set_keys_per_bin(data->chd_ph, keys_per_bin); +} + + +cmph_t *chd_new(cmph_config_t *mph, double c) +{ + cmph_t *mphf = NULL; + chd_data_t *chdf = NULL; + chd_config_data_t *chd = (chd_config_data_t *)mph->data; + chd_ph_config_data_t * chd_ph = (chd_ph_config_data_t *)chd->chd_ph->data; + compressed_rank_t cr; + + register cmph_t * chd_phf = NULL; + register cmph_uint32 packed_chd_phf_size = 0; + cmph_uint8 * packed_chd_phf = NULL; + + register cmph_uint32 packed_cr_size = 0; + cmph_uint8 * packed_cr = NULL; + + register cmph_uint32 i, idx, nkeys, nvals, nbins; + cmph_uint32 * vals_table = NULL; + register cmph_uint32 * occup_table = NULL; + #ifdef CMPH_TIMING + double construction_time_begin = 0.0; + double construction_time = 0.0; + ELAPSED_TIME_IN_SECONDS(&construction_time_begin); + #endif + + cmph_config_set_verbosity(chd->chd_ph, mph->verbosity); + cmph_config_set_graphsize(chd->chd_ph, c); + + if (mph->verbosity) + { + fprintf(stderr, "Generating a CHD_PH perfect hash function with a load factor equal to %.3f\n", c); + } + + chd_phf = cmph_new(chd->chd_ph); + + if(chd_phf == NULL) + { + return NULL; + } + + packed_chd_phf_size = cmph_packed_size(chd_phf); + DEBUGP("packed_chd_phf_size = %u\n", packed_chd_phf_size); + + /* Make sure that we have enough space to pack the mphf. */ + packed_chd_phf = calloc((size_t)packed_chd_phf_size,(size_t)1); + + /* Pack the mphf. */ + cmph_pack(chd_phf, packed_chd_phf); + + cmph_destroy(chd_phf); + + + if (mph->verbosity) + { + fprintf(stderr, "Compressing the range of the resulting CHD_PH perfect hash function\n"); + } + + compressed_rank_init(&cr); + nbins = chd_ph->n; + nkeys = chd_ph->m; + nvals = nbins - nkeys; + + vals_table = (cmph_uint32 *)calloc(nvals, sizeof(cmph_uint32)); + occup_table = (cmph_uint32 *)chd_ph->occup_table; + + for(i = 0, idx = 0; i < nbins; i++) + { + if(!GETBIT32(occup_table, i)) + { + vals_table[idx++] = i; + } + } + + compressed_rank_generate(&cr, vals_table, nvals); + free(vals_table); + + packed_cr_size = compressed_rank_packed_size(&cr); + packed_cr = (cmph_uint8 *) calloc(packed_cr_size, sizeof(cmph_uint8)); + compressed_rank_pack(&cr, packed_cr); + compressed_rank_destroy(&cr); + + mphf = (cmph_t *)malloc(sizeof(cmph_t)); + mphf->algo = mph->algo; + chdf = (chd_data_t *)malloc(sizeof(chd_data_t)); + + chdf->packed_cr = packed_cr; + packed_cr = NULL; //transfer memory ownership + + chdf->packed_chd_phf = packed_chd_phf; + packed_chd_phf = NULL; //transfer memory ownership + + chdf->packed_chd_phf_size = packed_chd_phf_size; + chdf->packed_cr_size = packed_cr_size; + + mphf->data = chdf; + mphf->size = nkeys; + + DEBUGP("Successfully generated minimal perfect hash\n"); + if (mph->verbosity) + { + fprintf(stderr, "Successfully generated minimal perfect hash function\n"); + } + #ifdef CMPH_TIMING + ELAPSED_TIME_IN_SECONDS(&construction_time); + register cmph_uint32 space_usage = chd_packed_size(mphf)*8; + construction_time = construction_time - construction_time_begin; + 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); + #endif + + return mphf; +} + +void chd_load(FILE *fd, cmph_t *mphf) +{ + register size_t nbytes; + chd_data_t *chd = (chd_data_t *)malloc(sizeof(chd_data_t)); + + DEBUGP("Loading chd mphf\n"); + mphf->data = chd; + + nbytes = fread(&chd->packed_chd_phf_size, sizeof(cmph_uint32), (size_t)1, fd); + DEBUGP("Loading CHD_PH perfect hash function with %u bytes to disk\n", chd->packed_chd_phf_size); + chd->packed_chd_phf = (cmph_uint8 *) calloc((size_t)chd->packed_chd_phf_size,(size_t)1); + nbytes = fread(chd->packed_chd_phf, chd->packed_chd_phf_size, (size_t)1, fd); + + nbytes = fread(&chd->packed_cr_size, sizeof(cmph_uint32), (size_t)1, fd); + DEBUGP("Loading Compressed rank structure, which has %u bytes\n", chd->packed_cr_size); + chd->packed_cr = (cmph_uint8 *) calloc((size_t)chd->packed_cr_size, (size_t)1); + nbytes = fread(chd->packed_cr, chd->packed_cr_size, (size_t)1, fd); +} + +int chd_dump(cmph_t *mphf, FILE *fd) +{ + register size_t nbytes; + chd_data_t *data = (chd_data_t *)mphf->data; + + __cmph_dump(mphf, fd); + // Dumping CHD_PH perfect hash function + + DEBUGP("Dumping CHD_PH perfect hash function with %u bytes to disk\n", data->packed_chd_phf_size); + nbytes = fwrite(&data->packed_chd_phf_size, sizeof(cmph_uint32), (size_t)1, fd); + nbytes = fwrite(data->packed_chd_phf, data->packed_chd_phf_size, (size_t)1, fd); + + DEBUGP("Dumping compressed rank structure with %u bytes to disk\n", buflen); + nbytes = fwrite(&data->packed_cr_size, sizeof(cmph_uint32), (size_t)1, fd); + nbytes = fwrite(data->packed_cr, data->packed_cr_size, (size_t)1, fd); + + return 1; +} + +void chd_destroy(cmph_t *mphf) +{ + chd_data_t *data = (chd_data_t *)mphf->data; + free(data->packed_chd_phf); + free(data->packed_cr); + free(data); + free(mphf); +} + +static inline cmph_uint32 _chd_search(void * packed_chd_phf, void * packed_cr, const char *key, cmph_uint32 keylen) +{ + register cmph_uint32 bin_idx = cmph_search_packed(packed_chd_phf, key, keylen); + register cmph_uint32 rank = compressed_rank_query_packed(packed_cr, bin_idx); + return bin_idx - rank; +} + +cmph_uint32 chd_search(cmph_t *mphf, const char *key, cmph_uint32 keylen) +{ + register chd_data_t * chd = mphf->data; + return _chd_search(chd->packed_chd_phf, chd->packed_cr, key, keylen); +} + +void chd_pack(cmph_t *mphf, void *packed_mphf) +{ + chd_data_t *data = (chd_data_t *)mphf->data; + cmph_uint32 * ptr = packed_mphf; + cmph_uint8 * ptr8; + + // packing packed_cr_size and packed_cr + *ptr = data->packed_cr_size; + ptr8 = (cmph_uint8 *) (ptr + 1); + + memcpy(ptr8, data->packed_cr, data->packed_cr_size); + ptr8 += data->packed_cr_size; + + ptr = (cmph_uint32 *) ptr8; + *ptr = data->packed_chd_phf_size; + + ptr8 = (cmph_uint8 *) (ptr + 1); + memcpy(ptr8, data->packed_chd_phf, data->packed_chd_phf_size); +} + +cmph_uint32 chd_packed_size(cmph_t *mphf) +{ + register chd_data_t *data = (chd_data_t *)mphf->data; + return (cmph_uint32)(sizeof(CMPH_ALGO) + 2*sizeof(cmph_uint32) + data->packed_cr_size + data->packed_chd_phf_size); + +} + +cmph_uint32 chd_search_packed(void *packed_mphf, const char *key, cmph_uint32 keylen) +{ + + register cmph_uint32 * ptr = packed_mphf; + register cmph_uint32 packed_cr_size = *ptr++; + register cmph_uint8 * packed_chd_phf = ((cmph_uint8 *) ptr) + packed_cr_size + sizeof(cmph_uint32); + return _chd_search(packed_chd_phf, ptr, key, keylen); +} + + |