From dfb7d4b2bd6a5bd7a2bf63927c84c46bf88ba379 Mon Sep 17 00:00:00 2001
From: Ekaitz Zarraga <ekaitz@elenq.tech>
Date: Sun, 3 Mar 2024 22:21:15 +0100
Subject: piece-table: fix memory and implement delete
---
src/piece-table.c | 107 +++++++++++++++++++++++++++++++++++++++++++-----------
src/piece-table.h | 4 +-
2 files changed, 89 insertions(+), 22 deletions(-)
(limited to 'src')
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
--
cgit v1.2.3