1 files changed, 123 insertions, 75 deletions

diff --git a/src/ht.c b/src/ht.c
index 923eca7..c44a57e 100644
--- a/src/ht.c
+++ b/src/ht.c
@@ -4,62 +4,56 @@
 
 #define HT_REHASH_THRESHOLD 0.5
 
-struct ht_s {
-  NUM *keys;
-  void **values;
-  UNUM capability;
-  /* REVIEW: What is the purpose of SIZE? */
-  int size;
-};
-
 /* 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. */
 ht *
 new_ht(UNUM size)
 {
-  ht *htp = MYALLOC(ht, 1);
-
-  if (htp == NULL) {
-    fleprintf0("Fail to malloc\n");
-    return NULL;
-  }
+  ht *htp = NULL;
+  SAFE_MALLOC(ht, htp, 1, return NULL;);
 
   htp->capability = (size<<1)+(size>>1);
   htp->size = 0;
-  htp->keys = MYALLOC(NUM, htp->capability);
 
-  if (htp->keys == NULL) {
-    fleprintf0("Fail to malloc\n");
-    free(htp);
-    return NULL;
-  }
+  /* For safer clean up */
+  htp->keys = NULL;
+  htp->values = NULL;
+  htp->indices = NULL;
 
-  htp->values = MYALLOC(void*, htp->capability);
+  SAFE_MALLOC(NUM, htp->keys, htp->capability, goto cleanup;);
 
-  if (htp->values == NULL) {
-    fleprintf0("Fail to malloc\n");
-    free(htp->keys);
-    free(htp);
-    return NULL;
-  }
+  SAFE_MALLOC(void*, htp->values, htp->capability, goto cleanup;);
+
+  SAFE_MALLOC(NUM, htp->indices, htp->capability, goto cleanup;);
 
   /* Initialize the keys to be -1 and the values to be NULL */
   memset(htp->keys, 0xff, sizeof (NUM) * htp->capability);
-  memset(htp->values, 0, sizeof (NUM) * htp->capability);
+  memset(htp->values, 0, sizeof (void*) * htp->capability);
+  /* Initialize indices to be -1 */
+  memset(htp->indices, 0xff, sizeof (NUM) * htp->capability);
 
   return htp;
+
+ cleanup:
+  if (htp->keys) free(htp->keys);
+  if (htp->values) free(htp->values);
+  if (htp->indices) free(htp->indices);
+  free(htp);
+  return NULL;
 }
 
 void
