1 files changed, 176 insertions, 66 deletions

diff --git a/src/ht.c b/src/ht.c
index c44a57e..2fc1206 100644
--- a/src/ht.c
+++ b/src/ht.c
@@ -1,20 +1,73 @@
+#include <stdarg.h>
 #include <string.h>
 #include <stdio.h>
 #include "ht.h"
 
 #define HT_REHASH_THRESHOLD 0.5
 
+P_ATTR
+static NUM
+num_hft(CCR_MOD(void *) key)
+{
+  if (key == NULL) {
+    fleprintf0("Got NULL key!\n");
+    return 0;
+  }
+
+  return *((NUM *) key);
+}
+
+P_ATTR
+static BOOL
+num_cft(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 *((NUM *) keya) == *((NUM *) keyb);
+}
+
 /* SIZE is a hint to the number of elements that might be put in the
    table.  In fact we will allocate more memory than this number, as a
-   hash table works better if it is not fully used. */
+   hash table works better if it is not fully used.
+
+   NARGS is the number of arguments to follow.  It should be between 0
+   and 2 (inclusive).  If there are more than one argument, the first
+   argument is used as the hashing function; if there are two
+   arguments, the second argument is used as the comparison
+   function. */
 ht *
-new_ht(UNUM size)
+new_ht(UNUM size, int nargs, ...)
 {
+
+  if (nargs < 0 || nargs > 2) {
+    fleprintf("NARGS should be between zero and two, but got %d\n",
+              nargs);
+    return NULL;
+  }
+
+  hash_func_t hft = num_hft;
+  compare_func_t cft = num_cft;
+
+  va_list args;
+
+  if (nargs) {
+    va_start(args, nargs);
+    if (nargs >= 1) hft = va_arg(args, hash_func_t);
+    if (nargs == 2) cft = va_arg(args, compare_func_t);
+    va_end(args);
+  }
+
   ht *htp = NULL;
   SAFE_MALLOC(ht, htp, 1, return NULL;);
 
   htp->capability = (size<<1)+(size>>1);
   htp->size = 0;
+  htp->hf = hft;
+  htp->cf = cft;
 
   /* For safer clean up */
   htp->keys = NULL;
@@ -47,13 +100,43 @@ void
 destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag)
 {
   switch (flag) {
+  case DESTROY_KEY_SELF:
+  case DESTROY_KEY_NO_SELF:
+  case DESTROY_EVERY_SELF:
   case DESTROY_EVERY_NO_SELF:
+  case DESTROY_KEY_VALUE_FIRST_SELF:
+  case DESTROY_KEY_VALUE_FIRST_NO_SELF:
+    for (NUM i = 0; i < htp->size;)
+      free(*(htp->keys+i++));
+    break;
+  case DESTROY_KEY_FIRST_SELF:
+  case DESTROY_KEY_FIRST_NO_SELF:
+  case DESTROY_EVERY_FIRST_SELF:
+  case DESTROY_EVERY_FIRST_NO_SELF:
+  case DESTROY_KEY_FIRST_VALUE_SELF:
+  case DESTROY_KEY_FIRST_VALUE_NO_SELF:
+    free(*(htp->keys));
+    break;
+  default:
+    break;
+  }
+
+  switch (flag) {
+  case DESTROY_VALUE_SELF:
+  case DESTROY_VALUE_NO_SELF:
   case DESTROY_EVERY_SELF:
+  case DESTROY_EVERY_NO_SELF:
+  case DESTROY_KEY_FIRST_VALUE_SELF:
+  case DESTROY_KEY_FIRST_VALUE_NO_SELF:
     for (NUM i = 0; i < htp->size;)
       free(*(htp->values+i++));
     break;
-  case DESTROY_FIRST_NO_SELF:
-  case DESTROY_FIRST_SELF:
+  case DESTROY_VALUE_FIRST_SELF:
+  case DESTROY_VALUE_FIRST_NO_SELF:
+  case DESTROY_EVERY_FIRST_SELF:
+  case DESTROY_EVERY_FIRST_NO_SELF:
+  case DESTROY_KEY_VALUE_FIRST_SELF:
+  case DESTROY_KEY_VALUE_FIRST_NO_SELF:
     free(*(htp->values));
     break;
   default:
@@ -68,8 +151,14 @@ destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag)
 
   switch (flag) {
   case DESTROY_NONE_SELF:
+  case DESTROY_KEY_SELF:
+  case DESTROY_KEY_FIRST_SELF:
+  case DESTROY_VALUE_SELF:
+  case DESTROY_VALUE_FIRST_SELF:
   case DESTROY_EVERY_SELF:
-  case DESTROY_FIRST_SELF:
+  case DESTROY_EVERY_FIRST_SELF:
+  case DESTROY_KEY_FIRST_VALUE_SELF:
+  case DESTROY_KEY_VALUE_FIRST_SELF:
     free(htp);
     break;
   default:
@@ -81,22 +170,22 @@ static BOOL
 ht_expand(ht *htp)
 {
   htp->capability <<= 1;
-  htp->capability++;
 
-  NUM *keys = NULL, size = htp->size;
+  void **keys = NULL;
+  NUM size = htp->size;
   void **values = NULL;
 
   if (size) {
-    SAFE_MALLOC(NUM, keys, size, goto cleanup;);
-    SAFE_MALLOC(NUM, values, size, goto cleanup;);
+    SAFE_MALLOC(void*, keys, size, goto cleanup;);
+    SAFE_MALLOC(void*, values, size, goto cleanup;);
 
-    memcpy(keys, htp->keys, sizeof(NUM) * size);
+    memcpy(keys, htp->keys, sizeof(void*) * size);
     memcpy(values, htp->values, sizeof(void*) * size);
   }
 
-  SAFE_REALLOC(NUM, htp->keys, htp->capability, goto cleanup;);
+  SAFE_REALLOC(void*, htp->keys, htp->capability, goto cleanup;);
 
-  memset(htp->keys, 0xff, sizeof (NUM) * htp->capability);
+  memset(htp->keys, 0, sizeof (void*) * htp->capability);
 
   SAFE_REALLOC(void*, htp->values, htp->capability, goto cleanup;);
 
@@ -122,8 +211,46 @@ ht_expand(ht *htp)
   return 1;
 }
 
+#define PERTURBATION_SHIFT 5
+
+/* On error return non-zero. */
+static BOOL
+ht_probe(CC_MOD(ht *) htp, CC_MOD(void *) key, NUM *result)
+{
+  NUM hashed = htp->hf(key);
+  NUM ikey = hashed % htp->capability;
+  unsigned long perturbation = hashed - ikey;
+
+  for (NUM count = 0;
+       count < htp->capability * HT_REHASH_THRESHOLD &&
+       *(htp->indices+ikey) >= 0 &&
+         /* continue if keys don't match */
+         !(htp->cf
+           (*(htp->keys+*(htp->indices+ikey)), key));
+       count++) {
+    ikey = 5 * ikey + 1 + perturbation;
+    perturbation >>= PERTURBATION_SHIFT;
+    ikey %= htp->capability;
+  }
+
+  if (*(htp->indices+ikey) >= 0 &&
+      !(htp->cf(*(htp->keys+*(htp->indices+ikey)), key))) {
+    /* failed for some reason */
+    fleprintf("Fail to probe a location for the key, ikey = %ld, "
+              "last index = %ld\n", ikey, *(htp->indices+ikey));
+    return 1;
+  }
+
+  *result = ikey;
+
+  /* if (*((NUM*) key) == 3) {
+   *   fleprintf("ikey = %ld, result = %ld\n", ikey, *result);
+   * } */
+  return 0;
+}
+
 BOOL
-ht_insert(ht *htp, NUM key, void *value)
+ht_insert(ht * const restrict htp, void *key, void *value)
 {
   if (htp->size+1 >= HT_REHASH_THRESHOLD * htp->capability) {
     if (ht_expand(htp)) {
@@ -132,15 +259,10 @@ ht_insert(ht *htp, NUM key, void *value)
     }
   }
 
-  NUM ikey = key % htp->capability;
+  NUM ikey = 0;
 
-  /* linear probing */
-  for (NUM count = 0;
-       count < htp->capability * HT_REHASH_THRESHOLD &&
-         *(htp->indices+ikey) >= 0 &&
-         *(htp->keys+*(htp->indices+ikey)) != key;
-       count++)
-    ikey = (ikey + 1) % htp->capability;
+  /* check errors */
+  if (ht_probe(htp, key, &ikey)) return 1;
 
   if (*(htp->indices+ikey) < 0) {
     /* not inserted before */
@@ -151,15 +273,9 @@ ht_insert(ht *htp, NUM key, void *value)
     *(htp->values+htp->size) = value;
 
     (htp->size)++;
-  } else if (*(htp->keys+*(htp->indices+ikey)) == key) {
-    *(htp->values+*(htp->indices+ikey)) = value;
   } else {
-    fleprintf("Fail to probe an appropriate slot for %ld, "
-              "the result ikey = %ld, last index = %ld, "
-              "last key = %ld\n",
-              key, ikey, *(htp->keys+*(htp->indices+ikey)),
-              *(htp->indices+ikey));
-    return 1;
+    /* error check is performed in ht_probe */
+    *(htp->values+*(htp->indices+ikey)) = value;
   }
 
   /* fleprintf("ikey = %ld, size = %d, capability = %llu\n",
@@ -169,33 +285,39 @@ ht_insert(ht *htp, NUM key, void *value)
 }
 
 BOOL
-ht_delete(ht * const restrict htp, NUM key, int flag)
+ht_delete(ht * const restrict htp, void *key, HT_DELETE_FLAG flag)
 {
-  NUM ikey = key % htp->capability;
+  NUM ikey = 0;
 
-  /* linear probing */
-  for (NUM count = 0;
-       count < htp->capability * HT_REHASH_THRESHOLD &&
-         *(htp->indices+ikey) > 0 &&
-         *(htp->keys+*(htp->indices+ikey)) != key;
-       count++)
-    ikey = (ikey + 1) % htp->capability;
+  /* check errors */
+  if (ht_probe(htp, key, &ikey)) return 1;
 
   if (*(htp->indices+ikey) < 0) {
     /* not inserted before */
-  } else if (*(htp->keys+*(htp->indices+ikey)) == key) {
+  } else {
     (htp->size)--;
-    *(htp->keys+*(htp->indices+ikey)) = -1;
-    if (flag) {
+
+    switch (flag) {
+    case DELETE_KEY:
+    case DELETE_EVERY:
+      free(*(htp->keys+*(htp->indices+ikey)));
+      break;
+    default:
+      break;
+    }
+
+    switch (flag) {
+    case DELETE_VALUE:
+    case DELETE_EVERY:
       free(*(htp->values+*(htp->indices+ikey)));
-      *(htp->values+*(htp->indices+ikey)) = NULL;
+      break;
+    default:
+      break;
     }
+
+    *(htp->values+*(htp->indices+ikey)) = NULL;
+    *(htp->keys+*(htp->indices+ikey)) = NULL;
     *(htp->indices+ikey) = -1;
-  } else {
-    fleprintf("Fail to probe an appropriate slot for %ld, "
-              "the result ikey = %ld\n",
-              key, ikey);
-    return 1;
   }
 
   return 0;
@@ -203,28 +325,16 @@ ht_delete(ht * const restrict htp, NUM key, int flag)
 
 P_ATTR
 void *
-ht_find(CCR_MOD(ht *) htp, NUM key)
+ht_find(CCR_MOD(ht *) htp, void *key)
 {
-  NUM ikey = key % htp->capability;
+  NUM ikey = 0;
 
-  /* linear probing */
-  for (NUM count = 0;
-       count < htp->capability * HT_REHASH_THRESHOLD &&
-         *(htp->indices+ikey) >= 0 &&
-         *(htp->keys+*(htp->indices+ikey)) != key;
-       count++)
-    ikey = (ikey + 1) % htp->capability;
+  /* check errors */
+  if (ht_probe(htp, key, &ikey)) return NULL;
 
-  if (*(htp->indices+ikey) >= 0 &&
-      *(htp->keys+*(htp->indices+ikey)) == key)
-    return *(htp->values+*(htp->indices+ikey));
-  else if (*(htp->indices+ikey) >= 0 &&
-           *(htp->keys+*(htp->indices+ikey)) >= 0)
-    fleprintf("Fail to probe an appropriate slot for %ld, "
-              "with the result ikey = %ld\n",
-              key, ikey);
+  if (*(htp->indices+ikey) < 0) return NULL;
 
-  return NULL;
+  return *(htp->values+*(htp->indices+ikey));
 }
 
 P_ATTR
@@ -242,7 +352,7 @@ ht_values(CCR_MOD(ht *) htp)
 }
 
 P_ATTR
-NUM *
+void **
 ht_keys(CCR_MOD(ht *) htp)
 {
   return htp->keys;