a Gap Buffer, in C

gap.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "gap.h"

#define DEFAULT_SIZE    4

#define TRACE(x) do{x;}while(0)

struct GapBuffer {
    char *b;        // The buffer itself
    unsigned int a;       // The size allocated for the buffer
    unsigned int s, e;    // The start and end indexes of the gap
};

static GapBuffer *create(unsigned int a) {
    GapBuffer *g = malloc(sizeof *g);
    if(!g)
        return NULL;
    g->a = a;
    g->b = malloc(g->a + 1);
    if(!g->b) {
        free(g);
        return NULL;
    }
    g->b[g->a] = '\0';
    g->s = 0;
    g->e = g->a;

    return g;
}

GapBuffer *gb_create() {
    return create(DEFAULT_SIZE);
}

GapBuffer *gb_make(const char *s) {
    unsigned int len = strlen(s);
    unsigned int a = DEFAULT_SIZE;
    while(a < len) a <<= 1;
    GapBuffer *g = create(a);
    memcpy(g->b, s, len);
    g->s = len;
    return g;
}

void gb_free(GapBuffer *g) {
    free(g->b);
    free(g);
}

static int grow(GapBuffer *g, unsigned int new_a) {
    unsigned int len = g->a - g->e;
    char *new_b = realloc(g->b, new_a + 1);
    if(!new_b)
        return 0;
    new_b[new_a] = '\0';
    g->b = new_b;
    memmove(g->b + new_a - len, g->b + g->e, len);
    g->e = new_a - len;
    g->a = new_a;
    return 1;
}

int gb_insert(GapBuffer *g, char c) {
    TRACE(printf("insert '%c'\n", c < ' '?'*':c));
    assert(g->s <= g->e);
    if(g->s == g->e) {
        if(!grow(g, g->a << 1))
            return 0;
    }
    g->b[g->s++] = c;
    return 1;
}

int gb_insert_str(GapBuffer *g, const char *s) {
    unsigned int len = strlen(s);
    unsigned int gs = g->e - g->s;
    if(len > gs) {
        unsigned int a = g->a << 1;
        unsigned int n = g->a - gs;
        while(n + len > a)
            a <<= 1;
        if(!grow(g, a))
            return 0;
    }
    memcpy(g->b + g->s, s, len);
    g->s += len;

    return 1;
}

void gb_backspace(GapBuffer *g) {
    TRACE(printf("backspace\n"));
    if(g->s > 0) {
        g->s--;
    }
}

void gb_delete(GapBuffer *g) {
    TRACE(printf("delete\n"));
    if(g->e < g->a) {
        g->e++;
    }
}

void gb_left(GapBuffer *g) {
    TRACE(printf("left\n"));
    if(g->s > 0) {
        g->b[--g->e] = g->b[--g->s];
    }
}

void gb_right(GapBuffer *g) {
    TRACE(printf("right\n"));
    if(g->e < g->a) {
        g->b[g->s++] = g->b[g->e++];
    }
}

void gb_home(GapBuffer *g) {
    TRACE(printf("home\n"));
    while(g->s > 0) {
        if(g->b[g->s - 1] == '\n')
            break;
        g->b[--g->e] = g->b[--g->s];
    }
}

void gb_end(GapBuffer *g) {
    TRACE(printf("end\n"));
    while(g->e < g->a) {
        if(g->b[g->e] == '\n')
            break;
        g->b[g->s++] = g->b[g->e++];
    }
}

void gb_set_cursor(GapBuffer *g, unsigned int pos) {
    TRACE(printf("cursor %u\n", pos));
    unsigned int len = g->e - g->s;
    if(pos > g->a - len)
        pos = g->a - len;
    if(pos < g->s) {
        len = g->s - pos;
        memmove(g->b + g->e - len, g->b + pos, len);
        g->s -= len;
        g->e -= len;
    } else {
        len = pos - g->s;
        memmove(g->b + g->s, g->b + g->e, len);
        g->s += len;
        g->e += len;
    }
}

unsigned int gb_get_cursor(GapBuffer *g) {
    return g->s;
}

unsigned int gb_get_column(GapBuffer *g) {
    unsigned int c = 0, i = g->s;
    while(i > 0 && g->b[i-1] != '\n') {
        i--;
        c++;
    }
    return c;
}

unsigned int gb_get_line(GapBuffer *g) {
    unsigned int r = 0, i = g->s;
    while(i > 0) {
        if(g->b[i] == '\n')
            r++;
        i--;
    }
    return r;
}

