[vte] [ring] Port to VteStream

[Behdad Esfahbod <behdad src gnome org>]

commit a88338e07429a5ce1fc4cb081448333c699f7f23
Author: Behdad Esfahbod <behdad behdad org>
Date:   Sat Sep 12 19:40:02 2009 -0400

    [ring] Port to VteStream
    
    Not optimized, simple file-based non-compact storage

 src/ring.c           |  668 +++++++++++---------------------------------------
 src/ring.h           |   48 ++---
 src/vtestream-base.h |   31 +++-
 src/vtestream-file.h |   17 +-
 src/vtestream.h      |    8 +
 5 files changed, 201 insertions(+), 571 deletions(-)
---
diff --git a/src/ring.c b/src/ring.c
index f3510e3..3b94e9b 100644
--- a/src/ring.c
+++ b/src/ring.c
@@ -25,510 +25,128 @@
 
 #include <string.h>
 
-#define VTE_RING_CHUNK_COMPACT_BYTES	(1024*1024 - 4 * sizeof (void *)) /* hopefully we get some nice mmapped region */
-
-
 /*
- * VteCompactRowData: Compact representation of a row
- */
-
-typedef struct _VteRowStorage {
-	guint8 charbytes : 3;
-	guint8 attrbytes : 3;
-} VteRowStorage;
-ASSERT_STATIC (sizeof (VteRowStorage) == 1);
-
-typedef struct _VteCompactRowData {
-	guchar *bytes;
-	guint16 len;
-	VteRowAttr attr;
-	VteRowStorage storage;
-} VteCompactRowData;
-ASSERT_STATIC (sizeof (VteCompactRowData) <= 2 * sizeof (void *));
-
-
-static guint
-_width (guint32 x)
-{
-	if (!x)
-		return 0;
-	if (G_LIKELY (x < 0x100))
-		return 1;
-	if (x < 0x10000)
-		return 2;
-	return 4;
-}
-
-static VteRowStorage
-_vte_row_storage_compute (const VteRowData *row)
-{
-	guint i;
-	const guint32 *c = (const guint32 *) row->cells;
-	guint len = row->len;
-	guint32 basic_attrs = basic_cell.i.attr;
-	guint32 chars = 0, attrs = 0;
-	VteRowStorage storage;
-
-	for (i = 0; i < len; i++) {
-		chars |= *c;
-		c++;
-		attrs |= *c ^ basic_attrs;
-		c++;
-	}
-
-	storage.charbytes = _width (chars);
-	storage.attrbytes = _width (attrs);
-
-	return storage;
-}
-
-static inline guint
-_vte_row_storage_get_size (VteRowStorage storage, guint len)
-{
-	return len * (storage.charbytes + storage.attrbytes);
-}
-
-static guchar *
-_store (guchar *to, const guint32 *from, guint32 xor, guint width, guint len)
-{
-	guint i;
-
-	switch (width) {
-        default: break;
-	case 1:
-		for (i = 0; i < len; i++) {
-			guint8 c = *from ^ xor;
-			*to++ = c;
-			from += 2;
-		}
-		break;
-	case 2:
-		for (i = 0; i < len; i++) {
-			guint16 c = *from ^ xor;
-			*to++ = c >> 8;
-			*to++ = c;
-			from += 2;
-		}
-		break;
-	case 4:
-		for (i = 0; i < len; i++) {
-			guint8 c = *from ^ xor;
-			*to++ = c >> 24;
-			*to++ = c >> 16;
-			*to++ = c >> 8;
-			*to++ = c;
-			from += 2;
-		}
-		break;
-	}
-
-	return to;
-}
-
-static const guchar *
-_fetch (const guchar *from, guint32 *to, guint32 xor, guint width, guint len)
-{
-	guint i;
-
-	switch (width) {
-        default:
-		for (i = 0; i < len; i++) {
-			guint32 c = 0;
-			*to = c ^ xor;
-			to += 2;
-		}
-		break;
-	case 1:
-		for (i = 0; i < len; i++) {
-			guint32 c = 0;
-			c += *from++;
-			*to = c ^ xor;
-			to += 2;
-		}
-		break;
-	case 2:
-		for (i = 0; i < len; i++) {
-			guint32 c = 0;
-			c += *from++ << 8;
-			c += *from++;
-			*to = c ^ xor;
-			to += 2;
-		}
-		break;
-	case 4:
-		for (i = 0; i < len; i++) {
-			guint8 c = 0;
-			c += *from++ << 24;
-			c += *from++ << 16;
-			c += *from++ << 8;
-			c += *from++;
-			*to = c ^ xor;
-			to += 2;
-		}
-		break;
-	}
-
-	return from;
-}
-
-static void
-_vte_compact_row_init (VteCompactRowData *compact_row, VteRowStorage storage, guchar *bytes)
-{
-	compact_row->len = 0;
-	compact_row->storage = storage;
-	compact_row->bytes = bytes;
-}
-
-static void
-_vte_compact_row_data_compact (VteCompactRowData *compact_row, const VteRowData *row)
-{
-	guint32 basic_attrs = basic_cell.i.attr;
-	guchar *to = compact_row->bytes;
-	VteRowStorage storage = compact_row->storage;
-
-	_vte_debug_print(VTE_DEBUG_RING, "Compacting row: %d %d.\n", storage.charbytes, storage.attrbytes);
-
-	compact_row->len = row->len;
-	compact_row->attr = row->attr;
-
-	to = _store (to,     (const guint32 *) row->cells, 0,           storage.charbytes, row->len);
-	to = _store (to, 1 + (const guint32 *) row->cells, basic_attrs, storage.attrbytes, row->len);
-}
-
-static void
-_vte_compact_row_data_uncompact (const VteCompactRowData *compact_row, VteRowData *row)
-{
-	guint32 basic_attrs = basic_cell.i.attr;
-	const guchar *from = compact_row->bytes;
-	VteRowStorage storage = compact_row->storage;
-
-	_vte_debug_print(VTE_DEBUG_RING, "Uncompacting row: %d %d.\n", storage.charbytes, storage.attrbytes);
-
-	row->attr = compact_row->attr;
-	if (G_UNLIKELY (!_vte_row_data_ensure (row, compact_row->len))) {
-		row->len = 0;
-		return;
-	}
-	row->len = compact_row->len;
-
-	from = _fetch (from,     (guint32 *) row->cells, 0,           storage.charbytes, compact_row->len);
-	from = _fetch (from, 1 + (guint32 *) row->cells, basic_attrs, storage.attrbytes, compact_row->len);
-}
-
-
-/*
- * VteRingChunk: A chunk of the scrollback buffer ring
+ * VteRing: A buffer ring
  */
 
