X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=bfd%2Felf-strtab.c;h=f5013d15e4a725d8f5b8c2969afda602efb6194f;hb=67ce33d768510c7f826be66a2b4ea22c7caea801;hp=59a25a5446453838414ea8d8982bbe8b4fda2b73;hpb=2b0f7ef92ee30445837f86ca0149ec6c6c01dc93;p=deliverable%2Fbinutils-gdb.git

diff --git a/bfd/elf-strtab.c b/bfd/elf-strtab.c
index 59a25a5446..f5013d15e4 100644
--- a/bfd/elf-strtab.c
+++ b/bfd/elf-strtab.c
@@ -1,41 +1,44 @@
 /* ELF strtab with GC and suffix merging support.
-   Copyright 2001 Free Software Foundation, Inc.
+   Copyright 2001, 2002, 2003, 2005, 2006, 2007, 2008
+   Free Software Foundation, Inc.
    Written by Jakub Jelinek <jakub@redhat.com>.
 
-This file is part of BFD, the Binary File Descriptor library.
+   This file is part of BFD, the Binary File Descriptor library.
 
-This program is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2 of the License, or
-(at your option) any later version.
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
 
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-GNU General Public License for more details.
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
 
-You should have received a copy of the GNU General Public License
-along with this program; if not, write to the Free Software
-Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+   MA 02110-1301, USA.  */
 
-#include "bfd.h"
 #include "sysdep.h"
+#include "bfd.h"
 #include "libbfd.h"
 #include "elf-bfd.h"
 #include "hashtab.h"
+#include "libiberty.h"
 
 /* An entry in the strtab hash table.  */
 
 struct elf_strtab_hash_entry
 {
   struct bfd_hash_entry root;
-  /* Length of this entry.  */
-  unsigned int len;
+  /* Length of this entry.  This includes the zero terminator.  */
+  int len;
   unsigned int refcount;
   union {
     /* Index within the merged section.  */
     bfd_size_type index;
-    /* Entry this is a suffix of (if len is 0).  */
+    /* Entry this is a suffix of (if len < 0).  */
     struct elf_strtab_hash_entry *suffix;
   } u;
 };
@@ -55,58 +58,51 @@ struct elf_strtab_hash
   struct elf_strtab_hash_entry **array;
 };
 
-static struct bfd_hash_entry *elf_strtab_hash_newfunc
-  PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
-static int cmplengthentry PARAMS ((const PTR, const PTR));
-static int last4_eq PARAMS ((const PTR, const PTR));
-static int last_eq PARAMS ((const PTR, const PTR));
-
 /* Routine to create an entry in a section merge hashtab.  */
 
 static struct bfd_hash_entry *
-elf_strtab_hash_newfunc (entry, table, string)
-     struct bfd_hash_entry *entry;
-     struct bfd_hash_table *table;
-     const char *string;
+elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
+			 struct bfd_hash_table *table,
+			 const char *string)
 {
-  struct elf_strtab_hash_entry *ret = (struct elf_strtab_hash_entry *) entry;
-
   /* Allocate the structure if it has not already been allocated by a
      subclass.  */
-  if (ret == (struct elf_strtab_hash_entry *) NULL)
-    ret = ((struct elf_strtab_hash_entry *)
-	   bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)));
-  if (ret == (struct elf_strtab_hash_entry *) NULL)
+  if (entry == NULL)
+    entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
+  if (entry == NULL)
     return NULL;
 
   /* Call the allocation method of the superclass.  */
-  ret = ((struct elf_strtab_hash_entry *)
-	 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
+  entry = bfd_hash_newfunc (entry, table, string);
 
-  if (ret)
+  if (entry)
     {
       /* Initialize the local fields.  */
+      struct elf_strtab_hash_entry *ret;
+
+      ret = (struct elf_strtab_hash_entry *) entry;
       ret->u.index = -1;
       ret->refcount = 0;
       ret->len = 0;
     }
 
-  return (struct bfd_hash_entry *)ret;
+  return entry;
 }
 
 /* Create a new hash table.  */
 
 struct elf_strtab_hash *
