One efficient approach is to split the buffer into chunks, for example
Code:
#define CHUNK_SIZE 16384
struct chunk {
struct chunk *prev;
struct chunk *next;
struct slines *cache; /* For ncurses stuff, explained below */
size_t lines;
size_t chars;
unsigned char data[CHUNK_SIZE];
};
Each chunk contains lines complete lines.
You'll keep a pointer to the current chunk, as well as the number of lines prior to the current chunk. This way you only need to work on one chunk at a time.
Another option is to use an array of lines.
For ncurses, especially if you intend to do syntax highlighting (adding attributes like color to arbitrary characters), a combination of the two would work well. For the current chunk(s), you construct an array of ncurses attribute-and-character strings, one per line:
Code:
struct slines {
struct chunk *owner;
size_t lines;
size_t *line_offset;
size_t *line_length;
size_t cchars;
cchar_t *buffer;
};
Instead of allocating each line separately, the structure contains one common buffer, which each line references. (For syntax highlighting, each chunk may also need some kind of "state" cookie, which I omitted above, so that the highlighter only needs to examine the current chunk to produce the current ncurses highlighted buffer.)
The line lengths are needed if you allow horizontal scrolling. (A line might be shorter than the current horizontal scrolling offset, in which case you don't print anything to that particular line.)
When modifying data, you can either keep a separate buffer for the current line (or paragraph), or modify the display buffer (contents in the slines structure) directly. When the user moves the cursor, this buffer is then used to reconstruct the original chunk or chunks.
These are the techniques we used when the machines had limited resources (memory and CPU power).
Nowadays, you can easily get away with just
Code:
struct line {
size_t max_length;
size_t length;
cchar_t data[];
};
struct file {
size_t max_lines;
size_t num_lines;
struct line **line;
};
When you read data from the file, you construct the character-and-attribute data for each line into a struct line, with a pointer to each struct stored in struct file.
If you add a new line, you make sure you have room for one more line pointer in struct file, and use memmove() to move the following lines one down. You remove a line by freeing the pointer to its struct line, and using memmove() to move the following lines one up.
If the contents are human-readable text, then the natural unit is not line, but a paragraph. Other than that, it's pretty much the same.
