ref: a8558cb1e89245ecb38501b0fe4b64462ba69889
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;
Cell *c;
while (s = findvaluep(s, &p)) {
c = getcell(p);
if (!c)
addcell(p, strdup("0"), FUNCTION, Aleft);
}
}
void
addcell(P cell, char *value, int type, int align)
{
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);
if (c->procvalue && c->procvalue != c->value)
free(c->procvalue);
if (c->buffered)
free(c->buffered);
c->value = strdup(value);
c->type = type;
c->align = align;
c->buffered = nil;
preprocess(c);
addempty(c->procvalue);
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;
c->align = align;
c->buffered = nil;
c->procvalue = nil;
c->points = nil;
c->size = 0;
c->num = 0;
c->indeg = 0;
preprocess(c);
addempty(c->procvalue);
}
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);
}
}