← Back to branch summary

~ubuntu-branches/ubuntu/precise/graphviz/precise-security

« back to all changes in this revision

Viewing changes to .pc/3_fix_circo_segfault/lib/circogen/blocktree.c

  • Committer: Bazaar Package Importer
  • Author(s): David Claughton
  • Date: 2010-03-24 22:45:18 UTC
  • mfrom: (1.2.7 upstream) (6.1.7 sid)
  • Revision ID: james.westby@ubuntu.com-20100324224518-do441tthbqjaqjzd
Tags: 2.26.3-4
http://bugs.debian.org/575255
Add patch to fix segfault in circo. Backported from upstream snapshot
release.  Thanks to Francis Russell for his work on this.
(Closes: #575255)

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/3_fix_circo_segfault/lib/circogen/blocktree.c
 
1
/* $Id: blocktree.c,v 1.9 2009/08/17 21:04:11 erg Exp $ $Revision: 1.9 $ */
 
2
/* vim:set shiftwidth=4 ts=8: */
 
3
 
 
4
/**********************************************************
 
5
*      This software is part of the graphviz package      *
 
6
*                http://www.graphviz.org/                 *
 
7
*                                                         *
 
8
*            Copyright (c) 1994-2004 AT&T Corp.           *
 
9
*                and is licensed under the                *
 
10
*            Common Public License, Version 1.0           *
 
11
*                      by AT&T Corp.                      *
 
12
*                                                         *
 
13
*        Information and Software Systems Research        *
 
14
*              AT&T Research, Florham Park NJ             *
 
15
**********************************************************/
 
16
 
 
17
 
 
18
#include "blocktree.h"
 
19
 
 
20
static void addNode(block_t * bp, Agnode_t * n)
 
21
{
 
22
#ifndef WITH_CGRAPH
 
23
    aginsert(bp->sub_graph, n);
 
24
#else /* WITH_CGRAPH */
 
25
    agsubnode(bp->sub_graph, n,1);
 
26
#endif /* WITH_CGRAPH */
 
27
    BLOCK(n) = bp;
 
28
}
 
29
 
 
30
static Agraph_t *makeBlockGraph(Agraph_t * g, circ_state * state)
 
31
{
 
32
    char name[SMALLBUF];
 
33
    Agraph_t *subg;
 
34
 
 
35
    sprintf(name, "_block_%d", state->blockCount++);
 
36
#ifndef WITH_CGRAPH
 
37
    subg = agsubg(g, name);
 
38
#else /* WITH_CGRAPH */
 
39
    subg = agsubg(g, name,1);
 
40
    agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);        //node custom data
 
41
#endif /* WITH_CGRAPH */
 
42
    return subg;
 
43
}
 
44
 
 
45
static block_t *makeBlock(Agraph_t * g, circ_state * state)
 
46
{
 
47
    Agraph_t *subg = makeBlockGraph(g, state);
 
48
    block_t *bp = mkBlock(subg);
 
49
 
 
50
    return bp;
 
51
}
 
52
 
 
53
typedef struct {
 
54
    Agedge_t *top;
 
55
    int sz;
 
56
} estack;
 
57
 
 
58
static void
 
59
push (estack* s, Agedge_t* e)
 
60
{
 
61
    ENEXT(e) = s->top;
 
62
    s->top = e;
 
63
    s->sz += 1;
 
64
}
 
65
 
 
66
static Agedge_t*
 
67
pop (estack* s)
 
68
{
 
69
    Agedge_t *top = s->top;
 
70
 
 
71
    if (top) {
 
72
        assert(s->sz > 0);
 
73
        s->top = ENEXT(top);
 
74
        s->sz -= 1;
 
75
    } else {
 
76
        assert(0);
 
77
    }
 
78
 
 
79
    return top;
 
80
}
 
81
 
 
82
 
 
83
static void dfs(Agraph_t * g, Agnode_t * u, circ_state * state, int isRoot, estack* stk)
 
84
{
 
85
    Agedge_t *e;
 
86
    Agnode_t *v;
 
87
 
 
88
    LOWVAL(u) = VAL(u) = state->orderCount++;
 
89
    for (e = agfstedge(g, u); e; e = agnxtedge(g, e, u)) {
 
90
        v = aghead (e);
 
91
        if (v == u) {
 
92
            v = agtail(e);
 
93
            if (!EDGEORDER(e)) EDGEORDER(e) = -1;
 
94
        }
 
95
        else {
 
96
            if (!EDGEORDER(e)) EDGEORDER(e) = 1;
 
97
        }
 
98
 
 
99
        if (VAL(v) == 0) {
 
100
            PARENT(v) = u;
 
101
            push(stk, e);
 
102
            dfs(g, v, state, 0, stk);
 
103
            LOWVAL(u) = MIN(LOWVAL(u), LOWVAL(v));
 
104
            if (LOWVAL(v) >= VAL(u)) {       /* u is an articulation point */
 
105
                block_t *block = NULL;
 
106
                Agnode_t *np;
 
107
                Agedge_t *ep;
 
108
                do {
 
109
                    ep = pop(stk);
 
110
                    if (EDGEORDER(ep) == 1)
 
111
                        np = aghead (ep);
 
112
                    else
 
113
                        np = agtail (ep);
 
114
                    if (!BLOCK(np)) {
 
115
                        if (!block)
 
116
                            block = makeBlock(g, state);
 
117
                        addNode(block, np);
 
118
                    }
 
119
                } while (ep != e);
 
120
                if (block) {    /* If block != NULL, it's not empty */
 
121
                    if (blockSize (block) > 1)
 
122
                        addNode(block, u);
 
123
                    if (isRoot && (BLOCK(u) == block))
 
124
                        insertBlock(&state->bl, block);
 
125
                    else
 
126
                        appendBlock(&state->bl, block);
 
127
                }
 
128
            }
 
129
        } else if (PARENT(u) != v) {
 
130
            LOWVAL(u) = MIN(LOWVAL(u), VAL(v));
 
131
        }
 
132
    }
 
133
    if (isRoot && !BLOCK(u)) {
 
134
        block_t *block = makeBlock(g, state);
 
135
        addNode(block, u);
 
136
        insertBlock(&state->bl, block);
 
137
    }
 
138
}
 
