| 1 |
#ifndef ROPE_H_ |
| 2 |
#define ROPE_H_ |
| 3 |
|
| 4 |
#include <stdint.h> |
| 5 |
#include <stdio.h> |
| 6 |
|
| 7 |
#define ROPE_MAX_DEPTH 80 |
| 8 |
#define ROPE_DEF_MAX_NODES 64 |
| 9 |
#define ROPE_DEF_BLOCK_LEN 512 |
| 10 |
|
| 11 |
typedef struct rpnode_s { |
| 12 |
struct rpnode_s *p; // child; at the bottom level, $p points to a string with the first 2 bytes giving the number of runs (#runs) |
| 13 |
uint64_t l:54, n:9, is_bottom:1; // $n and $is_bottom are only set for the first node in a bucket |
| 14 |
int64_t c[6]; // marginal counts |
| 15 |
} rpnode_t; |
| 16 |
|
| 17 |
typedef struct { |
| 18 |
int32_t max_nodes, block_len; // both MUST BE even numbers |
| 19 |
int64_t c[6]; // marginal counts |
| 20 |
rpnode_t *root; |
| 21 |
void *node, *leaf; // memory pool |
| 22 |
} rope_t; |
| 23 |
|
| 24 |
typedef struct { |
| 25 |
const rope_t *rope; // the rope |
| 26 |
const rpnode_t *pa[ROPE_MAX_DEPTH]; // parent nodes |
| 27 |
int ia[ROPE_MAX_DEPTH]; // index in the parent nodes |
| 28 |
int d; // the current depth in the B+-tree |
| 29 |
} rpitr_t; |
| 30 |
|
| 31 |
typedef struct { |
| 32 |
int beg; |
| 33 |
int64_t bc[6]; |
| 34 |
uint8_t *p; |
| 35 |
} rpcache_t; |
| 36 |
|
| 37 |
#ifdef __cplusplus |
| 38 |
extern "C" { |
| 39 |
#endif |
| 40 |
|
| 41 |
rope_t *rope_init(int max_nodes, int block_len); |
| 42 |
void rope_destroy(rope_t *rope); |
| 43 |
int64_t rope_insert_run(rope_t *rope, int64_t x, int a, int64_t rl, rpcache_t *cache); |
| 44 |
void rope_rank2a(const rope_t *rope, int64_t x, int64_t y, int64_t *cx, int64_t *cy); |
| 45 |
#define rope_rank1a(rope, x, cx) rope_rank2a(rope, x, -1, cx, 0) |
| 46 |
|
| 47 |
void rope_itr_first(const rope_t *rope, rpitr_t *i); |
| 48 |
const uint8_t *rope_itr_next_block(rpitr_t *i); |
| 49 |
|
| 50 |
void rope_print_node(const rpnode_t *p); |
| 51 |
void rope_dump(const rope_t *r, FILE *fp); |
| 52 |
rope_t *rope_restore(FILE *fp); |
| 53 |
|
| 54 |
#ifdef __cplusplus |
| 55 |
} |
| 56 |
#endif |
| 57 |
|
| 58 |
#endif |