From: Tom de Vries <tdevries@suse.de>
To: dwz@sourceware.org, jakub@redhat.com
Subject: [committed] Add emulate_htab
Date: Tue, 01 Jan 2019 00:00:00 -0000 [thread overview]
Message-ID: <20191121163233.GA23560@delia> (raw)
Hi,
Add a function emulate_htab that emulates how the hash tables in hashtab.c
grow in size.
Committed to trunk.
Thanks,
- Tom
Add emulate_htab
2019-11-20 Tom de Vries <tdevries@suse.de>
* hashtab.c (higher_prime_number): Remove static.
* hashtab.h (higher_prime_number): Declare.
* dwz.c (emulate_htab): New function.
---
dwz.c | 30 ++++++++++++++++++++++++++++++
hashtab.c | 3 +--
hashtab.h | 3 +++
3 files changed, 34 insertions(+), 2 deletions(-)
diff --git a/dwz.c b/dwz.c
index 846e42f..db134ab 100644
--- a/dwz.c
+++ b/dwz.c
@@ -1197,6 +1197,36 @@ estimate_nr_dies (void)
return nr_dies;
}
+static size_t UNUSED
+emulate_htab (size_t initial, size_t final_nr_elements)
+{
+ size_t size = initial;
+
+ /* Emulate creation. */
+ size = higher_prime_number (size);
+
+ /* Emulate growing till htab contains find_nr_elements. */
+ while (1)
+ {
+ /* Emulate expansion trigger. */
+ size_t nr_elements = size * 3 / 4;
+ while (!(size * 3 <= nr_elements * 4))
+ nr_elements++;
+
+ if (nr_elements > final_nr_elements)
+ {
+ nr_elements = final_nr_elements;
+ break;
+ }
+
+ /* Emulate expansion. */
+ size = size * 2;
+ size = higher_prime_number (size);
+ }
+
+ return size;
+}
+
/* Hash function for off_htab hash table. */
static hashval_t
off_hash (const void *p)
diff --git a/hashtab.c b/hashtab.c
index 5d98451..41eab30 100644
--- a/hashtab.c
+++ b/hashtab.c
@@ -51,7 +51,6 @@ Boston, MA 02110-1301, USA. */
#define DELETED_ENTRY ((void *) 1)
-static unsigned long higher_prime_number (unsigned long);
static hashval_t hash_pointer (const void *);
static int eq_pointer (const void *, const void *);
static int htab_expand (htab_t);
@@ -66,7 +65,7 @@ htab_eq htab_eq_pointer = eq_pointer;
/* The following function returns a nearest prime number which is
greater than N, and near a power of two. */
-static unsigned long
+unsigned long
higher_prime_number (n)
unsigned long n;
{
diff --git a/hashtab.h b/hashtab.h
index f1cc743..cb3da01 100644
--- a/hashtab.h
+++ b/hashtab.h
@@ -132,6 +132,9 @@ extern size_t htab_size (htab_t);
extern size_t htab_elements (htab_t);
extern double htab_collisions (htab_t);
+/* Utility function. */
+unsigned long higher_prime_number (unsigned long);
+
/* A hash function for pointers. */
extern htab_hash htab_hash_pointer;
reply other threads:[~2019-11-21 16:32 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20191121163233.GA23560@delia \
--to=tdevries@suse.de \
--cc=dwz@sourceware.org \
--cc=jakub@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).