-destroy_ht(ht * restrict htp, int flag)
+destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag)
 {
   switch (flag) {
-  case 1:
-    for (UNUM i = 0; i < htp->capability;)
+  case DESTROY_EVERY_NO_SELF:
+  case DESTROY_EVERY_SELF:
+    for (NUM i = 0; i < htp->size;)
       free(*(htp->values+i++));
     break;
-  case 2:
+  case DESTROY_FIRST_NO_SELF:
+  case DESTROY_FIRST_SELF:
     free(*(htp->values));
     break;
   default:
@@ -70,70 +64,101 @@ destroy_ht(ht * restrict htp, int flag)
 
   free(htp->keys);
 
-  free(htp);
+  free(htp->indices);
+
+  switch (flag) {
+  case DESTROY_NONE_SELF:
+  case DESTROY_EVERY_SELF:
+  case DESTROY_FIRST_SELF:
+    free(htp);
+    break;
+  default:
+    break;
+  }
 }
 
 static BOOL
 ht_expand(ht *htp)
 {
-  NUM oldcap = htp->capability;
   htp->capability <<= 1;
   htp->capability++;
 
-  NUM *newkeys = realloc(htp->keys, htp->capability);
+  NUM *keys = NULL, size = htp->size;
+  void **values = NULL;
 
-  if (newkeys == NULL) {
-    fleprintf0("Fail to realloc\n");
-    return 1;
+  if (size) {
+    SAFE_MALLOC(NUM, keys, size, goto cleanup;);
+    SAFE_MALLOC(NUM, values, size, goto cleanup;);
+
+    memcpy(keys, htp->keys, sizeof(NUM) * size);
+    memcpy(values, htp->values, sizeof(void*) * size);
   }
 
-  htp->keys = newkeys;
+  SAFE_REALLOC(NUM, htp->keys, htp->capability, goto cleanup;);
+
+  memset(htp->keys, 0xff, sizeof (NUM) * htp->capability);
 
-  memset(htp->keys+oldcap, 0xff,
-         sizeof (NUM) * (htp->capability - oldcap));
+  SAFE_REALLOC(void*, htp->values, htp->capability, goto cleanup;);
 
-  void **newvalues = realloc(htp->values, htp->capability);
+  memset(htp->values, 0, sizeof(void*) * htp->capability);
 
-  if (newvalues == NULL) {
-    fleprintf0("Fail to realloc\n");
-    return 1;
-  }
+  SAFE_REALLOC(NUM, htp->indices, htp->capability, goto cleanup;);
+
+  memset(htp->indices, 0xff, sizeof (NUM) * htp->capability);
+
+  htp->size = 0;
 
-  htp->values = newvalues;
+  for (NUM i = 0; i < size; i++)
+    ht_insert(htp, *(keys+i), *(values+i));
 
-  memset(htp->values+oldcap, 0,
-         sizeof(NUM) * (htp->capability - oldcap));
+  if (keys) free(keys);
+  if (values) free(values);
 
   return 0;
+
+ cleanup:
+  if (keys) free(keys);
+  if (values) free(values);
+  return 1;
 }
 
 BOOL
 ht_insert(ht *htp, NUM key, void *value)
 {
-  if (htp->size+1 >= HT_REHASH_THRESHOLD * htp->capability)
-    ht_expand(htp);
+  if (htp->size+1 >= HT_REHASH_THRESHOLD * htp->capability) {
+    if (ht_expand(htp)) {
+      fleprintf0("Fail to expand\n");
+      return 1;
+    }
+  }
 
   NUM ikey = key % htp->capability;
 
   /* linear probing */
   for (NUM count = 0;
        count < htp->capability * HT_REHASH_THRESHOLD &&
-         *(htp->keys+ikey) > 0 &&
-         *(htp->keys+ikey) != key;
+         *(htp->indices+ikey) >= 0 &&
+         *(htp->keys+*(htp->indices+ikey)) != key;
        count++)
     ikey = (ikey + 1) % htp->capability;
 
-  if (*(htp->keys+ikey) < 0) {
+  if (*(htp->indices+ikey) < 0) {
     /* not inserted before */
-    *(htp->keys+ikey) = key;
-    *(htp->values+ikey) = value;
+    *(htp->indices+ikey) = htp->size;
+
+    /* Store the key and the value in the array. */
+    *(htp->keys+htp->size) = key;
+    *(htp->values+htp->size) = value;
+
     (htp->size)++;
-  } else if (*(htp->keys+ikey) == key) {
-    *(htp->values+ikey) = value;
+  } 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\n",
-              key, ikey);
+              "the result ikey = %ld, last index = %ld, "
+              "last key = %ld\n",
+              key, ikey, *(htp->keys+*(htp->indices+ikey)),
+              *(htp->indices+ikey));
     return 1;
   }
 
@@ -151,22 +176,21 @@ ht_delete(ht * const restrict htp, NUM key, int flag)
   /* linear probing */
   for (NUM count = 0;
        count < htp->capability * HT_REHASH_THRESHOLD &&
-         *(htp->keys+ikey) > 0 &&
-         *(htp->keys+ikey) != key;
+         *(htp->indices+ikey) > 0 &&
+         *(htp->keys+*(htp->indices+ikey)) != key;
        count++)
     ikey = (ikey + 1) % htp->capability;
 
-  if (*(htp->keys+ikey) < 0) {
+  if (*(htp->indices+ikey) < 0) {
     /* not inserted before */
-    return 0;
-  } else if (*(htp->keys+ikey) == key) {
+  } else if (*(htp->keys+*(htp->indices+ikey)) == key) {
     (htp->size)--;
-    *(htp->keys+ikey) = -1;
+    *(htp->keys+*(htp->indices+ikey)) = -1;
     if (flag) {
-      free(*(htp->values+ikey));
-      *(htp->values+ikey) = NULL;
+      free(*(htp->values+*(htp->indices+ikey)));
+      *(htp->values+*(htp->indices+ikey)) = NULL;
     }
-    return 0;
+    *(htp->indices+ikey) = -1;
   } else {
     fleprintf("Fail to probe an appropriate slot for %ld, "
               "the result ikey = %ld\n",
@@ -177,25 +201,49 @@ ht_delete(ht * const restrict htp, NUM key, int flag)
   return 0;
 }
 
+P_ATTR
 void *
-ht_find(ht * const restrict htp, NUM key)
+ht_find(CCR_MOD(ht *) htp, NUM key)
 {
   NUM ikey = key % htp->capability;
 
   /* linear probing */
   for (NUM count = 0;
        count < htp->capability * HT_REHASH_THRESHOLD &&
-         *(htp->keys+ikey) > 0 &&
-         *(htp->keys+ikey) != key;
+         *(htp->indices+ikey) >= 0 &&
+         *(htp->keys+*(htp->indices+ikey)) != key;
        count++)
     ikey = (ikey + 1) % htp->capability;
 
-  if (*(htp->keys+ikey) == key)
-    return *(htp->values+ikey);
-  else if (*(htp->keys+ikey) > 0)
+  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);
 
   return NULL;
 }
+
+P_ATTR
+NUM
+ht_size(CCR_MOD(ht *) htp)
+{
+  return (NUM) htp->size;
+}
+
+P_ATTR
+void **
+ht_values(CCR_MOD(ht *) htp)
+{
+  return htp->values;
+}
+
+P_ATTR
+NUM *
+ht_keys(CCR_MOD(ht *) htp)
+{
+  return htp->keys;
+}