shithub: puzzles

Info  •  Files  •  Log  •  Branches

Stop putting dsfs in existing scratch int arrays.

I'm going to work towards turning 'dsf' into an opaque type, so that I
can improve its implementation without breaking clients. The first
step is to deal manually with puzzles that currently reuse a single
array of ints for multiple purposes, some of which are dsf and some
are not.

In divvy_rectangle_attempt, 'tmp' was used as an int array and later a
dsf, and I've made a new 'tmpdsf' to be the latter.

In Dominosa, solver->pc_scratch2 was sometimes a dsf, and now there's
a new solver->dsf_scratch.

In Map, parse_edge_list() needed a dsf internally and then never
exported it; it expected to be passed an array of 2*w*h ints and used
the second half as a dsf. Now it expects only w*h ints, and allocates
its own dsf internally, freeing it again before returning.

And in Tents, find_errors() was allocating a single block of 2*w*h
ints and using the second half of it as a dsf, apparently just to save
one malloc. Now we malloc and free the dsf separately.

--- a/divvy.c

+++ b/divvy.c

@@ -262,7 +262,7 @@

  */

 int *divvy_rectangle_attempt(int w, int h, int k, random_state *rs)

 {

-    int *order, *queue, *tmp, *own, *sizes, *addable, *retdsf;

+    int *order, *queue, *tmp, *own, *sizes, *addable, *retdsf, *tmpdsf;

     bool *removable;

     int wh = w*h;

     int i, j, n, x, y, qhead, qtail;

@@ -277,6 +277,7 @@

     queue = snewn(n, int);

     addable = snewn(wh*4, int);

     removable = snewn(wh, bool);

+    retdsf = tmpdsf = NULL;

     /*

      * Permute the grid squares into a random order, which will be

@@ -619,18 +620,18 @@

      * the ominoes really are k-ominoes and we haven't

      * accidentally split one into two disconnected pieces.

      */

-    dsf_init(tmp, wh);

+    tmpdsf = snew_dsf(wh);

     for (y = 0; y < h; y++)

 	for (x = 0; x+1 < w; x++)

 	    if (own[y*w+x] == own[y*w+(x+1)])

-		dsf_merge(tmp, y*w+x, y*w+(x+1));

+		dsf_merge(tmpdsf, y*w+x, y*w+(x+1));

     for (x = 0; x < w; x++)

 	for (y = 0; y+1 < h; y++)

 	    if (own[y*w+x] == own[(y+1)*w+x])

-		dsf_merge(tmp, y*w+x, (y+1)*w+x);

+		dsf_merge(tmpdsf, y*w+x, (y+1)*w+x);

     for (i = 0; i < wh; i++) {

 	j = dsf_canonify(retdsf, i);

-	assert(dsf_canonify(tmp, j) == dsf_canonify(tmp, i));

+	assert(dsf_canonify(tmpdsf, j) == dsf_canonify(tmpdsf, i));

     }

     cleanup:

@@ -640,6 +641,7 @@

      */

     sfree(order);

     sfree(tmp);

+    sfree(tmpdsf);

     sfree(own);

     sfree(sizes);

     sfree(queue);

--- a/dominosa.c

+++ b/dominosa.c

@@ -350,7 +350,7 @@

     struct solver_square **squares_by_number;

     struct findloopstate *fls;

     bool squares_by_number_initialised;

-    int *wh_scratch, *pc_scratch, *pc_scratch2, *dc_scratch;

+    int *wh_scratch, *pc_scratch, *pc_scratch2, *dc_scratch, *dsf_scratch;

 };

 static struct solver_scratch *solver_make_scratch(int n)

@@ -482,6 +482,7 @@

     sc->wh_scratch = NULL;

     sc->pc_scratch = sc->pc_scratch2 = NULL;

     sc->dc_scratch = NULL;

+    sc->dsf_scratch = NULL;

     return sc;

 }

@@ -509,6 +510,7 @@

     sfree(sc->pc_scratch);

     sfree(sc->pc_scratch2);

     sfree(sc->dc_scratch);

+    sfree(sc->dsf_scratch);

     sfree(sc);

 }

@@ -1425,19 +1427,21 @@

         sc->pc_scratch2 = snewn(sc->pc, int);

     if (!sc->dc_scratch)

         sc->dc_scratch = snewn(sc->dc, int);

+    if (!sc->dsf_scratch)

