Use trees rather than hashes in ar.c

The tree functions are more widely available.

Change-Id: Ic11a6485ae45f83e7ec8c18dcd7fa1a1902f7ff4
Reviewed-by: Christian Kandeler <[email protected]>

1 files changed, 44 insertions, 33 deletions

diff --git a/src/ar.c b/src/ar.c
index cc47f106..a13420c1 100644
--- a/src/ar.c
+++ b/src/ar.c
@@ -439,6 +439,20 @@ copy_content (Elf *elf, int newfd, off_t off, size_t n)
 
 
 static int
+string_compare (const void *a, const void *b)
+{
+  return strcmp((const char *)a, (const char *)b);
+}
+
+
+void
+free_node (void *node)
+{
+  (void) node;
+}
+
+
+static int
 do_oper_extract (int oper, const char *arfname, char **argv, int argc,
 		 long int instance)
 {
@@ -469,13 +483,11 @@ do_oper_extract (int oper, const char *arfname, char **argv, int argc,
   Elf *elf;
   int fd = open_archive (arfname, O_RDONLY | O_BINARY, 0, &elf, NULL, false);
 
-  if (hcreate (2 * argc) == 0)
-    error (EXIT_FAILURE, errno, gettext ("cannot create hash table"));
+  void *root = NULL;
 
   for (int cnt = 0; cnt < argc; ++cnt)
     {
-      ENTRY entry = { .key = argv[cnt], .data = &argv[cnt] };
-      if (hsearch (entry, ENTER) == NULL)
+      if (tsearch (argv[cnt], &root, &string_compare) == NULL)
 	error (EXIT_FAILURE, errno,
 	       gettext ("cannot insert into hash table"));
     }
@@ -517,12 +529,10 @@ do_oper_extract (int oper, const char *arfname, char **argv, int argc,
       bool do_extract = argc <= 0;
       if (!do_extract)
 	{
-	  ENTRY entry;
-	  entry.key = arhdr->ar_name;
-	  ENTRY *res = hsearch (entry, FIND);
+	  void *res = tfind (arhdr->ar_name, &root, &string_compare);
 	  if (res != NULL && (instance < 0 || instance-- == 0)
-	      && !found[(char **) res->data - argv])
-	    found[(char **) res->data - argv] = do_extract = true;
+	      && !found[(char **) res - argv])
+	    found[(char **) res - argv] = do_extract = true;
 	}
 
       if (do_extract)
@@ -741,7 +751,8 @@ cannot rename temporary file to %.*s"),
 	error (1, 0, "%s: %s", arfname, elf_errmsg (-1));
     }
 
-  hdestroy ();
+  tdestroy(root, &free_node);
+  root = NULL;
 
   if (force_symtab)
     {
@@ -921,13 +932,11 @@ do_oper_delete (const char *arfname, char **argv, int argc,
   struct stat st;
   int fd = open_archive (arfname, O_RDONLY | O_BINARY, 0, &elf, &st, false);
 
-  if (hcreate (2 * argc) == 0)
-    error (EXIT_FAILURE, errno, gettext ("cannot create hash table"));
+  void *root = NULL;
 
   for (int cnt = 0; cnt < argc; ++cnt)
     {
-      ENTRY entry = { .key = argv[cnt], .data = &argv[cnt] };
-      if (hsearch (entry, ENTER) == NULL)
+      if (tsearch (argv[cnt], &root, &string_compare) == NULL)
 	error (EXIT_FAILURE, errno,
 	       gettext ("cannot insert into hash table"));
     }
@@ -949,12 +958,10 @@ do_oper_delete (const char *arfname, char **argv, int argc,
       bool do_delete = argc <= 0;
       if (!do_delete)
 	{
-	  ENTRY entry;
-	  entry.key = arhdr->ar_name;
-	  ENTRY *res = hsearch (entry, FIND);
+	  void *res = tfind (arhdr->ar_name, &root, &string_compare);
 	  if (res != NULL && (instance < 0 || instance-- == 0)
-	      && !found[(char **) res->data - argv])
-	    found[(char **) res->data - argv] = do_delete = true;
+	      && !found[(char **) res - argv])
+	    found[(char **) res - argv] = do_delete = true;
 	}
 
       if (do_delete)
@@ -995,7 +1002,8 @@ do_oper_delete (const char *arfname, char **argv, int argc,
 
   arlib_finalize ();
 
-  hdestroy ();
+  tdestroy (root, &free_node);
+  root = NULL;
 
   /* Create a new, temporary file in the same directory as the
      original file.  */
@@ -1093,6 +1101,13 @@ no0print (bool ofmt, char *buf, int bufsize, long int val)
 
 
 static int
+basename_compare(const void *a, const void *b)
+{
+  return strcmp(basename((const char *)a), basename((const char *)b));
+}
+
+
+static int
 do_oper_insert (int oper, const char *arfname, char **argv, int argc,
 		const char *member)
 {
@@ -1100,6 +1115,7 @@ do_oper_insert (int oper, const char *arfname, char **argv, int argc,
   Elf *elf;
   struct stat st;
   int fd = open_archive (arfname, O_RDONLY | O_BINARY, 0, &elf, &st, oper != oper_move);
+  void *root = NULL;
 
   /* List of the files we keep.  */
   struct armem *all = NULL;
@@ -1127,15 +1143,9 @@ do_oper_insert (int oper, const char *arfname, char **argv, int argc,
      index.  */
   if (oper != oper_qappend)
     {
-      if (hcreate (2 * argc) == 0)
-	error (EXIT_FAILURE, errno, gettext ("cannot create hash table"));
-
       for (int cnt = 0; cnt < argc; ++cnt)
 	{
-	  ENTRY entry;
-	  entry.key = full_path ? argv[cnt] : basename (argv[cnt]);
-	  entry.data = &argv[cnt];
-	  if (hsearch (entry, ENTER) == NULL)
+	  if (tsearch (argv[cnt], &root, full_path ? &basename_compare : &string_compare) == NULL)
 	    error (EXIT_FAILURE, errno,
 		   gettext ("cannot insert into hash table"));
 	}
@@ -1178,12 +1188,10 @@ do_oper_insert (int oper, const char *arfname, char **argv, int argc,
 	      member = NULL;
 	    }
 
-	  ENTRY entry;
-	  entry.key = arhdr->ar_name;
-	  ENTRY *res = hsearch (entry, FIND);
-	  if (res != NULL && found[(char **) res->data - argv] == NULL)
+	  void *res = tfind(arhdr->ar_name, &root, full_path ? &basename_compare : &string_compare);
+	  if (res != NULL && found[(char **) res - argv] == NULL)
 	    {
-	      found[(char **) res->data - argv] = newp;
+	      found[(char **) res - argv] = newp;
 
 	      /* If we insert before or after a certain element move
 		 all files to a special list.  */
@@ -1215,7 +1223,10 @@ do_oper_insert (int oper, const char *arfname, char **argv, int argc,
     }
 
   if (oper != oper_qappend)
-    hdestroy ();
+    {
+      tdestroy(root, &free_node);
+      root = NULL;
+    }
 
  no_old:
   if (member != NULL)