mpgraph.c

早期freebsd实现

    DO_VLIST(v, ordered_vset)
	if (v->scc_members != NULL) {
	    print_cycle_information(v, f, total_bytes);
	    print_separator(f);
	    print_normal_vertex(v, f, total_bytes);
	} else if (v->in_cycle != NULL) {
	    print_vertex_in_cycle(v, f, total_bytes);
	} else {
	    print_normal_vertex(v, f, total_bytes);
	}
	print_separator(f);
    END_DO
      
    fflush(f);
}    

graph
read_graph()
{
    mpsym	s;
    int		i, count;
    mpcell	chain;
    mpcell	rest;
    mpcell	p;
    int		v_count, e_count;
    vecell	vset, eset;

    /*
     * First count the nodes and allocate space for them.
     */
    v_count = mp_count_nodes();
    e_count = 0;
    vset = NULL;
    eset = NULL;
    hcreate(2 * v_count);

    /*
     * Read in each vertex and store associated information.
     */
    count = 0;
    for (i = 0; i < MP_HASH_SIZE; i++) {
	chain = hmem[i];
	while (!mp_null(chain)) {
	    vertex	v;
	    s = (mpsym) mp_car(chain);
	    v = make_vertex(fn_name(s), count, fn_lcount(s), fn_parents(s));
	    vpush(v, vset);
	    count += 1;
	    chain = (mpcell) mp_cdr(chain);
	}
    }

    /*
     * Create the backedges
     */
    DO_VLIST (vto, vset)
	vecell	elist = NULL;
 	mpcell	rest;

        /*
	 * The parent list is stored in the scratch slot of the
         * vertex.
	 */
        rest = (mpcell) vto->scratch;
	while (!mp_null(rest)) {
	    char	*parent_name;
	    mpdata	parent_data;
	    mpcell	parent = (mpcell) mp_car(rest);
	    vertex	vfrom;
	    edge	e;
	    
	    parent_name = fn_name((mpsym) mp_car(parent));
	    parent_data = (mpdata) mp_cdr(parent);
	    vfrom = hlookup(parent_name);

	    if (vfrom == vto) {
		vto->srefs += 1;
	    } else {
		e = make_edge(vfrom, vto, parent_data);
		e_count +=  1;
		epush(e, eset);
		epush(e, elist);
	    }
   	    rest = mp_cdr(rest);
	}
        vto->backedges = elist;
    END_DO

    DO_VLIST (v, vset)
	DO_ELIST (e, v->backedges)
	    vertex	vfrom = e->from;
	    epush(e, vfrom->edges);
        END_DO
    END_DO
    return make_graph(v_count, vset, e_count, eset);
}


edge
same_edge(from_v, to_v, elist)
vertex	from_v, to_v;
vecell	elist;
{
    DO_ELIST (e, elist)
	if ((e->to == to_v) && (e->from == from_v)) {
	    return e;
	}
    END_DO
    return NULL;
}

int	
edge_less_compar(e1, e2)
edge	*e1, *e2;
{
    char	*e1_from, *e1_to, *e2_from, *e2_to;
    e1_from = (*e1)->from->name;
    e1_to = (*e1)->to->name;
    e2_from = (*e2)->from->name;
    e2_to = (*e2)->to->name;
    if (strcmp(e1_from, e2_from) == 0) {
	return strcmp(e1_to, e2_to);
    } else {
	return strcmp(e1_from, e2_from);
    }
}

int
vdata_compar(v1p, v2p)
vertex	*v1p, *v2p;
{
    int		d1 = mp_sum_data((*v1p)->data);
    int		d2 = mp_sum_data((*v2p)->data);
    if (d1 < d2) {
	return 1;
    } else if (d1 > d2) {
	return -1;
    } else {
	return 0;
    }
}

int
vbytes_compar(v1p, v2p)
vertex	*v1p, *v2p;
{
    int		d1 = sum_vertex_bytes1(*v1p);
    int		d2 = sum_vertex_bytes1(*v2p);
    if (d1 < d2) {
	return 1;
    } else if (d1 > d2) {
	return -1;
    } else {
	return 0;
    }
}