+#ifdef VTE_DEBUG
 static void
-_vte_ring_chunk_init (VteRingChunk *chunk)
-{
-	memset (chunk, 0, sizeof (*chunk));
-}
-
-static void
-_vte_ring_chunk_insert_chunk_before (VteRingChunk *chunk, VteRingChunk *new)
-{
-	new->prev_chunk = chunk->prev_chunk;
-	new->next_chunk = chunk;
-
-	if (chunk->prev_chunk)
-		chunk->prev_chunk->next_chunk = new;
-	chunk->prev_chunk = new;
-}
-
-
-/* Compact chunk type */
-
-typedef struct _VteRingChunkCompact {
-	VteRingChunk base;
-
-	guint offset;
-	guint bytes_left;
-	guchar *cursor; /* move backward */
-	union {
-		VteCompactRowData rows[1];
-		guchar data[1];
-	} p;
-} VteRingChunkCompact;
-
-static VteRingChunk *
-_vte_ring_chunk_new_compact (guint start)
+_vte_ring_validate (VteRing * ring)
 {
-	VteRingChunkCompact *chunk;
-
-	_vte_debug_print(VTE_DEBUG_RING, "Allocating compact chunk\n");
-
-	chunk = g_malloc (VTE_RING_CHUNK_COMPACT_BYTES);
-
-	_vte_ring_chunk_init (&chunk->base);
-	chunk->base.type = VTE_RING_CHUNK_TYPE_COMPACT;
-	chunk->offset = chunk->base.start = chunk->base.end = start;
-
-	chunk->bytes_left = VTE_RING_CHUNK_COMPACT_BYTES - G_STRUCT_OFFSET (VteRingChunkCompact, p);
-	chunk->cursor = chunk->p.data + chunk->bytes_left;
+	g_assert(ring != NULL);
+	_vte_debug_print(VTE_DEBUG_RING,
+			" Delta = %u, Length = %u, Max = %u, Writable = %u.\n",
+			ring->start, ring->end - ring->start,
+			ring->max, ring->end - ring->writable);
 
-	return &chunk->base;
-}
+	g_assert (ring->last_page <= ring->start);
+	g_assert (ring->start <= ring->writable);
+	g_assert (ring->writable <= ring->end);
 
-static void
-_vte_ring_chunk_compact_free (VteRingChunkCompact *bchunk)
-{
-	_vte_debug_print(VTE_DEBUG_RING, "Freeing compact chunk\n");
-	g_assert (bchunk->base.type == VTE_RING_CHUNK_TYPE_COMPACT);
-	g_free (bchunk);
+	g_assert (ring->end - ring->start <= ring->max);
+	g_assert (ring->end - ring->writable <= ring->mask);
 }
+#else
+#define _vte_ring_validate(ring) G_STMT_START {} G_STMT_END
+#endif
 
