ref: e6cdd70df867f064b0358dc3dba56d2667ab80a5
parent: 6b5142a7a9b31922d9c7ef505b27c33d551f5016
author: Simon Tatham <anakin@pobox.com>
date: Thu Jul 6 08:50:49 EDT 2023
grid.c: allocate face/edge/dot arrays incrementally. Previously, the 'faces', 'edges' and 'dots' arrays in a grid structure were arrays of actual grid_face, grid_edge and grid_dot structures, physically containing all the data about the grid. But they also referred to each other by pointers, which meant that they were hard to realloc larger (you'd have to go through and rewrite all the pointers whenever the base of an array moved). And _that_ meant that every grid type had to figure out a reasonably good upper bound on the number of all those things it was going to need, so that it could allocate those arrays the right size to begin with, and not have to grow them painfully later. For some grid types - particularly the new aperiodic ones - that was actually a painful part of the job. So I think enough is enough: counting up how much memory you're going to need before using it is a mug's game, and we should instead realloc on the fly. So now g->faces, g->edges and g->dots have an extra level of indirection. Instead of being arrays of actual structs, they're arrays of pointers, and each struct in them is individually allocated. Once a grid_face has been allocated, it never moves again, even if the array of pointers changes size. The old code had a common idiom of recovering the array index of a particular element by subtracting it from the array base, e.g. writing 'f - g->faces' or 'e - g->edges'. To make that lookup remain possible, I've added an 'index' field to each sub-structure, which is initialised at the point where we decide what array index it will live at. This should involve no functional change, but the code that previously had to figure out max_faces and max_dots up front for each grid type is now completely gone, and nobody has to solve those problems in advance any more.
--- a/grid.c
+++ b/grid.c
@@ -43,13 +43,18 @@
if (g->refcount == 0) {int i;
for (i = 0; i < g->num_faces; i++) {- sfree(g->faces[i].dots);
- sfree(g->faces[i].edges);
+ sfree(g->faces[i]->dots);
+ sfree(g->faces[i]->edges);
+ sfree(g->faces[i]);
}
for (i = 0; i < g->num_dots; i++) {- sfree(g->dots[i].faces);
- sfree(g->dots[i].edges);
+ sfree(g->dots[i]->faces);
+ sfree(g->dots[i]->edges);
+ sfree(g->dots[i]);
}
+ for (i = 0; i < g->num_edges; i++) {+ sfree(g->edges[i]);
+ }
sfree(g->faces);
sfree(g->edges);
sfree(g->dots);
@@ -66,6 +71,7 @@
g->edges = NULL;
g->dots = NULL;
g->num_faces = g->num_edges = g->num_dots = 0;
+ g->size_faces = g->size_edges = g->size_dots = 0;
g->refcount = 1;
g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0;
return g;
@@ -123,7 +129,7 @@
best_edge = NULL;
for (i = 0; i < g->num_edges; i++) {- grid_edge *e = &g->edges[i];
+ grid_edge *e = g->edges[i];
long e2; /* squared length of edge */
long a2, b2; /* squared lengths of other sides */
double dist;
@@ -192,7 +198,7 @@
if (which & SVG_FACES) {fprintf(fp, "<g>\n");
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
fprintf(fp, "<polygon points=\"");
for (j = 0; j < f->order; j++) {grid_dot *d = f->dots[j];
@@ -207,7 +213,7 @@
if (which & SVG_EDGES) {fprintf(fp, "<g>\n");
for (i = 0; i < g->num_edges; i++) {- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
grid_dot *d1 = e->dot1, *d2 = e->dot2;
fprintf(fp, "<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" "
@@ -220,7 +226,7 @@
if (which & SVG_DOTS) {fprintf(fp, "<g>\n");
for (i = 0; i < g->num_dots; i++) {- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
fprintf(fp, "<ellipse cx=\"%d\" cy=\"%d\" rx=\"%d\" ry=\"%d\" fill=\"%s\" />",
d->x, d->y, g->tilesize/20, g->tilesize/20, DOT_COLOUR);
}
@@ -259,12 +265,12 @@
int i;
printf("--- Basic Grid Data ---\n"); for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
printf("Face %d: dots[", i);int j;
for (j = 0; j < f->order; j++) {grid_dot *d = f->dots[j];
- printf("%s%d", j ? "," : "", (int)(d - g->dots)); + printf("%s%d", j ? "," : "", (int)(d->index));}
printf("]\n");}
@@ -282,38 +288,38 @@
int i;
printf("--- Derived Grid Data ---\n"); for (i = 0; i < g->num_edges; i++) {- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",- i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots),
- e->face1 ? (int)(e->face1 - g->faces) : -1,
- e->face2 ? (int)(e->face2 - g->faces) : -1);
+ i, (int)(e->dot1->index), (int)(e->dot2->index),
+ e->face1 ? (int)(e->face1->index) : -1,
+ e->face2 ? (int)(e->face2->index) : -1);
}
/* faces */
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
int j;
printf("Face %d: faces[", i); for (j = 0; j < f->order; j++) {grid_edge *e = f->edges[j];
grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1;
- printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1);+ printf("%s%d", j ? "," : "", f2 ? f2->index : -1);}
printf("]\n");}
/* dots */
for (i = 0; i < g->num_dots; i++) {- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
int j;
printf("Dot %d: dots[", i); for (j = 0; j < d->order; j++) {grid_edge *e = d->edges[j];
grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1;
- printf("%s%d", j ? "," : "", (int)(d2 - g->dots));+ printf("%s%d", j ? "," : "", d2->index);}
printf("] faces["); for (j = 0; j < d->order; j++) {grid_face *f = d->faces[j];
- printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1);+ printf("%s%d", j ? "," : "", f ? f->index : -1);}
printf("]\n");}
@@ -378,10 +384,10 @@
for (j = 0; j < g->num_dots; j++)
dotpairs[i*g->num_dots+j] = -1;
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
- int dot0 = f->dots[f->order-1] - g->dots;
+ grid_face *f = g->faces[i];
+ int dot0 = f->dots[f->order-1]->index;
for (j = 0; j < f->order; j++) {- int dot1 = f->dots[j] - g->dots;
+ int dot1 = f->dots[j]->index;
dotpairs[dot0 * g->num_dots + dot1] = i;
dot0 = dot1;
}
@@ -441,56 +447,48 @@
for (i = 0; i < g->num_dots; i++)
dots[i] = 0;
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
bool keep = false;
for (k = 0; k < f->order; k++)
- if (dsf_canonify(dsf, f->dots[k] - g->dots) == j)
+ if (dsf_canonify(dsf, f->dots[k]->index) == j)
keep = true;
if (keep) {faces[i] = 1;
for (k = 0; k < f->order; k++)
- dots[f->dots[k]-g->dots] = 1;
+ dots[f->dots[k]->index] = 1;
}
}
/*
- * Work out the new indices of those faces and dots, when we
- * compact the arrays containing them.
+ * Compact the faces array, rewriting the faces' indices and
+ * freeing the unwanted ones.
*/
- for (i = newfaces = 0; i < g->num_faces; i++)
- faces[i] = (faces[i] ? newfaces++ : -1);
- for (i = newdots = 0; i < g->num_dots; i++)
- dots[i] = (dots[i] ? newdots++ : -1);
+ for (i = newfaces = 0; i < g->num_faces; i++) {+ grid_face *f = g->faces[i];
+ if (faces[i]) {+ f->index = newfaces++;
+ g->faces[f->index] = f;
+ } else {+ sfree(f->dots);
+ sfree(f);
+ }
+ }
+ g->num_faces = newfaces;
/*
- * Free the dynamically allocated 'dots' pointer lists in faces
- * we're going to discard.
+ * Compact the dots array, similarly.
*/
- for (i = 0; i < g->num_faces; i++)
- if (faces[i] < 0)
- sfree(g->faces[i].dots);
-
- /*
- * Go through and compact the arrays.
- */
- for (i = 0; i < g->num_dots; i++)
- if (dots[i] >= 0) {- grid_dot *dnew = g->dots + dots[i], *dold = g->dots + i;
- *dnew = *dold; /* structure copy */
+ for (i = newdots = 0; i < g->num_dots; i++) {+ grid_dot *d = g->dots[i];
+ if (dots[i]) {+ d->index = newdots++;
+ g->dots[d->index] = d;
+ } else {+ sfree(d->edges);
+ sfree(d->faces);
+ sfree(d);
}
- for (i = 0; i < g->num_faces; i++)
- if (faces[i] >= 0) {- grid_face *fnew = g->faces + faces[i], *fold = g->faces + i;
- *fnew = *fold; /* structure copy */
- for (j = 0; j < fnew->order; j++) {- /*
- * Reindex the dots in this face.
- */
- k = fnew->dots[j] - g->dots;
- fnew->dots[j] = g->dots + dots[k];
- }
- }
- g->num_faces = newfaces;
+ }
g->num_dots = newdots;
sfree(dotpairs);
@@ -512,7 +510,6 @@
{int i;
tree234 *incomplete_edges;
- grid_edge *next_new_edge; /* Where new edge will go into g->edges */
grid_debug_basic(g);
@@ -520,14 +517,6 @@
* Generate edges
*/
- /* We know how many dots and faces there are, so we can find the exact
- * number of edges from Euler's polyhedral formula: F + V = E + 2 .
- * We use "-1", not "-2" here, because Euler's formula includes the
- * infinite face, which we don't count. */
- g->num_edges = g->num_faces + g->num_dots - 1;
- g->edges = snewn(g->num_edges, grid_edge);
- next_new_edge = g->edges;
-
/* Iterate over faces, and over each face's dots, generating edges as we
* go. As we find each new edge, we can immediately fill in the edge's
* dots, but only one of the edge's faces. Later on in the iteration, we
@@ -537,7 +526,7 @@
* their dots. */
incomplete_edges = newtree234(grid_edge_bydots_cmpfn);
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
int j;
for (j = 0; j < f->order; j++) {grid_edge e; /* fake edge for searching */
@@ -555,18 +544,28 @@
* Edge is already removed from incomplete_edges. */
edge_found->face2 = f;
} else {- assert(next_new_edge - g->edges < g->num_edges);
- next_new_edge->dot1 = e.dot1;
- next_new_edge->dot2 = e.dot2;
- next_new_edge->face1 = f;
- next_new_edge->face2 = NULL; /* potentially infinite face */
- add234(incomplete_edges, next_new_edge);
- ++next_new_edge;
+ grid_edge *new_edge = snew(grid_edge);
+ new_edge->dot1 = e.dot1;
+ new_edge->dot2 = e.dot2;
+ new_edge->face1 = f;
+ new_edge->face2 = NULL; /* potentially infinite face */
+ add234(incomplete_edges, new_edge);
+
+ /* And add it to g->edges. */
+ if (g->num_edges >= g->size_edges) {+ int increment = g->num_edges / 4 + 128;
+ g->size_edges = (increment < INT_MAX - g->num_edges ?
+ g->num_edges + increment : INT_MAX);
+ g->edges = sresize(g->edges, g->size_edges, grid_edge *);
+ }
+ assert(g->num_edges < INT_MAX);
+ new_edge->index = g->num_edges++;
+ g->edges[new_edge->index] = new_edge;
}
}
}
freetree234(incomplete_edges);
-
+
/* ====== Stage 2 ======
* For each face, build its edge list.
*/
@@ -574,7 +573,7 @@
/* Allocate space for each edge list. Can do this, because each face's
* edge-list is the same size as its dot-list. */
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
int j;
f->edges = snewn(f->order, grid_edge*);
/* Preload with NULLs, to help detect potential bugs. */
@@ -586,7 +585,7 @@
* the face's edge-list, after finding where it should go in the
* sequence. */
for (i = 0; i < g->num_edges; i++) {- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
int j;
for (j = 0; j < 2; j++) {grid_face *f = j ? e->face2 : e->face1;
@@ -648,16 +647,16 @@
* allocate the right space for these lists. Pre-compute the sizes by
* iterating over each edge and recording a tally against each dot. */
for (i = 0; i < g->num_dots; i++) {- g->dots[i].order = 0;
+ g->dots[i]->order = 0;
}
for (i = 0; i < g->num_edges; i++) {- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
++(e->dot1->order);
++(e->dot2->order);
}
/* Now we have the sizes, pre-allocate the edge and face lists. */
for (i = 0; i < g->num_dots; i++) {- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
int j;
assert(d->order >= 2); /* sanity check */
d->edges = snewn(d->order, grid_edge*);
@@ -670,7 +669,7 @@
/* For each dot, need to find a face that touches it, so we can seed
* the edge-face-edge-face process around each dot. */
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
int j;
for (j = 0; j < f->order; j++) {grid_dot *d = f->dots[j];
@@ -684,7 +683,7 @@
* blocks progress. But there's only one such face, so we will
* succeed in finding every edge and face this way. */
for (i = 0; i < g->num_dots; i++) {- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
int current_face1 = 0; /* ascends clockwise */
int current_face2 = 0; /* descends anticlockwise */
@@ -781,7 +780,7 @@
/* Bounding rectangle */
for (i = 0; i < g->num_dots; i++) {- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
if (i == 0) {g->lowest_x = g->highest_x = d->x;
g->lowest_y = g->highest_y = d->y;
@@ -809,12 +808,21 @@
else
return p2->x - p1->x;
}
-/* Add a new face to the grid, with its dot list allocated.
- * Assumes there's enough space allocated for the new face in grid->faces */
+/* Add a new face to the grid, with its dot list allocated. */
static void grid_face_add_new(grid *g, int face_size)
{int i;
- grid_face *new_face = g->faces + g->num_faces;
+ grid_face *new_face = snew(grid_face);
+ assert(g->num_faces < INT_MAX);
+ if (g->num_faces >= g->size_faces) {+ int increment = g->num_faces / 4 + 128;
+ g->size_faces = (increment < INT_MAX - g->num_faces ?
+ g->num_faces + increment : INT_MAX);
+ g->faces = sresize(g->faces, g->size_faces, grid_face *);
+ }
+ new_face->index = g->num_faces++;
+ g->faces[new_face->index] = new_face;
+
new_face->order = face_size;
new_face->dots = snewn(face_size, grid_dot*);
for (i = 0; i < face_size; i++)
@@ -821,24 +829,31 @@
new_face->dots[i] = NULL;
new_face->edges = NULL;
new_face->has_incentre = false;
- g->num_faces++;
}
-/* Assumes dot list has enough space */
static grid_dot *grid_dot_add_new(grid *g, int x, int y)
{- grid_dot *new_dot = g->dots + g->num_dots;
+ grid_dot *new_dot = snew(grid_dot);
+ if (g->num_dots >= g->size_dots) {+ int increment = g->num_dots / 4 + 128;
+ g->size_dots = (increment < INT_MAX - g->num_dots ?
+ g->num_dots + increment : INT_MAX);
+ g->dots = sresize(g->dots, g->size_dots, grid_dot *);
+ }
+ assert(g->num_dots < INT_MAX);
+ new_dot->index = g->num_dots++;
+ g->dots[new_dot->index] = new_dot;
+
new_dot->order = 0;
new_dot->edges = NULL;
new_dot->faces = NULL;
new_dot->x = x;
new_dot->y = y;
- g->num_dots++;
+
return new_dot;
}
/* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
* in the dot_list, or add a new dot to the grid (and the dot_list) and
- * return that.
- * Assumes g->dots has enough capacity allocated */
+ * return that. */
static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y)
{grid_dot test, *ret;
@@ -862,7 +877,7 @@
* previously been added, with the required number of dots allocated) */
static void grid_face_set_dot(grid *g, grid_dot *d, int position)
{- grid_face *last_face = g->faces + g->num_faces - 1;
+ grid_face *last_face = g->faces[g->num_faces - 1];
last_face->dots[position] = d;
}
@@ -1420,16 +1435,10 @@
/* Side length */
int a = SQUARE_TILESIZE;
- /* Upper bounds - don't have to be exact */
- int max_faces = width * height;
- int max_dots = (width + 1) * (height + 1);
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = a;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -1454,8 +1463,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -1495,16 +1502,10 @@
int a = HONEY_A;
int b = HONEY_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = width * height;
- int max_dots = 2 * (width + 1) * (height + 1);
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = HONEY_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -1535,8 +1536,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -1622,16 +1621,18 @@
* 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e
*/
- g->num_faces = width * height * 2;
- g->num_dots = (width + 1) * (height + 1);
- g->faces = snewn(g->num_faces, grid_face);
- g->dots = snewn(g->num_dots, grid_dot);
+ g->num_faces = g->size_faces = width * height * 2;
+ g->num_dots = g->size_dots = (width + 1) * (height + 1);
+ g->faces = snewn(g->size_faces, grid_face *);
+ g->dots = snewn(g->size_dots, grid_dot *);
/* generate dots */
index = 0;
for (y = 0; y <= height; y++) { for (x = 0; x <= width; x++) {- grid_dot *d = g->dots + index;
+ grid_dot *d = snew(grid_dot);
+ d->index = index;
+ g->dots[d->index] = d;
/* odd rows are offset to the right */
d->order = 0;
d->edges = NULL;
@@ -1647,8 +1648,11 @@
for (y = 0; y < height; y++) { for (x = 0; x < width; x++) {/* initialise two faces for this (x,y) */
- grid_face *f1 = g->faces + index;
- grid_face *f2 = f1 + 1;
+ grid_face *f1 = snew(grid_face), *f2 = snew(grid_face);
+ f1->index = index;
+ f2->index = index + 1;
+ g->faces[f1->index] = f1;
+ g->faces[f2->index] = f2;
f1->edges = NULL;
f1->order = 3;
f1->dots = snewn(f1->order, grid_dot*);
@@ -1661,19 +1665,19 @@
/* face descriptions depend on whether the row-number is
* odd or even */
if (y % 2) {- f1->dots[0] = g->dots + y * w + x;
- f1->dots[1] = g->dots + (y + 1) * w + x + 1;
- f1->dots[2] = g->dots + (y + 1) * w + x;
- f2->dots[0] = g->dots + y * w + x;
- f2->dots[1] = g->dots + y * w + x + 1;
- f2->dots[2] = g->dots + (y + 1) * w + x + 1;
+ f1->dots[0] = g->dots[y * w + x];
+ f1->dots[1] = g->dots[(y + 1) * w + x + 1];
+ f1->dots[2] = g->dots[(y + 1) * w + x];
+ f2->dots[0] = g->dots[y * w + x];
+ f2->dots[1] = g->dots[y * w + x + 1];
+ f2->dots[2] = g->dots[(y + 1) * w + x + 1];
} else {- f1->dots[0] = g->dots + y * w + x;
- f1->dots[1] = g->dots + y * w + x + 1;
- f1->dots[2] = g->dots + (y + 1) * w + x;
- f2->dots[0] = g->dots + y * w + x + 1;
- f2->dots[1] = g->dots + (y + 1) * w + x + 1;
- f2->dots[2] = g->dots + (y + 1) * w + x;
+ f1->dots[0] = g->dots[y * w + x];
+ f1->dots[1] = g->dots[y * w + x + 1];
+ f1->dots[2] = g->dots[(y + 1) * w + x];
+ f2->dots[0] = g->dots[y * w + x + 1];
+ f2->dots[1] = g->dots[(y + 1) * w + x + 1];
+ f2->dots[2] = g->dots[(y + 1) * w + x];
}
index += 2;
}
@@ -1690,13 +1694,7 @@
* 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1
*/
tree234 *points = newtree234(grid_point_cmp_fn);
- /* Upper bounds - don't have to be exact */
- int max_faces = height * (2*width+1);
- int max_dots = (height+1) * (width+1) * 4;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
-
for (y = 0; y < height; y++) {/*
* Each row contains (width+1) triangles one way up, and
@@ -1743,8 +1741,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
}
grid_make_consistent(g);
@@ -1786,16 +1782,10 @@
int a = SNUBSQUARE_A;
int b = SNUBSQUARE_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 3 * width * height;
- int max_dots = 2 * (width + 1) * (height + 1);
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = SNUBSQUARE_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -1871,8 +1861,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -1911,16 +1899,10 @@
int a = CAIRO_A;
int b = CAIRO_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 2 * width * height;
- int max_dots = 3 * (width + 1) * (height + 1);
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = CAIRO_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -1989,8 +1971,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -2030,16 +2010,10 @@
int a = GREATHEX_A;
int b = GREATHEX_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 6 * (width + 1) * (height + 1);
- int max_dots = 6 * width * height;
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = GREATHEX_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -2131,8 +2105,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -2172,16 +2144,10 @@
int a = KAGOME_A;
int b = KAGOME_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 6 * (width + 1) * (height + 1);
- int max_dots = 6 * width * height;
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = KAGOME_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -2239,8 +2205,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -2280,16 +2244,10 @@
int a = OCTAGONAL_A;
int b = OCTAGONAL_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 2 * width * height;
- int max_dots = 4 * (width + 1) * (height + 1);
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = OCTAGONAL_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -2334,8 +2292,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -2375,16 +2331,10 @@
int a = KITE_A;
int b = KITE_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 6 * width * height;
- int max_dots = 6 * (width + 1) * (height + 1);
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = KITE_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -2466,8 +2416,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -2520,16 +2468,10 @@
int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */
int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */
- /* Upper bounds - don't have to be exact */
- int max_faces = 6 * width * height;
- int max_dots = 9 * (width + 1) * (height + 1);
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = FLORET_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -2590,8 +2532,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -2632,16 +2572,10 @@
int a = DODEC_A;
int b = DODEC_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 3 * width * height;
- int max_dots = 14 * width * height;
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = DODEC_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -2688,8 +2622,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -2725,16 +2657,10 @@
int a = DODEC_A;
int b = DODEC_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 30 * width * height;
- int max_dots = 200 * width * height;
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = DODEC_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -2814,8 +2740,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -2852,16 +2776,10 @@
int a = DODEC_A;
int b = DODEC_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 50 * width * height;
- int max_dots = 300 * width * height;
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = DODEC_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -2996,8 +2914,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -3034,16 +2950,10 @@
int a = DODEC_A;
int b = DODEC_B;
- /* Upper bounds - don't have to be exact */
- int max_faces = 6 * width * height;
- int max_dots = 18 * width * height;
-
tree234 *points;
grid *g = grid_empty();
g->tilesize = DODEC_TILESIZE;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -3105,8 +3015,6 @@
}
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
grid_make_consistent(g);
return g;
@@ -3282,7 +3190,7 @@
static grid *grid_new_penrose(int width, int height, int which, const char *desc)
{- int max_faces, max_dots, tilesize = PENROSE_TILESIZE;
+ int tilesize = PENROSE_TILESIZE;
int xsz, ysz, xoff, yoff, aoff;
double rradius;
@@ -3301,13 +3209,8 @@
ps.new_tile = set_faces;
ps.ctx = &sf_ctx;
- max_faces = (width*3) * (height*3); /* somewhat paranoid... */
- max_dots = max_faces * 4; /* ditto... */
-
g = grid_empty();
g->tilesize = tilesize;
- g->faces = snewn(max_faces, grid_face);
- g->dots = snewn(max_dots, grid_dot);
points = newtree234(grid_point_cmp_fn);
@@ -3338,8 +3241,6 @@
penrose(&ps, which, aoff);
freetree234(points);
- assert(g->num_faces <= max_faces);
- assert(g->num_dots <= max_dots);
debug(("penrose: %d faces total (equivalent to %d wide by %d high)",g->num_faces, g->num_faces/height, g->num_faces/width));
@@ -3540,16 +3441,10 @@
error = grid_desc_to_hat_params(desc, &hp);
assert(error == NULL && "grid_validate_desc_hats should have failed");
- /* Upper bounds - don't have to be exact */
- int max_faces = (width * height * 6 + 7) / 8;
- int max_dots = width * height * 6 + width * 2 + height * 2 + 1;
-
struct hatcontext ctx[1];
ctx->g = grid_empty();
ctx->g->tilesize = HATS_TILESIZE;
- ctx->g->faces = snewn(max_faces, grid_face);
- ctx->g->dots = snewn(max_dots, grid_dot);
ctx->points = newtree234(grid_point_cmp_fn);
@@ -3696,30 +3591,10 @@
error = grid_desc_to_spectre_params(desc, &sp);
assert(error == NULL && "grid_validate_desc_spectres should have failed");
- /*
- * Bound on the number of faces: the area of a single face in the
- * output coordinates is 24 + 24 rt3, which is between 65 and 66.
- * Every face fits strictly inside the target rectangle, so the
- * number of faces times a lower bound on their area can't exceed
- * the area of the rectangle we give to spectre_tiling_generate.
- */
- int max_faces = width2 * height2 / 65;
-
- /*
- * Bound on number of dots: 14*faces is certainly enough, but
- * quite wasteful given that _most_ dots are shared between at
- * least two faces. But to get a better estimate we'd have to
- * figure out a bound for the number of dots on the perimeter,
- * which is the number by which the count exceeds 14*faces/2.
- */
- int max_dots = 14 * max_faces;
-
struct spectrecontext ctx[1];
ctx->g = grid_empty();
ctx->g->tilesize = SPECTRE_TILESIZE;
- ctx->g->faces = snewn(max_faces, grid_face);
- ctx->g->dots = snewn(max_dots, grid_dot);
ctx->points = newtree234(grid_point_cmp_fn);
--- a/grid.h
+++ b/grid.h
@@ -33,6 +33,7 @@
typedef struct grid_dot grid_dot;
struct grid_face {+ int index; /* index in grid->faces[] where this face appears */
int order; /* Number of edges, also the number of dots */
grid_edge **edges; /* edges around this face */
grid_dot **dots; /* corners of this face */
@@ -56,8 +57,10 @@
struct grid_edge {grid_dot *dot1, *dot2;
grid_face *face1, *face2; /* Use NULL for the infinite outside face */
+ int index; /* index in grid->edges[] where this edge appears */
};
struct grid_dot {+ int index; /* index in grid->dots[] where this dot appears */
int order;
grid_edge **edges;
grid_face **faces; /* A NULL grid_face* means infinite outside face */
@@ -69,11 +72,13 @@
int x, y;
};
typedef struct grid {- /* These are (dynamically allocated) arrays of all the
- * faces, edges, dots that are in the grid. */
- int num_faces; grid_face *faces;
- int num_edges; grid_edge *edges;
- int num_dots; grid_dot *dots;
+ /* Arrays of all the faces, edges, dots that are in the grid.
+ * The arrays themselves are dynamically allocated, and so is each object
+ * inside them. num_foo indicates the number of things actually stored,
+ * and size_foo indicates the allocated size of the array. */
+ int num_faces, size_faces; grid_face **faces;
+ int num_edges, size_edges; grid_edge **edges;
+ int num_dots, size_dots; grid_dot **dots;
/* Cache the bounding-box of the grid, so the drawing-code can quickly
* figure out the proper scaling to draw onto a given area. */
--- a/loopgen.c
+++ b/loopgen.c
@@ -83,7 +83,7 @@
enum face_colour colour)
{int i, j;
- grid_face *test_face = g->faces + face_index;
+ grid_face *test_face = g->faces[face_index];
grid_face *starting_face, *current_face;
grid_dot *starting_dot;
int transitions;
@@ -348,7 +348,7 @@
* to check every face of the board (the grid structure does not keep a
* list of the infinite face's neighbours). */
for (i = 0; i < num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
struct face_score *fs = face_scores + i;
if (board[i] != FACE_GREY) continue;
/* We need the full colourability check here, it's not enough simply
@@ -430,7 +430,7 @@
del234(darkable_faces_sorted, fs);
/* Remember which face we've just coloured */
- cur_face = g->faces + i;
+ cur_face = g->faces[i];
/* The face we've just coloured potentially affects the colourability
* and the scores of any neighbouring faces (touching at a corner or
@@ -456,7 +456,7 @@
if (FACE_COLOUR(f) != FACE_GREY) continue;
/* Find the face index and face_score* corresponding to f */
- fi = f - g->faces;
+ fi = f->index;
fs = face_scores + fi;
/* Remove from lightable list if it's in there. We do this,
@@ -517,7 +517,7 @@
enum face_colour opp =
(board[j] == FACE_WHITE) ? FACE_BLACK : FACE_WHITE;
if (can_colour_face(g, board, j, opp)) {- grid_face *face = g->faces +j;
+ grid_face *face = g->faces[j];
if (do_random_pass) {/* final random pass */
if (!random_upto(rs, 10))
--- a/loopgen.h
+++ b/loopgen.h
@@ -13,7 +13,7 @@
/* face should be of type grid_face* here. */
#define FACE_COLOUR(face) \
( (face) == NULL ? FACE_BLACK : \
- board[(face) - g->faces] )
+ board[(face)->index] )
typedef int (*loopgen_bias_fn_t)(void *ctx, char *board, int face);
--- a/loopy.c
+++ b/loopy.c
@@ -1097,7 +1097,7 @@
assert(state->grid_type == 0);
/* Work out the basic size unit */
- f = g->faces; /* first face */
+ f = g->faces[0]; /* first face */
assert(f->order == 4);
/* The dots are ordered clockwise, so the two opposite
* corners are guaranteed to span the square */
@@ -1120,7 +1120,7 @@
/* Fill in edge info */
for (i = 0; i < g->num_edges; i++) {- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
/* Cell coordinates, from (0,0) to (w-1,h-1) */
int x1 = (e->dot1->x - g->lowest_x) / cell_size;
int x2 = (e->dot2->x - g->lowest_x) / cell_size;
@@ -1148,7 +1148,7 @@
for (i = 0; i < g->num_faces; i++) {int x1, x2, y1, y2;
- f = g->faces + i;
+ f = g->faces[i];
assert(f->order == 4);
/* Cell coordinates, from (0,0) to (w-1,h-1) */
x1 = (f->dots[0]->x - g->lowest_x) / cell_size;
@@ -1228,26 +1228,26 @@
#endif
g = state->game_grid;
- e = g->edges + i;
+ e = g->edges[i];
/* Update the cache for both dots and both faces affected by this. */
if (line_new == LINE_YES) {- sstate->dot_yes_count[e->dot1 - g->dots]++;
- sstate->dot_yes_count[e->dot2 - g->dots]++;
+ sstate->dot_yes_count[e->dot1->index]++;
+ sstate->dot_yes_count[e->dot2->index]++;
if (e->face1) {- sstate->face_yes_count[e->face1 - g->faces]++;
+ sstate->face_yes_count[e->face1->index]++;
}
if (e->face2) {- sstate->face_yes_count[e->face2 - g->faces]++;
+ sstate->face_yes_count[e->face2->index]++;
}
} else {- sstate->dot_no_count[e->dot1 - g->dots]++;
- sstate->dot_no_count[e->dot2 - g->dots]++;
+ sstate->dot_no_count[e->dot1->index]++;
+ sstate->dot_no_count[e->dot2->index]++;
if (e->face1) {- sstate->face_no_count[e->face1 - g->faces]++;
+ sstate->face_no_count[e->face1->index]++;
}
if (e->face2) {- sstate->face_no_count[e->face2 - g->faces]++;
+ sstate->face_no_count[e->face2->index]++;
}
}
@@ -1271,10 +1271,10 @@
{int i, j, len;
grid *g = sstate->state->game_grid;
- grid_edge *e = g->edges + edge_index;
+ grid_edge *e = g->edges[edge_index];
- i = e->dot1 - g->dots;
- j = e->dot2 - g->dots;
+ i = e->dot1->index;
+ j = e->dot2->index;
i = dsf_canonify(sstate->dotdsf, i);
j = dsf_canonify(sstate->dotdsf, j);
@@ -1332,12 +1332,12 @@
{int n = 0;
grid *g = state->game_grid;
- grid_dot *d = g->dots + dot;
+ grid_dot *d = g->dots[dot];
int i;
for (i = 0; i < d->order; i++) {grid_edge *e = d->edges[i];
- if (state->lines[e - g->edges] == line_type)
+ if (state->lines[e->index] == line_type)
++n;
}
return n;
@@ -1349,12 +1349,12 @@
{int n = 0;
grid *g = state->game_grid;
- grid_face *f = g->faces + face;
+ grid_face *f = g->faces[face];
int i;
for (i = 0; i < f->order; i++) {grid_edge *e = f->edges[i];
- if (state->lines[e - g->edges] == line_type)
+ if (state->lines[e->index] == line_type)
++n;
}
return n;
@@ -1375,10 +1375,10 @@
return false;
g = state->game_grid;
- d = g->dots + dot;
+ d = g->dots[dot];
for (i = 0; i < d->order; i++) {- int line_index = d->edges[i] - g->edges;
+ int line_index = d->edges[i]->index;
if (state->lines[line_index] == old_type) {r = solver_set_line(sstate, line_index, new_type);
assert(r);
@@ -1402,10 +1402,10 @@
return false;
g = state->game_grid;
- f = g->faces + face;
+ f = g->faces[face];
for (i = 0; i < f->order; i++) {- int line_index = f->edges[i] - g->edges;
+ int line_index = f->edges[i]->index;
if (state->lines[line_index] == old_type) {r = solver_set_line(sstate, line_index, new_type);
assert(r);
@@ -1434,7 +1434,7 @@
* algorithm does work, and there aren't any GREY faces still there. */
memset(clues, 0, g->num_faces);
for (i = 0; i < g->num_edges; i++) {- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
grid_face *f1 = e->face1;
grid_face *f2 = e->face2;
enum face_colour c1 = FACE_COLOUR(f1);
@@ -1442,8 +1442,8 @@
assert(c1 != FACE_GREY);
assert(c2 != FACE_GREY);
if (c1 != c2) {- if (f1) clues[f1 - g->faces]++;
- if (f2) clues[f2 - g->faces]++;
+ if (f1) clues[f1->index]++;
+ if (f2) clues[f2->index]++;
}
}
sfree(board);
@@ -1725,8 +1725,8 @@
/* Build the dsf. */
for (i = 0; i < g->num_edges; i++) { if (state->lines[i] == LINE_YES) {- grid_edge *e = g->edges + i;
- int d1 = e->dot1 - g->dots, d2 = e->dot2 - g->dots;
+ grid_edge *e = g->edges[i];
+ int d1 = e->dot1->index, d2 = e->dot2->index;
dsf_merge(dsf, d1, d2);
}
}
@@ -1751,10 +1751,10 @@
int unknown = dot_order(state, i, LINE_UNKNOWN);
if ((yes == 1 && unknown == 0) || (yes >= 3)) {/* violation, so mark all YES edges as errors */
- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
int j;
for (j = 0; j < d->order; j++) {- int e = d->edges[j] - g->edges;
+ int e = d->edges[j]->index;
if (state->lines[e] == LINE_YES)
state->line_errors[e] = true;
}
@@ -1817,8 +1817,8 @@
*/
for (i = 0; i < g->num_edges; i++) { if (state->lines[i] == LINE_YES) {- grid_edge *e = g->edges + i;
- int d1 = e->dot1 - g->dots; /* either endpoint is good enough */
+ grid_edge *e = g->edges[i];
+ int d1 = e->dot1->index; /* either endpoint is good enough */
int comp = dsf_canonify(dsf, d1);
if ((component_state[comp] == COMP_PATH &&
-1 != largest_comp) ||
@@ -1916,11 +1916,10 @@
if (i2 == d->order) i2 = 0;
e2 = d->edges[i2];
#endif
- ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0);
+ ret = 2 * (e->index) + ((e->dot1 == d) ? 1 : 0);
#ifdef DEBUG_DLINES
printf("dline_index_from_dot: d=%d,i=%d, edges [%d,%d] - %d\n",- (int)(d - g->dots), i, (int)(e - g->edges),
- (int)(e2 - g->edges), ret);
+ (int)(d->index), i, (int)(e->index), (int)(e2 ->index), ret);
#endif
return ret;
}
@@ -1939,11 +1938,10 @@
if (i2 < 0) i2 += f->order;
e2 = f->edges[i2];
#endif
- ret = 2 * (e - g->edges) + ((e->dot1 == d) ? 1 : 0);
+ ret = 2 * (e->index) + ((e->dot1 == d) ? 1 : 0);
#ifdef DEBUG_DLINES
printf("dline_index_from_face: f=%d,i=%d, edges [%d,%d] - %d\n",- (int)(f - g->faces), i, (int)(e - g->edges),
- (int)(e2 - g->edges), ret);
+ (int)(f->index), i, (int)(e->index), (int)(e2->index), ret);
#endif
return ret;
}
@@ -2001,9 +1999,9 @@
opp2 = opp + 1;
if (opp2 == N) opp2 = 0;
/* Check if opp, opp2 point to LINE_UNKNOWNs */
- if (state->lines[d->edges[opp] - g->edges] != LINE_UNKNOWN)
+ if (state->lines[d->edges[opp]->index] != LINE_UNKNOWN)
continue;
- if (state->lines[d->edges[opp2] - g->edges] != LINE_UNKNOWN)
+ if (state->lines[d->edges[opp2]->index] != LINE_UNKNOWN)
continue;
/* Found opposite UNKNOWNS and they're next to each other */
opp_dline_index = dline_index_from_dot(g, d, opp);
@@ -2025,7 +2023,7 @@
bool retval = false;
game_state *state = sstate->state;
grid *g = state->game_grid;
- grid_face *f = g->faces + face_index;
+ grid_face *f = g->faces[face_index];
int N = f->order;
int i, j;
int can1, can2;
@@ -2032,11 +2030,11 @@
bool inv1, inv2;
for (i = 0; i < N; i++) {- int line1_index = f->edges[i] - g->edges;
+ int line1_index = f->edges[i]->index;
if (state->lines[line1_index] != LINE_UNKNOWN)
continue;
for (j = i + 1; j < N; j++) {- int line2_index = f->edges[j] - g->edges;
+ int line2_index = f->edges[j]->index;
if (state->lines[line2_index] != LINE_UNKNOWN)
continue;
@@ -2060,9 +2058,8 @@
int *e /* Returned edge indices */)
{int c = 0;
- grid *g = state->game_grid;
while (c < expected_count) {- int line_index = *edge_list - g->edges;
+ int line_index = (*edge_list)->index;
if (state->lines[line_index] == LINE_UNKNOWN) {e[c] = line_index;
c++;
@@ -2191,7 +2188,7 @@
/* Per-face deductions */
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
if (sstate->face_solved[i])
continue;
@@ -2249,22 +2246,22 @@
int j, k, e1, e2, e, d;
for (j = 0; j < f->order; j++) {- e1 = f->edges[j] - g->edges;
- e2 = f->edges[j+1 < f->order ? j+1 : 0] - g->edges;
+ e1 = f->edges[j]->index;
+ e2 = f->edges[j+1 < f->order ? j+1 : 0]->index;
- if (g->edges[e1].dot1 == g->edges[e2].dot1 ||
- g->edges[e1].dot1 == g->edges[e2].dot2) {- d = g->edges[e1].dot1 - g->dots;
+ if (g->edges[e1]->dot1 == g->edges[e2]->dot1 ||
+ g->edges[e1]->dot1 == g->edges[e2]->dot2) {+ d = g->edges[e1]->dot1->index;
} else {- assert(g->edges[e1].dot2 == g->edges[e2].dot1 ||
- g->edges[e1].dot2 == g->edges[e2].dot2);
- d = g->edges[e1].dot2 - g->dots;
+ assert(g->edges[e1]->dot2 == g->edges[e2]->dot1 ||
+ g->edges[e1]->dot2 == g->edges[e2]->dot2);
+ d = g->edges[e1]->dot2->index;
}
if (state->lines[e1] == LINE_UNKNOWN &&
state->lines[e2] == LINE_UNKNOWN) {- for (k = 0; k < g->dots[d].order; k++) {- int e = g->dots[d].edges[k] - g->edges;
+ for (k = 0; k < g->dots[d]->order; k++) {+ int e = g->dots[d]->edges[k]->index;
if (state->lines[e] == LINE_YES)
goto found; /* multi-level break */
}
@@ -2278,7 +2275,7 @@
* they're e1 and e2.
*/
for (j = 0; j < f->order; j++) {- e = f->edges[j] - g->edges;
+ e = f->edges[j]->index;
if (state->lines[e] == LINE_UNKNOWN && e != e1 && e != e2) {bool r = solver_set_line(sstate, e, LINE_YES);
assert(r);
@@ -2292,7 +2289,7 @@
/* Per-dot deductions */
for (i = 0; i < g->num_dots; i++) {- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
int yes, no, unknown;
if (sstate->dot_solved[i])
@@ -2389,7 +2386,7 @@
for (i = 0; i < g->num_faces; i++) {int maxs[MAX_FACE_SIZE][MAX_FACE_SIZE];
int mins[MAX_FACE_SIZE][MAX_FACE_SIZE];
- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
int N = f->order;
int j,m;
int clue = state->clues[i];
@@ -2400,7 +2397,7 @@
/* Calculate the (j,j+1) entries */
for (j = 0; j < N; j++) {- int edge_index = f->edges[j] - g->edges;
+ int edge_index = f->edges[j]->index;
int dline_index;
enum line_state line1 = state->lines[edge_index];
enum line_state line2;
@@ -2411,7 +2408,7 @@
mins[j][k] = (line1 == LINE_YES) ? 1 : 0;
/* Calculate the (j,j+2) entries */
dline_index = dline_index_from_face(g, f, k);
- edge_index = f->edges[k] - g->edges;
+ edge_index = f->edges[k]->index;
line2 = state->lines[edge_index];
k++;
if (k >= N) k = 0;
@@ -2456,7 +2453,7 @@
for (j = 0; j < N; j++) {int k;
grid_edge *e = f->edges[j];
- int line_index = e - g->edges;
+ int line_index = e->index;
int dline_index;
if (state->lines[line_index] != LINE_UNKNOWN)
@@ -2491,7 +2488,7 @@
if (sstate->diff >= DIFF_TRICKY) { /* Now see if we can make dline deduction for edges{j,j+1} */e = f->edges[k];
- if (state->lines[e - g->edges] != LINE_UNKNOWN)
+ if (state->lines[e->index] != LINE_UNKNOWN)
/* Only worth doing this for an UNKNOWN,UNKNOWN pair.
* Dlines where one of the edges is known, are handled in the
* dot-deductions */
@@ -2523,7 +2520,7 @@
/* ------ Dot deductions ------ */
for (i = 0; i < g->num_dots; i++) {- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
int N = d->order;
int yes, no, unknown;
int j;
@@ -2541,8 +2538,8 @@
k = j + 1;
if (k >= N) k = 0;
dline_index = dline_index_from_dot(g, d, j);
- line1_index = d->edges[j] - g->edges;
- line2_index = d->edges[k] - g->edges;
+ line1_index = d->edges[j]->index;
+ line2_index = d->edges[k] ->index;
line1 = state->lines[line1_index];
line2 = state->lines[line2_index];
@@ -2639,7 +2636,7 @@
int opp_index;
if (opp == j || opp == k)
continue;
- opp_index = d->edges[opp] - g->edges;
+ opp_index = d->edges[opp]->index;
if (state->lines[opp_index] == LINE_UNKNOWN) {solver_set_line(sstate, opp_index,
LINE_YES);
@@ -2690,7 +2687,7 @@
if (clue < 0)
continue;
- N = g->faces[i].order;
+ N = g->faces[i]->order;
yes = sstate->face_yes_count[i];
if (yes + 1 == clue) {if (face_setall_identical(sstate, i, LINE_NO))
@@ -2708,7 +2705,7 @@
/* Deductions with small number of LINE_UNKNOWNs, based on overall
* parity of lines. */
- diff_tmp = parity_deductions(sstate, g->faces[i].edges,
+ diff_tmp = parity_deductions(sstate, g->faces[i]->edges,
(clue - yes) % 2, unknown);
diff = min(diff, diff_tmp);
}
@@ -2715,7 +2712,7 @@
/* ------ Dot deductions ------ */
for (i = 0; i < g->num_dots; i++) {- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
int N = d->order;
int j;
int yes, no, unknown;
@@ -2728,12 +2725,12 @@
int can1, can2;
bool inv1, inv2;
int j2;
- line1_index = d->edges[j] - g->edges;
+ line1_index = d->edges[j]->index;
if (state->lines[line1_index] != LINE_UNKNOWN)
continue;
j2 = j + 1;
if (j2 == N) j2 = 0;
- line2_index = d->edges[j2] - g->edges;
+ line2_index = d->edges[j2]->index;
if (state->lines[line2_index] != LINE_UNKNOWN)
continue;
/* Infer dline flags from linedsf */
@@ -2855,9 +2852,9 @@
* loop it would create is a solution.
*/
for (i = 0; i < g->num_edges; i++) {- grid_edge *e = g->edges + i;
- int d1 = e->dot1 - g->dots;
- int d2 = e->dot2 - g->dots;
+ grid_edge *e = g->edges[i];
+ int d1 = e->dot1->index;
+ int d2 = e->dot2->index;
int eqclass, val;
if (state->lines[i] != LINE_UNKNOWN)
continue;
@@ -2894,13 +2891,13 @@
*/
sm1_nearby = 0;
if (e->face1) {- int f = e->face1 - g->faces;
+ int f = e->face1->index;
int c = state->clues[f];
if (c >= 0 && sstate->face_yes_count[f] == c - 1)
sm1_nearby++;
}
if (e->face2) {- int f = e->face2 - g->faces;
+ int f = e->face2->index;
int c = state->clues[f];
if (c >= 0 && sstate->face_yes_count[f] == c - 1)
sm1_nearby++;
@@ -3065,7 +3062,7 @@
if (e == NULL)
return NULL;
- i = e - g->edges;
+ i = e->index;
/* I think it's only possible to play this game with mouse clicks, sorry */
/* Maybe will add mouse drag support some time */
@@ -3126,7 +3123,7 @@
for (j = n_found = 0; j < dot->order; j++) {grid_edge *e_candidate = dot->edges[j];
- int i_candidate = e_candidate - g->edges;
+ int i_candidate = e_candidate->index;
if (e_candidate != e_this &&
(ui->autofollow == AF_FIXED ||
state->lines[i] == LINE_NO ||
@@ -3137,7 +3134,7 @@
}
if (n_found != 1 ||
- state->lines[e_next - g->edges] != state->lines[i])
+ state->lines[e_next->index] != state->lines[i])
break;
if (e_next == e) {@@ -3164,7 +3161,7 @@
}
e_this = e_next;
movelen += sprintf(movebuf+movelen, "%d%c",
- (int)(e_this - g->edges), button_char);
+ (int)(e_this->index), button_char);
}
autofollow_done:;
}
@@ -3237,7 +3234,7 @@
static void face_text_pos(const game_drawstate *ds, const grid *g,
grid_face *f, int *xret, int *yret)
{- int faceindex = f - g->faces;
+ int faceindex = f->index;
/*
* Return the cached position for this face, if we've already
@@ -3280,7 +3277,7 @@
const game_state *state, int i)
{grid *g = state->game_grid;
- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
int x, y;
char c[20];
@@ -3345,7 +3342,7 @@
const game_state *state, int i, int phase)
{grid *g = state->game_grid;
- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
int x1, x2, y1, y2;
int line_colour;
@@ -3384,7 +3381,7 @@
const game_state *state, int i)
{grid *g = state->game_grid;
- grid_dot *d = g->dots + i;
+ grid_dot *d = g->dots[i];
int x, y;
grid_to_screen(ds, g, d->x, d->y, &x, &y);
@@ -3415,7 +3412,7 @@
for (i = 0; i < g->num_faces; i++) { if (state->clues[i] >= 0) {- face_text_bbox(ds, g, &g->faces[i], &bx, &by, &bw, &bh);
+ face_text_bbox(ds, g, g->faces[i], &bx, &by, &bw, &bh);
if (boxes_intersect(x, y, w, h, bx, by, bw, bh))
game_redraw_clue(dr, ds, state, i);
}
@@ -3422,13 +3419,13 @@
}
for (phase = 0; phase < NPHASES; phase++) { for (i = 0; i < g->num_edges; i++) {- edge_bbox(ds, g, &g->edges[i], &bx, &by, &bw, &bh);
+ edge_bbox(ds, g, g->edges[i], &bx, &by, &bw, &bh);
if (boxes_intersect(x, y, w, h, bx, by, bw, bh))
game_redraw_line(dr, ds, ui, state, i, phase);
}
}
for (i = 0; i < g->num_dots; i++) {- dot_bbox(ds, g, &g->dots[i], &bx, &by, &bw, &bh);
+ dot_bbox(ds, g, g->dots[i], &bx, &by, &bw, &bh);
if (boxes_intersect(x, y, w, h, bx, by, bw, bh))
game_redraw_dot(dr, ds, state, i);
}
@@ -3488,7 +3485,7 @@
/* First, trundle through the faces. */
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
int sides = f->order;
int yes_order, no_order;
bool clue_mistake;
@@ -3588,7 +3585,7 @@
/* Right. Now we roll up our sleeves. */
for (i = 0; i < nfaces; i++) {- grid_face *f = g->faces + faces[i];
+ grid_face *f = g->faces[faces[i]];
int x, y, w, h;
face_text_bbox(ds, g, f, &x, &y, &w, &h);
@@ -3596,7 +3593,7 @@
}
for (i = 0; i < nedges; i++) {- grid_edge *e = g->edges + edges[i];
+ grid_edge *e = g->edges[edges[i]];
int x, y, w, h;
edge_bbox(ds, g, e, &x, &y, &w, &h);
@@ -3660,7 +3657,7 @@
for (i = 0; i < g->num_dots; i++) {int x, y;
- grid_to_screen(ds, g, g->dots[i].x, g->dots[i].y, &x, &y);
+ grid_to_screen(ds, g, g->dots[i]->x, g->dots[i]->y, &x, &y);
draw_circle(dr, x, y, ds->tilesize / 15, ink, ink);
}
@@ -3668,7 +3665,7 @@
* Clues.
*/
for (i = 0; i < g->num_faces; i++) {- grid_face *f = g->faces + i;
+ grid_face *f = g->faces[i];
int clue = state->clues[i];
if (clue >= 0) {char c[20];
@@ -3686,7 +3683,7 @@
*/
for (i = 0; i < g->num_edges; i++) {int thickness = (state->lines[i] == LINE_YES) ? 30 : 150;
- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
int x1, y1, x2, y2;
grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1);
grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2);
--- a/pearl.c
+++ b/pearl.c
@@ -980,9 +980,9 @@
* to reprocess the edges for this boundary.
*/
if (oldface == c || newface == c) {- grid_face *f = &g->faces[face];
+ grid_face *f = g->faces[face];
for (k = 0; k < f->order; k++)
- tdq_add(b->edges_todo, f->edges[k] - g->edges);
+ tdq_add(b->edges_todo, f->edges[k]->index);
}
}
}
@@ -998,15 +998,15 @@
* the vertextypes_todo list.
*/
while ((j = tdq_remove(b->edges_todo)) >= 0) {- grid_edge *e = &g->edges[j];
- int fc1 = e->face1 ? board[e->face1 - g->faces] : FACE_BLACK;
- int fc2 = e->face2 ? board[e->face2 - g->faces] : FACE_BLACK;
+ grid_edge *e = g->edges[j];
+ int fc1 = e->face1 ? board[e->face1->index] : FACE_BLACK;
+ int fc2 = e->face2 ? board[e->face2->index] : FACE_BLACK;
bool oldedge = b->edges[j];
bool newedge = (fc1==c) ^ (fc2==c);
if (oldedge != newedge) {b->edges[j] = newedge;
- tdq_add(b->vertextypes_todo, e->dot1 - g->dots);
- tdq_add(b->vertextypes_todo, e->dot2 - g->dots);
+ tdq_add(b->vertextypes_todo, e->dot1->index);
+ tdq_add(b->vertextypes_todo, e->dot2->index);
}
}
@@ -1021,7 +1021,7 @@
* old neighbours.
*/
while ((j = tdq_remove(b->vertextypes_todo)) >= 0) {- grid_dot *d = &g->dots[j];
+ grid_dot *d = g->dots[j];
int neighbours[2], type = 0, n = 0;
for (k = 0; k < d->order; k++) {@@ -1029,10 +1029,10 @@
grid_dot *d2 = (e->dot1 == d ? e->dot2 : e->dot1);
/* dir == 0,1,2,3 for an edge going L,U,R,D */
int dir = (d->y == d2->y) + 2*(d->x+d->y > d2->x+d2->y);
- int ei = e - g->edges;
+ int ei = e->index;
if (b->edges[ei]) {type |= 1 << dir;
- neighbours[n] = d2 - g->dots;
+ neighbours[n] = d2->index;
n++;
}
}
@@ -1141,7 +1141,7 @@
}
for (i = 0; i < g->num_edges; i++) {- grid_edge *e = g->edges + i;
+ grid_edge *e = g->edges[i];
enum face_colour c1 = FACE_COLOUR(e->face1);
enum face_colour c2 = FACE_COLOUR(e->face2);
assert(c1 != FACE_GREY);