shithub: spread

ref: 1322210e058aee6327c77ea4acf8779d6620682f
dir: /cells.c/

#include <u.h>
#include <libc.h>
#include <regexp.h>
#include "spread.h"

#define GROW 64
#define PGROW 4

typedef struct Cellblock Cellblock;
struct Cellblock {
	Cell *cells;
	int size;
	int num;
};

Cellblock block;

Reprog *funcregexp;

static char* findvaluep(char *s, P *p);

static void
addempty(char *s)
{
	P p;
	
	while (s = findvaluep(s, &p)) {
		addcell(p, strdup("0"), FUNCTION);
	}
}

void
addcell(P cell, char *value, int type)
{
	Cell *c;
	
	assert(type != FUNCTION || type != STRING);
	assert(value);
	
	if (!block.cells) {
		block.size = GROW;
		block.cells = mallocz(sizeof(Cell) * block.size, 1);
		assert(block.cells);
		block.num = 0;
	}
	
	if (c = getcell(cell)) {
		if (c->value)
			free(c->value);
		c->value = strdup(value);
		c->type = type;
		addempty(value);
		return;
	}
	
	if (block.num + 1 >= block.size) {
		block.size += GROW;
		block.cells = realloc(block.cells, sizeof(Cell) * block.size);
		assert(block.cells);
		memset(&block.cells[block.num], 0, block.size - block.num);
	}
	c = &block.cells[block.num++];
	c->p = cell;
	c->value = strdup(value);
	c->type = type;
	addempty(value);
}

void
rmcell(P cell)
{
	int i;
	Cell *c;
	
	for (i = 0; i < block.num; i++) {
		c = &block.cells[i];
		
		if (PEQ(c->p, cell))
			continue;
		
		if (c->value)
			free(c->value);
		c->value = nil;
		c->type = 0;
		c->p.x = 0;
		c->p.y = 0;
	}
}

Cell*
getcell(P cell)
{
	int i;
	Cell *c;
	
	for (i = 0; i < block.num; i++) {
		c = &block.cells[i];
		if (c->type != FUNCTION && c->type != STRING)
			continue;
		if (PEQ(cell, c->p))
			return c;
	}
	return nil;
}

void
foreachcell(void (*f)(Cell*,void*), void *aux)
{
	int i;
	Cell *c;
	
	for (i = 0; i < block.num; i++) {
		c = &block.cells[i];
		if (c->type != FUNCTION && c->type != STRING)
			continue;
		f(c, aux);
	}
}

static char*
findvaluep(char *s, P *p)
{
	Resub match;
	
	if (!funcregexp)
		funcregexp = regcomp("[A-Z]+[0-9]+[(]+[)]+");
	
	memset(&match, 0, sizeof(Resub));
	if (regexec(funcregexp, s, &match, 1)) {
		*p = atop(match.sp);
		return match.ep;
	}
	return nil;
}

static int
hascell(Cell *c, Cell *d)
{
	int i;
	if (!c->points)
		return 0;
	
	for (i = 0; i < c->num; i++)
		if (c->points[i] == d)
			return 1;
	return 0;
}

static void
addcelldep(Cell *c, Cell *d)
{
	if (hascell(c, d))
		return;
	
	if (!c->points) {
		c->size = PGROW;
		c->points = mallocz(c->size * sizeof(Cell*), 1);
		assert(c->points);
		c->num = 0;
	}
	if (c->num + 1 >= c->size) {
		c->size += PGROW;
		c->points = realloc(c->points, c->size * sizeof(Cell*));
		assert(c->points);
		memset(&c->points[c->num], 0, c->size - c->num);
	}
	c->points[c->num] = d;
	c->num++;
}

static void
celldeps(Cell* c, void*)
{
	Cell *d;
	char *s;
	P p;
	
	if (c->type != FUNCTION)
		return;
	
	c->indeg = 0;
	s = c->value;
	while (s = findvaluep(s, &p)) {
		c->indeg++;
		d = getcell(p);
		if (!d) {
			dumpcells();
			sysfatal("cannot find cell %s (%d %d)", ptoa(p), p.x, p.y);
		}
		addcelldep(d, c);
	}
}

