ref: 348aac4c85da21e09c29c58866d178df3204d73c
parent: dad2f35502c611dae758915cfb6dface4a303550
author: Simon Tatham <anakin@pobox.com>
date: Thu Apr 20 10:46:46 EDT 2023
Remove size parameter from dsf init and copy functions. Now that the dsf knows its own size internally, there's no need to tell it again when one is copied or reinitialised. This makes dsf_init much more about *re*initialising a dsf, since now dsfs are always allocated using a function that will initialise them anyway. So I think it deserves a rename.
--- a/bridges.c
+++ b/bridges.c
@@ -1140,13 +1140,13 @@
static void map_group(game_state *state)
{- int i, wh = state->w*state->h, d1, d2;
+ int i, d1, d2;
int x, y, x2, y2;
DSF *dsf = state->solver->dsf;
struct island *is, *is_join;
/* Initialise dsf. */
- dsf_init(dsf, wh);
+ dsf_reinit(dsf);
/* For each island, find connected islands right or down
* and merge the dsf for the island squares as well as the
@@ -1532,7 +1532,6 @@
{int i, n, x, y, missing, spc, curr, maxb;
bool didsth = false;
- int wh = is->state->w * is->state->h;
struct solver_state *ss = is->state->solver;
assert(didsth_r);
@@ -1556,7 +1555,7 @@
maxb = -1;
/* We have to squirrel the dsf away and restore it afterwards;
* it is additive only, and can't be removed from. */
- dsf_copy(ss->tmpdsf, ss->dsf, wh);
+ dsf_copy(ss->tmpdsf, ss->dsf);
for (n = curr+1; n <= curr+spc; n++) {solve_join(is, i, n, false);
map_update_possibles(is->state);
@@ -1572,7 +1571,7 @@
}
}
solve_join(is, i, curr, false); /* put back to before. */
- dsf_copy(ss->dsf, ss->tmpdsf, wh);
+ dsf_copy(ss->dsf, ss->tmpdsf);
if (maxb != -1) {/*debug_state(is->state);*/
@@ -1641,7 +1640,7 @@
is->adj.points[j].dx ? G_LINEH : G_LINEV);
if (before[i] != 0) continue; /* this idea is pointless otherwise */
- dsf_copy(ss->tmpdsf, ss->dsf, wh);
+ dsf_copy(ss->tmpdsf, ss->dsf);
for (j = 0; j < is->adj.npoints; j++) {spc = island_adjspace(is, true, missing, j);
@@ -1656,7 +1655,7 @@
for (j = 0; j < is->adj.npoints; j++)
solve_join(is, j, before[j], false);
- dsf_copy(ss->dsf, ss->tmpdsf, wh);
+ dsf_copy(ss->dsf, ss->tmpdsf);
if (got) { debug(("island at (%d,%d) must connect in direction (%d,%d) to"--- a/dominosa.c
+++ b/dominosa.c
@@ -1438,7 +1438,7 @@
* class for each entire forcing chain, with the two possible sets
* of dominoes for the chain listed as inverses.
*/
- dsf_init(sc->dsf_scratch, sc->pc);
+ dsf_reinit(sc->dsf_scratch);
for (si = 0; si < sc->wh; si++) {struct solver_square *sq = &sc->squares[si];
if (sq->nplacements == 2)
--- a/dsf.c
+++ b/dsf.c
@@ -66,11 +66,12 @@
sfree(inverse_elements);
}*/
-void dsf_init(DSF *dsf, int size)
+void dsf_reinit(DSF *dsf)
{int i;
- for (i = 0; i < size; i++) dsf->p[i] = 6;
+ for (i = 0; i < dsf->size; i++)
+ dsf->p[i] = 6;
/* Bottom bit of each element of this array stores whether that
* element is opposite to its parent, which starts off as
* false. Second bit of each element stores whether that element
@@ -79,9 +80,10 @@
* bits are the number of elements in the tree. */
}
-void dsf_copy(DSF *to, DSF *from, int size)
+void dsf_copy(DSF *to, DSF *from)
{- memcpy(to->p, from->p, size * sizeof(int));
+ assert(to->size == from->size && "Mismatch in dsf_copy");
+ memcpy(to->p, from->p, to->size * sizeof(int));
}
DSF *snew_dsf(int size)
@@ -90,7 +92,7 @@
ret->size = size;
ret->p = snewn(size, int);
- dsf_init(ret, size);
+ dsf_reinit(ret);
/*print_dsf(ret, size); */
--- a/filling.c
+++ b/filling.c
@@ -411,7 +411,7 @@
dsf = snew_dsf(sz);
retry:
- dsf_init(dsf, sz);
+ dsf_reinit(dsf);
shuffle(board, sz, sizeof (int), rs);
do {@@ -946,7 +946,7 @@
* have a completely new n-region in it.
*/
for (n = 1; n <= 9; n++) {- dsf_init(dsf, sz);
+ dsf_reinit(dsf);
/* Build the dsf */
for (y = 0; y < h; y++)
@@ -1137,7 +1137,7 @@
if (!dsf)
dsf = snew_dsf(w * h);
else
- dsf_init(dsf, w * h);
+ dsf_reinit(dsf);
for (i = 0; i < sz; ++i) {int j;
--- a/galaxies.c
+++ b/galaxies.c
@@ -2283,7 +2283,7 @@
* doesn't contain its own dot is an 'exclave', and will need some
* kind of path of tiles to connect it back to the dot.
*/
- dsf_init(sctx->dsf, sctx->sz);
+ dsf_reinit(sctx->dsf);
for (x = 1; x < state->sx; x += 2) { for (y = 1; y < state->sy; y += 2) {int dotx, doty;
@@ -3084,7 +3084,7 @@
dsf = snew_dsf(w*h);
free_dsf = true;
} else {- dsf_init(dsf, w*h);
+ dsf_reinit(dsf);
free_dsf = false;
}
--- a/keen.c
+++ b/keen.c
@@ -821,11 +821,10 @@
static const char *parse_block_structure(const char **p, int w, DSF *dsf)
{- int a = w*w;
int pos = 0;
int repc = 0, repn = 0;
- dsf_init(dsf, a);
+ dsf_reinit(dsf);
while (**p && (repn > 0 || **p != ',')) {int c;
@@ -960,7 +959,7 @@
for (i = 0; i < a; i++)
singletons[i] = true;
- dsf_init(dsf, a);
+ dsf_reinit(dsf);
/* Place dominoes. */
for (i = 0; i < a; i++) {--- a/loopy.c
+++ b/loopy.c
@@ -457,7 +457,7 @@
ret->dotdsf = snew_dsf(num_dots);
ret->looplen = snewn(num_dots, int);
- dsf_copy(ret->dotdsf, sstate->dotdsf, num_dots);
+ dsf_copy(ret->dotdsf, sstate->dotdsf);
memcpy(ret->looplen, sstate->looplen,
num_dots * sizeof(int));
@@ -486,7 +486,7 @@
if (sstate->linedsf) {ret->linedsf = snew_dsf(num_edges);
- dsf_copy(ret->linedsf, sstate->linedsf, num_edges);
+ dsf_copy(ret->linedsf, sstate->linedsf);
} else {ret->linedsf = NULL;
}
--- a/pearl.c
+++ b/pearl.c
@@ -593,7 +593,7 @@
{int nonblanks, loopclass;
- dsf_init(dsf, w*h);
+ dsf_reinit(dsf);
for (x = 0; x < w*h; x++)
dsfsize[x] = 1;
--- a/puzzles.h
+++ b/puzzles.h
@@ -432,7 +432,7 @@
void print_dsf(DSF *dsf, int size);
-void dsf_copy(DSF *to, DSF *from, int size);
+void dsf_copy(DSF *to, DSF *from);
/* Return the canonical element of the equivalence class containing element
* val. If 'inverse' is non-NULL, this function will put into it a flag
@@ -448,7 +448,9 @@
* be both opposite and non-opposite. */
void edsf_merge(DSF *dsf, int v1, int v2, bool inverse);
void dsf_merge(DSF *dsf, int v1, int v2);
-void dsf_init(DSF *dsf, int len);
+
+/* Reinitialise a dsf to the starting 'all elements distinct' state. */
+void dsf_reinit(DSF *dsf);
/*
* tdq.c
--- a/signpost.c
+++ b/signpost.c
@@ -282,7 +282,7 @@
memset(state->next, -1, state->n*sizeof(int));
memset(state->prev, -1, state->n*sizeof(int));
memset(state->numsi, -1, (state->n+1)*sizeof(int));
- dsf_init(state->dsf, state->n);
+ dsf_reinit(state->dsf);
}
static bool check_nums(game_state *orig, game_state *copy, bool only_immutable)
@@ -482,7 +482,7 @@
memcpy(to->next, from->next, to->n*sizeof(int));
memcpy(to->prev, from->prev, to->n*sizeof(int));
- dsf_copy(to->dsf, from->dsf, to->n);
+ dsf_copy(to->dsf, from->dsf);
memcpy(to->numsi, from->numsi, (to->n+1)*sizeof(int));
}
@@ -1018,7 +1018,7 @@
{int i, di, dni;
- dsf_init(state->dsf, state->n);
+ dsf_reinit(state->dsf);
for (i = 0; i < state->n; i++) { if (state->next[i] != -1) {assert(state->prev[state->next[i]] == i);
--- a/singles.c
+++ b/singles.c
@@ -439,7 +439,7 @@
/* Construct a dsf array for connected blocks; connections
* tracked to right and down. */
- dsf_init(dsf, state->n);
+ dsf_reinit(dsf);
for (x = 0; x < state->w; x++) { for (y = 0; y < state->h; y++) {i = y*state->w + x;
--- a/slant.c
+++ b/slant.c
@@ -472,13 +472,13 @@
* Establish a disjoint set forest for tracking connectedness
* between grid points.
*/
- dsf_init(sc->connected, W*H);
+ dsf_reinit(sc->connected);
/*
* Establish a disjoint set forest for tracking which squares
* are known to slant in the same direction.
*/
- dsf_init(sc->equiv, w*h);
+ dsf_reinit(sc->equiv);
/*
* Clear the slashval array.
--- a/tents.c
+++ b/tents.c
@@ -2267,7 +2267,7 @@
* start of the game, before the user had done anything wrong!)
*/
#define TENT(x) ((x)==TENT || (x)==BLANK)
- dsf_init(dsf, w*h);
+ dsf_reinit(dsf);
/* Construct the equivalence classes. */
for (y = 0; y < h; y++) { for (x = 0; x < w-1; x++) {--- a/tracks.c
+++ b/tracks.c
@@ -1466,7 +1466,7 @@
if (!sc->dsf)
sc->dsf = snew_dsf(wh);
- dsf_init(sc->dsf, wh);
+ dsf_reinit(sc->dsf);
for (xi = 0; xi < w; xi++) { for (yi = 0; yi < h; yi++) {--- a/unfinished/separate.c
+++ b/unfinished/separate.c
@@ -331,7 +331,7 @@
* contents array, however, because this will change if we
* adjust the letter arrangement and re-run the solver.
*/
- dsf_init(sc->dsf, wh);
+ dsf_reinit(sc->dsf);
for (i = 0; i < wh; i++) sc->size[i] = 1;
memset(sc->disconnect, 0, wh*wh * sizeof(bool));
}