vecell
vsort(vlist, compar)
vecell	vlist;
int 	(*compar)();
{
    int	llength = velength(vlist);
    vertex	*vvec = (vertex *) calloc(llength, sizeof(vertex));
    int		i;
    vecell	newvlist = NULL;

    i = 0;
    DO_VLIST (v, vlist)
        vvec[i] = v;
        i += 1;
    END_DO

    qsort((char *) vvec, llength, sizeof(vertex), compar);

    for (i = (llength - 1); i >= 0; i--) {
	epush(vvec[i], newvlist);
    }
    return newvlist;
}

vecell
esort(elist, compar)
vecell	elist;
int 	(*compar)();
{
    int	llength = velength(elist);
    edge	*evec = (edge *) calloc(llength, sizeof(edge));
    int		i;
    vecell	newelist = NULL;

    i = 0;
    DO_ELIST (e, elist)
        evec[i] = e;
        i += 1;
    END_DO

    qsort((char *) evec, llength, sizeof(edge), compar);

    for (i = (llength - 1); i >= 0; i--) {
	epush(evec[i], newelist);
    }
    return newelist;
}

graph
merge_scc(g)
graph	g;
{
    graph	newg = copy_graph(g);
    vecell	vset = NULL, eset = NULL, added_eset = NULL;
    int	cycle_count = 0;

    vecell	cc_list = scc(newg);
/*    print_graph(stdout, newg);
*/

    /*
     * Create vertices corresponding to each of the cycles.
     */

    DO_LIST (cc, cc_list)
	if (velength(cc) != 1) {
	    vertex newv;
	    /*
	     * Create a vertex to represent the SCC.
	     */
	    cycle_count += 1;
	    newv = make_vertex(new_cycle_name(cycle_count),
			       cycle_count + newg->v_count - 1,
			       mp_new_data(),
			       NULL);
	    vpush(newv, vset);
	    newv->scc_members = cc;

	    DO_VLIST(v, cc)
		vpush(v, vset);
		v->in_cycle = newv;
		newv->data = mp_add_data(newv->data, v->data);
	    END_DO
	} else {
	    vpush((vertex) vehd(cc), vset);
	}
    END_DO

    /*
     * Look at all the edges and create a new edge set.
     */
    DO_ELIST (e, newg->eset) 
	/*
	 * Cases --
	 * 1. Either vertex is part of a cycle.
	 * 2. Neither vertex is in a cycle.
	 */
	vertex	from_v = (e->from)->in_cycle;
	vertex	to_v = (e->to)->in_cycle;
	
	if ((from_v != NULL) || (to_v != NULL)) {
	    if (from_v == NULL) {
		from_v = e->from;
	    }
	    if (to_v == NULL) {
		to_v = e->to;
	    }
	    if (from_v != to_v) {
		edge newe = same_edge(from_v, to_v, added_eset);
		if (newe != NULL) {
		    newe->data = mp_add_data(newe->data, e->data);
		} else {
		    mpdata	newdata = mp_new_data();
		    
		    newdata = mp_add_data(newdata, e->data);
		    newe = make_edge(from_v, to_v, newdata);
		    epush(newe, added_eset);
		}
	    } else {
		from_v->srefs += 1;
	    }
	}
	epush(e, eset);
    END_DO

    DO_ELIST (e, added_eset)
	epush(e, eset);
    END_DO
    eset = esort(eset, edge_less_compar);

    /*
     * Remove the old edges and add the new ones.
     */
    DO_VLIST(v, vset) 
	v->edges = NULL;
	v->backedges = NULL;
    END_DO

    DO_ELIST(e, eset)
	vertex	vfrom = e->from;
	vertex	vto = e->to;

	epush(e, vfrom->edges);
	epush(e, vto->backedges);
    END_DO

    newg->v_count = velength(vset);
    newg->vset = vereverse(vset);
    newg->e_count = velength(eset);
    newg->eset = eset;
    return newg;
}

bool
no_unused_incident_edges_from(v)
vertex	v;
{
    vecell	elist = v->edges;
    DO_ELIST (e, elist)
	if (e->mark == UNUSED) {
	    return FALSE;
	}
    END_DO
    return TRUE;
}

edge
first_unused_edge(elist)
vecell	elist;
{
    DO_ELIST (e, elist)
	if (e->mark == UNUSED) {
	    return e;
	}
    END_DO
    fprintf(stderr, "first_unused_edge -- no unused edges present:\n");
    print_vecons(stderr, elist);
    return NULL;
}

vertex
find_vertex_with_k_equal_zero(vlist)
vecell	vlist;
{
    DO_VLIST (v, vlist)
	if (v->k == 0) {
	    return v;
	}
    END_DO;
    return NULL;
}
  
/*
 * Find the strongly connected components in the graph.
 */
vecell
scc(g)
graph	g;
{
    vecell	vset = g->vset;
    vecell	eset = g->eset;
    vecell	scc_vset = NULL;
    vecell	S = NULL;
    int		i = 0;
    vertex	v = (vertex) vehd(vset);
    vertex	u, new_u;
    edge	e;

    DO_ELIST (e, eset)
	e->mark = UNUSED;
    END_DO

    DO_VLIST (v, vset)
        v->father = (vertex) UNDEFINED;
        v->k = 0;
    END_DO

 step2:
    i += 1;
    v->k = i;
    v->L = i;
    vpush(v, S);
    v->on_S = TRUE;
 step3:
    if (no_unused_incident_edges_from(v)) {
	goto step7;
    }
 step4:
    e = first_unused_edge(v->edges);
    u = e->to;
    e->mark = USED;
    if (u->k == 0) {
	u->father = v;
	v = u;
	goto step2;
    }
 step5:
    if (u->k > v->k) {
	goto step3;
    }
    if (!(u->on_S)) {
	goto step3;
    }
 step6:
    if (!((u->k < v->k) && u->on_S)) {
	fprintf(stderr, "assertion at step6 failed\n");
    }
    v->L = min(v->L, u->k);
    goto step3;
 step7:
    if (v->L == v->k) {
	vecell	comp = NULL;
	vertex	topv;

	do {
	    topv = (vertex) vehd(S);
	    S = vetl(S);
	    vpush(topv, comp);
	    topv->on_S = FALSE;
	} while (topv != v);
	cpush(comp, scc_vset);
    }
 step8:
    if (v->father != (vertex) UNDEFINED) {
	(v->father)->L = min(v->L, (v->father)->L);
	v = v->father;
	goto step3;
    }
 step9:
    if (v->father != (vertex) UNDEFINED) {
	fprintf(stderr, "assertion at step9 failed\n");
    }
    new_u = find_vertex_with_k_equal_zero(vset);
    if (new_u != NULL) {
	v = new_u;
	goto step2;
    }
    if (S != NULL) {
	cpush(S, scc_vset);
    }
    return scc_vset;
}

int
mp_count_nodes()
{
    int		i, count;
    mpcell	chain;

    count = 0;
    for (i = 0; i < MP_HASH_SIZE; i++) {
	chain = hmem[i];
	while (!mp_null(chain)) {
	    count += 1;
	    chain = (mpcell) mp_cdr(chain);
	}
    }
    return count;
}


char *
new_cycle_name(n)
int	n;
{
    char	chars[255];
    sprintf(chars, "<cycle %d>", n);
    return strdup(chars);
}

char *
int1_sprintf(fmt, n)
char	*fmt;
int	n;

{
    char	chars[255];
    sprintf(chars, fmt, n);
    return strdup(chars);
}

char *
s1_sprintf(fmt, s)
char	*fmt;
char	*s;
{
    char	chars[255];
    sprintf(chars, fmt, s);
    return strdup(chars);
}

char *
f1_sprintf(fmt, d)
char	*fmt;
double	d;
{
    char	chars[255];
    sprintf(chars, fmt, d);
    return strdup(chars);
}

char *
vertex_name_string(v)
vertex	v;
{
    char	chars[255];
    if (v->in_cycle == NULL) {
	sprintf(chars, "%s [%d]", v->name, v->index);
    } else {
	sprintf(chars, "%s [%d] in %s", v->name, v->index, v->in_cycle->name);
    }
    return strdup(chars);
}
	
void
print_dynamic_graph_header(f)
FILE	*f;
{
    fprintf(f, "\f\n\n");
    fprintf(f, template2,
	    "",
	    "self",
	    "",
	    "",
	    "     /ances",
	    "     /ances",
	    "called",
	    "/total ",
	    "    ancestors");
    fprintf(f, template2,
	    "index",
	    "+  ",
	    "self",
	    "(%)",
	    " size-func",
	    " frac",
	    "called",
	    "/recur",
	    "name [index]");
    fprintf(f, template2,
	    "",
	    "desc",
	    "",
	    "",
	    "     \\desc",
	    "     \\desc",
	    "called",
	    "/total",
	    "    descendents");
    print_separator(f);
}

#define template3 \
"\n-------------------------------s--m--l--x----s--m--l--x----------\n\n"
  
void
print_separator(f)
FILE	*f;
{
    fprintf(f, template3, "", "");
}


vecell
filter_cycle_edges(elist)
vecell	elist;
{
    vecell	result = NULL;
    
    DO_ELIST(e, elist)
	if (!((e->to->scc_members != NULL) ||
	      (e->from->scc_members != NULL))) {
	    epush(e, result);
	}
    END_DO
    return vereverse(result);
}

mpdata    
add_data_over(elist)
vecell	elist;
{
    mpdata	result = mp_new_data();
    
    DO_ELIST(e, elist)
	result = mp_add_data(result, e->data);
    END_DO
    return result;
}

void
print_normal_vertex(v, f, nbytes)
vertex	v;
FILE	*f;
int	nbytes;
{
    vecell	plist = v->backedges;
    vecell	clist = v->edges;
    vecell	filt_plist, filt_clist;
    int		pbytesum = sum_data_over_edges(plist);
    int		cbytesum = sum_data_over_edges(clist);
    mpdata	all_pdata;
    mpdata	all_cdata;

    if (v->scc_members != NULL) {
	filt_plist = plist;
	filt_clist = clist;
    } else {
	filt_plist = filter_cycle_edges(plist);
	filt_clist = filter_cycle_edges(clist);
    }
    all_pdata = add_data_over(filt_plist);
    all_cdata = add_data_over(filt_clist);

    /*
     * Parent listings.
     */
    if (velength(filt_plist) > 1) {
	fprintf(f, template2p1,
		"", "all",
		mp_sum_data(all_pdata),
		"",
		type_fraction_string(all_pdata),
		"", "", "", "");
    }
    
    DO_ELIST(e, filt_plist)
	mpdata	edata = e->data;
	int	pcallsum = sum_vertex_outgoing_calls(e->from);
	int	ecallsum = mp_sum_calls(edata);
	int	ebytesum = mp_sum_data(edata);
	fprintf(f, template2p2,
		"", "",
		ebytesum,
		percent_string(ebytesum, pbytesum),
		type_fraction_string(edata),
		relative_type_string(edata, all_pdata),
		ecallsum,
		int1_sprintf("/%d", pcallsum),
		s1_sprintf("    %s", vertex_name_string(e->from)));
    END_DO

    /*
     * Self listing.
     */
    print_self_line(f, v, nbytes, FALSE);

    /*
     * Children listings.
     */
	
    DO_ELIST(e, filt_clist)
	mpdata	edata = e->data;
	int	ccallsum = sum_vertex_incoming_calls(e->to);
	int	ecallsum = mp_sum_calls(edata);
	int	ebytesum = mp_sum_data(edata);
	fprintf(f, template2p2,
		"", "",
		ebytesum,
		percent_string(ebytesum, cbytesum),
		type_fraction_string(edata),
		relative_type_string(edata, all_cdata),
		ecallsum,
		int1_sprintf("/%d", ccallsum),
		s1_sprintf("    %s", vertex_name_string(e->to)));
    END_DO
      
    if (velength(filt_clist) > 1) {
	fprintf(f, template2p1,
		"", "all",
		mp_sum_data(all_cdata),
		"",
		type_fraction_string(all_cdata),
		"", "", "", "");
    }
}


void
print_self_line(f, v, nbytes, cyclep)
FILE	*f;
vertex	v;
int	nbytes;
bool	cyclep;
{
    vecell	plist = v->backedges;
    vecell	clist = v->edges;
    int		pcallsum = sum_calls_over_edges(plist);
    int		cbytesum = sum_data_over_edges(clist);
    int		self_bytesum = mp_sum_data(v->data);
    int		fbytesum = self_bytesum + cbytesum;

    fprintf(f, template2p2,
	    int1_sprintf("[%d]", v->index),
	    f1_sprintf("%7.1f", dpercent(fbytesum, nbytes)),
	    self_bytesum,
	    percent_string(self_bytesum, fbytesum),
	    type_fraction_string(v->data),
	    " -----------",
	    pcallsum,
	    ((v->srefs == 0) ? "" : int1_sprintf("+%d", v->srefs)),
	    ((cyclep != 0) ? s1_sprintf("%s as a whole", vertex_name_string(v))
	     : vertex_name_string(v)));
}
    
void
print_vertex_in_cycle(v, f, nbytes)
vertex	v;
FILE	*f;
int	nbytes;
{
    vecell	plist = filter_cycle_edges(v->backedges);
    vecell	clist = filter_cycle_edges(v->edges);
    int		pcallsum = 0;
    int		self_bytesum = mp_sum_data(v->data);

    /*
     * Parent listings.
     */
    
    DO_ELIST(e, plist)
	mpdata	edata = e->data;
	int	ecallsum = mp_sum_calls(edata);
    
        pcallsum += ecallsum;
	fprintf(f, template2c1,
		"", "", "", "", "", "", 
		ecallsum,
		"",
		s1_sprintf("    %s", vertex_name_string(e->from)));
    END_DO

    /*
     * Self listing.
     */
    fprintf(f, template2p2,
	    int1_sprintf("[%d]", v->index),
	    f1_sprintf("%7.1f", dpercent(self_bytesum, nbytes)),
	    self_bytesum,
	    "",
	    type_fraction_string(v->data),
	    " -----------",
	    pcallsum,
	    ((v->srefs == 0) ? "" : int1_sprintf("+%d", v->srefs)),
	    vertex_name_string(v));


    /*
     * Children listings.
     */
	
    DO_ELIST(e, clist)
	mpdata	edata = e->data;
	int	ecallsum = mp_sum_calls(edata);
    
	fprintf(f, template2c1,
		"", "", "", "", "", "", 
		ecallsum,
		"",
		s1_sprintf("    %s", vertex_name_string(e->to)));
    END_DO
}

void
print_cycle_information(v, f, nbytes)
vertex	v;
FILE	*f;
int	nbytes;
{
    vecell	members = v->scc_members;
    mpdata	mdata = v->data;
    int		mbytesum = mp_sum_data(mdata);

    /*
     * Self listing.
     */
    print_self_line(f, v, nbytes, TRUE);

    /*
     * Members listing.
     */
    DO_VLIST(v, members)
	mpdata	vdata = v->data;
	int	vbytesum = mp_sum_data(vdata);
	fprintf(f, template2p1,
		"", "",
		vbytesum,
		percent_string(vbytesum, (mbytesum == 0 ? 1 : mbytesum)),
		type_fraction_string(vdata),
		relative_type_string(vdata, mdata),
		"", "", s1_sprintf("    %s", vertex_name_string(v)));
    END_DO
}