-static inline VteCompactRowData *
-_vte_ring_chunk_compact_index (VteRingChunkCompact *chunk, guint position)
-{
-	return &chunk->p.rows[position - chunk->offset];
-}
-
-static gboolean
-_vte_ring_chunk_compact_push_head_row (VteRingChunk *bchunk, VteRowData *row)
-{
-	VteRingChunkCompact *chunk = (VteRingChunkCompact *) bchunk;
-	VteRowStorage storage;
-	VteCompactRowData *compact_row;
-	guint compact_size, total_size;
-
-	storage = _vte_row_storage_compute (row);
-
-	compact_size = _vte_row_storage_get_size (storage, row->len);
-	total_size = compact_size + sizeof (chunk->p.rows[0]);
-
-	if (chunk->bytes_left < total_size)
-		return FALSE;
-
-	chunk->cursor -= compact_size;
-	chunk->bytes_left -= total_size;
-
-	compact_row = _vte_ring_chunk_compact_index (chunk, chunk->base.end);
-	_vte_compact_row_init (compact_row, storage, chunk->cursor);
-	_vte_compact_row_data_compact (compact_row, row);
-
-	/* Truncate rows of no information */
-	if (!compact_size)
-		compact_row->len = 0;
-
-	chunk->base.end++;
-	return TRUE;
-}
 
-static void
-_vte_ring_chunk_compact_pop_head_row (VteRingChunk *bchunk, VteRowData *row)
+void
+_vte_ring_init (VteRing *ring, guint max_rows)
 {
-	VteRingChunkCompact *chunk = (VteRingChunkCompact *) bchunk;
-	const VteCompactRowData *compact_row;
-	guint compact_size, total_size;
-
-	compact_row = _vte_ring_chunk_compact_index (chunk, chunk->base.end - 1);
-
-	_vte_compact_row_data_uncompact (compact_row, row);
-
-	compact_size = _vte_row_storage_get_size (compact_row->storage, row->len);
-	total_size = compact_size + sizeof (chunk->p.rows[0]);
+	_vte_debug_print(VTE_DEBUG_RING, "New ring %p.\n", ring);
 
-	chunk->base.end--;
-	chunk->cursor += compact_size;
-	chunk->bytes_left += total_size;
-}
+	ring->max = MAX (max_rows, 3);
 
+	ring->mask = 31;
+	ring->array = g_malloc0 (sizeof (ring->array[0]) * (ring->mask + 1));
 
-/* Writable chunk type */
+	ring->cell_stream = _vte_file_stream_new ();
+	ring->row_stream = _vte_file_stream_new ();
 
-static void
-_vte_ring_chunk_init_writable (VteRingChunkWritable *chunk)
-{
-	_vte_ring_chunk_init (&chunk->base);
+	_vte_row_data_init (&ring->cached_row);
+	ring->cached_row_num = (guint) -1;
 
-	chunk->base.type = VTE_RING_CHUNK_TYPE_WRITABLE;
-	chunk->mask = 31;
-	chunk->array = g_malloc0 (sizeof (chunk->array[0]) * (chunk->mask + 1));
+	_vte_ring_validate(ring);
 }
 
-static void
-_vte_ring_chunk_fini_writable (VteRingChunkWritable *chunk)
+void
+_vte_ring_fini (VteRing *ring)
 {
 	guint i;
-	g_assert (chunk->base.type == VTE_RING_CHUNK_TYPE_WRITABLE);
-
-	for (i = 0; i <= chunk->mask; i++)
-		_vte_row_data_fini (&chunk->array[i]);
-
-	g_free (chunk->array);
-	chunk->array = NULL;
-}
-
-static inline VteRowData *
-_vte_ring_chunk_writable_index (VteRingChunkWritable *chunk, guint position)
-{
-	return &chunk->array[position & chunk->mask];
-}
-
-static void
-_vte_ring_chunk_writable_ensure_tail (VteRingChunkWritable *chunk)
-{
-	guint new_mask, old_mask, i, end;
-	VteRowData *old_array, *new_array;;
-
-	if (G_LIKELY (chunk->base.start + chunk->mask > chunk->base.end))
-		return;
 
-	_vte_debug_print(VTE_DEBUG_RING, "Enlarging writable array.\n");
-
-	old_mask = chunk->mask;
-	old_array = chunk->array;
-
-	chunk->mask = (chunk->mask << 1) + 1;
-	chunk->array = g_malloc0 (sizeof (chunk->array[0]) * (chunk->mask + 1));
-
-	new_mask = chunk->mask;
-	new_array = chunk->array;
+	for (i = 0; i <= ring->mask; i++)
+		_vte_row_data_fini (&ring->array[i]);
 
-	end = chunk->base.start + old_mask + 1;
-	for (i = chunk->base.start; i < end; i++)
-		new_array[i & new_mask] = old_array[i & old_mask];
-
-	g_free (old_array);
-}
+	g_free (ring->array);
 
