include/elf/

[deliverable/binutils-gdb.git] / bfd / elf-strtab.c

diff --git a/bfd/elf-strtab.c b/bfd/elf-strtab.c
index 7a993c252f518daf5c3cb2986f9267673113c962..f5013d15e4a725d8f5b8c2969afda602efb6194f 100644 (file)
--- a/bfd/elf-strtab.c
+++ b/bfd/elf-strtab.c
@@ -1,12 +1,13 @@
 /* ELF strtab with GC and suffix merging support.
 /* ELF strtab with GC and suffix merging support.

-   Copyright 2001, 2002 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 program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    Written by Jakub Jelinek <jakub@redhat.com>.
 
    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
+   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,
    (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,


@@ -16,10 +17,11 @@
 
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
 
    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.  */
+   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+   MA 02110-1301, USA.  */

 
 

-#include "bfd.h"

 #include "sysdep.h"
 #include "sysdep.h"

+#include "bfd.h"

 #include "libbfd.h"
 #include "elf-bfd.h"
 #include "hashtab.h"
 #include "libbfd.h"
 #include "elf-bfd.h"
 #include "hashtab.h"


@@ -30,15 +32,14 @@
 struct elf_strtab_hash_entry
 {
   struct bfd_hash_entry root;
 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;
   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;
     struct elf_strtab_hash_entry *suffix;

-    struct elf_strtab_hash_entry *next;

   } u;
 };
 
   } u;
 };
 


@@ -57,57 +58,51 @@ struct elf_strtab_hash
   struct elf_strtab_hash_entry **array;
 };
 
   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));
-

 /* Routine to create an entry in a section merge hashtab.  */
 
 static struct bfd_hash_entry *
 /* 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.  */
   /* 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.  */
     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.  */
     {
       /* 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;
     }
 
       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 *
 }
 
 /* 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);
 
 {
   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 (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;
     {
       free (table);
       return NULL;


@@ -117,8 +112,7 @@ _bfd_elf_strtab_init ()
   table->size = 1;
   table->alloced = 64;
   amt = sizeof (struct elf_strtab_hasn_entry *);
   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);
   if (table->array == NULL)
     {
       free (table);


@@ -133,8 +127,7 @@ _bfd_elf_strtab_init ()
 /* Free a strtab.  */
 
 void
 /* 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);
 {
   bfd_hash_table_free (&tab->table);
   free (tab->array);


@@ -145,10 +138,9 @@ _bfd_elf_strtab_free (tab)
    already present.  */
 
 bfd_size_type
    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;
 
 {
   register struct elf_strtab_hash_entry *entry;
 


@@ -159,7 +151,7 @@ _bfd_elf_strtab_add (tab, str, copy)
 
   BFD_ASSERT (tab->sec_size == 0);
   entry = (struct elf_strtab_hash_entry *)
 
   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;
 
   if (entry == NULL)
     return (bfd_size_type) -1;


@@ -168,12 +160,13 @@ _bfd_elf_strtab_add (tab, str, copy)
   if (entry->len == 0)
     {
       entry->len = strlen (str) + 1;
   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;
       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;
        }
          if (tab->array == NULL)
            return (bfd_size_type) -1;
        }


@@ -185,9 +178,7 @@ _bfd_elf_strtab_add (tab, str, copy)
 }
 
 void
 }
 
 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;
 {
   if (idx == 0 || idx == (bfd_size_type) -1)
     return;


@@ -197,9 +188,7 @@ _bfd_elf_strtab_addref (tab, idx)
 }
 
 void
 }
 
 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;
 {
   if (idx == 0 || idx == (bfd_size_type) -1)
     return;


@@ -210,8 +199,7 @@ _bfd_elf_strtab_delref (tab, idx)
 }
 
 void
 }
 
 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;
 
 {
   bfd_size_type idx;
 


@@ -220,16 +208,13 @@ _bfd_elf_strtab_clear_all_refs (tab)
 }
 
 bfd_size_type
 }
 
 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
 {
   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;
 
 {
   struct elf_strtab_hash_entry *entry;
 


@@ -243,88 +228,80 @@ _bfd_elf_strtab_offset (tab, idx)
   return tab->array[idx]->u.index;
 }
 
   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)
 {
   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;
 
   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);
       BFD_ASSERT (tab->array[i]->refcount == 0);

