This is the mail archive of the
elfutils-devel@sourceware.org
mailing list for the elfutils project.
[PATCH] Use trees rather than hashes in ar.c
- From: Ulf Hermann <ulf dot hermann at qt dot io>
- To: <elfutils-devel at sourceware dot org>
- Date: Thu, 4 May 2017 18:47:11 +0200
- Subject: [PATCH] Use trees rather than hashes in ar.c
- Authentication-results: sourceware.org; auth=none
- Authentication-results: sourceware.org; dkim=none (message not signed) header.d=none;sourceware.org; dmarc=none action=none header.from=qt.io;
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=qtcompany.onmicrosoft.com; s=selector1-qt-io; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=0w3MmO4w+OSGr6BVElPqgqJ5dJkR74YiM3gGILgr7pU=; b=fJHmjMhV1uRxY7bl+z0vxM1zOcH3eplp9cqkAHmAUNjibQNKBsly+pSUI0om0z5hws9ilpyZyppAsxRGH1hLZ/uVLluuFZ2gwUfcoPwCnF4gyxyTa3yeMPFu6ivGbBlZrAWXv/B7K3srt32AA0THGZC6AKNrYm9F8CokI/oG0Z8=
- Spamdiagnosticmetadata: NSPM
- Spamdiagnosticoutput: 1:99
The tree functions are more widely available.
Signed-off-by: Ulf Hermann <ulf.hermann@qt.io>
---
src/ChangeLog | 4 ++++
src/ar.c | 77 ++++++++++++++++++++++++++++++++++-------------------------
2 files changed, 48 insertions(+), 33 deletions(-)
diff --git a/src/ChangeLog b/src/ChangeLog
index 332b07c..32cd0c3 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,5 +1,9 @@
2017-05-04 Ulf Hermann <ulf.hermann@qt.io>
+ * ar.c: Use trees rather than hashes.
+
+2017-05-04 Ulf Hermann <ulf.hermann@qt.io>
+
* ar.c: Use octal numbers instead of permission macros.
* elfcompress.c: Likewise.
* ranlib.c: Likewise.
diff --git a/src/ar.c b/src/ar.c
index cc47f10..a13420c 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)
--
2.1.4