Debian Codegraph @

bwa-apache2/rope.h

raw
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