* corefile.c (cmp_symbol_map): New function.

        (read_function_mappins): Use qsort to sort the symbols.
        (search_mapped_symbol): New function.
        (core_create_function_syms): Use bsearch to find symbols.
        * corefile.h (struct function_map): Add new bit-field: is_first.
        * cg_print.c (cmp_symbol_map): New function.
        (cg_print_file_ordering): Sort the symbol map.

4 files changed, 74 insertions, 53 deletions

diff --git a/gprof/ChangeLog b/gprof/ChangeLog
index a359bd6..68428aa 100644
--- a/gprof/ChangeLog
+++ b/gprof/ChangeLog
@@ -1,3 +1,13 @@
+2009-06-16  Homer Xing  <homer.xing@yahoo.com>
+
+	* corefile.c (cmp_symbol_map): New function.
+	(read_function_mappins): Use qsort to sort the symbols.
+	(search_mapped_symbol): New function.
+	(core_create_function_syms): Use bsearch to find symbols.
+	* corefile.h (struct function_map): Add new bit-field: is_first.
+	* cg_print.c (cmp_symbol_map): New function.
+	(cg_print_file_ordering): Sort the symbol map.
+
 2009-06-15  Homer Xing  <homer.xing@yahoo.com>
 
 	* corefile.c (core_create_syms_from): Use BFD_VMA_FMT when
diff --git a/gprof/cg_print.c b/gprof/cg_print.c
index 58ff608..0b2e989 100644
--- a/gprof/cg_print.c
+++ b/gprof/cg_print.c
@@ -1,6 +1,7 @@
 /* cg_print.c -  Print routines for displaying call graphs.
 
-   Copyright 2000, 2001, 2002, 2004, 2007 Free Software Foundation, Inc.
+   Copyright 2000, 2001, 2002, 2004, 2007, 2009
+   Free Software Foundation, Inc.
 
    This file is part of GNU Binutils.
 
@@ -1212,12 +1213,22 @@ order_and_dump_functions_by_arcs (the_arcs, arc_count, all,
       }
 }
 
+/* Compare two function_map structs based on file name.
+   We want to sort in ascending order.  */
+
+static int
+cmp_symbol_map (const void * l, const void * r)
+{
+  return strcmp (((struct function_map *) l)->file_name, 
+	         ((struct function_map *) r)->file_name);
+}
+
 /* Print a suggested .o ordering for files on a link line based
    on profiling information.  This uses the function placement
    code for the bulk of its work.  */
 
 void
-cg_print_file_ordering ()
+cg_print_file_ordering (void)
 {
   unsigned long scratch_arc_count, index;
   Arc **scratch_arcs;
@@ -1244,6 +1255,8 @@ cg_print_file_ordering ()
 	printf ("%s\n", symtab.base[index].name);
     }
 
+  qsort (symbol_map, symbol_map_count, sizeof (struct function_map), cmp_symbol_map);
+
   /* Now output any .o's that didn't have any text symbols.  */
   last = NULL;
   for (index = 0; index < symbol_map_count; index++)
diff --git a/gprof/corefile.c b/gprof/corefile.c
index d7df904..9f1118a 100644
--- a/gprof/corefile.c
+++ b/gprof/corefile.c
@@ -61,12 +61,23 @@ parse_error (const char *filename)
   done (1);
 }
 
+/* Compare two function_map structs based on function name.
+   We want to sort in ascending order.  */
+
+static int
+cmp_symbol_map (const void * l, const void * r)
+{
+  return strcmp (((struct function_map *) l)->function_name, 
+		 ((struct function_map *) r)->function_name);
+}
+
 static void
 read_function_mappings (const char *filename)
 {
-  FILE *file = fopen (filename, "r");
+  FILE * file = fopen (filename, "r");
   char dummy[1024];
   int count = 0;
+  unsigned int i;
 
   if (!file)
     {
@@ -144,11 +155,16 @@ read_function_mappings (const char *filename)
 
   /* Record the size of the map table for future reference.  */
   symbol_map_count = count;
-}
 
+  for (i = 0; i < symbol_map_count; ++i)
+    if (i == 0 || strcmp (symbol_map[i].file_name, symbol_map[i - 1].file_name))
+      symbol_map[i].is_first = 1;
+
+  qsort (symbol_map, symbol_map_count, sizeof (struct function_map), cmp_symbol_map);
+}
 
 void
-core_init (const char *aout_name)
+core_init (const char * aout_name)
 {
   int core_sym_bytes;
   asymbol *synthsyms;
@@ -532,17 +548,23 @@ core_create_syms_from (const char * sym_table_file)
   free (name);
 }
 
+static int
+search_mapped_symbol (const void * l, const void * r)
+{
+    return strcmp ((const char *) l, ((const struct function_map *) r)->function_name);
+}
+
 /* Read in symbol table from core.
    One symbol per function is entered.  */
 
 void