void gb_up_n(GapBuffer *g, unsigned int n) {
    TRACE(printf("up %u\n", n));
    unsigned int c = 0, i = g->s;
    while(i > 0 && g->b[i-1] != '\n') {
        i--;
        c++;
    }
    if(i == 0)
        return;
    while(n > 0 && --i > 0) {
        if(g->b[i-1] == '\n')
            n--;
    }
    while(c > 0) {
        if(g->b[i] == '\n')
            break;
        i++;
        c--;
    }
    gb_set_cursor(g, i);
}

void gb_up(GapBuffer *g) {
    gb_up_n(g, 1);
}

void gb_down_n(GapBuffer *g, unsigned int n) {
    unsigned int c = 0, i = g->s;
    while(i > 0 && g->b[i-1] != '\n') {
        i--;
        c++;
    }
    i = g->e;
    while(n > 0) {
        if(g->b[i] == '\n')
            n--;
        i++;
        if(i == g->a)
            return;
    }
    while(c > 0 && i < g->a) {
        if(g->b[i] == '\n')
            break;
        i++;
        c--;
    }
    gb_set_cursor(g, i - (g->e - g->s));
}

void gb_down(GapBuffer *g) {
    gb_down_n(g, 1);
}

void gb_bof(GapBuffer *g) {
    TRACE(printf("bof\n"));
    if(g->s > 0) {
        unsigned int len = g->s;
        memmove(g->b + g->e - len, g->b, len);
        g->s -= len;
        g->e -= len;
    }
}

void gb_eof(GapBuffer *g) {
    TRACE(printf("eof\n"));
    unsigned int pos = g->a - (g->e - g->s);
    if(g->s < pos) {
        unsigned int len = pos - g->s;
        memmove(g->b + g->s, g->b + g->e, len);
        g->s += len;
        g->e += len;
    }
}

const char *gb_text(GapBuffer *g) {
    gb_eof(g);
    g->b[g->s] = '\0';
    return g->b;
}

unsigned int gb_strlen(GapBuffer *g) {
    return g->a - (g->e - g->s);
}

char gb_char(GapBuffer *g, unsigned int i) {
    if(i >= g->s) {
        i += g->e - g->s;
        if(i >= g->a)
            return '\0';
    }
    return g->b[i];
}

#ifdef TEST

void gb_show(GapBuffer *g) {
    unsigned int i;
    for(i = 0; i < g->a; i++) {
        if(i >= g->s && i < g->e)
            putchar('_');
        else if(g->b[i] < ' ')
            putchar('*');
        else
            putchar(g->b[i]);
    }
    putchar('\n');
    fflush(stdout);
}

