File: rope.h

package info (click to toggle)
fermi-lite 0.1-5
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 652 kB
  • sloc: ansic: 5,157; makefile: 63; sh: 13
file content (54 lines) | stat: -rw-r--r-- 1,428 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#ifndef ROPE_H_
#define ROPE_H_

#include <stdint.h>
#include <stdio.h>

#define ROPE_MAX_DEPTH 80
#define ROPE_DEF_MAX_NODES 64
#define ROPE_DEF_BLOCK_LEN 512

typedef struct rpnode_s {
	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)
	uint64_t l:54, n:9, is_bottom:1; // $n and $is_bottom are only set for the first node in a bucket
	int64_t c[6]; // marginal counts
} rpnode_t;

typedef struct {
	int32_t max_nodes, block_len; // both MUST BE even numbers
	int64_t c[6]; // marginal counts
	rpnode_t *root;
	void *node, *leaf; // memory pool
} rope_t;

typedef struct {
	const rope_t *rope; // the rope
	const rpnode_t *pa[ROPE_MAX_DEPTH]; // parent nodes
	int ia[ROPE_MAX_DEPTH]; // index in the parent nodes
	int d; // the current depth in the B+-tree
} rpitr_t;

typedef struct {
	int beg;
	int64_t bc[6];
	uint8_t *p;
} rpcache_t;

#ifdef __cplusplus
extern "C" {
#endif

	rope_t *rope_init(int max_nodes, int block_len);
	void rope_destroy(rope_t *rope);
	int64_t rope_insert_run(rope_t *rope, int64_t x, int a, int64_t rl, rpcache_t *cache);
	void rope_rank2a(const rope_t *rope, int64_t x, int64_t y, int64_t *cx, int64_t *cy);
	#define rope_rank1a(rope, x, cx) rope_rank2a(rope, x, -1, cx, 0)

	void rope_itr_first(const rope_t *rope, rpitr_t *i);
	const uint8_t *rope_itr_next_block(rpitr_t *i);
	
#ifdef __cplusplus
}
#endif

#endif