From 8b1fa00fdab8c024ae6ab72c84bce8dc41a28167 Mon Sep 17 00:00:00 2001 From: north Date: Mon, 15 Feb 2010 20:25:46 +0000 Subject: [PATCH] Fixes for stability; large graphs --- lib/cgraph/edge.c | 42 ++++++++++++++++++++++++++---------------- lib/cgraph/graph.c | 6 ++++-- lib/cgraph/mem.c | 2 +- lib/cgraph/node.c | 19 +++++++++++++++---- lib/cgraph/rec.c | 2 +- 5 files changed, 47 insertions(+), 24 deletions(-) diff --git a/lib/cgraph/edge.c b/lib/cgraph/edge.c index 8ea11cf4b..75dd75f4a 100644 --- a/lib/cgraph/edge.c +++ b/lib/cgraph/edge.c @@ -31,9 +31,11 @@ Agedge_t *agfstout(Agraph_t * g, Agnode_t * n) Agedge_t *e = NILedge; sn = agsubrep(g, n); - dtrestore(g->e_seq, sn->out_seq); - e = (Agedge_t *) dtfirst(g->e_seq); - sn->out_seq = dtextract(g->e_seq); + if (sn) { + dtrestore(g->e_seq, sn->out_seq); + e = (Agedge_t *) dtfirst(g->e_seq); + sn->out_seq = dtextract(g->e_seq); + } return e; } @@ -42,13 +44,15 @@ Agedge_t *agnxtout(Agraph_t * g, Agedge_t * e) { Agnode_t *n; Agsubnode_t *sn; - Agedge_t *f; + Agedge_t *f = NILedge; n = AGTAIL(e); sn = agsubrep(g, n); - dtrestore(g->e_seq, sn->out_seq); - f = (Agedge_t *) dtnext(g->e_seq, e); - sn->out_seq = dtextract(g->e_seq); + if (sn) { + dtrestore(g->e_seq, sn->out_seq); + f = (Agedge_t *) dtnext(g->e_seq, e); + sn->out_seq = dtextract(g->e_seq); + } return f; } @@ -58,9 +62,11 @@ Agedge_t *agfstin(Agraph_t * g, Agnode_t * n) Agedge_t *e = NILedge; sn = agsubrep(g, n); - dtrestore(g->e_seq, sn->in_seq); - e = (Agedge_t *) dtfirst(g->e_seq); - sn->in_seq = dtextract(g->e_seq); + if (sn) { + dtrestore(g->e_seq, sn->in_seq); + e = (Agedge_t *) dtfirst(g->e_seq); + sn->in_seq = dtextract(g->e_seq); + } return e; } @@ -68,14 +74,16 @@ Agedge_t *agnxtin(Agraph_t * g, Agedge_t * e) { Agnode_t *n; Agsubnode_t *sn; - Agedge_t *f; + Agedge_t *f = NILedge; n = AGHEAD(e); sn = agsubrep(g, n); - dtrestore(g->e_seq, sn->in_seq); - f = (Agedge_t *) dtnext(g->e_seq, e); - sn->in_seq = dtextract(g->e_seq); - return f; + if (sn) { + dtrestore(g->e_seq, sn->in_seq); + f = (Agedge_t *) dtnext(g->e_seq, e); + sn->in_seq = dtextract(g->e_seq); + } + return f; } Agedge_t *agfstedge(Agraph_t * g, Agnode_t * n) @@ -167,8 +175,10 @@ static void ins(Dict_t * d, Dtlink_t ** set, Agedge_t * e) static void del(Dict_t * d, Dtlink_t ** set, Agedge_t * e) { + void *x; dtrestore(d, *set); - dtdelete(d, e); + x = dtdelete(d, e); + assert(x); *set = dtextract(d); } diff --git a/lib/cgraph/graph.c b/lib/cgraph/graph.c index 0d071d930..2685d4a6f 100644 --- a/lib/cgraph/graph.c +++ b/lib/cgraph/graph.c @@ -229,8 +229,10 @@ int agdegree(Agraph_t * g, Agnode_t * n, int want_in, int want_out) int rv = 0; sn = agsubrep(g, n); - if (want_out) rv += cnt(g->e_seq,&(sn->out_seq)); - if (want_in) rv += cnt(g->e_seq,&(sn->in_seq)); + if (sn) { + if (want_out) rv += cnt(g->e_seq,&(sn->out_seq)); + if (want_in) rv += cnt(g->e_seq,&(sn->in_seq)); + } return rv; } diff --git a/lib/cgraph/mem.c b/lib/cgraph/mem.c index eb52d662c..7d5e7434a 100644 --- a/lib/cgraph/mem.c +++ b/lib/cgraph/mem.c @@ -35,7 +35,7 @@ static void *memalloc(void *heap, size_t request) { void *rv; rv = vmalloc((Vmalloc_t *) heap, request); - memset(rv, 0, request); + if (rv) memset(rv, 0, request); return rv; } diff --git a/lib/cgraph/node.c b/lib/cgraph/node.c index a989e0942..b8a4d0b00 100644 --- a/lib/cgraph/node.c +++ b/lib/cgraph/node.c @@ -49,7 +49,7 @@ Agnode_t *agnxtnode(Agraph_t * g, Agnode_t * n) { Agsubnode_t *sn; sn = agsubrep(g, n); - sn = ((Agsubnode_t *) dtnext(g->n_seq, sn)); + if (sn) sn = ((Agsubnode_t *) dtnext(g->n_seq, sn)); return sn ? sn->node : NILnode; } @@ -64,7 +64,7 @@ Agnode_t *agprvnode(Agraph_t * g, Agnode_t * n) { Agsubnode_t *sn; sn = agsubrep(g, n); - sn = ((Agsubnode_t *) dtprev(g->n_seq, sn)); + if (sn) sn = ((Agsubnode_t *) dtprev(g->n_seq, sn)); return sn ? sn->node : NILnode; } @@ -90,11 +90,17 @@ static Agnode_t *newnode(Agraph_t * g, unsigned long id, unsigned long seq) static void installnode(Agraph_t * g, Agnode_t * n) { Agsubnode_t *sn; + int osize; + + assert(dtsize(g->n_id) == dtsize(g->n_seq)); + osize = dtsize(g->n_id); if (g == agroot(g)) sn = &(n->mainsub); else sn = agalloc(g, sizeof(Agsubnode_t)); sn->node = n; dtinsert(g->n_id, sn); dtinsert(g->n_seq, sn); + assert(dtsize(g->n_id) == dtsize(g->n_seq)); + assert(dtsize(g->n_id) == osize + 1); } static void installnodetoroot(Agraph_t * g, Agnode_t * n) @@ -158,6 +164,7 @@ Agnode_t *agnode(Agraph_t * g, char *name, int cflag) n = newnode(g, id, agnextseq(g, AGNODE)); installnodetoroot(g, n); initnode(g, n); + assert(agsubrep(g,n)); return n; } @@ -264,18 +271,22 @@ Agnode_t *agsubnode(Agraph_t * g, Agnode_t * n0, int cflag) int agsubnodeidcmpf(Dict_t * d, void *arg0, void *arg1, Dtdisc_t * disc) { + long v; Agsubnode_t *sn0, *sn1; sn0 = (Agsubnode_t *) arg0; sn1 = (Agsubnode_t *) arg1; - return (AGID(sn0->node) - AGID(sn1->node)); + v = (AGID(sn0->node) - AGID(sn1->node)); + return ((v==0)?0:(v<0?-1:1)); } int agsubnodeseqcmpf(Dict_t * d, void *arg0, void *arg1, Dtdisc_t * disc) { Agsubnode_t *sn0, *sn1; + long v; sn0 = (Agsubnode_t *) arg0; sn1 = (Agsubnode_t *) arg1; - return (AGSEQ(sn0->node) - AGSEQ(sn1->node)); + v = (AGSEQ(sn0->node) - AGSEQ(sn1->node)); + return ((v==0)?0:(v<0?-1:1)); } Dtdisc_t Ag_subnode_id_disc = { diff --git a/lib/cgraph/rec.c b/lib/cgraph/rec.c index 2a007f418..b1cc32141 100644 --- a/lib/cgraph/rec.c +++ b/lib/cgraph/rec.c @@ -203,7 +203,7 @@ void aginit(Agraph_t * g, int kind, char *rec_name, int rec_size, int mtf) Agnode_t *n; Agedge_t *e; Agraph_t *s; - int rec; + int rec; /* if recursive on subgraphs */ rec = (rec_size < 0); if (rec) rec_size = -rec_size; -- 2.40.0