2004-02-27 H.J. Lu <hongjiu.lu@intel.com>

	* elflink.h (sort_symbol): New.
	(elf_link_add_object_symbols): Use a sorted symbol array for
	weakdef.

2 files changed, 135 insertions, 38 deletions

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index 1d808b0..f731c9e 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,9 @@
+2004-02-27  H.J. Lu  <hongjiu.lu@intel.com>
+
+	* elflink.h (sort_symbol): New.
+	(elf_link_add_object_symbols): Use a sorted symbol array for
+	weakdef.
+
 2004-02-27  Jakub Jelinek  <jakub@redhat.com>
 
 	* elf32-s390.c (allocate_dynrelocs): Use SYMBOL_REFERENCES_LOCAL
diff --git a/bfd/elflink.h b/bfd/elflink.h
index 96d5981..86db016 100644
--- a/bfd/elflink.h
+++ b/bfd/elflink.h
@@ -392,6 +392,28 @@ elf_link_add_archive_symbols (bfd *abfd, struct bfd_link_info *info)
   return FALSE;
 }
 
+/* Sort symbol by value and section.  */
+static int
+sort_symbol (const void *arg1, const void *arg2)
+{
+  const struct elf_link_hash_entry *h1
+    = *(const struct elf_link_hash_entry **) arg1;
+  const struct elf_link_hash_entry *h2
+    = *(const struct elf_link_hash_entry **) arg2;
+  bfd_signed_vma vdiff = h1->root.u.def.value - h2->root.u.def.value;
+
+  if (vdiff)
+    return vdiff > 0 ? 1 : -1;
+  else
+    {
+      long sdiff = h1->root.u.def.section - h2->root.u.def.section;
+      if (sdiff)
+	return sdiff > 0 ? 1 : -1;
+      else
+	return 0;
+    }
+}
+
 /* Add symbols from an ELF object file to the linker hash table.  */
 
 static bfd_boolean
@@ -1493,63 +1515,132 @@ elf_link_add_object_symbols (bfd *abfd, struct bfd_link_info *info)
      assembler code, handling it correctly would be very time
      consuming, and other ELF linkers don't handle general aliasing
      either.  */
