| 1 |
#ifndef __CMPH_COMPRESSED_RANK_H__ |
| 2 |
#define __CMPH_COMPRESSED_RANK_H__ |
| 3 |
|
| 4 |
#include "select.h" |
| 5 |
|
| 6 |
struct _compressed_rank_t |
| 7 |
{ |
| 8 |
cmph_uint32 max_val; |
| 9 |
cmph_uint32 n; // number of values stored in vals_rems |
| 10 |
// The length in bits of each value is decomposed into two compnents: the lg(n) MSBs are stored in rank_select data structure |
| 11 |
// the remaining LSBs are stored in a table of n cells, each one of rem_r bits. |
| 12 |
cmph_uint32 rem_r; |
| 13 |
select_t sel; |
| 14 |
cmph_uint32 * vals_rems; |
| 15 |
}; |
| 16 |
|
| 17 |
typedef struct _compressed_rank_t compressed_rank_t; |
| 18 |
|
| 19 |
void compressed_rank_init(compressed_rank_t * cr); |
| 20 |
|
| 21 |
void compressed_rank_destroy(compressed_rank_t * cr); |
| 22 |
|
| 23 |
void compressed_rank_generate(compressed_rank_t * cr, cmph_uint32 * vals_table, cmph_uint32 n); |
| 24 |
|
| 25 |
cmph_uint32 compressed_rank_query(compressed_rank_t * cr, cmph_uint32 idx); |
| 26 |
|
| 27 |
cmph_uint32 compressed_rank_get_space_usage(compressed_rank_t * cr); |
| 28 |
|
| 29 |
void compressed_rank_dump(compressed_rank_t * cr, char **buf, cmph_uint32 *buflen); |
| 30 |
|
| 31 |
void compressed_rank_load(compressed_rank_t * cr, const char *buf, cmph_uint32 buflen); |
| 32 |
|
| 33 |
|
| 34 |
/** \fn void compressed_rank_pack(compressed_rank_t *cr, void *cr_packed); |
| 35 |
* \brief Support the ability to pack a compressed_rank structure into a preallocated contiguous memory space pointed by cr_packed. |
| 36 |
* \param cr points to the compressed_rank structure |
| 37 |
* \param cr_packed pointer to the contiguous memory area used to store the compressed_rank structure. The size of cr_packed must be at least @see compressed_rank_packed_size |
| 38 |
*/ |
| 39 |
void compressed_rank_pack(compressed_rank_t *cr, void *cr_packed); |
| 40 |
|
| 41 |
/** \fn cmph_uint32 compressed_rank_packed_size(compressed_rank_t *cr); |
| 42 |
* \brief Return the amount of space needed to pack a compressed_rank structure. |
| 43 |
* \return the size of the packed compressed_rank structure or zero for failures |
| 44 |
*/ |
| 45 |
cmph_uint32 compressed_rank_packed_size(compressed_rank_t *cr); |
| 46 |
|
| 47 |
|
| 48 |
/** \fn cmph_uint32 compressed_rank_query_packed(void * cr_packed, cmph_uint32 idx); |
| 49 |
* \param cr_packed is a pointer to a contiguous memory area |
| 50 |
* \param idx is an index to compute the rank |
| 51 |
* \return an integer that represents the compressed_rank value. |
| 52 |
*/ |
| 53 |
cmph_uint32 compressed_rank_query_packed(void * cr_packed, cmph_uint32 idx); |
| 54 |
|
| 55 |
#endif |