+        sc->dsf_scratch = snew_dsf(sc->pc);

     /*

      * Start by identifying chains of placements which must all occur

      * together if any of them occurs. We do this by making

-     * pc_scratch2 an edsf binding the placements into an equivalence

+     * dsf_scratch an edsf binding the placements into an equivalence

      * class for each entire forcing chain, with the two possible sets

      * of dominoes for the chain listed as inverses.

      */

-    dsf_init(sc->pc_scratch2, sc->pc);

+    dsf_init(sc->dsf_scratch, sc->pc);

     for (si = 0; si < sc->wh; si++) {

         struct solver_square *sq = &sc->squares[si];

         if (sq->nplacements == 2)

-            edsf_merge(sc->pc_scratch2,

+            edsf_merge(sc->dsf_scratch,

                        sq->placements[0]->index,

                        sq->placements[1]->index, true);

     }

@@ -1452,7 +1456,7 @@

      */

     for (pi = 0; pi < sc->pc; pi++) {

         bool inv;

-        int c = edsf_canonify(sc->pc_scratch2, pi, &inv);

+        int c = edsf_canonify(sc->dsf_scratch, pi, &inv);

         sc->pc_scratch[pi] = c * 2 + (inv ? 1 : 0);

     }

--- a/map.c

+++ b/map.c

@@ -1724,9 +1724,9 @@

     int i, k, pos;

     bool state;

     const char *p = *desc;

+    const char *err = NULL;

+    int *dsf = snew_dsf(wh);

-    dsf_init(map+wh, wh);

-

     pos = -1;

     state = false;

@@ -1736,8 +1736,10 @@

      * pairs of squares whenever the edge list shows a non-edge).

      */

     while (*p && *p != ',') {

-	if (*p < 'a' || *p > 'z')

-	    return "Unexpected character in edge list";

+	if (*p < 'a' || *p > 'z') {

+            err = "Unexpected character in edge list";

+            goto out;

+        }

 	if (*p == 'z')

 	    k = 25;

 	else

@@ -1760,10 +1762,12 @@

 		y = (pos - w*(h-1)) % h;

 		dx = 1;

 		dy = 0;

-	    } else

-		return "Too much data in edge list";

+	    } else {

+                err = "Too much data in edge list";

+                goto out;

+            }

 	    if (!state)

-		dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx));

+		dsf_merge(dsf, y*w+x, (y+dy)*w+(x+dx));

 	    pos++;

 	}

@@ -1772,8 +1776,10 @@

 	p++;

     }

     assert(pos <= 2*wh-w-h);

-    if (pos < 2*wh-w-h)

-	return "Too little data in edge list";

+    if (pos < 2*wh-w-h) {

+        err = "Too little data in edge list";

+        goto out;

+    }

     /*

      * Now go through again and allocate region numbers.

@@ -1782,17 +1788,22 @@

     for (i = 0; i < wh; i++)

 	map[i] = -1;

     for (i = 0; i < wh; i++) {

-	k = dsf_canonify(map+wh, i);

+	k = dsf_canonify(dsf, i);

 	if (map[k] < 0)

 	    map[k] = pos++;

 	map[i] = map[k];

     }

-    if (pos != n)

-	return "Edge list defines the wrong number of regions";

+    if (pos != n) {

+        err = "Edge list defines the wrong number of regions";

+        goto out;

+    }

     *desc = p;

+    err = NULL; /* no error */

-    return NULL;

+  out:

+    sfree(dsf);

+    return err;

 }

 static const char *validate_desc(const game_params *params, const char *desc)

@@ -1802,7 +1813,7 @@

     int *map;

     const char *ret;

-    map = snewn(2*wh, int);

+    map = snewn(wh, int);

     ret = parse_edge_list(params, &desc, map);

     sfree(map);

     if (ret)

--- a/tents.c

+++ b/tents.c

@@ -2006,7 +2006,7 @@

 {

     int w = state->p.w, h = state->p.h;

     int *ret = snewn(w*h + w + h, int);

-    int *tmp = snewn(w*h*2, int), *dsf = tmp + w*h;

+    int *tmp = snewn(w*h, int), *dsf;

     int x, y;

     /*

@@ -2223,7 +2223,7 @@

      * all the tents in any component which has a smaller tree

      * count.

      */

-    dsf_init(dsf, w*h);

+    dsf = snew_dsf(w*h);

     /* Construct the equivalence classes. */

     for (y = 0; y < h; y++) {

 	for (x = 0; x < w-1; x++) {

@@ -2302,6 +2302,7 @@

 #undef TENT

     sfree(tmp);

+    sfree(dsf);

     return ret;

 }