piece-table: fix memory and implement delete

2 files changed, 89 insertions, 22 deletions

diff --git a/src/piece-table.c b/src/piece-table.c
index be9f1b2..5f2b171 100644
--- a/src/piece-table.c
+++ b/src/piece-table.c
@@ -1,58 +1,83 @@
 #include <assert.h>
+#include <stdio.h>
 #include "piece-table.h"
 
+/*
+ * We probably should have a pool of pieces and go using them and deleting them
+ * from there instead of malloc/free but we are lazy
+ */
+static void print_string(char *str, size_t size) {
+    size_t i;
+    printf("\"");
+    for ( i=0; i < size; i++) {
+        printf("%c", str[i]);
+    }
+    printf("\"");
+}
+
+void print_piece_table (piece_table *pt) {
+    piece *cur;
+    printf("piece_table {");
+    printf("\n\toriginal: "); print_string(pt->orig.content, pt->orig.size);
+    printf("\n\tadd: "); print_string(pt->add.content, pt->add.used);
+    printf("\n\tlength: %ld", pt->length);
+    printf("\n\tpieces: ");
+    for ( cur = pt->sentinel->next; cur != pt->sentinel; cur = cur->next ) {
+        printf("\n\t\ttext: "); print_string(cur->start, cur->length);
+    }
+    printf("\n}\n");
+}
+
 static piece *make_piece() {
     return malloc(sizeof(piece));
 }
 
-static piece *make_sentinel() {
+static piece *make_piece_list() {
+    /* Makes a sentinel connected to itself in a ring*/
     piece *p = make_piece();
+    p->next = p;
+    p->prev = p;
     p->length = 0;
-    p->next   = NULL;
-    p->prev   = NULL;
     p->start  = NULL;
     return p;
 }
 
-bool init_piece_table(piece_table *pt, char *orig) {
-    piece *pc, *sentinel;
+void init_piece_table(piece_table *pt, char *orig) {
+    piece *pc;
 
     init_growable_buffer(&pt->add);
     init_fixed_buffer(&pt->orig, orig);
 
     pt->length = pt->orig.size;
 
+    pt->sentinel = make_piece_list();
+
     pc = make_piece();
-    if(pc == NULL){
-        return false;
-    }
-    sentinel = make_sentinel();
-    if(sentinel == NULL){
-        return false;
-    }
     pc->start = pt->orig.content;
     pc->length = pt->orig.size;
-    pc->prev = sentinel;
-    pc->next = sentinel;
+    pc->prev = pt->sentinel;
+    pc->next = pt->sentinel;
+
+    pt->sentinel->next = pc;
+    pt->sentinel->prev = pc;
 
     pt->cached_offset = 0;
     pt->cached = pc;
-    return true;
 }
 
 
 static void free_piece_list(piece *p) {
     piece *cur, *next;
     assert(p != NULL);
-    for ( cur = p; cur != p; cur = next ) {
+    for ( cur = p->next; cur != p; cur = next ) {
         next = cur->next;
         free( cur );
     }
+    free(cur);
 }
 
 void free_piece_table(piece_table *pt) {
     free_growable_buffer(&pt->add);
-    free_fixed_buffer(&pt->orig);
     free_piece_list(pt->sentinel);
     pt->sentinel = NULL;
     pt->cached = NULL;
@@ -67,7 +92,7 @@ static void find_piece_by_pos(piece_table *pt, size_t pos) {
     if ( pos >= pt->cached_offset ) {
         /* Search forward */
         for ( cur = pt->cached; ; cur = cur->next ) {
-            if ( pt->cached_offset + pt->length > pos ) {
+            if ( pt->cached_offset + cur->length > pos ) {
                 pt->cached = cur;
                 assert(pt->cached != pt->sentinel);
                 return;
@@ -93,15 +118,55 @@ char index_piece_table(piece_table *pt, size_t pos) {
     return pt->cached->start[pos - pt->cached_offset];
 }
 
+
+static void split_piece(piece *p, size_t pos) {
+    assert(pos < p->length);
+    assert(p->start != NULL); /* Not a sentinel piece */
+    assert(p->start != 0);    /* Not an empty piece (they should not exist) */
+    piece *second = make_piece();
+    second->length = p->length - pos;
+    p->length = pos;
+    second->next = p->next;
+    p->next = second;
+    second->prev = p;
+    second->start = p->start + pos;
+}
+
 void insert_piece_table(piece_table *pt, char val, size_t pos) {
     /* At the moment inserts only one char */
-    append_growable_buffer(&pt->add, &val, 1);
-
-    find_piece_by_pos(pt, pos);
+    // piece *cur;
+    assert(pos <= pt->length );
 
+    append_growable_buffer(&pt->add, &val, 1);
     // TODO
 }
 
 void delete_piece_table(piece_table *pt, size_t pos, size_t len) {
+    piece *cur, *next, *start, *end;
+    assert( pos + len <= pt->length );
 
+    if ( pos == 0) {
+        start = pt->sentinel;
+    } else {
+        find_piece_by_pos(pt, pos);
+        split_piece(pt->cached, pos - pt->cached_offset);
+        start = pt->cached;
+    }
+
+    if (pos + len == pt->length) {
+        end = pt->sentinel;
+    } else {
+        find_piece_by_pos(pt, pos + len);
+        split_piece(pt->cached, pos + len - pt->cached_offset);
+        end = pt->cached->next;
+    }
+
+    /* Free unneeded pieces */
+    for ( cur = start->next; cur != end ; cur = next ) {
+        next = cur->next;
+        free(cur);
+    }
+    start->next = end;
+    end->prev = start;
+    pt->length -= len;
 }
diff --git a/src/piece-table.h b/src/piece-table.h
index c053069..8a13ae3 100644
--- a/src/piece-table.h
+++ b/src/piece-table.h
@@ -22,11 +22,13 @@ typedef struct {
     size_t cached_offset;
 } piece_table;
 
-bool init_piece_table(piece_table *pt, char *orig);
+void init_piece_table(piece_table *pt, char *orig);
 void free_piece_table(piece_table *pt);
 
 char index_piece_table(piece_table *pt, size_t pos);
 void insert_piece_table(piece_table *pt, char val, size_t pos);
 void delete_piece_table(piece_table *pt, size_t pos, size_t len);
 
+void print_piece_table(piece_table *pt);
+
 #endif // PIECE_TABLE_H