BSR

A prototype of BSR is roughly finished.

1 files changed, 188 insertions, 3 deletions

diff --git a/src/ht.c b/src/ht.c
index 2fc1206..7965941 100644
--- a/src/ht.c
+++ b/src/ht.c
@@ -99,6 +99,8 @@ new_ht(UNUM size, int nargs, ...)
 void
 destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag)
 {
+  if (htp == NULL) return;
+
   switch (flag) {
   case DESTROY_KEY_SELF:
   case DESTROY_KEY_NO_SELF:
@@ -214,6 +216,7 @@ ht_expand(ht *htp)
 #define PERTURBATION_SHIFT 5
 
 /* On error return non-zero. */
+__attribute__((__hot__))
 static BOOL
 ht_probe(CC_MOD(ht *) htp, CC_MOD(void *) key, NUM *result)
 {
@@ -243,9 +246,6 @@ ht_probe(CC_MOD(ht *) htp, CC_MOD(void *) key, NUM *result)
 
   *result = ikey;
 
-  /* if (*((NUM*) key) == 3) {
-   *   fleprintf("ikey = %ld, result = %ld\n", ikey, *result);
-   * } */
   return 0;
 }
 
@@ -357,3 +357,188 @@ ht_keys(CCR_MOD(ht *) htp)
 {
   return htp->keys;
 }
+
+/* Calculate binomial coefficients efficiently.
+
+   The algorithm is adapted from the following website.
+
+   <https://blog.plover.com/math/choose.html> */
+
+UHC_ATTR
+static NUM
+binom(NUM n, int k) {
+  if (k < 1) {
+    fleprintf("Invalid k: %d\n", k);
+    return 0;
+  }
+
+  NUM result = 1;
+
+  for (int d = 1; d <= k;) {
+    result *= n--;
+    result /= d++;
+  }
+
+  return result;
+}
+
+/* REVIEW: I might want a faster hashing function in the future.
+   Consider using bit manipulations as shown in the following file.
+
+   <http://burtleburtle.net/bob/c/lookup3.c> */
+
+/* A generalization of Cantor's pairing functions.  See Wikipedia for
+   more information.
+
+   <https://en.wikipedia.org/wiki/Fueter–Pólya_theorem>
+
+   The integer n determins the number of arguments, which are all of
+   type NUM. */
+
+/* I later changed my mind and decided to use another pairing
+   function, the elegant pairing function of Szudzik.  See the
+   following page for details.
+
+   <http://szudzik.com/ElegantPairing.pdf> */
+UHC_ATTR
+static NUM
+pair(int n, ...) {
+  if (n < 1) {
+    fleprintf("Invalid n: %d\n", n);
+    return 0;
+  }
+
+  va_list args;
+
+  va_start(args, n);
+
+  NUM result = va_arg(args, NUM), temp = 0;
+
+  /* a simple fold */
+  for (int i = 1; i < n; i++) {
+    temp = va_arg(args, NUM);
+    result = (result >= temp) ?
+      result * result + result + temp :
+      result + temp * temp;
+  }
+
+  va_end(args);
+
+  return result;
+}
+
+HP_ATTR
+static NUM
+pair2_hf(CCR_MOD(void *) key) {
+  if (key == NULL) {
+    fleprintf0("Got NULL key!\n");
+    return 0;
+  }
+
+  NUM result = pair(2, ((pair2 *) key)->x, ((pair2 *) key)->y);
+
+  /* fleprintf("Hash of (%ld, %ld) is %ld\n",
+   *           ((pair2 *) key)->x,
+   *           ((pair2 *) key)->y,
+   *           result); */
+
+  return result;
+}
+
+HP_ATTR
+static BOOL
+pair2_cf(CCR_MOD(void *) keya, CCR_MOD(void *) keyb) {
+  if ((keya == NULL && keyb != NULL) ||
+      (keyb == NULL && keya != NULL))
+    return 0;
+
+  if (keya == NULL && keyb == NULL) return 1;
+
+  return ((pair2 *) keya)->x == ((pair2 *) keyb)->x &&
+    ((pair2 *) keya)->y == ((pair2 *) keyb)->y;
+}
+
+HP_ATTR
+static NUM
+pair3_hf(CCR_MOD(void *) key) {
+  if (key == NULL) {
+    fleprintf0("Got NULL key!\n");
+    return 0;
+  }
+
+  NUM result =
+    pair(3,
+         ((pair3 *) key)->x,
+         ((pair3 *) key)->y,
+         ((pair3 *) key)->z);
+
+  /* fleprintf("Hash of (%ld, %ld, %ld) is %ld\n",
+   *           ((pair3 *) key)->x,
+   *           ((pair3 *) key)->y,
+   *           ((pair3 *) key)->z,
+   *           result); */
+
+  return result;
+}
+
+HP_ATTR
+static BOOL
+pair3_cf(CCR_MOD(void *) keya, CCR_MOD(void *) keyb) {
+  if ((keya == NULL && keyb != NULL) ||
+      (keyb == NULL && keya != NULL))
+    return 0;
+
+  if (keya == NULL && keyb == NULL) return 1;
+
+  return ((pair3 *) keya)->x == ((pair3 *) keyb)->x &&
+    ((pair3 *) keya)->y == ((pair3 *) keyb)->y &&
+    ((pair3 *) keya)->z == ((pair3 *) keyb)->z;
+}
+
+HP_ATTR
+static NUM
+pair4_hf(CCR_MOD(void *) key) {
+  if (key == NULL) {
+    fleprintf0("Got NULL key!\n");
+    return 0;
+  }
+
+  NUM result =
+    pair(4,
+         ((pair4 *) key)->x,
+         ((pair4 *) key)->y,
+         ((pair4 *) key)->z,
+         ((pair4 *) key)->w);
+
+  /* fleprintf("Hash of (%ld, %ld, %ld) is %ld\n",
+   *           ((pair3 *) key)->x,
+   *           ((pair3 *) key)->y,
+   *           ((pair3 *) key)->z,
+   *           result); */
+
+  return result;
+}
+
+HP_ATTR
+static BOOL
+pair4_cf(CCR_MOD(void *) keya, CCR_MOD(void *) keyb) {
+  if ((keya == NULL && keyb != NULL) ||
+      (keyb == NULL && keya != NULL))
+    return 0;
+
+  if (keya == NULL && keyb == NULL) return 1;
+
+  return ((pair4 *) keya)->x == ((pair4 *) keyb)->x &&
+    ((pair4 *) keya)->y == ((pair4 *) keyb)->y &&
+    ((pair4 *) keya)->z == ((pair4 *) keyb)->z &&
+    ((pair4 *) keya)->w == ((pair4 *) keyb)->w;
+}
+
+ht *
+new_ht2(UNUM size) { return new_ht(size, 2, pair2_hf, pair2_cf); }
+
+ht *
+new_ht3(UNUM size) { return new_ht(size, 2, pair3_hf, pair3_cf); }
+
+ht *
+new_ht4(UNUM size) { return new_ht(size, 2, pair4_hf, pair4_cf); }