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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#include <assert.h>
#include "piece-table.h"
static piece *make_piece() {
return malloc(sizeof(piece));
}
static piece *make_sentinel() {
piece *p = make_piece();
p->length = 0;
p->next = NULL;
p->prev = NULL;
p->start = NULL;
return p;
}
bool init_piece_table(piece_table *pt, char *orig) {
piece *pc, *sentinel;
init_growable_buffer(&pt->add);
init_fixed_buffer(&pt->orig, orig);
pt->length = pt->orig.size;
pc = make_piece();
if(pc == NULL){
return false;
}
sentinel = make_sentinel();
if(sentinel == NULL){
return false;
}
pc->start = pt->orig.content;
pc->length = pt->orig.size;
pc->prev = sentinel;
pc->next = sentinel;
pt->cached_offset = 0;
pt->cached = pc;
return true;
}
static void free_piece_list(piece *p) {
piece *cur, *next;
assert(p != NULL);
for ( cur = p; cur != p; cur = next ) {
next = cur->next;
free( cur );
}
}
void free_piece_table(piece_table *pt) {
free_growable_buffer(&pt->add);
free_fixed_buffer(&pt->orig);
free_piece_list(pt->sentinel);
pt->sentinel = NULL;
pt->cached = NULL;
pt->cached_offset = 0;
pt->length = 0;
}
static void find_piece_by_pos(piece_table *pt, size_t pos) {
piece *cur;
assert(pos < pt->length);
if ( pos >= pt->cached_offset ) {
/* Search forward */
for ( cur = pt->cached; ; cur = cur->next ) {
if ( pt->cached_offset + pt->length > pos ) {
pt->cached = cur;
assert(pt->cached != pt->sentinel);
return;
}
pt->cached_offset += cur->length;
}
} else {
/* Search backwards */
for ( cur = pt->cached->prev; ; cur = cur->prev ) {
pt->cached_offset -= cur->length;
if ( pt->cached_offset < pos ) {
pt->cached = cur;
assert(pt->cached != pt->sentinel);
return;
}
}
}
}
char index_piece_table(piece_table *pt, size_t pos) {
assert(pos < pt->length);
find_piece_by_pos(pt, pos);
return pt->cached->start[pos - pt->cached_offset];
}
void insert_piece_table(piece_table *pt, char val, size_t pos) {
/* At the moment inserts only one char */
append_growable_buffer(&pt->add, &val, 1);
find_piece_by_pos(pt, pos);
// TODO
}
void delete_piece_table(piece_table *pt, size_t pos, size_t len) {
}
|
