Compressed binary tape idea

tm.c

#include <stdio.h>
#include <stdint.h>

#define BASE_SIZE 8

struct cell {
	uint64_t value :  1;
	uint64_t reps  : 17;
	uint64_t prev  : 23;
	uint64_t next  : 23;
};

struct tape_ptr {
	uint32_t pos;
	uint32_t rep_pos;
};

struct tape {
	uint32_t size;
	uint32_t capacity;
	struct tape_ptr p;
	struct cell *cells
	struct cell base_cells[BASE_SIZE];
};

void
tape_init(struct tape *t)
{
	t->cells = t->base_cells;
	t->capacity = BASE_SIZE;
}

int
tape_get(struct tape *t)
{
	return t->cells[t->p.pos].value;
}

int
tape_expand(struct tape *t)
{
	struct cell *cn;
	if (SIZE_MAX / sizeof(*t->cells) / 2 > t->size)
		return 1;
	if (t->cells == t->base_cells) {
		cn = calloc(BASE_SIZE * 2, sizeof(*t->cells));
		if (cn == NULL)
			return 1;
		t->cells = cn;
		memcpy(t->cells, t->base_cells, BASE_SIZE * sizeof(*t->cells));
	} else {
		cn = realloc(t->cells, 2 * t->size * sizeof(*t->cells))
		if (cn == NULL)
			return 1;
		t->cells = cn;
	}
	t->size *= 2;
	return 0;
}

int
tape_set(struct tape *t, int value)
{
	struct cell c = t->cells[t->p.pos];
	if (tape_get(t) == value) {
		return 0;
	}
	if (c.reps == 0) {
		c.value = value;
		return 0;
	}
  // Idea: need to insert one or two new cells to split the current one
	if (t->size == t->capacity) {
		if (tape_expand(t))
			return 1;
	}
  // TODO
	t->cells[t->size+1].prev = t->p.pos;
	t->cells[t->size+1].next = c.next
}

int
main(void)
{
	struct cell c;
	c.value = 1ull;
	printf("%d\n", c.value);
	return 0;
}