-core_create_function_syms ()
+core_create_function_syms (void)
 {
-  bfd_vma min_vma = ~(bfd_vma) 0;
+  bfd_vma min_vma = ~ (bfd_vma) 0;
   bfd_vma max_vma = 0;
   int class;
-  long i, found, skip;
-  unsigned int j;
+  long i;
+  struct function_map * found;
 
   /* Pass 1 - determine upper bound on number of function names.  */
   symtab.len = 0;
@@ -552,23 +574,12 @@ core_create_function_syms ()
       if (!core_sym_class (core_syms[i]))
 	continue;
 
-      /* This should be replaced with a binary search or hashed
-	 search.  Gross.
-
-	 Don't create a symtab entry for a function that has
+      /* Don't create a symtab entry for a function that has
 	 a mapping to a file, unless it's the first function
 	 in the file.  */
-      skip = 0;
-      for (j = 0; j < symbol_map_count; j++)
-	if (!strcmp (core_syms[i]->name, symbol_map[j].function_name))
-	  {
-	    if (j > 0 && ! strcmp (symbol_map [j].file_name,
-				   symbol_map [j - 1].file_name))
-	      skip = 1;
-	    break;
-	  }
-
-      if (!skip)
+      found = bsearch (core_syms[i]->name, symbol_map, symbol_map_count,
+		       sizeof (struct function_map), search_mapped_symbol);
+      if (found == NULL || found->is_first)
 	++symtab.len;
     }
 
@@ -598,23 +609,9 @@ core_create_function_syms ()
 	  continue;
 	}
 
-      /* This should be replaced with a binary search or hashed
-	 search.  Gross.   */
-      skip = 0;
-      found = 0;
-
-      for (j = 0; j < symbol_map_count; j++)
-	if (!strcmp (core_syms[i]->name, symbol_map[j].function_name))
-	  {
-	    if (j > 0 && ! strcmp (symbol_map [j].file_name,
-				   symbol_map [j - 1].file_name))
-	      skip = 1;
-	    else
-	      found = j;
-	    break;
-	  }
-
-      if (skip)
+      found = bsearch (core_syms[i]->name, symbol_map, symbol_map_count,
+		       sizeof (struct function_map), search_mapped_symbol);
+      if (found && ! found->is_first)
 	continue;
 
       sym_init (symtab.limit);
@@ -625,10 +622,9 @@ core_create_function_syms ()
       if (sym_sec)
 	symtab.limit->addr += bfd_get_section_vma (sym_sec->owner, sym_sec);
 
-      if (symbol_map_count
-	  && !strcmp (core_syms[i]->name, symbol_map[found].function_name))
+      if (found)
 	{
-	  symtab.limit->name = symbol_map[found].file_name;
+	  symtab.limit->name = found->file_name;
 	  symtab.limit->mapped = 1;
 	}
       else
@@ -639,10 +635,11 @@ core_create_function_syms ()
 
       /* Lookup filename and line number, if we can.  */
       {
-	const char *filename, *func_name;
+	const char * filename;
+	const char * func_name;
 
-	if (get_src_info (symtab.limit->addr, &filename, &func_name,
-			  &symtab.limit->line_num))
+	if (get_src_info (symtab.limit->addr, & filename, & func_name,
+			  & symtab.limit->line_num))
 	  {
 	    symtab.limit->file = source_file_lookup_path (filename);
 
@@ -702,7 +699,7 @@ core_create_function_syms ()
    One symbol per line of source code is entered.  */
 
 void
-core_create_line_syms ()
+core_create_line_syms (void)
 {
   char *prev_name, *prev_filename;
   unsigned int prev_name_len, prev_filename_len;
diff --git a/gprof/corefile.h b/gprof/corefile.h
index ccdaf13..d3844f0 100644
--- a/gprof/corefile.h
+++ b/gprof/corefile.h
@@ -24,8 +24,9 @@
 
 struct function_map
 {
-  char *function_name;
-  char *file_name;
+  char *         function_name;
+  char *         file_name;
+  unsigned int   is_first:1;	/* Is this the first symbol in an object file?  */
 };
 
 extern struct function_map * symbol_map;
@@ -33,9 +34,9 @@ extern unsigned int symbol_map_count;
 
 extern bfd * core_bfd;		  /* BFD for core-file.  */
 extern asection * core_text_sect; /* Core text section.  */
-extern void * core_text_space;	/* Text space of a.out in core.  */
-extern int offset_to_code;	/* Offset (in bytes) of code from entry
-				   address of routine.  */
+extern void * core_text_space;    /* Text space of a.out in core.  */
+extern int offset_to_code;	  /* Offset (in bytes) of code from entry
+				     address of routine.  */
 
 extern void core_init                  (const char *);
 extern void core_get_text_space        (bfd *);