-      if (len == 0)
+      len = tab->array[i]->len;
+      if ((int) len < 0)

        continue;
 
        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);
 
       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
 
 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);
+  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
-last4_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 (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),
   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;
+                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
 }
 
 /* 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 last4tab = NULL;
+  struct elf_strtab_hash_entry **array, **a, *e;

   bfd_size_type size, amt;
   bfd_size_type size, amt;

-  struct elf_strtab_hash_entry *last[256], **last_ptr[256];

 
   /* 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.
 
   /* 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.


@@ -332,105 +309,71 @@ _bfd_elf_strtab_finalize (tab)
      cycles.  */
   size_t i;
 
      cycles.  */
   size_t i;
 

-  /* Now sort the strings by length, longest first.  */
-  array = NULL;
+  /* Sort the strings by suffix and length.  */

   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
   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;
 
   if (array == NULL)
     goto alloc_failure;
 

-  memset (last, 0, sizeof (last));
-  for (i = 0; i < 256; ++i)
-    last_ptr[i] = &last[i];

   for (i = 1, a = array; i < tab->size; ++i)
   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;
 
   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_alloc (size * 4, NULL, last4_eq, NULL, calloc, free);
-  if (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 j;
-      const unsigned char *s;
-      PTR *p;
-
-      e = *a;
-      if (e->len > 4)
-       {
-         s = e->root.string + e->len - 1;
-         hash = 0;
-         for (j = 0; j < 4; j++)
-           {
-             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;
+        to end up as

 
 

-             ent = (struct elf_strtab_hash_entry *) *p;
-             e->u.suffix = ent;
-             e->len = 0;
-             continue;
-           }
-         else
-           *p = (PTR) e;
-       }
-      else
-       {
-         struct elf_strtab_hash_entry *tem;
+        s3 -> "abcd"
+        s2 _____^
+        s1 _______^

 
 

-         c = e->root.string[e->len - 2] & 0xff;
+        ie. we don't want s1 pointing into the old s2.  */
+      e = *--a;
+      e->len += 1;
+      while (--a >= array)
+       {
+         struct elf_strtab_hash_entry *cmp = *a;

 
 

-         for (tem = last[c]; tem; tem = tem->u.next)
-           if (tem->len > e->len
-               && memcmp (tem->root.string + (tem->len - e->len),
-                          e->root.string, e->len - 1) == 0)
-             break;
-         if (tem)
+         cmp->len += 1;
+         if (is_suffix (e, cmp))

            {
            {

-             e->u.suffix = tem;
-             e->len = 0;
-             continue;
+             cmp->u.suffix = e;
+             cmp->len = -cmp->len;

            }
            }

+         else
+           e = cmp;

        }
        }

-
-      c = e->root.string[e->len - 2] & 0xff;
-      /* Put longest strings first.  */
-      *last_ptr[c] = e;
-      last_ptr[c] = &e->u.next;
-      e->u.next = NULL;

     }
 
 alloc_failure:
   if (array)
     free (array);
     }
 
 alloc_failure:
   if (array)
     free (array);

-  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];
   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;
        {
          e->u.index = size;
          size += e->len;


@@ -439,12 +382,11 @@ alloc_failure:
 
   tab->sec_size = size;
 
 
   tab->sec_size = size;
 

-  /* And now adjust the rest.  */
+  /* Adjust the rest.  */

   for (i = 1; i < tab->size; ++i)
     {
       e = tab->array[i];
   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);

     }
 }
     }
 }