139
 
 
140
 
 
141
/* find_blocks:
 
142
 */
 
143
static void find_blocks(Agraph_t * g, circ_state * state)
 
144
{
 
145
    Agnode_t *n;
 
146
    Agnode_t *root = NULL;
 
147
    estack stk;
 
148
 
 
149
    /*      check to see if there is a node which is set to be the root
 
150
     */
 
151
    if (state->rootname) {
 
152
        root = agfindnode(g, state->rootname);
 
153
    }
 
154
    if (!root && state->N_root) {
 
155
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
 
156
            if (late_bool(ORIGN(n), state->N_root, 0)) {
 
157
                root = n;
 
158
                break;
 
159
            }
 
160
        }
 
161
    }
 
162
 
 
163
    if (!root)
 
164
        root = agfstnode(g);
 
165
    if (Verbose)
 
166
        fprintf (stderr, "root = %s\n", agnameof(root));
 
167
    stk.sz = 0;
 
168
    stk.top = NULL;
 
169
    dfs(g, root, state, 1, &stk);
 
170
 
 
171
}
 
172
 
 
173
/* create_block_tree:
 
174
 * Construct block tree by peeling nodes from block list in state.
 
175
 * When done, return root. The block list is empty
 
176
 * FIX: use largest block as root
 
177
 */
 
178
block_t *createBlocktree(Agraph_t * g, circ_state * state)
 
179
{
 
180
    block_t *bp;
 
181
    block_t *next;
 
182
    block_t *root;
 
183
    int min;
 
184
    /* int        ordercnt; */
 
185
 
 
186
    find_blocks(g, state);
 
187
 
 
188
    bp = state->bl.first;       /* if root chosen, will be first */
 
189
    /* Otherwise, just pick first as root */
 
190
    root = bp;
 
191
 
 
192
    /* Find node with minimum VAL value to find parent block */
 
193
    /* FIX: Should be some way to avoid search below.               */
 
194
    /* ordercnt = state->orderCount;  */
 
195
    for (bp = bp->next; bp; bp = next) {
 
196
        Agnode_t *n;
 
197
        Agnode_t *parent;
 
198
        Agnode_t *child;
 
199
        Agraph_t *subg = bp->sub_graph;
 
200
 
 
201
        child = n = agfstnode(subg);
 
202
 
 
203
        min = VAL(n);
 
204
        parent = PARENT(n);
 
205
        for (n = agnxtnode(subg, n); n; n = agnxtnode(subg, n)) {
 
206
            if (VAL(n) < min) {
 
207
                child = n;
 
208
                min = VAL(n);
 
209
                parent = PARENT(n);
 
210
            }
 
211
        }
 
212
        SET_PARENT(parent);
 
213
        CHILD(bp) = child;
 
214
        next = bp->next;        /* save next since list insertion destroys it */
 
215
        appendBlock(&(BLOCK(parent)->children), bp);
 
216
    }
 
217
    initBlocklist(&state->bl);  /* zero out list */
 
218
    return root;
 
219
}
 
220
 
 
221
void freeBlocktree(block_t * bp)
 
222
{
 
223
    block_t *child;
 
224
    block_t *next;
 
225
 
 
226
    for (child = bp->children.first; child; child = next) {
 
227
        next = child->next;
 
228
        freeBlocktree(child);
 
229
    }
 
230
 
 
231
    freeBlock(bp);
 
232
}
 
233
 
 
234
#ifdef DEBUG
 
235
static void indent(int i)
 
236
{
 
237
    while (i--)
 
238
        fputs("  ", stderr);
 
239
}
 
240
 
 
241
void print_blocktree(block_t * sn, int depth)
 
242
{
 
243
    block_t *child;
 
244
    Agnode_t *n;
 
245
    Agraph_t *g;
 
246
 
 
247
    indent(depth);
 
248
    g = sn->sub_graph;
 
249
    fprintf(stderr, "%s:", g->name);
 
250
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
 
251
        fprintf(stderr, " %s", n->name);
 
252
    }
 
253
    fputs("\n", stderr);
 
254
 
 
255
    depth++;
 
256
    for (child = sn->children.first; child; child = child->next) {
 
257
        print_blocktree(child, depth);
 
258
    }
 
259
}
 
260
 
 
261
#endif