piece-chain

Research & implementation of a Piece Chain
git clone git://src.gearsix.net/piece-chain.git
Log | Files | Refs | Atom | README

commit 07c375538c76517bf86691133c563cc55388a3c9
parent 91ebb9e95268e8a39d3bb7b6643c1e53420d7fa3
Author: gearsix <gearsix@tuta.io>
Date:   Thu, 14 Jul 2022 01:29:30 +0100

buffer.c: fixes & cleanups to insert & deletes; added pfind.

test_buffer.c: improved test coverage, now cleanup still done on
assertion failure.

Diffstat:
Mbuffer.c | 113++++++++++++++++++++++++++++++++++++++++++++++++-------------------------------
Mbuffer.h | 3+--
Mtest.c | 2+-
Mtest_buffer.c | 83+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------
4 files changed, 138 insertions(+), 63 deletions(-)

diff --git a/buffer.c b/buffer.c @@ -1,4 +1,3 @@ - #include "buffer.h" #include <stdio.h> @@ -79,20 +78,44 @@ static Piece *palloc() returned. */ static Piece *psplit(Piece *p, long int offset) { - Piece *q = palloc(); + Piece *q = p; if (offset > 0 && offset <= (int)p->len) { + q = palloc(); memcpy(q, p, sizeof(Piece)); - q->off += offset; q->len -= p->len = offset; q->next = p->next; q->prev = p; p->next = q; if (q->next) q->next->prev = q; + } else if (offset == 0) { + q = palloc(); + q->next = p; + p->prev = q; + } + return q; +} - p = q; +/* pfind will find the `Piece` which contains index `pos`. + The search starts from `p`, where the index is `idx`. + `p` will be set to the found `Piece`. + The new index will be returned. */ +static size_t pfind(Piece **ptr, size_t idx, size_t pos) +{ + Piece *p = *ptr; + if (pos >= idx) { + while (pos >= idx + p->len && p->next) { + idx += p->len; + p = p->next; + } + } else { + do { + p = p->prev; + idx -= p->len; + } while (pos < idx && p->prev); } - return p; + *ptr = p; + return idx; } struct Buffer *bufinit(FILE *read, FILE *append) @@ -124,41 +147,28 @@ void buffree(Buffer *b) Piece *bufidx(Buffer *b, size_t pos) { - size_t idx = b->idx, offset; - Piece *p = b->pos; - - if (pos >= idx) { - while (pos >= idx + p->len && p->next) { - idx += p->len; - p = p->next; - } - } else { - do { - p = p->prev; - idx -= p->len; - } while(pos > idx && p->prev); - } + size_t offset, idx = pfind(&b->pos, b->idx, pos); - if (idx == pos) { - b->idx = idx; - b->pos = p; - } else { + if (idx != pos || idx == 0) { offset = (idx >= pos) ? idx - pos : pos - idx; - b->pos = psplit(p, offset); + b->pos = psplit(b->pos, offset); + if (!b->pos->prev) b->tail = b->pos; if (!b->pos->next) b->head = b->pos; - b->idx = pos; } - + + b->idx = pos; return b->pos; } size_t bufins(Buffer *b, size_t pos, const char *s) { const size_t slen = strlen(s); - Piece *p = palloc(); + Piece *p; b->pos = bufidx(b, pos)->prev; - + if (!b->pos) b->pos = b->tail; + + p = palloc(); p->f = b->append; p->off = ftell(b->append); p->len = slen; @@ -170,22 +180,36 @@ size_t bufins(Buffer *b, size_t pos, const char *s) fprintf(b->append, "%s", s); CATCH(ferror(b->append), "bufins: write to append", { pfree(p); p = 0; }); + if (p != 0) { b->idx += slen; + b->size += slen; b->pos = p->next; } - return (p == 0) ? b->size : (b->size += slen); + return b->size; } -size_t bufdel(Buffer *b, size_t pos, size_t num) +size_t bufdel(Buffer *b, size_t pos, int num) { + size_t tmp; Piece *pre, *post; - size_t end = pos+num; - pre = bufidx(b, (pos == 0) ? 0 : pos-1); - post = bufidx(b, (end > b->size) ? b->size : end)->next; - if (!post) post = b->head; + if (num < 0) { + if ((int)pos-num < 0) + num = pos; + else { + tmp = abs(num); + num = pos; + pos = (tmp > pos) ? 0 : tmp; + } + } + + if (pos+num > b->size) num = b->size - pos; + + pre = bufidx(b, pos)->prev; + if (!pre) pre = b->tail; + post = bufidx(b, pos+num); pre->next = post; post->prev = pre; @@ -201,18 +225,19 @@ int bufout(Buffer *b, FILE *f) Piece *p = b->tail; do { - if ((size_t)ftell(p->f) != p->off) + if (p->len > 0 && p->f) { + if ((size_t)ftell(p->f) != p->off) fseek(p->f, p->off, SEEK_SET); - n = 0; - do { - buf[0] = '\0'; - fread(buf, 1, p->len, p->f); - CATCH(ferror(p->f), "bufout: fread failed", break); - fsiz += fwrite(buf, 1, p->len, f); - CATCH(ferror(f), "bufout: fwrite failed", break); - } while (p->len - (BUFSIZ*n++) > BUFSIZ); - + n = 0; + do { + buf[0] = '\0'; + fread(buf, 1, p->len, p->f); + CATCH(ferror(p->f), "bufout: fread failed", break); + fsiz += fwrite(buf, 1, p->len, f); + CATCH(ferror(f), "bufout: fwrite failed", break); + } while (p->len - (BUFSIZ*n++) > BUFSIZ); + } p = p->next; } while(p); diff --git a/buffer.h b/buffer.h @@ -47,9 +47,8 @@ bufins(Buffer *b, size_t pos, const char *s); /* Removed all pieces from index `pos` to `pos+num`. `pos` and `pos+num` are found using `bufidx`. */ size_t -bufdel(Buffer *b, size_t pos, size_t num); +bufdel(Buffer *b, size_t pos, int num); /* writes all data in `b` to `f`. */ int bufout(Buffer *b, FILE *f); - diff --git a/test.c b/test.c @@ -6,6 +6,6 @@ int main() { test_buffer(); - puts("success - no assertions failed"); + puts("no assertions failed"); return 0; } diff --git a/test_buffer.c b/test_buffer.c @@ -2,6 +2,7 @@ #include "buffer.h" #include <stdio.h> +#include <signal.h> #include <string.h> #include <assert.h> @@ -10,7 +11,7 @@ static Buffer *B; static FILE *in_f; static const char *in_p = "in.txt", *in_buf = "hello world"; static FILE *out_f; -static const char *out_p = "out.txt", *out_buf = "hey buddy!"; +static const char *out_p = "out.txt", *out_buf = "Hey buddy!"; static FILE *tmp_f; static const char *tmp_p = "tmp.txt"; @@ -22,20 +23,25 @@ static void test_bufidx(); static void test_bufins(); static void test_bufdel(); static void test_bufins1(); +static void test_bufdel1(); +static void test_bufins2(); static void test_bufout(); void test_buffer() { printf("test_buffer: "); - setup(); + setup(); + signal(SIGABRT, setdown); test_bufinit(); test_bufidx(); test_bufins(); test_bufdel(); test_bufins1(); + test_bufdel1(); + test_bufins2(); test_bufout(); - setdown(); + setdown(0); puts("success"); } @@ -43,7 +49,7 @@ static void debugprint() { Piece *p = B->tail; - printf("Buf: %p\n", (void *)B); + printf("\nBuf: %p\n", (void *)B); printf("size: %d, index: %d\n", (int)B->size, (int)B->idx); do { printf("%p", (void *)p); @@ -69,15 +75,17 @@ static void setup() if (ferror(tmp_f)) perror("fopen tmp"); } -static void setdown() +static void setdown(int n) { buffree(B); fclose(out_f); fclose(in_f); fclose(tmp_f); - remove(in_p); - remove(out_p); - remove(tmp_p); + if (n != SIGABRT) { + remove(in_p); + remove(out_p); + remove(tmp_p); + } } static void test_bufinit() @@ -115,8 +123,8 @@ static void test_bufidx() static void test_bufins() { - const char *buf = "y"; - const size_t idx = 2, len = strlen(buf); + const char *buf = "y"; size_t idx = 2; + const size_t len = strlen(buf); bufins(B, idx, buf); @@ -133,11 +141,12 @@ static void test_bufins() static void test_bufdel() { - const size_t idx = 3, len = 9; + size_t idx = 3; int len = B->size+1; + const size_t bsiz = B->size; bufdel(B, idx, len); - - assert(B->size == strlen(in_buf)+1-len); /* +1 for bufins */ + + assert(B->size == bsiz-(bsiz-idx)); assert(B->idx == idx); assert(B->pos == B->head); assert(B->tail->next->next == B->pos); @@ -151,8 +160,8 @@ static void test_bufdel() static void test_bufins1() { - const char *buf = " buddy!"; - const size_t idx = 3, len = strlen(buf), bsiz = B->size; + size_t idx = 3; const char *buf = " buddy!"; + const size_t len = strlen(buf), bsiz = B->size; bufins(B, idx, buf); @@ -168,6 +177,49 @@ static void test_bufins1() assert(B->pos->next == NULL); } +static void test_bufdel1() +{ + size_t idx = 0; int len = 1; + const size_t bsiz = B->size; + + bufdel(B, idx, len); + + assert(B->size == bsiz - len); + assert(B->idx == idx); + + assert(B->pos->prev == B->tail); + assert(B->pos->prev->f == 0); + assert(B->pos->prev->off == 0); + assert(B->pos->prev->len == 0); + assert(B->pos->prev->prev == 0); + assert(B->pos->prev->next == B->pos); + + assert(B->pos->f == B->read); + assert(B->pos->off == 1); + assert(B->pos->len == (size_t)len); + assert(B->pos->prev == B->tail); + assert(B->pos->next->next->next == B->head); +} + +static void test_bufins2() +{ + const char *buf = "H"; const size_t idx = 0; + size_t len = strlen(buf), bsiz = B->size; + + bufins(B, idx, buf); + + assert(B->size == bsiz + len); + assert(B->idx == idx + len); + assert(B->pos == B->tail->next->next); + + assert(B->pos->prev == B->tail->next); + assert(B->pos->prev->f == B->append); + assert(B->pos->prev->off == 8); + assert(B->pos->prev->len == 1); + assert(B->pos->prev->prev == B->tail); + assert(B->pos->prev->next == B->pos); +} + static void test_bufout() { size_t n = 0; @@ -176,7 +228,6 @@ static void test_bufout() bufout(B, out_f); rewind(out_f); n = fread(buf, 1, BUFSIZ, out_f); - assert(n > 0); assert(strcmp(buf, out_buf) == 0); }