Implement a simple hash table.

It is a very basic and simple hash table.  It is so simple that I
hesitate to call it a hash table.  Anyways, I think it suffices for my
purposes here.

* Makefile.am: Add necessary files.

* grammar.c (new_tnt_string): Formatting.

* ht.c (new_ht): Constructor

(destroy_ht): Destructor

(ht_expand): Rehash

(ht_insert, ht_delete, ht_find): Main functions.

* list.c (add_to_list, list_assure_size): Modify the use of realloc.

* test/check_ht.c: Ensure this is working correctly.

* util.c (read_entire_file): Modify the use of realloc.

1 files changed, 201 insertions, 0 deletions

diff --git a/src/ht.c b/src/ht.c
new file mode 100644
index 0000000..923eca7
--- /dev/null
+++ b/src/ht.c
@@ -0,0 +1,201 @@
+#include <string.h>
+#include <stdio.h>
+#include "ht.h"
+
+#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;
+  }
+
+  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;
+  }
+
+  htp->values = MYALLOC(void*, htp->capability);
+
+  if (htp->values == NULL) {
+    fleprintf0("Fail to malloc\n");
+    free(htp->keys);
+    free(htp);
+    return NULL;
+  }
+
+  /* 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);
+
+  return htp;
+}
+
+void
+destroy_ht(ht * restrict htp, int flag)
+{
+  switch (flag) {
+  case 1:
+    for (UNUM i = 0; i < htp->capability;)
+      free(*(htp->values+i++));
+    break;
+  case 2:
+    free(*(htp->values));
+    break;
+  default:
+    break;
+  }
+
+  free(htp->values);
+
+  free(htp->keys);
+
+  free(htp);
+}
+
+static BOOL
+ht_expand(ht *htp)
+{
+  NUM oldcap = htp->capability;
+  htp->capability <<= 1;
+  htp->capability++;
+
+  NUM *newkeys = realloc(htp->keys, htp->capability);
+
+  if (newkeys == NULL) {
+    fleprintf0("Fail to realloc\n");
+    return 1;
+  }
+
+  htp->keys = newkeys;
+
+  memset(htp->keys+oldcap, 0xff,
+         sizeof (NUM) * (htp->capability - oldcap));
+
+  void **newvalues = realloc(htp->values, htp->capability);
+
+  if (newvalues == NULL) {
+    fleprintf0("Fail to realloc\n");
+    return 1;
+  }
+
+  htp->values = newvalues;
+
+  memset(htp->values+oldcap, 0,
+         sizeof(NUM) * (htp->capability - oldcap));
+
+  return 0;
+}
+
+BOOL
+ht_insert(ht *htp, NUM key, void *value)
+{
+  if (htp->size+1 >= HT_REHASH_THRESHOLD * htp->capability)
+    ht_expand(htp);
+
+  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;
+       count++)
+    ikey = (ikey + 1) % htp->capability;
+
+  if (*(htp->keys+ikey) < 0) {
+    /* not inserted before */
+    *(htp->keys+ikey) = key;
+    *(htp->values+ikey) = value;
+    (htp->size)++;
+  } else if (*(htp->keys+ikey) == key) {
+    *(htp->values+ikey) = value;
+  } else {
+    fleprintf("Fail to probe an appropriate slot for %ld, "
+              "the result ikey = %ld\n",
+              key, ikey);
+    return 1;
+  }
+
+  /* fleprintf("ikey = %ld, size = %d, capability = %llu\n",
+   *           ikey, htp->size, htp->capability); */
+
+  return 0;
+}
+
+BOOL
+ht_delete(ht * const restrict htp, NUM key, int flag)
+{
+  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;
+       count++)
+    ikey = (ikey + 1) % htp->capability;
+
+  if (*(htp->keys+ikey) < 0) {
+    /* not inserted before */
+    return 0;
+  } else if (*(htp->keys+ikey) == key) {
+    (htp->size)--;
+    *(htp->keys+ikey) = -1;
+    if (flag) {
+      free(*(htp->values+ikey));
+      *(htp->values+ikey) = NULL;
+    }
+    return 0;
+  } else {
+    fleprintf("Fail to probe an appropriate slot for %ld, "
+              "the result ikey = %ld\n",
+              key, ikey);
+    return 1;
+  }
+
+  return 0;
+}
+
+void *
+ht_find(ht * const restrict 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;
+       count++)
+    ikey = (ikey + 1) % htp->capability;
+
+  if (*(htp->keys+ikey) == key)
+    return *(htp->values+ikey);
+  else if (*(htp->keys+ikey) > 0)
+    fleprintf("Fail to probe an appropriate slot for %ld, "
+              "with the result ikey = %ld\n",
+              key, ikey);
+
+  return NULL;
+}