static Cell*
findindegzero(void)
{
	Cell *c;
	for (int i = 0; i < block.num; i++) {
		c = &block.cells[i];
		if (c->type != FUNCTION && c->type != STRING)
			continue;
		if (c->indeg == 0)
			return c;
	}
	return nil;
}

static void
cleandeps(Cell *c)
{
	for (int i = 0; i < c->num; i++) {
		c->points[i]->indeg--;
	}
	free(c->points);
	c->points = nil;
	c->size = 0;
	c->num = 0;
}

int
findfree(int i)
{
	for (; i < block.num; i++) {
		if (block.cells[i].type == INVALID)
			return i;
	}
	return -1;
}

int
sortcells(void)
{
	Cell *c;
	Cellblock b;
	int nq;
	P p;
	
	// build DAG information
	foreachcell(celldeps, nil);
	funcregexp = nil;
	
	b.size = block.size;
	b.num = 0;
	b.cells = mallocz(sizeof(Cell) * b.size, 1);
	assert(b.cells);
	
	// sort DAG to linear list
	while (c = findindegzero()) {
		cleandeps(c);
		memcpy(&b.cells[b.num], c, sizeof(Cell));
		memset(c, 0, sizeof(Cell));
		b.num++;
	}
	
	for (int i = 0; i < b.num; i++) {
		c = &b.cells[i];
		if (c->points)
			free(c->points);
		c->points = nil;
		c->num = 0;
		c->size = 0;
		c->indeg = 0;
	}
	
	for (int i = 0; i < block.num; i++) {
		c = &block.cells[i];
		if (c->type == 0)
			continue;
		goto Errout;
	}
	
	block.num = b.num;
	block.cells = b.cells;
	memset(&b, 0, sizeof(Cellblock));
	return 1;
	
Errout:
	p = c->p;
	
	/* free dependency calculation */
	for (int i = 0; i < block.num; i++) {
		c = &block.cells[i];
		if (c->type == 0)
			continue;
		if (c->points)
			free(c->points);
		c->points = nil;
		c->num = 0;
		c->size = 0;
		c->indeg = 0;
	}
	
	/* move cells back to original block */
	nq = 0;
	for (int i = 0; i < b.num; i++) {
		c = &b.cells[i];
		if (c->type == 0)
			continue;
		nq = findfree(nq);
		if (nq < 0)
			sysfatal("can't happen");
		memcpy(&block.cells[nq], c, sizeof(Cell));
		nq++;
	}
	
	free(b.cells);
	memset(&b, 0, sizeof(Cellblock));
	
	werrstr("cyclic dependencies found involving %s", ptoa(p));
	return 0;
}

void
gccells()
{
	
}

static void
dumpcellpoints(Cell *c)
{
	Cell **n;
	if (!c->points) {
		fprint(2, "%5s (%d) : <none>\n", ptoa(c->p), c->indeg);
		return;
	}
	fprint(2, "%5s (%d) :", ptoa(c->p), c->indeg);
	for (n = c->points; *n; n++) {
		fprint(2, " %s", ptoa((*n)->p));
	}
	fprint(2, "\n");
}

void
dumpcells(void)
{
	int i;
	Cell *c;
	
	fprint(2, "dump cells:\n");
	if (!block.cells) {
		fprint(2, "empty\n");
		exits(nil);
	}
	
	for (i = 0; i < block.size; i++) {
		c = &block.cells[i];
		switch (c->type) {
		case 0:
			fprint(2, "%5d : invalid\n", i);
			break;
		case FUNCTION:
			fprint(2, "%5d : %s = %s\n", i, ptoa(c->p), c->value);
			break;
		case STRING:
			fprint(2, "%5d : %s : %s\n", i, ptoa(c->p), c->value);
			break;
		default:
			fprint(2, "%5d : error\n", i);
		}
	}
	
	fprint(2, "Cell points (DAG):\n");
	for (i = 0; i < block.size; i++) {
		c = &block.cells[i];
		if (c->type == 0)
			continue;
		dumpcellpoints(c);
	}
}