Restart!

1 files changed, 367 insertions, 184 deletions

diff --git a/src/piece-table.c b/src/piece-table.c
index d77ffa0..c6e2375 100644
--- a/src/piece-table.c
+++ b/src/piece-table.c
@@ -1,233 +1,416 @@
-#include <assert.h>
+/* parc
+ * Copyright (C) 2025 Ekaitz Zarraga <ekaitz@elenq.tech>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
 #include <stdio.h>
-#include "piece-table.h"
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.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("\"");
+typedef struct
+  {
+    size_t len;
+    size_t size;
+    char *contents;
+  }
+text_buffer;
+
+typedef struct _piece
+  {
+    text_buffer *buffer;
+    size_t start;
+    size_t length;
+    struct _piece *next;
+    struct _piece *prev;
+  }
+piece;
+
+typedef struct _piece_buffer
+  {
+    size_t len;
+    size_t size;
+    struct _piece_buffer *next;
+    piece *start;
+  }
+piece_buffer;
+
+typedef struct _piece_table
+  {
+    text_buffer orig;
+    text_buffer add;
+    piece_buffer *pieces;
+    piece *sentinel;
+    piece *empty;
+    size_t length;
+
+    piece *cached;
+    size_t cached_offset;
+  }
+piece_table;
+
+
+void
+text_buffer_init (text_buffer *tb)
+{
+  tb->len = 0;
+  tb->size = 0;
+  tb->contents = NULL;
 }
 
-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);
+void
+text_buffer_append (text_buffer *tb, char c)
+{
+  if (tb->size == tb->len)
+    {
+      tb->contents = realloc(tb->contents, sizeof(*tb->contents) * tb->len*2);
     }
-    printf("\n\t cached_offset: %ld", pt->cached_offset);
-    printf("\n\t cached (piece-text):");
-        print_string(pt->cached->start, pt->cached->length);
-    printf("\n}\n");
+  tb->contents[tb->len++] = c;
 }
 
-static piece *make_piece() {
-    return malloc(sizeof(piece));
+char
+text_buffer_index (text_buffer *tb, size_t pos)
+{
+  assert(pos < tb->len);
+  return tb->contents[pos];
 }
 
-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->start  = NULL;
-    return p;
+void
+text_buffer_empty (text_buffer *tb)
+{
+  free(tb->contents);
+  text_buffer_init(tb);
 }
 
-void init_piece_table(piece_table *pt, char *orig) {
-    piece *pc;
-
-    init_growable_buffer(&pt->add);
-    init_fixed_buffer(&pt->orig, orig);
+void
+text_buffer_fill (text_buffer *tb, char *fill, size_t size)
+{
+  size_t i;
+  tb->len = size;
+  tb->size = size;
+  free(tb->contents);
+  tb->contents = malloc(sizeof(*tb->contents) * size);
+  for (i=0; i<size; i++)
+    {
+      tb->contents[i] = fill[i];
+    }
+}
 
-    pt->length = pt->orig.size;
+void
+text_buffer_free (text_buffer *tb)
+{
+  free(tb->contents);
+  text_buffer_init(tb);
+}
 
-    pt->sentinel = make_piece_list();
+
+piece_buffer *
+piece_buffer_create (size_t size)
+{
+  piece_buffer *pb;
+  size_t s = (sizeof(piece_buffer) + sizeof(piece) * size);
+  pb = malloc (s);
+  memset (pb, 0, s);
+  pb->start = (piece *)pb+1;
+  return pb;
+}
 
-    pc = make_piece();
-    pc->start = pt->orig.content;
-    pc->length = pt->orig.size;
-    pc->prev = pt->sentinel;
-    pc->next = pt->sentinel;
+piece *
+piece_buffer_bump (piece_buffer *pb)
+{
+  while (pb->next != NULL)
+    {
+      pb = pb->next;
+    }
 
-    pt->sentinel->next = pc;
-    pt->sentinel->prev = pc;
+  if (pb->len == pb->size)
+    {
+      pb->next = piece_buffer_create (1024);
+    }
+  return &pb->start[pb->len++];
+}
 
-    pt->cached_offset = 0;
-    pt->cached = pc;
+void
+piece_buffer_destroy (piece_buffer *pb)
+{
+  piece_buffer *next;
+  do
+    {
+      next = pb->next;
+      free (pb);
+      pb = next;
+    }
+  while (pb != NULL);
 }
 
 
-static void free_piece_list(piece *p) {
-    piece *cur, *next;
-    assert(p != NULL);
-    for ( cur = p->next; cur != p; cur = next ) {
-        next = cur->next;
-        free(cur);
-    }
-    free(cur);
+
+void
+piece_table_piece_mark_empty (piece_table *pt, piece *p)
+{
+  p->next = pt->empty;
+  pt->empty = p;
 }
 
-void free_piece_table(piece_table *pt) {
-    free_growable_buffer(&pt->add);
-    free_piece_list(pt->sentinel);
-    pt->sentinel = NULL;
-    pt->cached = NULL;
-    pt->cached_offset = 0;
-    pt->length = 0;
+piece *
+piece_table_piece_new (piece_table *pt)
+{
+  piece *p;
+  if (pt->empty != NULL)
+    {
+      p = pt->empty;
+      pt->empty = pt->empty->next;
+      return p;
+    }
+  /* TODO: Resize if needed */
+  return piece_buffer_bump (pt->pieces);
 }
 
 
