Last active
April 21, 2018 20:43
-
-
Save hadrianw/4447052496bd019ea4a8eea7fef868af to your computer and use it in GitHub Desktop.
Blocks data structure for text editor.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define _XOPEN_SOURCE | |
#include <assert.h> | |
#include <stdbool.h> | |
#include <stddef.h> | |
#include <stdint.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <unistd.h> | |
#define MIN(a, b) ((a) < (b) ? (a) : (b)) | |
#define MAX(a, b) ((a) < (b) ? (b) : (a)) | |
#define LEN(a) (sizeof(a) / sizeof(a)[0]) | |
#define TEST(X) void TEST_##X(void) | |
#define BLOCK_SIZE 4096 | |
typedef struct { | |
int len; // 0..BLOCK_SIZE | |
int nlines; // 0..BLOCK_SIZE | |
char (*buf)[BLOCK_SIZE]; // != NULL | |
} block_t; | |
typedef struct { | |
int nblocks; // 1..INT_MAX | |
int64_t nlines // 0..INT64_MAX | |
block_t *block; // != NULL | |
} buffer_t; | |
typedef struct { | |
int blk; // 0..INT_MAX | |
int off; // 0..BLOCK_SIZE | |
} address_t; | |
// for undo use buffer wide offsets | |
typedef struct { | |
address_t start; | |
address_t end; | |
} range_t; | |
void | |
buffer_init(buffer_t *buffer, int nblocks) | |
{ | |
// FIXME: check for NULL / xrealloc | |
buffer->block = calloc(nblocks, sizeof(*buffer->block)); | |
for(int i = 0; i < nblocks; i++) { | |
// FIXME: check for NULL / xmalloc | |
buffer->block[i].buf = malloc(BLOCK_SIZE); | |
} | |
buffer->nlines = 0; | |
buffer->nblocks = nblocks; | |
} | |
void | |
buffer_free(buffer_t *buffer) | |
{ | |
for(int i = 0; i < buffer->nblocks; i++) { | |
free(buffer->block[i]); | |
} | |
free(buffer->block); | |
} | |
#define LEN_TO_NBLOCKS(x) (((x) + BLOCK_SIZE - 1) / BLOCK_SIZE) | |
void | |
buffer_copy_head(buffer_t *buffer, range_t *rng, block_t *blk) | |
{ | |
memcpy(blk->buf, buffer->block[rng->start.blk].buf, rng->start.off); | |
} | |
int | |
buffer_read(buffer_t *buffer, range_t *rng, char *buf, int len) | |
{ | |
return buffer_read_blocks(buffer, rng, &(block_t){.len = len, .buf = buf}, 1); | |
} | |
int | |
buffer_read_blocks(buffer_t *buffer, range_t *rng, block_t *blk, int nblk) | |
{ | |
} | |
int | |
buffer_read_fd(buffer_t *buffer, range_t *rng, int fd) | |
{ | |
int nsel = rng->end.blk - rng->start.blk + 1; | |
int nmod = 0; // 0..LEN(blk) | |
struct iovec iov[8]; | |
block_t blk[LEN(iov)+1]; | |
buffer_t buf = { | |
.nblocks = LEN(blk), | |
.block = blk | |
}; | |
for(int i = 0; i < LEN(blk); i++) { | |
// FIXME: check for NULL / xmalloc | |
blk[i].buf = malloc(BLOCK_SIZE); | |
blk[i].len = BLOCK_SIZE; | |
} | |
// copy the head of the first selected block | |
memcpy(blk[0].buf, buffer->block[rng->start.blk].buf, rng->start.off); | |
iov[0].iov_base = &blk[0].buf[rng->start.off]; | |
iov[0].iov_len = BLOCK_SIZE - rng->start.off; | |
for(int i = 1; i < LEN(iov); i++) { | |
iov[i].iov_base = blk[i].buf; | |
iov[i].iov_len = BLOCK_SIZE; | |
} | |
ssize_t len = readv(fd, &iov, LEN(iov)); | |
if(len < 0) { | |
goto out; | |
} | |
int total = rng->start.off + len; // 0..BLOCK_SIZE*LEN(blk) | |
blk[nmod-1].len = total % BLOCK_SIZE; | |
nmod = LEN_TO_NBLOCKS(total); | |
int tail_len = buffer->block[rng->end.blk].len - rng->end.off; | |
int tail_front_len = MIN(tail_len, BLOCK_SIZE - last_len); | |
memcpy( | |
&blk[nmod-1].buf[blk[nmod-1].len], | |
&buffer->block[rng->end.blk].buf[rng->end.off], | |
tail_front_len | |
); | |
total += tail_front_len; | |
nmod = LEN_TO_NBLOCKS(total); | |
int tail_back_len = tail_len - tail_font_len; | |
memcpy( | |
&blk[nmod-1].buf, | |
&buffer->block[rng->end.blk].buf[rng->end.off+tail_front_len], | |
tail_back_len | |
); | |
total += tail_back_len; | |
nmod = LEN_TO_NBLOCKS(total); | |
blk[nmod-1].len = total % BLOCK_SIZE; | |
// if last block too small | |
if(rng->end.blk < buffer->nblocks-1 && | |
blk[nmod-1].len < BLOCK_SIZE/2 | |
) { | |
// take some from the right buffer | |
block_t *right = &buffer->block[rng->end.blk+1]; | |
if(blk[nmod-1].len + right->len > BLOCK_SIZE) { | |
int right_back_len = (blk[nmod-1].len + right->len) / 2; | |
int right_front_len = right->len - right_front_len; | |
// take the front of the right buffer | |
memcpy( | |
&blk[nmod-1].buf[blk[nmod-1].len], | |
right->buf, | |
right_front_len | |
); | |
blk[nmod-1].len += right_front_len; | |
// shift the back of the right buffer | |
memmove( | |
right->buf, | |
&right->buf[right_front_len], | |
right_back_len | |
); | |
right->len = right_back_len; | |
} else { | |
// join the right block | |
memcpy( | |
&blk[nmod-1].buf[last_len], | |
right->buf, | |
right->len | |
); | |
blk[nmod-1].len += right->len; | |
// FIXME: undo does not need the right buffer | |
nsel++; | |
} | |
} | |
// TODO: undo | |
int sel_end = rng->start.blk + nsel; | |
int mod_end = rng->start.blk + nblk; | |
if(nmod < nsel) { | |
for(int i = mod_end; i < sel_end; i++) { | |
free(buffer->block[i]); | |
} | |
memmove( | |
&buffer->block[mod_end], | |
&buffer->block[sel_end], | |
(buffer->nblocks - sel_end) * sizeof(buffer->block[0]) | |
); | |
} | |
buffer->nblocks = buffer->nblocks - nblk + new_nblk; | |
// FIXME: check for NULL / xreallocarray | |
buffer->block = reallocarray(buffer->block, | |
buffer->nblocks, sizeof(buffer->block[0]) | |
); | |
if(nmod > nsel) { | |
memmove( | |
&buffer->block[mod_end], | |
&buffer->block[sel_end], | |
(buffer->nblocks - sel_end) * sizeof(buffer->block[0]) | |
); | |
for(int i = sel_end; i < mod_end; i++) { | |
buffer->block[i].len = 0; | |
buffer->block[i].nlines = 0; | |
// FIXME: check for NULL / xmalloc | |
buffer->block[i].buf = malloc(BLOCK_SIZE); | |
} | |
} | |
memcpy(&buffer->block[rng->start.blk], blk, nmod * sizeof(blk[0])); | |
out: | |
for(int i = nmod; i < LEN(blk); i++) { | |
free(blk[i].buf); | |
} | |
return len; | |
} | |
int | |
buffer_write(buffer_t *buffer, range_t *rng, int fd) | |
{ | |
struct iovec iov[8]; | |
int nsel = rng->end.blk - rng->start.blk + 1; | |
int niov = MIN(nsel, LEN(iov)); | |
iov[0].iov_base = &blk[0].buf[rng->start.off]; | |
iov[0].iov_len = buffer->block[rng->start.blk].len - rng->start.off; | |
for(int i = 1; i < niov; i++) { | |
iov[i].iov_base = buffer->block[i].buf; | |
iov[i].iov_len = buffer->block[i].len; | |
} | |
if(nsel <= LEN(iov)) { | |
iov[nsel-1].iov_len = rng->end.off; | |
} | |
ssize_t len = writev(fd, &iov, niov); | |
if(len < 0) { | |
return -1; | |
} | |
int rest = len; | |
for(int i = 0; i < niov; i++) { | |
rest -= iov[i].iov_len; | |
if(rest <= 0) { | |
// FIXME: is it correct? | |
if(i > 0) { | |
rng->start.blk += i; | |
rng->start.off = 0; | |
} | |
rng->start.off += iov[i].iov_len + rest; | |
// FIXME: should here be return len? | |
break; | |
} | |
} | |
// FIXME: should here be an error? | |
return len; | |
} | |
int | |
main(int argc, char *argv[]) | |
{ | |
return 0; | |
} | |
/* | |
// Get a block position for an address in a buffer | |
// Potential optimalizations: | |
// - begin search from block index and line number | |
// could be useful having just return a block index for a line number | |
// additional parameters: uint32_t start_block, uint64_t start_nr | |
// - search from the end for adr->nr > buffer->nlines/2 | |
block_pos_t | |
buffer_address_to_block_pos(buffer_t *buffer, address_t *adr) | |
{ // 2= [0]_1_2__ 0= _____ 2= __3__4_ | |
uint64_t nr = 0; | |
for(uint32_t i = 0; i < buffer->nblocks; i++) { | |
nr += buffer->block[i].nlines; | |
if(nr >= adr.nr) { | |
char *prev_line = buffer->block[i].data.buf; | |
char *line = buffer->block[i].data.buf; | |
uint16_t rest = buffer->block[i].len; | |
for(nr -= buffer->block[i].nlines; ; nr++) { | |
line = memchr(prev_line, '\n', rest); | |
if(line != NULL) { | |
line++; | |
rest -= line - prev_line; | |
} else { | |
assert(1 || "broken line count cache"); | |
return BLOCK_NOT_FOUND; | |
} | |
if(nr == adr.nr) { | |
uint16_t off; | |
if(rest <= adr.off) { | |
off = //this block | |
} | |
return (block_pos_t){i, off}; | |
} | |
line = prev_line; | |
} | |
return BLOCK_NOT_FOUND; | |
} | |
} | |
return BLOCK_NOT_FOUND; | |
} | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment