[deliverable/binutils-gdb.git] / gprof / sym_ids.c

#include "libiberty.h"
#include "cg_arcs.h"
#include "sym_ids.h"

struct sym_id {
    struct sym_id	*next;
    char		*spec;		/* parsing modifies this */
    Table_Id		which_table;
    bool		has_right;
    struct match {
	int		prev_index;		/* index of prev match */
	Sym		*prev_match;		/* previous match */
	Sym		*first_match;		/* chain of all matches */
	Sym		sym;
    } left, right;
} *id_list;

Sym_Table syms[NUM_TABLES];

#ifdef DEBUG
const char *table_name[] = {
    "INCL_GRAPH", "EXCL_GRAPH",
    "INCL_ARCS", "EXCL_ARCS",
    "INCL_FLAT", "EXCL_FLAT",
    "INCL_TIME", "EXCL_TIME",
    "INCL_ANNO", "EXCL_ANNO",
    "INCL_EXEC", "EXCL_EXEC"
};
#endif /* DEBUG */

/*
 * This is the table in which we keep all the syms that match
 * the right half of an arc id.  It is NOT sorted according
 * to the addresses, because it is accessed only through
 * the left half's CHILDREN pointers (so it's crucial not
 * to reorder this table once pointers into it exist).
 */
static Sym_Table right_ids;

static Source_File non_existent_file = {
    0, "<non-existent-file>"
};


void
DEFUN(sym_id_add, (spec, which_table),
      const char *spec AND Table_Id which_table)
{
    struct sym_id *id;
    int len = strlen(spec);

    id = (struct sym_id*) xmalloc(sizeof(*id) + len + 1);
    memset(id, 0, sizeof(*id));

    id->spec = (char*)id + sizeof(*id);
    strcpy(id->spec, spec);
    id->which_table = which_table;

    id->next = id_list;
    id_list = id;
} /* sym_id_add */


/*
 * A spec has the syntax FILENAME:(FUNCNAME|LINENUM).  As a convenience
 * to the user, a spec without a colon is interpreted as:
 *
 *	(i)   a FILENAME if it contains a dot
 *	(ii)  a FUNCNAME if it starts with a non-digit character
 *	(iii) a LINENUM if it starts with a digit
 *
 * A FUNCNAME containing a dot can be specified by :FUNCNAME, a
 * FILENAME not containing a dot can be specified by FILENAME:.
 */
static void
DEFUN(parse_spec, (spec, sym), char *spec AND Sym *sym)
{
    char *colon;

    sym_init(sym);
    colon = strrchr(spec, ':');
    if (colon) {
	*colon = '\0';
	if (colon > spec) {
	    sym->file = source_file_lookup_name(spec);
	    if (!sym->file) {
		sym->file = &non_existent_file;
	    } /* if */
	} /* if */
	spec = colon + 1;
	if (strlen(spec)) {
	    if (isdigit(spec[0])) {
		sym->line_num = atoi(spec);
	    } else {
		sym->name = spec;
	    } /* if */
	} /* if */
    } else if (strlen(spec)) {
	/* no colon: spec is a filename if it contains a dot: */
	if (strchr(spec, '.')) {
	    sym->file = source_file_lookup_name(spec);
	    if (!sym->file) {
		sym->file = &non_existent_file;
	    } /* if */
	} else if (isdigit(*spec)) {
	    sym->line_num = atoi(spec);
	} else if (strlen(spec)) {
	    sym->name = spec;
	} /* if */
    } /* if */
} /* parse_spec */


/*
 * A symbol id has the syntax SPEC[/SPEC], where SPEC is is defined
 * by parse_spec().
 */
static void
DEFUN(parse_id, (id), struct sym_id *id)
{
    char *slash;

    DBG(IDDEBUG, printf("[parse_id] %s -> ", id->spec));

    slash = strchr(id->spec, '/');
    if (slash) {
	parse_spec(slash + 1, &id->right.sym);
	*slash = '\0';
	id->has_right = TRUE;
    } /* if */
    parse_spec(id->spec, &id->left.sym);

    DBG(IDDEBUG,
	printf("%s:", id->left.sym.file ? id->left.sym.file->name : "*");
	if (id->left.sym.name) {
	    printf("%s", id->left.sym.name);
	} else if (id->left.sym.line_num) {
	    printf("%d", id->left.sym.line_num);
	} else {
	    printf("*");
	} /* if */
	if (id->has_right) {
	    printf("/%s:",
		   id->right.sym.file ? id->right.sym.file->name : "*");
	    if (id->right.sym.name) {
		printf("%s", id->right.sym.name);
	    } else if (id->right.sym.line_num) {
		printf("%d", id->right.sym.line_num);
	    } else {
		printf("*");
	    } /* if */
	} /* if */
	printf("\n"));
} /* parse_id */


/*
 * Return TRUE iff PATTERN matches SYM.
 */
static bool
DEFUN(match, (pattern, sym), Sym *pattern AND Sym *sym)
{
    return (pattern->file ? pattern->file == sym->file : TRUE)
      && (pattern->line_num ? pattern->line_num == sym->line_num : TRUE)
	&& (pattern->name ? strcmp(pattern->name, sym->name) == 0 : TRUE);
} /* match */


static void
DEFUN(extend_match, (m, sym, tab, second_pass),
      struct match *m AND Sym *sym AND Sym_Table *tab AND bool second_pass)
{
    if (m->prev_match != sym - 1) {
	/* discontinuity: add new match to table: */
	if (second_pass) {
	    tab->base[tab->len] = *sym;
	    m->prev_index = tab->len;

	    /* link match into match's chain: */
	    tab->base[tab->len].next = m->first_match;
	    m->first_match = &tab->base[tab->len];
	} /* if */
	++tab->len;
    } /* if */

    /* extend match to include this symbol: */
    if (second_pass) {
	tab->base[m->prev_index].end_addr = sym->end_addr;
    } /* if */
    m->prev_match = sym;
} /* extend_match */


/*
 * Go through sym_id list produced by option processing and fill
 * in the various symbol tables indicating what symbols should
 * be displayed or suppressed for the various kinds of outputs.
 *
 * This can potentially produce huge tables and in particulars
 * tons of arcs, but this happens only if the user makes silly
 * requests---you get what you ask for!
 */
void
DEFUN_VOID(sym_id_parse)
{
    Sym *sym, *left, *right;
    struct sym_id *id;
    Sym_Table *tab;

    /*
     * Convert symbol ids into Syms, so we can deal with them more easily:
     */
    for (id = id_list; id; id = id->next) {
	parse_id(id);
    } /* for */

    /* first determine size of each table: */

    for (sym = symtab.base; sym < symtab.limit; ++sym) {
	for (id = id_list; id; id = id->next) {
	    if (match(&id->left.sym, sym)) {
		extend_match(&id->left, sym, &syms[id->which_table], FALSE);
	    } /* if */
	    if (id->has_right && match(&id->right.sym, sym)) {
		extend_match(&id->right, sym, &right_ids, FALSE);
	    } /* if */
	} /* for */
    } /* for */

    /* create tables of appropriate size and reset lengths: */

    for (tab = syms; tab < &syms[NUM_TABLES]; ++tab) {
	if (tab->len) {
	    tab->base = (Sym*) xmalloc(tab->len * sizeof(Sym));
	    tab->limit = tab->base + tab->len;
	    tab->len = 0;
	} /* if */
    } /* for */
    if (right_ids.len) {
	right_ids.base = (Sym*) xmalloc(right_ids.len * sizeof(Sym));
	right_ids.limit = right_ids.base + right_ids.len;
	right_ids.len = 0;
    } /* if */

    /* make a second pass through symtab, creating syms as necessary: */

    for (sym = symtab.base; sym < symtab.limit; ++sym) {
	for (id = id_list; id; id = id->next) {
	    if (match(&id->left.sym, sym)) {
		extend_match(&id->left, sym, &syms[id->which_table], TRUE);
	    } /* if */
	    if (id->has_right && match(&id->right.sym, sym)) {
		extend_match(&id->right, sym, &right_ids, TRUE);
	    } /* if */
	} /* for */
    } /* for */

    /* go through ids creating arcs as needed: */

    for (id = id_list; id; id = id->next) {
	if (id->has_right) {
	    for (left = id->left.first_match; left; left = left->next) {
		for (right = id->right.first_match; right; right = right->next)
		{
		    DBG(IDDEBUG,
			printf(
"[sym_id_parse]: arc %s:%s(%lx-%lx) -> %s:%s(%lx-%lx) to %s\n",
			       left->file ? left->file->name : "*",
			       left->name ? left->name : "*", left->addr,
			       left->end_addr,
			       right->file ? right->file->name : "*",
			       right->name ? right->name : "*", right->addr,
			       right->end_addr,
			       table_name[id->which_table]));
		    arc_add(left, right, 0);
		} /* for */
	    } /* for */
	} /* if */
    } /* for */

    /* finally, we can sort the tables and we're done: */

    for (tab = &syms[0]; tab < &syms[NUM_TABLES]; ++tab) {
	DBG(IDDEBUG, printf("[sym_id_parse] syms[%s]:\n",
			    table_name[tab - &syms[0]]));
	symtab_finalize(tab);
    } /* for */
} /* sym_id_parse */


/*
 * Symbol tables storing the FROM symbols of arcs do not necessarily
 * have distinct address ranges.  For example, somebody might request
 * -k /_mcount to suppress any arcs into _mcount, while at the same
 * time requesting -k a/b.  Fortunately, those symbol tables don't get
 * very big (the user has to type them!), so a linear search is probably
 * tolerable.
 */
bool
DEFUN(sym_id_arc_is_present, (symtab, from, to),
      Sym_Table *symtab AND Sym *from AND Sym *to)
{
    Sym *sym;

    for (sym = symtab->base; sym < symtab->limit; ++sym) {
	if (from->addr >= sym->addr && from->addr <= sym->end_addr
	    && arc_lookup(sym, to))
	{
	    return TRUE;
	} /* if */
    } /* for */
    return FALSE;
} /* sym_id_arc_is_present */

			/*** end of sym_ids.h ***/
Commit	Line	Data
5489fcc3 KR	1	#include "libiberty.h"
	2	#include "cg_arcs.h"
	3	#include "sym_ids.h"
	4
	5	struct sym_id {
	6	struct sym_id *next;
	7	char spec; / parsing modifies this */
	8	Table_Id which_table;
	9	bool has_right;
	10	struct match {
	11	int prev_index; /* index of prev match */
	12	Sym prev_match; / previous match */
	13	Sym first_match; / chain of all matches */
	14	Sym sym;
	15	} left, right;
	16	} *id_list;
	17
	18	Sym_Table syms[NUM_TABLES];
	19
	20	#ifdef DEBUG
	21	const char *table_name[] = {
	22	"INCL_GRAPH", "EXCL_GRAPH",
	23	"INCL_ARCS", "EXCL_ARCS",
	24	"INCL_FLAT", "EXCL_FLAT",
	25	"INCL_TIME", "EXCL_TIME",
	26	"INCL_ANNO", "EXCL_ANNO",
	27	"INCL_EXEC", "EXCL_EXEC"
	28	};
	29	#endif /* DEBUG */
	30
	31	/*
	32	* This is the table in which we keep all the syms that match
	33	* the right half of an arc id. It is NOT sorted according
	34	* to the addresses, because it is accessed only through
	35	* the left half's CHILDREN pointers (so it's crucial not
	36	* to reorder this table once pointers into it exist).
	37	*/
	38	static Sym_Table right_ids;
	39
	40	static Source_File non_existent_file = {
	41	0, "<non-existent-file>"
	42	};
	43
	44
	45	void
	46	DEFUN(sym_id_add, (spec, which_table),
	47	const char *spec AND Table_Id which_table)
	48	{
	49	struct sym_id *id;
	50	int len = strlen(spec);
	51
	52	id = (struct sym_id) xmalloc(sizeof(id) + len + 1);
	53	memset(id, 0, sizeof(*id));
	54
	55	id->spec = (char)id + sizeof(id);
	56	strcpy(id->spec, spec);
	57	id->which_table = which_table;
	58
	59	id->next = id_list;
	60	id_list = id;
	61	} /* sym_id_add */
	62
	63
	64	/*
65	* A spec has the syntax FILENAME:(FUNCNAME\|LINENUM). As a convenience
66	* to the user, a spec without a colon is interpreted as:
67	*
68	* (i) a FILENAME if it contains a dot
69	* (ii) a FUNCNAME if it starts with a non-digit character
70	* (iii) a LINENUM if it starts with a digit
71	*
72	* A FUNCNAME containing a dot can be specified by :FUNCNAME, a
73	* FILENAME not containing a dot can be specified by FILENAME:.
74	*/
75	static void
76	DEFUN(parse_spec, (spec, sym), char spec AND Sym sym)
77	{
78	char *colon;
79
80	sym_init(sym);
81	colon = strrchr(spec, ':');
82	if (colon) {
83	*colon = '\0';
84	if (colon > spec) {
85	sym->file = source_file_lookup_name(spec);
86	if (!sym->file) {
87	sym->file = &non_existent_file;
88	} /* if */
89	} /* if */
90	spec = colon + 1;
91	if (strlen(spec)) {
92	if (isdigit(spec[0])) {
93	sym->line_num = atoi(spec);
94	} else {
95	sym->name = spec;
96	} /* if */
97	} /* if */
98	} else if (strlen(spec)) {
99	/* no colon: spec is a filename if it contains a dot: */
100	if (strchr(spec, '.')) {
101	sym->file = source_file_lookup_name(spec);
102	if (!sym->file) {
103	sym->file = &non_existent_file;
104	} /* if */
105	} else if (isdigit(*spec)) {
106	sym->line_num = atoi(spec);
107	} else if (strlen(spec)) {
108	sym->name = spec;
109	} /* if */
110	} /* if */
111	} /* parse_spec */
112
113
114	/*
115	* A symbol id has the syntax SPEC[/SPEC], where SPEC is is defined
116	* by parse_spec().
117	*/
118	static void
119	DEFUN(parse_id, (id), struct sym_id *id)
120	{
121	char *slash;
122
123	DBG(IDDEBUG, printf("[parse_id] %s -> ", id->spec));
124
125	slash = strchr(id->spec, '/');
126	if (slash) {
127	parse_spec(slash + 1, &id->right.sym);
128	*slash = '\0';
129	id->has_right = TRUE;
130	} /* if */
131	parse_spec(id->spec, &id->left.sym);
132
133	DBG(IDDEBUG,
134	printf("%s:", id->left.sym.file ? id->left.sym.file->name : "*");
135	if (id->left.sym.name) {
136	printf("%s", id->left.sym.name);
137	} else if (id->left.sym.line_num) {
138	printf("%d", id->left.sym.line_num);
139	} else {
140	printf("*");
141	} /* if */
142	if (id->has_right) {
143	printf("/%s:",
144	id->right.sym.file ? id->right.sym.file->name : "*");
145	if (id->right.sym.name) {
146	printf("%s", id->right.sym.name);
147	} else if (id->right.sym.line_num) {
148	printf("%d", id->right.sym.line_num);
149	} else {
150	printf("*");
151	} /* if */
152	} /* if */
153	printf("\n"));
154	} /* parse_id */
155
156
157	/*
158	* Return TRUE iff PATTERN matches SYM.
159	*/
160	static bool
161	DEFUN(match, (pattern, sym), Sym pattern AND Sym sym)
162	{
163	return (pattern->file ? pattern->file == sym->file : TRUE)
164	&& (pattern->line_num ? pattern->line_num == sym->line_num : TRUE)
165	&& (pattern->name ? strcmp(pattern->name, sym->name) == 0 : TRUE);
166	} /* match */
167
168
169	static void
170	DEFUN(extend_match, (m, sym, tab, second_pass),
171	struct match m AND Sym sym AND Sym_Table *tab AND bool second_pass)
172	{
173	if (m->prev_match != sym - 1) {
174	/* discontinuity: add new match to table: */
175	if (second_pass) {
176	tab->base[tab->len] = *sym;
177	m->prev_index = tab->len;
178
179	/* link match into match's chain: */
180	tab->base[tab->len].next = m->first_match;
181	m->first_match = &tab->base[tab->len];
182	} /* if */
183	++tab->len;
184	} /* if */
185
186	/* extend match to include this symbol: */
187	if (second_pass) {
188	tab->base[m->prev_index].end_addr = sym->end_addr;
189	} /* if */
190	m->prev_match = sym;
191	} /* extend_match */
192
193
194	/*
195	* Go through sym_id list produced by option processing and fill
196	* in the various symbol tables indicating what symbols should
197	* be displayed or suppressed for the various kinds of outputs.
198	*
199	* This can potentially produce huge tables and in particulars
200	* tons of arcs, but this happens only if the user makes silly
201	* requests---you get what you ask for!
202	*/
203	void
204	DEFUN_VOID(sym_id_parse)
205	{
206	Sym sym, left, *right;
207	struct sym_id *id;
208	Sym_Table *tab;
209
210	/*
211	* Convert symbol ids into Syms, so we can deal with them more easily:
212	*/
213	for (id = id_list; id; id = id->next) {
214	parse_id(id);
215	} /* for */
216
217	/* first determine size of each table: */
218
219	for (sym = symtab.base; sym < symtab.limit; ++sym) {
220	for (id = id_list; id; id = id->next) {
221	if (match(&id->left.sym, sym)) {
222	extend_match(&id->left, sym, &syms[id->which_table], FALSE);
223	} /* if */
224	if (id->has_right && match(&id->right.sym, sym)) {
225	extend_match(&id->right, sym, &right_ids, FALSE);
226	} /* if */
227	} /* for */
228	} /* for */
229
230	/* create tables of appropriate size and reset lengths: */
231
232	for (tab = syms; tab < &syms[NUM_TABLES]; ++tab) {
233	if (tab->len) {
234	tab->base = (Sym) xmalloc(tab->len sizeof(Sym));
235	tab->limit = tab->base + tab->len;
236	tab->len = 0;
237	} /* if */
238	} /* for */
239	if (right_ids.len) {
240	right_ids.base = (Sym) xmalloc(right_ids.len sizeof(Sym));
241	right_ids.limit = right_ids.base + right_ids.len;
242	right_ids.len = 0;
243	} /* if */
244
245	/* make a second pass through symtab, creating syms as necessary: */
246
247	for (sym = symtab.base; sym < symtab.limit; ++sym) {
248	for (id = id_list; id; id = id->next) {
249	if (match(&id->left.sym, sym)) {
250	extend_match(&id->left, sym, &syms[id->which_table], TRUE);
251	} /* if */
252	if (id->has_right && match(&id->right.sym, sym)) {
253	extend_match(&id->right, sym, &right_ids, TRUE);
254	} /* if */
255	} /* for */
256	} /* for */
257
258	/* go through ids creating arcs as needed: */
259
260	for (id = id_list; id; id = id->next) {
261	if (id->has_right) {
262	for (left = id->left.first_match; left; left = left->next) {
263	for (right = id->right.first_match; right; right = right->next)
264	{
265	DBG(IDDEBUG,
266	printf(
267	"[sym_id_parse]: arc %s:%s(%lx-%lx) -> %s:%s(%lx-%lx) to %s\n",
268	left->file ? left->file->name : "*",
269	left->name ? left->name : "*", left->addr,
270	left->end_addr,
271	right->file ? right->file->name : "*",
272	right->name ? right->name : "*", right->addr,
273	right->end_addr,
274	table_name[id->which_table]));
275	arc_add(left, right, 0);
276	} /* for */
277	} /* for */
278	} /* if */
279	} /* for */
280
281	/* finally, we can sort the tables and we're done: */
282
283	for (tab = &syms[0]; tab < &syms[NUM_TABLES]; ++tab) {
284	DBG(IDDEBUG, printf("[sym_id_parse] syms[%s]:\n",
285	table_name[tab - &syms[0]]));
286	symtab_finalize(tab);
287	} /* for */
288	} /* sym_id_parse */
289
290
291	/*
292	* Symbol tables storing the FROM symbols of arcs do not necessarily
293	* have distinct address ranges. For example, somebody might request
294	* -k /_mcount to suppress any arcs into _mcount, while at the same
295	* time requesting -k a/b. Fortunately, those symbol tables don't get
296	* very big (the user has to type them!), so a linear search is probably
297	* tolerable.
298	*/
299	bool
300	DEFUN(sym_id_arc_is_present, (symtab, from, to),
301	Sym_Table symtab AND Sym from AND Sym *to)
302	{
303	Sym *sym;
304
305	for (sym = symtab->base; sym < symtab->limit; ++sym) {
306	if (from->addr >= sym->addr && from->addr <= sym->end_addr
307	&& arc_lookup(sym, to))
308	{
309	return TRUE;
310	} /* if */
311	} /* for */
312	return FALSE;
313	} /* sym_id_arc_is_present */
314
315	/* end of sym_ids.h */