-_bfd_elf_strtab_init ()
+_bfd_elf_strtab_init (void)
 {
   struct elf_strtab_hash *table;
   bfd_size_type amt = sizeof (struct elf_strtab_hash);
 
-  table = (struct elf_strtab_hash *) bfd_malloc (amt);
+  table = bfd_malloc (amt);
   if (table == NULL)
     return NULL;
 
-  if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc))
+  if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
+			    sizeof (struct elf_strtab_hash_entry)))
     {
       free (table);
       return NULL;
@@ -116,8 +112,7 @@ _bfd_elf_strtab_init ()
   table->size = 1;
   table->alloced = 64;
   amt = sizeof (struct elf_strtab_hasn_entry *);
-  table->array = (struct elf_strtab_hash_entry **)
-		 bfd_malloc (table->alloced * amt);
+  table->array = bfd_malloc (table->alloced * amt);
   if (table->array == NULL)
     {
       free (table);
@@ -132,8 +127,7 @@ _bfd_elf_strtab_init ()
 /* Free a strtab.  */
 
 void
-_bfd_elf_strtab_free (tab)
-     struct elf_strtab_hash *tab;
+_bfd_elf_strtab_free (struct elf_strtab_hash *tab)
 {
   bfd_hash_table_free (&tab->table);
   free (tab->array);
@@ -144,10 +138,9 @@ _bfd_elf_strtab_free (tab)
    already present.  */
 
 bfd_size_type
-_bfd_elf_strtab_add (tab, str, copy)
-     struct elf_strtab_hash *tab;
-     const char *str;
-     boolean copy;
+_bfd_elf_strtab_add (struct elf_strtab_hash *tab,
+		     const char *str,
+		     bfd_boolean copy)
 {
   register struct elf_strtab_hash_entry *entry;
 
@@ -158,7 +151,7 @@ _bfd_elf_strtab_add (tab, str, copy)
 
   BFD_ASSERT (tab->sec_size == 0);
   entry = (struct elf_strtab_hash_entry *)
-	  bfd_hash_lookup (&tab->table, str, true, copy);
+	  bfd_hash_lookup (&tab->table, str, TRUE, copy);
 
   if (entry == NULL)
     return (bfd_size_type) -1;
@@ -167,12 +160,13 @@ _bfd_elf_strtab_add (tab, str, copy)
   if (entry->len == 0)
     {
       entry->len = strlen (str) + 1;
+      /* 2G strings lose.  */
+      BFD_ASSERT (entry->len > 0);
       if (tab->size == tab->alloced)
 	{
 	  bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
 	  tab->alloced *= 2;
-	  tab->array = (struct elf_strtab_hash_entry **)
-		       bfd_realloc (tab->array, tab->alloced * amt);
+	  tab->array = bfd_realloc_or_free (tab->array, tab->alloced * amt);
 	  if (tab->array == NULL)
 	    return (bfd_size_type) -1;
 	}
@@ -184,9 +178,7 @@ _bfd_elf_strtab_add (tab, str, copy)
 }
 
 void
-_bfd_elf_strtab_addref (tab, idx)
-     struct elf_strtab_hash *tab;
-     bfd_size_type idx;
+_bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
 {
   if (idx == 0 || idx == (bfd_size_type) -1)
     return;
@@ -196,9 +188,7 @@ _bfd_elf_strtab_addref (tab, idx)
 }
 
 void
-_bfd_elf_strtab_delref (tab, idx)
-     struct elf_strtab_hash *tab;
-     bfd_size_type idx;
+_bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
 {
   if (idx == 0 || idx == (bfd_size_type) -1)
     return;
@@ -209,8 +199,7 @@ _bfd_elf_strtab_delref (tab, idx)
 }
 
 void
-_bfd_elf_strtab_clear_all_refs (tab)
-     struct elf_strtab_hash *tab;
+_bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
 {
   bfd_size_type idx;
 
@@ -219,16 +208,13 @@ _bfd_elf_strtab_clear_all_refs (tab)
 }
 
 bfd_size_type
-_bfd_elf_strtab_size (tab)
-     struct elf_strtab_hash *tab;
+_bfd_elf_strtab_size (struct elf_strtab_hash *tab)
 {
   return tab->sec_size ? tab->sec_size : tab->size;
 }
 
 bfd_size_type
-_bfd_elf_strtab_offset (tab, idx)
-     struct elf_strtab_hash *tab;
-     bfd_size_type idx;
+_bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
 {
   struct elf_strtab_hash_entry *entry;
 
@@ -242,204 +228,152 @@ _bfd_elf_strtab_offset (tab, idx)
   return tab->array[idx]->u.index;
 }
 
-boolean
-_bfd_elf_strtab_emit (abfd, tab)
-     register bfd *abfd;
-     struct elf_strtab_hash *tab;
+bfd_boolean
+_bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
 {
   bfd_size_type off = 1, i;
 
   if (bfd_bwrite ("", 1, abfd) != 1)
-    return false;
+    return FALSE;
 
   for (i = 1; i < tab->size; ++i)
     {
       register const char *str;
-      register size_t len;
+      register unsigned int len;
 
-      str = tab->array[i]->root.string;
-      len = tab->array[i]->len;
       BFD_ASSERT (tab->array[i]->refcount == 0);
-      if (len == 0)
+      len = tab->array[i]->len;
+      if ((int) len < 0)
 	continue;
 
-      if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
-	return false;
+      str = tab->array[i]->root.string;
+      if (bfd_bwrite (str, len, abfd) != len)
+	return FALSE;
 
       off += len;
     }
 
   BFD_ASSERT (off == tab->sec_size);
-  return true;
+  return TRUE;
 }
 
-/* Compare two elf_strtab_hash_entry structures.  This is called via qsort.  */
+/* Compare two elf_strtab_hash_entry structures.  Called via qsort.  */
 
 static int
-cmplengthentry (a, b)
-     const PTR a;
-     const PTR b;
+strrevcmp (const void *a, const void *b)
 {
-  struct elf_strtab_hash_entry * A = *(struct elf_strtab_hash_entry **) a;
-  struct elf_strtab_hash_entry * B = *(struct elf_strtab_hash_entry **) b;
-
-  if (A->len < B->len)
-    return 1;
-  else if (A->len > B->len)
-    return -1;
-
-  return memcmp (A->root.string, B->root.string, A->len);
-}
-
-static int
-last4_eq (a, b)
-     const PTR a;
-     const PTR b;
-{
-  struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a;
-  struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b;
-
-  if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
-      != 0)
-    /* This was a hashtable collision.  */
-    return 0;
-
-  if (A->len <= B->len)
-    /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
-       not to be equal by the hash table.  */
-    return 0;
-
-  return memcmp (A->root.string + (A->len - B->len),
-		 B->root.string, B->len - 5) == 0;
+  struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
+  struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
+  unsigned int lenA = A->len;
+  unsigned int lenB = B->len;
+  const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
+  const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
+  int l = lenA < lenB ? lenA : lenB;
+
+  while (l)
+    {
+      if (*s != *t)
+	return (int) *s - (int) *t;
+      s--;
+      t--;
+      l--;
+    }
+  return lenA - lenB;
 }
 
-static int
-last_eq (a, b)
-     const PTR a;
-     const PTR b;
+static inline int
+is_suffix (const struct elf_strtab_hash_entry *A,
+	   const struct elf_strtab_hash_entry *B)
 {
-  struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a;
-  struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b;
-
-  if (B->len >= 5)
-    /* Longer strings are just pushed into the hash table,
-       they'll be used when looking up for very short strings.  */
-    return 0;
-
-  if (memcmp (A->root.string + A->len - 2, B->root.string + B->len - 2, 1)
-      != 0)
-    /* This was a hashtable collision.  */
-    return 0;
-
   if (A->len <= B->len)
     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
        not to be equal by the hash table.  */
     return 0;
 
   return memcmp (A->root.string + (A->len - B->len),
-		 B->root.string, B->len - 2) == 0;
+		 B->root.string, B->len - 1) == 0;
 }
 
 /* This function assigns final string table offsets for used strings,
    merging strings matching suffixes of longer strings if possible.  */
 
 void
-_bfd_elf_strtab_finalize (tab)
-     struct elf_strtab_hash *tab;
+_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
 {
-  struct elf_strtab_hash_entry **array, **a, **end, *e;
-  htab_t lasttab = NULL, last4tab = NULL;
-  bfd_size_type size, amt, i;
+  struct elf_strtab_hash_entry **array, **a, *e;
+  bfd_size_type size, amt;
 
-  /* Now sort the strings by length, longest first.  */
-  array = NULL;
+  /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
+     a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
+     Besides, indexing with a long long wouldn't give anything but extra
+     cycles.  */
+  size_t i;
+
+  /* Sort the strings by suffix and length.  */
   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
-  array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
+  array = bfd_malloc (amt);
   if (array == NULL)
     goto alloc_failure;
 
   for (i = 1, a = array; i < tab->size; ++i)
-    if (tab->array[i]->refcount)
-      *a++ = tab->array[i];
-    else
-      tab->array[i]->len = 0;
+    {
+      e = tab->array[i];
+      if (e->refcount)
+	{
+	  *a++ = e;
+	  /* Adjust the length to not include the zero terminator.  */
+	  e->len -= 1;
+	}
+      else
+	e->len = 0;
+    }
 
   size = a - array;
+  if (size != 0)
+    {
+      qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
 
-  qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
+      /* Loop over the sorted array and merge suffixes.  Start from the
+	 end because we want eg.
 
-  last4tab = htab_create (size * 4, NULL, last4_eq, NULL);
-  lasttab = htab_create (size * 4, NULL, last_eq, NULL);
-  if (lasttab == NULL || last4tab == NULL)
-    goto alloc_failure;
+	 s1 -> "d"
+	 s2 -> "bcd"
+	 s3 -> "abcd"
 
-  /* Now insert the strings into hash tables (strings with last 4 characters
-     and strings with last character equal), look for longer strings which
-     we're suffix of.  */
-  for (a = array, end = array + size; a < end; a++)
-    {
-      register hashval_t hash;
-      unsigned int c;
-      unsigned int i;
-      const unsigned char *s;
-      PTR *p;
-
-      e = *a;
-      if (e->len > 4)
+	 to end up as
+
+	 s3 -> "abcd"
+	 s2 _____^
+	 s1 _______^
+
+	 ie. we don't want s1 pointing into the old s2.  */
+      e = *--a;
+      e->len += 1;
+      while (--a >= array)
 	{
-	  s = e->root.string + e->len - 1;
-	  hash = 0;
-	  for (i = 0; i < 4; i++)
-	    {
-	      c = *--s;
-	      hash += c + (c << 17);
-	      hash ^= hash >> 2;
-	    }
-	  p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
-	  if (p == NULL)
-	    goto alloc_failure;
-	  if (*p)
-	    {
-	      struct elf_strtab_hash_entry *ent;
+	  struct elf_strtab_hash_entry *cmp = *a;
 
-	      ent = (struct elf_strtab_hash_entry *) *p;
-	      e->u.suffix = ent;
-	      e->len = 0;
-	      continue;
+	  cmp->len += 1;
+	  if (is_suffix (e, cmp))
+	    {
+	      cmp->u.suffix = e;
+	      cmp->len = -cmp->len;
 	    }
 	  else
-	    *p = (PTR) e;
-	}
-      c = (unsigned char) e->root.string[e->len - 1];
-      p = htab_find_slot_with_hash (lasttab, e, c, INSERT);
-      if (p == NULL)
-	goto alloc_failure;
-      if (*p)
-	{
-	  struct elf_strtab_hash_entry *ent;
-
-	  ent = (struct elf_strtab_hash_entry *) *p;
-	  e->u.suffix = ent;
-	  e->len = 0;
+	    e = cmp;
 	}
-      else
-	*p = (PTR) e;
     }
 
 alloc_failure:
   if (array)
     free (array);
-  if (lasttab)
-    htab_delete (lasttab);
-  if (last4tab)
-    htab_delete (last4tab);
 
-  /* Now assign positions to the strings we want to keep.  */
+  /* Assign positions to the strings we want to keep.  */
   size = 1;
   for (i = 1; i < tab->size; ++i)
     {
       e = tab->array[i];
-      if (e->refcount && e->len)
+      if (e->refcount && e->len > 0)
 	{
 	  e->u.index = size;
 	  size += e->len;
@@ -448,12 +382,11 @@ alloc_failure:
 
   tab->sec_size = size;
 
-  /* And now adjust the rest.  */
+  /* Adjust the rest.  */
   for (i = 1; i < tab->size; ++i)
     {
       e = tab->array[i];
-      if (e->refcount && ! e->len)
-	e->u.index = e->u.suffix->u.index
-		     + (e->u.suffix->len - strlen (e->root.string) - 1);
+      if (e->refcount && e->len < 0)
+	e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
     }
 }