shithub: mc

Info  •  Files  •  Log  •  Branches

Grow the adjacency lists incrementally.

	We don't need to waste *THAT* much RAM on them.

--- a/6/asm.h

+++ b/6/asm.h

@@ -190,6 +190,7 @@

 	size_t *gbits;      /* igraph matrix repr */

 	regid **gadj;      /* igraph adj set repr */

 	size_t *ngadj;

+	size_t *gadjsz;

 	size_t nreg;      /* maxregid at time of alloc */

 	int *degree;        /* degree of nodes */

 	int *nuses;         /* number of uses of nodes */

--- a/6/ra.c

+++ b/6/ra.c

@@ -371,8 +371,10 @@

 static void alputedge(Isel *s, regid u, regid v)

 {

-	if (!s->gadj[u])

-		s->gadj[u] = xalloc(maxregid*sizeof(regid));

+	if (s->ngadj[u] == s->gadjsz[u]) {

+		s->gadjsz[u] = s->gadjsz[u]*2 + 1;

+		s->gadj[u] = xrealloc(s->gadj[u], s->gadjsz[u]*sizeof(regid));

+	}

 	s->gadj[u][s->ngadj[u]] = v;

 	s->ngadj[u]++;

 }

@@ -444,6 +446,7 @@

 	/* fresh adj list repr. */

 	s->gadj = zalloc(s->nreg * sizeof(regid*));

 	s->ngadj = zalloc(s->nreg * sizeof(size_t));

+	s->gadjsz = zalloc(s->nreg * sizeof(size_t));

 	s->mactiveset = bsclear(s->mactiveset);

 	s->wlmoveset = bsclear(s->wlmoveset);