-static void find_piece_by_pos(piece_table *pt, size_t pos) {
-    piece *cur;
-    assert(pos < pt->length);
-    if ( pos >= pt->cached_offset ) {
-        /* Search forward */
-        for ( cur = pt->cached; ; cur = cur->next ) {
-            if ( pt->cached_offset + cur->length > pos ) {
-                pt->cached = cur;
-                assert(pt->cached != pt->sentinel);
-                return;
+static piece *
+piece_table_piece_split(piece_table *pt, piece *p, size_t pos)
+{
+  /* Returns the first piece */
+  piece *second;
+  assert(pos < p->length);
+  assert(p->start != 0);    /* Not a sentinel piece */
+  assert(p->length != 0);   /* Not an empty piece (they should not exist) */
+  if ( pos == 0 )
+    {
+      return p->prev;
+    }
+  second = piece_buffer_bump (pt->pieces);
+  second->length = p->length - pos;
+  p->length = pos;
+  second->next = p->next;
+  p->next = second;
+  second->prev = p;
+  second->start = p->start + pos;
+  second->buffer = p->buffer;
+  return p;
+}
+
+static void
+piece_find_by_pos(piece_table *pt, size_t pos)
+{
+  piece *cur;
+  assert(pos < pt->length);
+  if ( pos >= pt->cached_offset )
+    {
+      /* Search forward */
+      for ( cur = pt->cached; ; cur = cur->next )
+        {
+          if ( pt->cached_offset + cur->length > pos )
+            {
+              pt->cached = cur;
+              assert(pt->cached != pt->sentinel);
+              return;
             }
-            pt->cached_offset += cur->length;
+          pt->cached_offset += cur->length;
         }
-    } else {
-        /* Search backwards */
-        for ( cur = pt->cached->prev; ; cur = cur->prev ) {
-            pt->cached_offset -= cur->length;
-            if ( pt->cached_offset < pos ) {
-                pt->cached = cur;
-                assert(pt->cached != pt->sentinel);
-                return;
+    }
+  else
+    {
+      /* Search backwards */
+      for ( cur = pt->cached->prev; ; cur = cur->prev )
+        {
+          pt->cached_offset -= cur->length;
+          if ( pt->cached_offset <= pos )
+            {
+              pt->cached = cur;
+              assert(pt->cached != pt->sentinel);
+              return;
             }
         }
     }
 }
 
-char index_piece_table(piece_table *pt, size_t pos) {
-    assert(pos < pt->length);
-    find_piece_by_pos(pt, pos);
-    return pt->cached->start[pos - pt->cached_offset];
-}
 
+void
+piece_table_insert (piece_table *pt, size_t pos, char *in, size_t len)
+{
+  piece *start, *end, *new;
+  size_t i;
+
+  assert( pos <= pt->length );
+  assert( len > 0 );
 
-static piece *split_piece(piece *p, size_t pos) {
-    /* Returns the first piece */
-    piece *second;
-    assert(pos < p->length);
-    assert(p->start != NULL); /* Not a sentinel piece */
-    assert(p->start != 0);    /* Not an empty piece (they should not exist) */
-    if ( pos == 0 ) {
-        return p->prev;
+  for (i = 0; i<len; i++)
+    {
+      text_buffer_append (&pt->add, in[i]);
     }
-    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;
-    return p;
-}
 
-void insert_piece_table(piece_table *pt, size_t pos, char *in, size_t in_len) {
-    piece *start, *end, *new;
+  if ( pos == 0 )
+    {
+      start = pt->sentinel;
+    }
+  else if ( pos == pt->length )
+    {
+      start = pt->sentinel->prev;
+      pt->cached_offset = pt->length - start->length;
+      pt->cached = start;
+    }
+  else
+    {
+      piece_find_by_pos(pt, pos);
+      start = piece_table_piece_split(pt, pt->cached, pos - pt->cached_offset);
+    }
+  end = start->next;
+
+  /* Update cache;
+   * If we insert before our cached piece, the offset is not up-to-date
+   * anymore.
+   */
+  if ( pt->cached_offset >= pos )
+    {
+      pt->cached = pt->cached->prev;
+      pt->cached_offset -= pt->cached->length;
+    }
 
-    assert( pos <= pt->length );
-    assert( in_len > 0 );
+  /* Make a new piece and insert it */
+  new = piece_buffer_bump(pt->pieces);
+  new->buffer = &pt->add;
+  new->start = pt->add.len - len;
+  new->length = len;
+
+  start->next = new;
+  new->prev = start;
+  new->next = end;
+  end->prev = new;
+  pt->length += len;
+}
 
-    append_growable_buffer(&pt->add, in, in_len);
+void
+piece_table_delete(piece_table *pt, size_t pos, size_t len)
+{
+  piece *cur, *next, *start, *end;
+  size_t off_start;
+  assert( pos + len <= pt->length );
+  assert( len > 0 );
+
+  if ( pos == 0 )
+    {
+      start = pt->sentinel;
+      off_start = 0;
+    }
+  else
+    {
+      piece_find_by_pos(pt, pos);
+      off_start = pt->cached_offset;
+      start = piece_table_piece_split(pt, pt->cached, pos - pt->cached_offset);
+    }
 
-    if ( pos == 0 ) {
-        start = pt->sentinel;
-    } else if ( pos == pt->length ) {
-        start = pt->sentinel->prev;
-        pt->cached_offset = pt->length - start->length;
-        pt->cached = start;
-    } else {
-        find_piece_by_pos(pt, pos);
-        start = split_piece(pt->cached, pos - pt->cached_offset);
+  if ( pos + len == pt->length )
+    {
+      end = pt->sentinel;
+    }
+  else
+    {
+      piece_find_by_pos(pt, pos + len);
+      end = piece_table_piece_split(pt, pt->cached, pos + len - pt->cached_offset)->next;
     }
-    end = start->next;
 
-    /* Update cache;
-     * If we insert before our cached piece, the offset is not up-to-date
-     * anymore.
-     */
-    if ( pt->cached_offset >= pos ) {
-        pt->cached = pt->cached->prev;
-        pt->cached_offset -= pt->cached->length;
+  /* Update cache to before the start */
+  if ( pt->cached_offset >= pos )
+    {
+      pt->cached = start;
+      pt->cached_offset = off_start;
     }
 
-    /* Optimization!
-     * Add in the end of the buffer, and the end of the piece: enlarge
-     */
-    if ( pt->add.used != 0 &&
-         pt->cached_offset + start->length == pos &&
-         pt->add.content + pt->add.used ==
-            start->start + start->length + in_len ) {
-        pt->length += in_len;
-        start->length += in_len;
-        return;
+  /* Free unneeded pieces */
+  for ( cur = start->next; cur != end ; cur = next )
+    {
+      next = cur->next;
+      /* Free the piece! */
+      piece_table_piece_mark_empty (pt, cur);
     }
-    /* Make a new piece and insert it */
-    new = make_piece();
-    new->start = pt->add.content + pt->add.used - in_len;
-    new->length = in_len;
 
-    start->next = new;
-    new->prev = start;
-    new->next = end;
-    end->prev = new;
-    pt->length += in_len;
+  start->next = end;
+  end->prev = start;
+  pt->length -= len;
 }
 
-void delete_piece_table(piece_table *pt, size_t pos, size_t len) {
-    piece *cur, *next, *start, *end;
-    size_t off_start;
-    assert( pos + len <= pt->length );
-    assert( len > 0 );
 
-    if ( pos == 0 ) {
-        start = pt->sentinel;
-        off_start = 0;
-    } else {
-        find_piece_by_pos(pt, pos);
-        off_start = pt->cached_offset;
-        start = split_piece(pt->cached, pos - pt->cached_offset);
-    }
+piece_table *
+piece_table_create (char *orig)
+{
+  piece *original;
+  piece_table * pt = malloc (sizeof (*pt));
+  size_t len = strlen(orig); /* obtain from the outside? */
+  pt->length = len;
+
+  /* Original buffer */
+  text_buffer_init(&pt->orig);
+  text_buffer_fill(&pt->orig, orig, len);
+
+  /* Add buffer */
+  text_buffer_init(&pt->add);
+
+  pt->pieces = piece_buffer_create (1024);
+
+  pt->sentinel = piece_buffer_bump (pt->pieces);
+  original = piece_buffer_bump (pt->pieces);
+  original->buffer = &pt->orig;
+  original->start = 0;
+  original->length = pt->length;
+  original->next = pt->sentinel;
+  original->prev = pt->sentinel;
+  pt->sentinel->next = original;
+  pt->sentinel->prev = original;
+
+  pt->empty = NULL;
+  pt->cached = NULL;
+  pt->cached_offset = 0;
+  return pt;
+}
+
+void
+piece_table_print (piece_table *pt)
+{
+  printf("orig: %s\n"
+         " add: %s\n", pt->orig.contents, pt->add.contents);
+}
 
-    if ( pos + len == pt->length ) {
-        end = pt->sentinel;
-    } else {
-        find_piece_by_pos(pt, pos + len);
-        end = split_piece(pt->cached, pos + len - pt->cached_offset)->next;
-    }
-
-    /* Update cache to before the start */
-    if ( pt->cached_offset >= pos ) {
-        pt->cached = start;
-        pt->cached_offset = off_start;
-    }
-
-    /* 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;
+void
+piece_table_destroy (piece_table *pt)
+{
+  text_buffer_free (&pt->orig);
+  text_buffer_free (&pt->add);
+  piece_buffer_destroy (pt->pieces);
+  free (pt);
+}
+
+char
+piece_table_index (piece_table *pt, size_t pos)
+{
+  assert(pos < pt->length);
+  piece_find_by_pos(pt, pos);
+  return text_buffer_index(pt->cached->buffer,
+                           pt->cached->start + pos - pt->cached_offset);
+}
+
+char *
+piece_table_to_string (piece_table *pt)
+{
+  size_t i;
+  char *ret = malloc (sizeof (*ret) * pt->length + 1);
+  for (i = 0; i < pt->length; i++)
+    {
+      ret[i] = piece_table_index(pt, i);
+    }
+  ret[i] = '\0';
+  return ret;
 }