From e4153a1990695daf33bcf8b0f004e201b721bb03 Mon Sep 17 00:00:00 2001 From: Curtis McEnroe Date: Sun, 18 Nov 2018 01:41:46 -0500 Subject: Add seeds of edi --- bin/edi/.gitignore | 4 ++ bin/edi/Makefile | 30 +++++++++++ bin/edi/buffer.c | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++++ bin/edi/edi.h | 86 +++++++++++++++++++++++++++++++ bin/edi/log.c | 63 +++++++++++++++++++++++ bin/edi/table.c | 136 +++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 464 insertions(+) create mode 100644 bin/edi/.gitignore create mode 100644 bin/edi/Makefile create mode 100644 bin/edi/buffer.c create mode 100644 bin/edi/edi.h create mode 100644 bin/edi/log.c create mode 100644 bin/edi/table.c diff --git a/bin/edi/.gitignore b/bin/edi/.gitignore new file mode 100644 index 00000000..c76928a8 --- /dev/null +++ b/bin/edi/.gitignore @@ -0,0 +1,4 @@ +*.o +*.t +edi +tags diff --git a/bin/edi/Makefile b/bin/edi/Makefile new file mode 100644 index 00000000..2d9128c0 --- /dev/null +++ b/bin/edi/Makefile @@ -0,0 +1,30 @@ +CFLAGS += -Wall -Wextra -Wpedantic +LDLIBS = -lcursesw + +OBJS += buffer.o +OBJS += log.o +OBJS += table.o + +TESTS += buffer.t +TESTS += table.t + +all: tags edi test + +tags: *.h *.c + ctags -w *.h *.c + +edi: $(OBJS) + $(CC) $(LDFLAGS) $(OBJS) $(LDLIBS) -o $@ + +$(OBJS): edi.h + +test: $(TESTS) + set -e; $(TESTS:%=./%;) + +.SUFFIXES: .t + +.c.t: + $(CC) $(CFLAGS) -DTEST $(LDFLAGS) $< $(LDLIBS) -o $@ + +clean: + rm -f tags edi $(OBJS) $(TESTS) diff --git a/bin/edi/buffer.c b/bin/edi/buffer.c new file mode 100644 index 00000000..e9422951 --- /dev/null +++ b/bin/edi/buffer.c @@ -0,0 +1,145 @@ +/* Copyright (C) 2018 Curtis McEnroe + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see . + */ + +#include +#include +#include +#include +#include + +#include "edi.h" + +static struct Block *blockAlloc(struct Block *prev, size_t cap) { + size_t size = sizeof(struct Block) + sizeof(wchar_t) * cap; + struct Block *block = malloc(size); + if (!block) err(EX_OSERR, "malloc"); + block->prev = prev; + return block; +} + +struct Buffer bufferAlloc(size_t cap) { + struct Block *block = blockAlloc(NULL, cap); + return (struct Buffer) { + .cap = cap, + .len = 0, + .slice = { block->chars, 0 }, + .block = block, + }; +} + +void bufferFree(struct Buffer *buf) { + struct Block *prev; + for (struct Block *it = buf->block; it; it = prev) { + prev = it->prev; + free(it); + } +} + +void bufferInsert(struct Buffer *buf) { + buf->slice.ptr = &buf->block->chars[buf->len]; + buf->slice.len = 0; +} + +void bufferAppend(struct Buffer *buf, wchar_t ch) { + if (buf->len == buf->cap) { + if (buf->slice.len == buf->cap) buf->cap *= 2; + struct Block *block = blockAlloc(buf->block, buf->cap); + memcpy(block->chars, buf->slice.ptr, sizeof(wchar_t) * buf->slice.len); + buf->len = buf->slice.len; + buf->slice.ptr = block->chars; + buf->block = block; + } + buf->block->chars[buf->len++] = ch; + buf->slice.len++; +} + +wchar_t *bufferDest(struct Buffer *buf, size_t len) { + if (buf->len + len > buf->cap) { + while (len > buf->cap) buf->cap *= 2; + buf->block = blockAlloc(buf->block, buf->cap); + buf->len = 0; + } + wchar_t *ptr = &buf->block->chars[buf->len]; + buf->slice.ptr = ptr; + buf->slice.len = len; + buf->len += len; + return ptr; +} + +#ifdef TEST +#include + +int main() { + struct Buffer buf = bufferAlloc(6); + + bufferInsert(&buf); + bufferAppend(&buf, L'A'); + bufferAppend(&buf, L'B'); + assert(!wcsncmp(L"AB", buf.slice.ptr, buf.slice.len)); + + bufferInsert(&buf); + bufferAppend(&buf, L'C'); + bufferAppend(&buf, L'D'); + assert(!wcsncmp(L"CD", buf.slice.ptr, buf.slice.len)); + + bufferInsert(&buf); + bufferAppend(&buf, L'E'); + bufferAppend(&buf, L'F'); + bufferAppend(&buf, L'G'); + bufferAppend(&buf, L'H'); + assert(!wcsncmp(L"EFGH", buf.slice.ptr, buf.slice.len)); + + bufferFree(&buf); + + buf = bufferAlloc(4); + bufferInsert(&buf); + bufferAppend(&buf, L'A'); + bufferAppend(&buf, L'B'); + bufferAppend(&buf, L'C'); + bufferAppend(&buf, L'D'); + bufferAppend(&buf, L'E'); + bufferAppend(&buf, L'F'); + assert(!wcsncmp(L"ABCDEF", buf.slice.ptr, buf.slice.len)); + bufferFree(&buf); + + buf = bufferAlloc(4); + + wchar_t *dest = bufferDest(&buf, 2); + dest[0] = L'A'; + dest[1] = L'B'; + assert(!wcsncmp(L"AB", buf.slice.ptr, buf.slice.len)); + + dest = bufferDest(&buf, 3); + dest[0] = L'C'; + dest[1] = L'D'; + dest[2] = L'E'; + assert(!wcsncmp(L"CDE", buf.slice.ptr, buf.slice.len)); + + bufferFree(&buf); + + buf = bufferAlloc(4); + dest = bufferDest(&buf, 6); + dest[0] = L'A'; + dest[1] = L'B'; + dest[2] = L'C'; + dest[3] = L'D'; + dest[4] = L'E'; + dest[5] = L'F'; + assert(!wcsncmp(L"ABCDEF", buf.slice.ptr, buf.slice.len)); + bufferFree(&buf); +} + +#endif diff --git a/bin/edi/edi.h b/bin/edi/edi.h new file mode 100644 index 00000000..77c9d734 --- /dev/null +++ b/bin/edi/edi.h @@ -0,0 +1,86 @@ +/* Copyright (C) 2018 Curtis McEnroe + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see . + */ + +#include +#include + +struct Span { + size_t at, to; +}; + +static inline struct Span spanNext(struct Span span, size_t len) { + return (struct Span) { span.to, span.to + len }; +} + +struct Slice { + const wchar_t *ptr; + size_t len; +}; + +struct Buffer { + size_t cap; + size_t len; + struct Slice slice; + struct Block { + struct Block *prev; + wchar_t chars[]; + } *block; +}; + +struct Buffer bufferAlloc(size_t cap); +void bufferFree(struct Buffer *buf); +void bufferInsert(struct Buffer *buf); +void bufferAppend(struct Buffer *buf, wchar_t ch); +wchar_t *bufferDest(struct Buffer *buf, size_t len); + +struct Table { + size_t len; + struct Slice slices[]; +}; + +struct Table *tableInsert(const struct Table *prev, size_t at, struct Slice slice); +struct Table *tableDelete(const struct Table *prev, struct Span del); + +struct Log { + size_t cap; + size_t len; + size_t index; + struct State { + struct Table *table; + size_t prev; + size_t next; + } *states; +}; + +struct Log logAlloc(size_t cap); +void logFree(struct Log *log); +void logPush(struct Log *log, struct Table *table); + +static inline struct Table *logTable(struct Log *log) { + return log->states[log->index].table; +} +static inline void logPrev(struct Log *log) { + log->index = log->states[log->index].prev; +} +static inline void logNext(struct Log *log) { + log->index = log->states[log->index].next; +} +static inline void logBack(struct Log *log) { + if (log->index) log->index--; +} +static inline void logFore(struct Log *log) { + if (log->index + 1 < log->len) log->index++; +} diff --git a/bin/edi/log.c b/bin/edi/log.c new file mode 100644 index 00000000..2c146aaf --- /dev/null +++ b/bin/edi/log.c @@ -0,0 +1,63 @@ +/* Copyright (C) 2018 Curtis McEnroe + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see . + */ + +#include +#include +#include +#include +#include + +#include "edi.h" + +struct Log logAlloc(size_t cap) { + assert(cap); + struct State *states = malloc(sizeof(*states) * cap); + if (!states) err(EX_OSERR, "malloc"); + states[0] = (struct State) { + .table = NULL, + .prev = 0, + .next = 0, + }; + return (struct Log) { + .cap = cap, + .len = 1, + .index = 0, + .states = states, + }; +} + +void logFree(struct Log *log) { + for (size_t i = 0; i < log->len; ++i) { + free(log->states[i].table); + } + free(log->states); +} + +void logPush(struct Log *log, struct Table *table) { + if (log->len == log->cap) { + log->cap *= 2; + log->states = realloc(log->states, sizeof(*log->states) * log->cap); + if (!log->states) err(EX_OSERR, "realloc"); + } + size_t next = log->len++; + log->states[next] = (struct State) { + .table = table, + .prev = log->index, + .next = next, + }; + log->states[log->index].next = next; + log->index = next; +} diff --git a/bin/edi/table.c b/bin/edi/table.c new file mode 100644 index 00000000..318f1ac2 --- /dev/null +++ b/bin/edi/table.c @@ -0,0 +1,136 @@ +/* Copyright (C) 2018 Curtis McEnroe + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see . + */ + +#include +#include +#include +#include + +#include "edi.h" + +static struct Table *alloc(size_t cap) { + size_t size = sizeof(struct Table) + sizeof(struct Slice) * cap; + struct Table *table = malloc(size); + if (!table) err(EX_OSERR, "malloc"); + table->len = 0; + return table; +} + +struct Table *tableInsert(const struct Table *prev, size_t at, struct Slice slice) { + if (!prev || !prev->len) { + struct Table *next = alloc(1); + next->slices[next->len++] = slice; + return next; + } + + struct Table *next = alloc(prev->len + 2); + struct Span span = { 0, 0 }; + for (size_t i = 0; i < prev->len; ++i) { + span = spanNext(span, prev->slices[i].len); + if (span.at == at) { + next->slices[next->len++] = slice; + next->slices[next->len++] = prev->slices[i]; + } else if (span.at < at && span.to > at) { + next->slices[next->len++] = (struct Slice) { + prev->slices[i].ptr, + at - span.at, + }; + next->slices[next->len++] = slice; + next->slices[next->len++] = (struct Slice) { + &prev->slices[i].ptr[at - span.at], + prev->slices[i].len - (at - span.at), + }; + } else { + next->slices[next->len++] = prev->slices[i]; + } + } + if (span.to == at) { + next->slices[next->len++] = slice; + } + return next; +} + +struct Table *tableDelete(const struct Table *prev, struct Span del) { + if (!prev || !prev->len) return alloc(0); + + struct Table *next = alloc(prev->len + 1); + struct Span span = { 0, 0 }; + for (size_t i = 0; i < prev->len; ++i) { + span = spanNext(span, prev->slices[i].len); + if (span.at >= del.at && span.to <= del.to) { + (void)prev->slices[i]; + } else if (span.at < del.at && span.to > del.to) { + next->slices[next->len++] = (struct Slice) { + prev->slices[i].ptr, + del.at - span.at, + }; + next->slices[next->len++] = (struct Slice) { + &prev->slices[i].ptr[del.to - span.at], + prev->slices[i].len - (del.to - span.at), + }; + } else if (span.at < del.at && span.to > del.at) { + next->slices[next->len++] = (struct Slice) { + prev->slices[i].ptr, + del.at - span.at, + }; + } else if (span.at < del.to && span.to > del.to) { + next->slices[next->len++] = (struct Slice) { + &prev->slices[i].ptr[del.to - span.at], + prev->slices[i].len - (del.to - span.at), + }; + } else { + next->slices[next->len++] = prev->slices[i]; + } + } + return next; +} + +#ifdef TEST +#include + +static struct Span span(size_t at, size_t to) { + return (struct Span) { at, to }; +} + +static struct Slice slice(const wchar_t *str) { + return (struct Slice) { str, wcslen(str) }; +} + +static int eq(const struct Table *table, const wchar_t *str) { + for (size_t i = 0; i < table->len; ++i) { + if (wcsncmp(str, table->slices[i].ptr, table->slices[i].len)) { + return 0; + } + str = &str[table->slices[i].len]; + } + return 1; +} + +int main() { + struct Table *abc = tableInsert(NULL, 0, slice(L"ABC")); + assert(eq(abc, L"ABC")); + + assert(eq(tableInsert(abc, 0, slice(L"D")), L"DABC")); + assert(eq(tableInsert(abc, 3, slice(L"D")), L"ABCD")); + assert(eq(tableInsert(abc, 1, slice(L"D")), L"ADBC")); + + assert(eq(tableDelete(abc, span(0, 1)), L"BC")); + assert(eq(tableDelete(abc, span(2, 3)), L"AB")); + assert(eq(tableDelete(abc, span(1, 2)), L"AC")); + assert(eq(tableDelete(abc, span(0, 3)), L"")); +} + +#endif -- cgit 1.4.1