From b7b4a6a14b7e8d096dc8cbc255b23be17a228cbb Mon Sep 17 00:00:00 2001
From: Alexandre Bonnetain <Shir0kamii@gmail.com>
Date: Tue, 12 Apr 2016 18:04:41 +0200
Subject: [PATCH] shrink the hashmap when it's too sparse

Signed-off-by: Alexandre Bonnetain <alexandre.bonnetain@1000mercis.com>
---
 job.c    | 21 +++++++++++++++------
 primes.c | 12 +++++++-----
 2 files changed, 22 insertions(+), 11 deletions(-)

diff --git a/job.c b/job.c
index f716fee..32487da 100644
--- a/job.c
+++ b/job.c
@@ -34,30 +34,36 @@ store_job(job j)
     all_jobs_used++;
 
     /* accept a load factor of 4 */
-    if (all_jobs_used > (all_jobs_cap << 2)) rehash();
+    if (all_jobs_used > (all_jobs_cap << 2)) rehash(1);
 }
 
 static void
-rehash()
+rehash(int is_upscaling)
 {
     job *old = all_jobs;
     size_t old_cap = all_jobs_cap, old_used = all_jobs_used, i;
+    int old_prime = cur_prime;
+    int d = is_upscaling ? 1 : -1;
 
-    if (cur_prime >= NUM_PRIMES) return;
-    if (hash_table_was_oom) return;
+    if (cur_prime + d >= NUM_PRIMES) return;
+    if (cur_prime + d < 0) return;
+    if (is_upscaling && hash_table_was_oom) return;
 
-    all_jobs_cap = primes[++cur_prime];
+    cur_prime += d;
+
+    all_jobs_cap = primes[cur_prime];
     all_jobs = calloc(all_jobs_cap, sizeof(job));
     if (!all_jobs) {
         twarnx("Failed to allocate %zu new hash buckets", all_jobs_cap);
         hash_table_was_oom = 1;
-        --cur_prime;
+        cur_prime = old_prime;
         all_jobs = old;
         all_jobs_cap = old_cap;
         all_jobs_used = old_used;
         return;
     }
     all_jobs_used = 0;
+    hash_table_was_oom = 0;
 
     for (i = 0; i < old_cap; i++) {
         while (old[i]) {
@@ -135,6 +141,9 @@ job_hash_free(job j)
         *slot = (*slot)->ht_next;
         --all_jobs_used;
     }
+
+    // Downscale when the hashmap is too sparse
+    if (all_jobs_used < (all_jobs_cap >> 4)) rehash(0);
 }
 
 void
diff --git a/primes.c b/primes.c
index 4d2f3fd..82f4e12 100644
--- a/primes.c
+++ b/primes.c
@@ -1,11 +1,13 @@
 #include <stdlib.h>
 
+// prime // downscale treshold / upscale treshold
+
 size_t primes[] = {
-    12289,
-    24593,
-    49193,
-    98387,
-    196799,
+    12289, // NA / 3072
+    24593, // 1537 / 6148
+    49193, // 3074 / 12298
+    98387, // 6149 / 24596
+    196799, // etc
     393611,
     787243,
     1574491,
-- 
2.11.4.GIT