Blocks data structure for text editor.

blocks.c

#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;
}
*/