int main(int argc, char *argv[]) {
    GapBuffer *g = gb_create();
#if 1

    gb_free(g);
    g = gb_make("line 1\nline 2\nline 3\nline 4");

    gb_set_cursor(g, 17);
    gb_show(g);
    printf("line: %u; col: %u\n", gb_get_line(g), gb_get_column(g));

    /*
    gb_set_cursor(g, 2);
    gb_show(g);
    printf("line: %u; col: %u\n", gb_get_line(g), gb_get_column(g));

    gb_set_cursor(g, 14);
    gb_show(g);
    printf("line: %u; col: %u\n", gb_get_line(g), gb_get_column(g));
    */

    gb_down_n(g, 2);
    gb_show(g);
    printf("line: %u; col: %u\n", gb_get_line(g), gb_get_column(g));

    gb_down(g);
    gb_show(g);
    printf("line: %u; col: %u\n", gb_get_line(g), gb_get_column(g));

    gb_end(g);
    gb_show(g);
    printf("line: %u; col: %u\n", gb_get_line(g), gb_get_column(g));

    /*
    gb_up_n(g,6);
    gb_show(g);
    printf("line: %u; col: %u\n", gb_get_line(g), gb_get_column(g));
    */


#elif 0
    gb_insert(g, 'A');
    gb_show(g);
    gb_insert(g, 'B');
    gb_show(g);
    gb_insert(g, 'C');
    gb_left(g);
    gb_left(g);
    gb_show(g);
    gb_insert_str(g, "Hello World To You");
    gb_show(g);
    gb_insert_str(g, "------------");
    gb_show(g);
#else
    gb_show(g);
    gb_insert(g, 'A');
    gb_show(g);
    gb_insert(g, 'B');
    gb_show(g);
    gb_insert(g, 'C');
    gb_show(g);
    gb_insert(g, 'D');
    gb_show(g);
    gb_backspace(g);
    gb_show(g);
    gb_insert(g, 'D');
    gb_show(g);
    gb_insert(g, 'E');
    gb_show(g);
    gb_left(g);
    gb_show(g);
    gb_insert(g, 'F');
    gb_show(g);
    gb_left(g);
    gb_left(g);
    gb_left(g);
    gb_show(g);
    gb_insert(g, 'G');
    gb_show(g);
    gb_insert(g, '\n');
    gb_show(g);
    gb_insert(g, 'H');
    gb_show(g);
    gb_insert(g, 'I');
    gb_show(g);
    gb_right(g);
    gb_show(g);
    gb_delete(g);
    gb_show(g);
    gb_home(g);
    gb_show(g);
    gb_left(g);
    gb_show(g);
    gb_home(g);
    gb_show(g);
    gb_end(g);
    gb_show(g);
    gb_right(g);
    gb_show(g);
    gb_end(g);
    gb_show(g);
    gb_set_cursor(g, 2);
    gb_show(g);
    gb_set_cursor(g, 4);
    gb_show(g);
    gb_set_cursor(g, 19);
    gb_show(g);
    gb_set_cursor(g, 0);
    gb_show(g);
    gb_set_cursor(g, 5);
    gb_show(g);
    gb_bof(g);
    gb_show(g);
    gb_eof(g);
    gb_show(g);

    printf("text: \"%s\"\n", gb_text(g));

    gb_set_cursor(g, 5);
    printf("strlen: %u\n", gb_strlen(g));
#endif

    /*
    int i;
    for(i = 0; i < gb_strlen(g); i++)
        printf("char at(%2d): '%c'\n", i,  gb_char(g, i));
    */

    gb_free(g);
    return 0;
}
#endif

gap.h

/*
 * https://en.wikipedia.org/wiki/Gap_buffer
 * https://www.codeproject.com/Articles/20910/Generic-Gap-Buffer - old, but had some nice pictures
 */

typedef struct GapBuffer GapBuffer;

GapBuffer *gb_create();

GapBuffer *gb_make(const char *s);

void gb_free(GapBuffer *g);

int gb_insert(GapBuffer *g, char c);

int gb_insert_str(GapBuffer *g, const char *s);

void gb_backspace(GapBuffer *g);

void gb_delete(GapBuffer *g);

void gb_left(GapBuffer *g);

void gb_right(GapBuffer *g);

void gb_up(GapBuffer *g);

void gb_down(GapBuffer *g);

void gb_up_n(GapBuffer *g, unsigned int n);

void gb_down_n(GapBuffer *g, unsigned int n);

void gb_home(GapBuffer *g);

void gb_end(GapBuffer *g);

void gb_set_cursor(GapBuffer *g, unsigned int pos);

unsigned int gb_get_cursor(GapBuffer *g);

unsigned int gb_get_column(GapBuffer *g);

unsigned int gb_get_line(GapBuffer *g);

void gb_bof(GapBuffer *g);

void gb_eof(GapBuffer *g);

const char *gb_text(GapBuffer *g);

unsigned int gb_strlen(GapBuffer *g);

char gb_char(GapBuffer *g, unsigned int i);

Makefile

CC=gcc
CFLAGS=-c -Wall -DTEST
LDFLAGS=-lm

EXECUTABLE=gap

BUILD=debug

# Detect operating system:
# More info: http://stackoverflow.com/q/714100
ifeq ($(OS),Windows_NT)
  EXECUTABLE:=$(EXECUTABLE).exe
  LDFLAGS += -mwindows
endif

ifeq ($(BUILD),debug)
  # Debug
  CFLAGS += -O0 -g
  LDFLAGS +=
else
  # Release mode
  CFLAGS += -O2 -DNDEBUG
  LDFLAGS += -s
endif

SOURCES=gap.c
OBJECTS=$(SOURCES:.c=.o)

all: $(EXECUTABLE)

debug:
	make BUILD=debug

$(EXECUTABLE): $(OBJECTS)
	$(CC) $^ $(LDFLAGS) -o $@

.c.o:
	$(CC) $(CFLAGS) $< -o $@

gap.o: gap.c gap.h

.PHONY : clean

clean:
	-rm -f $(EXECUTABLE)
	-rm -f *.o