-static VteRowData *
-_vte_ring_chunk_writable_insert (VteRingChunkWritable *chunk, guint position)
-{
-	guint i;
-	VteRowData *row, tmp;
-
-	tmp = *_vte_ring_chunk_writable_index (chunk, chunk->base.end);
-	for (i = chunk->base.end; i > position; i--)
-		*_vte_ring_chunk_writable_index (chunk, i) = *_vte_ring_chunk_writable_index (chunk, i - 1);
-	*_vte_ring_chunk_writable_index (chunk, position) = tmp;
-
-	row = _vte_ring_chunk_writable_index(chunk, position);
-	_vte_row_data_clear (row);
-	chunk->base.end++;
+	g_object_unref (ring->cell_stream);
+	g_object_unref (ring->row_stream);
 
-	return row;
+	_vte_row_data_fini (&ring->cached_row);
 }
 
 static void
-_vte_ring_chunk_writable_remove (VteRingChunkWritable *chunk, guint position)
+_vte_ring_freeze_row (VteRing *ring, guint position, const VteRowData *row)
 {
-	guint i;
+	gsize cell_position;
 	VteRowData tmp;
 
-	tmp = *_vte_ring_chunk_writable_index (chunk, position);
-	for (i = position; i < chunk->base.end - 1; i++)
-		*_vte_ring_chunk_writable_index (chunk, i) = *_vte_ring_chunk_writable_index (chunk, i + 1);
-	*_vte_ring_chunk_writable_index (chunk, chunk->base.end - 1) = tmp;
-
-	if (chunk->base.end > chunk->base.start)
-		chunk->base.end--;
-}
-
+	_vte_debug_print (VTE_DEBUG_RING, "Freezing row %d.\n", position);
 
-/* Generic chunks */
+	cell_position = _vte_stream_append (ring->cell_stream, (const char *) row->cells, row->len * sizeof (row->cells[0]));
 
-static void
-_vte_ring_chunk_free (VteRingChunk *chunk)
-{
-	g_assert (chunk->type == VTE_RING_CHUNK_TYPE_COMPACT);
-
-	_vte_ring_chunk_compact_free ((VteRingChunkCompact *) chunk);
+	tmp = *row;
+	tmp.cells = GSIZE_TO_POINTER (cell_position);
+	_vte_stream_append (ring->row_stream, (const char *) &tmp, sizeof (tmp));
 }
 
-
-/*
- * VteRing: A buffer ring
- */
-
-#ifdef VTE_DEBUG
 static void
