/* ELF strtab with GC and suffix merging support.
- Copyright 2001 Free Software Foundation, Inc.
+ Copyright 2001, 2002 Free Software Foundation, Inc.
-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 2 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
#include "bfd.h"
#include "sysdep.h"
#include "libbfd.h"
#include "elf-bfd.h"
#include "hashtab.h"
+#include "libiberty.h"
/* An entry in the strtab hash table. */
bfd_size_type index;
/* Entry this is a suffix of (if len is 0). */
struct elf_strtab_hash_entry *suffix;
+ struct elf_strtab_hash_entry *next;
} u;
};
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;
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);
/* 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);
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;
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;
{
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 (tab->array, tab->alloced * amt);
if (tab->array == NULL)
return (bfd_size_type) -1;
}
}
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;
}
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;
}
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
-_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;
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)
{
if (len == 0)
continue;
- if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
- return false;
+ 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. */
static int
-cmplengthentry (a, b)
- const PTR a;
- const PTR b;
+cmplengthentry (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;
+ 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;
}
static int
-last4_eq (a, b)
- const PTR a;
- const PTR b;
+last4_eq (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;
+ const struct elf_strtab_hash_entry *A = a;
+ const struct elf_strtab_hash_entry *B = b;
if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
!= 0)
B->root.string, B->len - 5) == 0;
}
-static int
-last_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 (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;
-}
-
/* 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;
+ htab_t last4tab = NULL;
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.
/* Now sort the strings by length, longest first. */
array = NULL;
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;
+ 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)
if (tab->array[i]->refcount)
*a++ = tab->array[i];
qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
- last4tab = htab_create (size * 4, NULL, last4_eq, NULL);
- lasttab = htab_create (size * 4, NULL, last_eq, NULL);
- if (lasttab == NULL || last4tab == NULL)
+ last4tab = htab_create_alloc (size * 4, NULL, last4_eq, NULL, calloc, free);
+ if (last4tab == NULL)
goto alloc_failure;
/* Now insert the strings into hash tables (strings with last 4 characters
unsigned int c;
unsigned int j;
const unsigned char *s;
- PTR *p;
+ void **p;
e = *a;
if (e->len > 4)
{
struct elf_strtab_hash_entry *ent;
- ent = (struct elf_strtab_hash_entry *) *p;
+ ent = *p;
e->u.suffix = ent;
e->len = 0;
continue;
}
else
- *p = (PTR) e;
+ *p = 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)
+ else
{
- struct elf_strtab_hash_entry *ent;
+ struct elf_strtab_hash_entry *tem;
- ent = (struct elf_strtab_hash_entry *) *p;
- e->u.suffix = ent;
- e->len = 0;
+ c = e->root.string[e->len - 2] & 0xff;
+
+ 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)
+ {
+ e->u.suffix = tem;
+ e->len = 0;
+ continue;
+ }
}
- else
- *p = (PTR) e;
+
+ 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);
- if (lasttab)
- htab_delete (lasttab);
if (last4tab)
htab_delete (last4tab);
projects / binutils.git / blobdiff