-  while (weaks != NULL)
+  if (weaks != NULL)
     {
-      struct elf_link_hash_entry *hlook;
-      asection *slook;
-      bfd_vma vlook;
       struct elf_link_hash_entry **hpp;
       struct elf_link_hash_entry **hppend;
+      struct elf_link_hash_entry **sorted_sym_hash;
+      struct elf_link_hash_entry *h;
+      size_t sym_count;
 
-      hlook = weaks;
-      weaks = hlook->weakdef;
-      hlook->weakdef = NULL;
-
-      BFD_ASSERT (hlook->root.type == bfd_link_hash_defined
-		  || hlook->root.type == bfd_link_hash_defweak
-		  || hlook->root.type == bfd_link_hash_common
-		  || hlook->root.type == bfd_link_hash_indirect);
-      slook = hlook->root.u.def.section;
-      vlook = hlook->root.u.def.value;
-
+      /* Since we have to search the whole symbol list for each weak
+	 defined symbol, search time for N weak defined symbols will be
+	 O(N^2). Binary search will cut it down to O(NlogN).  */
+      amt = extsymcount * sizeof (struct elf_link_hash_entry *);
+      sorted_sym_hash = bfd_malloc (amt);
+      if (sorted_sym_hash == NULL)
+	goto error_return;
+      sym_hash = sorted_sym_hash;
       hpp = elf_sym_hashes (abfd);
       hppend = hpp + extsymcount;
+      sym_count = 0;
       for (; hpp < hppend; hpp++)
 	{
-	  struct elf_link_hash_entry *h;
-
 	  h = *hpp;
-	  if (h != NULL && h != hlook
+	  if (h != NULL
 	      && h->root.type == bfd_link_hash_defined
-	      && h->root.u.def.section == slook
-	      && h->root.u.def.value == vlook)
+	      && h->type != STT_FUNC)
 	    {
-	      hlook->weakdef = h;
+	      *sym_hash = h;
+	      sym_hash++;
+	      sym_count++;
+	    }
+	}
+
+      qsort (sorted_sym_hash, sym_count,
+	     sizeof (struct elf_link_hash_entry *),
+	     sort_symbol);
 
-	      /* If the weak definition is in the list of dynamic
-		 symbols, make sure the real definition is put there
-		 as well.  */
-	      if (hlook->dynindx != -1
-		  && h->dynindx == -1)
+      while (weaks != NULL)
+	{
+	  struct elf_link_hash_entry *hlook;
+	  asection *slook;
+	  bfd_vma vlook;
+	  long ilook;
+	  size_t i, j, idx;
+
+	  hlook = weaks;
+	  weaks = hlook->weakdef;
+	  hlook->weakdef = NULL;
+
+	  BFD_ASSERT (hlook->root.type == bfd_link_hash_defined
+		      || hlook->root.type == bfd_link_hash_defweak
+		      || hlook->root.type == bfd_link_hash_common
+		      || hlook->root.type == bfd_link_hash_indirect);
+	  slook = hlook->root.u.def.section;
+	  vlook = hlook->root.u.def.value;
+
+	  ilook = -1;
+	  i = 0;
+	  j = sym_count;
+	  while (i < j)
+	    {
+	      bfd_signed_vma vdiff;
+	      idx = (i + j) / 2;
+	      h = sorted_sym_hash [idx];
+	      vdiff = vlook - h->root.u.def.value;
+	      if (vdiff < 0)
+		j = idx;
+	      else if (vdiff > 0)
+		i = idx + 1;
+	      else
 		{
-		  if (! _bfd_elf_link_record_dynamic_symbol (info, h))
-		    goto error_return;
+		  long sdiff = slook - h->root.u.def.section;
+		  if (sdiff < 0)
+		    j = idx;
+		  else if (sdiff > 0)
+		    i = idx + 1;
+		  else
+		    {
+		      ilook = idx;
+		      break;
+		    }
 		}
+	    }
+
+	  /* We didn't find a value/section match.  */
+	  if (ilook == -1)
+	    continue;
+
+	  for (i = ilook; i < sym_count; i++)
+	    {
+	      h = sorted_sym_hash [i];
 
-	      /* If the real definition is in the list of dynamic
-		 symbols, make sure the weak definition is put there
-		 as well.  If we don't do this, then the dynamic
-		 loader might not merge the entries for the real
-		 definition and the weak definition.  */
-	      if (h->dynindx != -1
-		  && hlook->dynindx == -1)
+	      /* Stop if value or section doesn't match.  */
+	      if (h->root.u.def.value != vlook
+		  || h->root.u.def.section != slook)
+		break;
+	      else if (h != hlook)
 		{
-		  if (! _bfd_elf_link_record_dynamic_symbol (info, hlook))
-		    goto error_return;
+		  hlook->weakdef = h;
+
+		  /* If the weak definition is in the list of dynamic
+		     symbols, make sure the real definition is put
+		     there as well.  */
+		  if (hlook->dynindx != -1 && h->dynindx == -1)
+		    {
+		      if (! _bfd_elf_link_record_dynamic_symbol (info,
+								 h))
+			goto error_return;
+		    }
+
+		  /* If the real definition is in the list of dynamic
+		     symbols, make sure the weak definition is put
+		     there as well.  If we don't do this, then the
+		     dynamic loader might not merge the entries for the
+		     real definition and the weak definition.  */
+		  if (h->dynindx != -1 && hlook->dynindx == -1)
+		    {
+		      if (! _bfd_elf_link_record_dynamic_symbol (info,
+								 hlook))
+			goto error_return;
+		    }
+		  break;
 		}
-	      break;
 	    }
 	}
+
+      free (sorted_sym_hash);
     }
 
   /* If this object is the same format as the output object, and it is