-_vte_ring_validate (VteRing * ring)
+_vte_ring_thaw_row (VteRing *ring, guint position, VteRowData *row)
 {
-	VteRingChunk *chunk;
+	VteCell *cells;
+	gsize cell_position;
 
-	g_assert(ring != NULL);
-	_vte_debug_print(VTE_DEBUG_RING,
-			" Delta = %u, Length = %u, Max = %u, Writable = %u.\n",
-			ring->tail->start, ring->head->base.end - ring->tail->start,
-			ring->max, ring->head->base.end - ring->head->base.start);
+	_vte_debug_print (VTE_DEBUG_RING, "Thawing row %d.\n", position);
 
-	g_assert(ring->head->base.end - ring->tail->start <= ring->max);
+	cells = row->cells;
+	_vte_stream_read (ring->row_stream, position * sizeof (*row), (char *) row, sizeof (*row));
+	cell_position = GPOINTER_TO_SIZE (row->cells);
+	row->cells = cells;
 
-	g_assert(ring->head->base.start <= ring->head->base.end);
-	chunk = ring->head->base.prev_chunk;
-	while (chunk) {
-		g_assert(chunk->start < chunk->end);
-		g_assert(chunk->end == chunk->next_chunk->start);
-		chunk = chunk->prev_chunk;
+	if (G_UNLIKELY (!_vte_row_data_ensure (row, row->len))) {
+		row->len = 0;
+		return;
 	}
-}
-#else
-#define _vte_ring_validate(ring) G_STMT_START {} G_STMT_END
-#endif
-
-
-void
-_vte_ring_init (VteRing *ring, guint max_rows)
-{
-	ring->max = MAX (max_rows, 2);
-
-	_vte_row_data_init (&ring->cached_row);
-	ring->cached_row_num = (guint) -1;
 
-	ring->tail = ring->cursor = &ring->head->base;
-
-	_vte_ring_chunk_init_writable (ring->head);
-
-	_vte_debug_print(VTE_DEBUG_RING, "New ring %p.\n", ring);
-	_vte_ring_validate(ring);
+	_vte_stream_read (ring->cell_stream, cell_position, (char *) row->cells, row->len * sizeof (row->cells[0]));
 }
 
-void
-_vte_ring_fini (VteRing *ring)
+static void
+_vte_ring_new_page (VteRing *ring)
 {
-	VteRingChunk *chunk;
-
-	_vte_row_data_fini (&ring->cached_row);
-
-	chunk = ring->head->base.prev_chunk;
-	while (chunk) {
-		VteRingChunk *prev_chunk = chunk->prev_chunk;
-		_vte_ring_chunk_free (chunk);
-		chunk = prev_chunk;
-	}
+	_vte_stream_new_page (ring->cell_stream);
+	_vte_stream_new_page (ring->row_stream);
 
-	_vte_ring_chunk_fini_writable (ring->head);
+	ring->last_page = ring->writable;
 }
 
-static const VteRingChunk *
-_vte_ring_find_chunk (VteRing *ring, guint position)
-{
-	g_assert (_vte_ring_contains (ring, position));
 
-	while (position < ring->cursor->start)
-		ring->cursor = ring->cursor->prev_chunk;
-	while (position >= ring->cursor->end)
-		ring->cursor = ring->cursor->next_chunk;
-
-	return ring->cursor;
+static inline VteRowData *
+_vte_ring_writable_index (VteRing *ring, guint position)
+{
+	return &ring->array[position & ring->mask];
 }
 
 const VteRowData *
 _vte_ring_index (VteRing *ring, guint position)
 {
-	if (G_LIKELY (position >= ring->head->base.start))
-		return _vte_ring_chunk_writable_index (ring->head, position);
+	if (G_LIKELY (position >= ring->writable))
+		return _vte_ring_writable_index (ring, position);
 
 	if (ring->cached_row_num != position) {
-		VteRingChunkCompact *chunk = (VteRingChunkCompact *) _vte_ring_find_chunk (ring, position);
-		VteCompactRowData *compact_row = _vte_ring_chunk_compact_index (chunk, position);
-
 		_vte_debug_print(VTE_DEBUG_RING, "Caching row %d.\n", position);
-
-		_vte_compact_row_data_uncompact (compact_row, &ring->cached_row);
+		_vte_ring_thaw_row (ring, position, &ring->cached_row);
 		ring->cached_row_num = position;
 	}
 
@@ -541,116 +159,92 @@ VteRowData *
 _vte_ring_index_writable (VteRing *ring, guint position)
 {
 	_vte_ring_ensure_writable (ring, position);
-	return _vte_ring_chunk_writable_index (ring->head, position);
+	return _vte_ring_writable_index (ring, position);
 }
 
 static void
-_vte_ring_free_chunk (VteRing *ring, VteRingChunk *chunk)
+_vte_ring_freeze_one_row (VteRing *ring)
 {
-	_vte_debug_print(VTE_DEBUG_RING, "Freeing chunk.\n");
-
-	if (chunk == &ring->head->base)
-		return;
+	VteRowData *row;
 
-	if (ring->tail == chunk)
-		ring->tail = chunk->next_chunk;
-	if (ring->cursor == chunk)
-		ring->cursor = chunk->next_chunk;
+	if (G_UNLIKELY (ring->start - ring->last_page >= ring->max))
+		_vte_ring_new_page (ring);
 
-	chunk->next_chunk->prev_chunk = chunk->prev_chunk;
-	if (chunk->prev_chunk)
-		chunk->prev_chunk->next_chunk = chunk->next_chunk;
+	row = _vte_ring_writable_index (ring, ring->writable);
+	_vte_ring_freeze_row (ring, ring->writable, row);
 
-	_vte_ring_chunk_free (chunk);
+	ring->writable++;
 }
 
 static void
-_vte_ring_pop_tail_row (VteRing *ring)
+_vte_ring_ensure_writable_head (VteRing *ring)
 {
-	ring->tail->start++;
-	if (ring->tail->start == ring->tail->end)
-		_vte_ring_free_chunk (ring, ring->tail);
+	if (G_LIKELY (ring->writable + ring->mask == ring->end))
+		_vte_ring_freeze_one_row (ring);
 }
 
 static void
-_vte_ring_compact_one_row (VteRing *ring)
+_vte_ring_ensure_writable_tail (VteRing *ring)
 {
-	VteRowData *row;
-	VteRingChunk *head = &ring->head->base;
-
-	_vte_debug_print(VTE_DEBUG_RING, "Compacting row %d.\n", head->start);
-
-	row = _vte_ring_chunk_writable_index (ring->head, head->start);
+	guint new_mask, old_mask, i, end;
+	VteRowData *old_array, *new_array;;
 
-	if (!head->prev_chunk ||
-	    !_vte_ring_chunk_compact_push_head_row (head->prev_chunk, row))
-	{
-		/* Previous chunk doesn't have enough room, add a new chunk and retry */
-		VteRingChunk *new_chunk = _vte_ring_chunk_new_compact (head->start);
+	if (G_LIKELY (ring->start + ring->mask > ring->end))
+		return;
 
-		_vte_debug_print(VTE_DEBUG_RING, "Allocating chunk.\n");
+	_vte_debug_print(VTE_DEBUG_RING, "Enlarging writable array.\n");
 
-		_vte_ring_chunk_insert_chunk_before (head, new_chunk);
-		if (ring->tail == head)
-			ring->tail = new_chunk;
+	old_mask = ring->mask;
+	old_array = ring->array;
 
-		/* TODO this may fail too */
-		_vte_ring_chunk_compact_push_head_row (head->prev_chunk, row);
-	}
+	ring->mask = (ring->mask << 1) + 1;
+	ring->array = g_malloc0 (sizeof (ring->array[0]) * (ring->mask + 1));
 
-	head->start++;
-}
+	new_mask = ring->mask;
+	new_array = ring->array;
 
-static void
-_vte_ring_ensure_writable_head (VteRing *ring)
-{
-	if (G_LIKELY (ring->head->base.start + ring->head->mask == ring->head->base.end))
-		_vte_ring_compact_one_row (ring);
-}
+	end = ring->writable + old_mask + 1;
+	for (i = ring->writable; i < end; i++)
+		new_array[i & new_mask] = old_array[i & old_mask];
 
-static void
-_vte_ring_ensure_writable_tail (VteRing *ring)
-{
-	_vte_ring_chunk_writable_ensure_tail (ring->head);
+	g_free (old_array);
 }
 
 static void
-_vte_ring_uncompact_one_row (VteRing *ring)
+_vte_ring_thaw_one_row (VteRing *ring)
 {
 	VteRowData *row;
-	VteRingChunk *head = &ring->head->base;
-
-	_vte_debug_print(VTE_DEBUG_RING, "Uncompacting row %d.\n", head->start - 1);
 
 	_vte_ring_ensure_writable_tail (ring);
 
-	head->start--;
+	ring->writable--;
 
-	if (head->start == ring->cached_row_num)
+	if (ring->writable == ring->cached_row_num)
 		/* Invalidate cached row */
 		ring->cached_row_num = (guint) -1;
 
-	row = _vte_ring_chunk_writable_index (ring->head, head->start);
-	_vte_row_data_clear (row);
+	row = _vte_ring_writable_index (ring, ring->writable);
 
-	if (!head->prev_chunk)
+	if (ring->start >= ring->writable) {
+		g_assert_not_reached ();
+		_vte_row_data_clear (row);
+		ring->start = ring->writable;
 		return;
+	}
 
-	_vte_ring_chunk_compact_pop_head_row (head->prev_chunk, row);
-	if (head->prev_chunk->start == head->prev_chunk->end)
-		_vte_ring_free_chunk (ring, head->prev_chunk);
+	_vte_ring_thaw_row (ring, ring->writable, row);
 }
 
 static void
 _vte_ring_ensure_writable (VteRing *ring, guint position)
 {
-	if (G_LIKELY (position >= ring->head->base.start))
+	if (G_LIKELY (position >= ring->writable))
 		return;
 
 	_vte_debug_print(VTE_DEBUG_RING, "Ensure writable %d.\n", position);
 
-	while (position < ring->head->base.start)
-		_vte_ring_uncompact_one_row (ring);
+	while (position < ring->writable)
+		_vte_ring_thaw_one_row (ring);
 }
 
 
@@ -667,13 +261,9 @@ _vte_ring_resize (VteRing *ring, guint max_rows)
 	_vte_debug_print(VTE_DEBUG_RING, "Resizing to %d.\n", max_rows);
 	_vte_ring_validate(ring);
 
-	/* Get rid of unneeded chunks at the tail */
-	while (&ring->head->base != ring->tail && ring->head->base.end - ring->tail->end >= max_rows)
-		_vte_ring_free_chunk (ring, ring->tail);
-
 	/* Adjust the start of tail chunk now */
 	if (_vte_ring_length (ring) > max_rows)
-		ring->tail->start = ring->head->base.end - max_rows;
+		ring->start = ring->end - max_rows;
 
 	ring->max = max_rows;
 }
@@ -687,16 +277,16 @@ _vte_ring_shrink (VteRing *ring, guint max_len)
 	_vte_debug_print(VTE_DEBUG_RING, "Shrinking to %d.\n", max_len);
 	_vte_ring_validate(ring);
 
-	if (ring->head->base.start - ring->tail->start <= max_len)
-		ring->head->base.end = ring->tail->start + max_len;
+	if (ring->writable - ring->start <= max_len)
+		ring->end = ring->start + max_len;
 	else {
-		while (ring->head->base.start - ring->tail->start > max_len) {
-			_vte_ring_ensure_writable (ring, ring->head->base.start - 1);
-			ring->head->base.end = ring->head->base.start;
+		while (ring->writable - ring->start > max_len) {
+			_vte_ring_ensure_writable (ring, ring->writable - 1);
+			ring->end = ring->writable;
 		}
 	}
 
-	/* TODO May want to shrink down ring->head */
+	/* TODO May want to shrink down ring->array */
 
 	_vte_ring_validate(ring);
 }
@@ -714,23 +304,31 @@ _vte_ring_shrink (VteRing *ring, guint max_len)
 static VteRowData *
 _vte_ring_insert_internal (VteRing *ring, guint position)
 {
-	VteRowData *row;
+	guint i;
+	VteRowData *row, tmp;
 
 	_vte_debug_print(VTE_DEBUG_RING, "Inserting at position %u.\n", position);
 	_vte_ring_validate(ring);
 
 	if (_vte_ring_length (ring) == ring->max)
-		_vte_ring_pop_tail_row (ring);
+		ring->start++;
 
-	g_assert (position >= ring->tail->start);
-	g_assert (position <= ring->head->base.end);
+	g_assert (position >= ring->start && position <= ring->end);
 
+	/* Make room */
 	_vte_ring_ensure_writable (ring, position);
-	if (position == ring->head->base.start)
+	if (position == ring->writable)
 		_vte_ring_ensure_writable_tail (ring);
 	_vte_ring_ensure_writable_head (ring);
 
-	row = _vte_ring_chunk_writable_insert (ring->head, position);
+	tmp = *_vte_ring_writable_index (ring, ring->end);
+	for (i = ring->end; i > position; i--)
+		*_vte_ring_writable_index (ring, i) = *_vte_ring_writable_index (ring, i - 1);
+	*_vte_ring_writable_index (ring, position) = tmp;
+
+	row = _vte_ring_writable_index (ring, position);
+	_vte_row_data_clear (row);
+	ring->end++;
 
 	_vte_ring_validate(ring);
 	return row;
@@ -746,13 +344,23 @@ _vte_ring_insert_internal (VteRing *ring, guint position)
 void
 _vte_ring_remove (VteRing * ring, guint position)
 {
+	guint i;
+	VteRowData tmp;
+
 	_vte_debug_print(VTE_DEBUG_RING, "Removing item at position %u.\n", position);
 	_vte_ring_validate(ring);
 
 	g_assert (_vte_ring_contains (ring, position));
 
 	_vte_ring_ensure_writable (ring, position);
-	_vte_ring_chunk_writable_remove (ring->head, position);
+
+	tmp = *_vte_ring_writable_index (ring, position);
+	for (i = position; i < ring->end - 1; i++)
+		*_vte_ring_writable_index (ring, i) = *_vte_ring_writable_index (ring, i + 1);
+	*_vte_ring_writable_index (ring, ring->end - 1) = tmp;
+
+	if (ring->end > ring->writable)
+		ring->end--;
 
 	_vte_ring_validate(ring);
 }
diff --git a/src/ring.h b/src/ring.h
index 6a5cc32..45b8299 100644
--- a/src/ring.h
+++ b/src/ring.h
@@ -22,34 +22,10 @@
 #define vte_ring_h_included
 
 #include "vterowdata.h"
+#include "vtestream.h"
 
 G_BEGIN_DECLS
 
-/*
- * VteRingChunk: A chunk of the scrollback buffer ring
- */
-
-typedef enum _VteRingChunkType VteRingChunkType;
-enum _VteRingChunkType {
-	VTE_RING_CHUNK_TYPE_INVALID,
-	VTE_RING_CHUNK_TYPE_WRITABLE,
-	VTE_RING_CHUNK_TYPE_COMPACT
-
-};
-
-typedef struct _VteRingChunk VteRingChunk;
-struct _VteRingChunk {
-	VteRingChunkType type; /* Chunk implementation type */
-	VteRingChunk *prev_chunk, *next_chunk;
-	guint start, end;
-};
-
-typedef struct _VteRingChunkWritable {
-	VteRingChunk base;
-
-	guint mask;
-	VteRowData *array;
-} VteRingChunkWritable;
 
 /*
  * VteRing: A scrollback buffer ring
@@ -59,19 +35,27 @@ typedef struct _VteRing VteRing;
 struct _VteRing {
 	guint max;
 
+	guint start, end;
+
+	/* Writable */
+	guint writable, mask;
+	VteRowData *array;
+
+	/* Storage */
+	guint last_page;
+	VteStream *cell_stream, *row_stream;
+
 	VteRowData cached_row;
 	guint cached_row_num;
 
-	VteRingChunk *tail, *cursor;
-	VteRingChunkWritable head[1];
 };
 
 #define _vte_ring_contains(__ring, __position) \
-	(((__position) >= (__ring)->tail->start) && \
-	 ((__position) < (__ring)->head->base.end))
-#define _vte_ring_delta(__ring) ((__ring)->tail->start + 0)
-#define _vte_ring_length(__ring) ((__ring)->head->base.end - (__ring)->tail->start)
-#define _vte_ring_next(__ring) ((__ring)->head->base.end + 0)
+	(((__position) >= (__ring)->start) && \
+	 ((__position) < (__ring)->end))
+#define _vte_ring_delta(__ring) ((__ring)->start + 0)
+#define _vte_ring_length(__ring) ((__ring)->end - (__ring)->start)
+#define _vte_ring_next(__ring) ((__ring)->end + 0)
 
 const VteRowData *_vte_ring_index (VteRing *ring, guint position);
 VteRowData *_vte_ring_index_writable (VteRing *ring, guint position);
diff --git a/src/vtestream-base.h b/src/vtestream-base.h
index b6c6596..fd3bd02 100644
--- a/src/vtestream-base.h
+++ b/src/vtestream-base.h
@@ -29,14 +29,17 @@ struct _VteStream {
 };
 
 typedef struct _VteStreamClass {
-	void (*add) (VteStream *stream, const char *data, gsize len);
+	GObjectClass parent_class;
+
+	gsize (*append) (VteStream *stream, const char *data, gsize len);
 	void (*read) (VteStream *stream, gsize offset, char *data, gsize len);
 	void (*trunc) (VteStream *stream, gsize offset);
-	void (*newpage) (VteStream *stream);
+	void (*new_page) (VteStream *stream);
 } VteStreamClass;
 
 static GType _vte_stream_get_type (void);
 #define VTE_TYPE_STREAM _vte_stream_get_type ()
+#define VTE_STREAM_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), VTE_TYPE_STREAM, VteStreamClass))
 
 G_DEFINE_ABSTRACT_TYPE (VteStream, _vte_stream, G_TYPE_OBJECT)
 
@@ -49,3 +52,27 @@ static void
 _vte_stream_init (VteStream *stream)
 {
 }
+
+gsize
+_vte_stream_append (VteStream *stream, const char *data, gsize len)
+{
+	return VTE_STREAM_GET_CLASS (stream)->append (stream, data, len);
+}
+
+void
+_vte_stream_read (VteStream *stream, gsize offset, char *data, gsize len)
+{
+	VTE_STREAM_GET_CLASS (stream)->read (stream, offset, data, len);
+}
+
+void
+_vte_stream_trunc (VteStream *stream, gsize offset)
+{
+	VTE_STREAM_GET_CLASS (stream)->trunc (stream, offset);
+}
+
+void
+_vte_stream_new_page (VteStream *stream)
+{
+	VTE_STREAM_GET_CLASS (stream)->new_page (stream);
+}
diff --git a/src/vtestream-file.h b/src/vtestream-file.h
index 64d285a..3eabc84 100644
--- a/src/vtestream-file.h
+++ b/src/vtestream-file.h
@@ -39,7 +39,7 @@ typedef VteStreamClass VteFileStreamClass;
 static GType _vte_file_stream_get_type (void);
 #define VTE_TYPE_FILE_STREAM _vte_file_stream_get_type ()
 
-G_DEFINE_ABSTRACT_TYPE (VteFileStream, _vte_file_stream, VTE_TYPE_STREAM)
+G_DEFINE_TYPE (VteFileStream, _vte_file_stream, VTE_TYPE_STREAM)
 
 static void
 _vte_file_stream_init (VteFileStream *stream)
@@ -99,15 +99,18 @@ _xwrite (int fd, const char *data, gsize len)
 	}
 }
 
