Re: [PATCH] Objcopy: use a hash table for symbol renaming

[Eirik Byrkjeflot Anonsen <eirik at opera dot com>]

Eirik Byrkjeflot Anonsen <eirik@opera.com> writes:

> Nick Clifton <nickc@redhat.com> writes:
>
>> Hi Eirik,
>>
>>> The attached patch replaces the linked list with a hash table
>>> implementation.
>>
>> Thanks for submitting this patch.  It is a good idea, but as
>> Hans-Peter has pointed out it would be better to make use of the
>> hashing functions that are already implemented in the libiberty
>> library, rather than creating your own.
>
> Fully agreed.  I just didn't know that libiberty has a hash table
> implementation.  I didn't even know that I was allowed to use libiberty
> in binutils.  In fact, you could say I know precious little about
> libiberty :)

Ok, I finally got around to spending some time trying to figure out how
libiberty's hash tables work.  I found the documentation to be somewhat
thin, so I ended up implementing the symbol redefinition hash table by
the time-honored coding style of "cut and paste".  (Though the resulting
code seems sensible.  And it seems to do the right thing.)

(Astonishingly, this version seems to be about 10% slower than mine.
"Astonishingly" because my version was optimized for correctness and
readability, not for performance.  Still, it's not a performance
difference that matters significantly.  The benefits of using a standard
implementation of hash tables far outweighs that minor performance hit.)

>
>> Also, with a change of this size, you will need to complete an FSF
>> copyright assignment, so that we can make use of your code.  I have
>> attached an emailable form which you can fill out in order to start
>> this process.
>
> Urgh!  I had forgotten about that.  I'll do that.

This is still in progress, but maybe this change is small enough to not
need it...

eirik


diff --git a/binutils/objcopy.c b/binutils/objcopy.c
index f92bdca..3c6fd7d 100644
--- a/binutils/objcopy.c
+++ b/binutils/objcopy.c
@@ -62,7 +62,6 @@ struct redefine_node
 {
   char *source;
   char *target;
-  struct redefine_node *next;
 };
 
 typedef struct section_rename
@@ -214,7 +213,8 @@ static htab_t localize_specific_htab = NULL;
 static htab_t globalize_specific_htab = NULL;
 static htab_t keepglobal_specific_htab = NULL;
 static htab_t weaken_specific_htab = NULL;
-static struct redefine_node *redefine_sym_list = NULL;
+static htab_t redefine_sym_htab = NULL;
+static htab_t redefine_sym_target_htab = NULL;
 
 /* If this is TRUE, we weaken global symbols (set BSF_WEAK).  */
 static bfd_boolean weaken = FALSE;
@@ -1013,7 +1013,7 @@ filter_symbols (bfd *abfd, bfd *obfd, asymbol **osyms,
 
       undefined = bfd_is_und_section (bfd_get_section (sym));
 
-      if (redefine_sym_list)
+      if (redefine_sym_htab)
 	{
 	  char *old_name, *new_name;
 
@@ -1180,42 +1180,83 @@ filter_symbols (bfd *abfd, bfd *obfd, asymbol **osyms,
 static const char *
 lookup_sym_redefinition (const char *source)
 {
-  struct redefine_node *list;
+  struct redefine_node *node;
+  struct redefine_node search_node;
 
-  for (list = redefine_sym_list; list != NULL; list = list->next)
-    if (strcmp (source, list->source) == 0)
-      return list->target;
+  if (redefine_sym_htab == NULL)
+	  return source;
 
-  return source;
+  search_node.source = (char*)source;
+  node = (struct redefine_node*)htab_find(redefine_sym_htab, &search_node);
+  if (node == NULL)
+    return source;
+  return node->target;
 }
 
-/* Add a node to a symbol redefine list.  */
+/* Symbol redefine hashtab functions. */
+
+static hashval_t htab_hash_redefine_sym(const void * item)
+{
+  struct redefine_node * node = (struct redefine_node *)item;
+  return htab_hash_string(node->source);
+}
+
+static hashval_t htab_hash_redefine_sym_target(const void * item)
+{
+  struct redefine_node * node = (struct redefine_node *)item;
+  return htab_hash_string(node->target);
+}
+
+static int htab_eq_redefine_sym(const void * first, const void * second)
+{
+  struct redefine_node * first_node = (struct redefine_node*)first;
+  struct redefine_node * second_node = (struct redefine_node*)second;
+  return strcmp(first_node->source, second_node->source) == 0;
+}
+
+static int htab_eq_redefine_sym_target(const void * first, const void * second)
+{
+  struct redefine_node * first_node = (struct redefine_node*)first;
+  struct redefine_node * second_node = (struct redefine_node*)second;
+  return strcmp(first_node->target, second_node->target) == 0;
+}
+
+/* Add a node to a symbol redefine hashtab.  */
 
 static void
 redefine_list_append (const char *cause, const char *source, const char *target)
 {
-  struct redefine_node **p;
-  struct redefine_node *list;
+  struct redefine_node *p;
   struct redefine_node *new_node;
 
-  for (p = &redefine_sym_list; (list = *p) != NULL; p = &list->next)
-    {
-      if (strcmp (source, list->source) == 0)
-	fatal (_("%s: Multiple redefinition of symbol \"%s\""),
-	       cause, source);
-
-      if (strcmp (target, list->target) == 0)
-	fatal (_("%s: Symbol \"%s\" is target of more than one redefinition"),
-	       cause, target);
-    }
+  if (redefine_sym_htab == NULL)
+  {
+    redefine_sym_target_htab = htab_create_alloc(
+		16,
+		htab_hash_redefine_sym_target, htab_eq_redefine_sym_target,
+		NULL, xcalloc, free);
+    redefine_sym_htab = htab_create_alloc(
+		16,
+		htab_hash_redefine_sym, htab_eq_redefine_sym,
+		NULL, xcalloc, free);
+  }
 
   new_node = (struct redefine_node *) xmalloc (sizeof (struct redefine_node));
-
   new_node->source = strdup (source);
   new_node->target = strdup (target);
-  new_node->next = NULL;
 
-  *p = new_node;
+  p = (struct redefine_node*)htab_find(redefine_sym_htab, new_node);
+  if (p != NULL)
+    fatal (_("%s: Multiple redefinition of symbol \"%s\""),
+	   cause, source);
+
+  p = (struct redefine_node*)htab_find(redefine_sym_target_htab, new_node);
+  if (p != NULL)
+    fatal (_("%s: Symbol \"%s\" is target of more than one redefinition"),
+	   cause, target);
+
+  *htab_find_slot(redefine_sym_htab, new_node, INSERT) = (char *) new_node;
+  *htab_find_slot(redefine_sym_target_htab, new_node, INSERT) = (char *) new_node;
 }
 
 /* Handle the --redefine-syms option.  Read lines containing "old new"
@@ -1815,7 +1856,7 @@ copy_object (bfd *ibfd, bfd *obfd)
       || convert_debugging
       || change_leading_char
       || remove_leading_char
-      || redefine_sym_list
+      || redefine_sym_htab
       || weaken)
     {
       /* Mark symbols used in output relocations so that they