-static void
-_vte_file_stream_add (VteStream *astream, const char *data, gsize len)
+static gsize
+_vte_file_stream_append (VteStream *astream, const char *data, gsize len)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
+	gsize ret;
 
 	_vte_file_stream_ensure_fd0 (stream);
 
-	lseek (stream->fd[0], 0, SEEK_END);
+	ret = lseek (stream->fd[0], 0, SEEK_END);
 	_xwrite (stream->fd[0], data, len);
+
+	return ret;
 }
 
 static gsize
@@ -191,7 +194,7 @@ _vte_file_stream_trunc (VteStream *astream, gsize offset)
 }
 
 static void
-_vte_file_stream_newpage (VteStream *astream)
+_vte_file_stream_new_page (VteStream *astream)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
 
@@ -208,8 +211,8 @@ _vte_file_stream_class_init (VteFileStreamClass *klass)
 
 	gobject_class->finalize = _vte_file_stream_finalize;
 
-	klass->add = _vte_file_stream_add;
+	klass->append = _vte_file_stream_append;
 	klass->read = _vte_file_stream_read;
 	klass->trunc = _vte_file_stream_trunc;
-	klass->newpage = _vte_file_stream_newpage;
+	klass->new_page = _vte_file_stream_new_page;
 }
diff --git a/src/vtestream.h b/src/vtestream.h
index 447fa3b..cd1079d 100644
--- a/src/vtestream.h
+++ b/src/vtestream.h
@@ -27,6 +27,14 @@ G_BEGIN_DECLS
 
 typedef struct _VteStream VteStream;
 
+gsize _vte_stream_append (VteStream *stream, const char *data, gsize len);
+void _vte_stream_read (VteStream *stream, gsize offset, char *data, gsize len);
+void _vte_stream_trunc (VteStream *stream, gsize offset);
+void _vte_stream_new_page (VteStream *stream);
+
+
+/* Various streams */
+
 VteStream *
 _vte_file_stream_new (void);