From 510b10b96b546fcc6c6b6be85050305ddd192a41 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Sat, 5 Feb 2022 17:30:11 +0800
Subject: replace some hash table usage by tuples

Previously I used hash tables, which consume too much memory.  Now the
critical parts are replaced by a new hand-written library called
"tuple.h".  Now we can easily parse larger inputs.  I haven't tested
its limits, though.
---
 src/splist.c | 141 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 141 insertions(+)
 create mode 100644 src/splist.c

(limited to 'src/splist.c')

diff --git a/src/splist.c b/src/splist.c
new file mode 100644
index 0000000..c990bfa
--- /dev/null
+++ b/src/splist.c
@@ -0,0 +1,141 @@
+#include "splist.h"
+#include "list.h"
+#include <stdio.h>
+
+struct splist_s {
+  List *ls;                     /* a list */
+  List *inv;                    /* and its inverse */
+  NUM len;                      /* how many elements are stored */
+};
+
+splist *
+new_splist()
+{
+  splist *result = MYALLOC(splist, 1);
+
+  if (result == NULL) return NULL;
+
+  result->ls = new_list();
+
+  if (result->ls == NULL) {
+    free(result);
+    return NULL;
+  }
+
+  result->inv = new_list();
+
+  if (result->inv == NULL) {
+    destroy_list(result->ls, 0);
+    free(result);
+    return NULL;
+  }
+
+  result->len = 0;
+
+  return result;
+}
+
+unsigned char
+init_splist(splist *s, NUM size)
+{
+  unsigned char result = 0;
+
+  result = list_assure_size(s->ls, size);
+
+  if (result) return result;
+
+  result = list_set_length(s->ls, size);
+
+  if (result) return result;
+
+  result = list_assure_size(s->inv, size);
+
+  if (result) return result;
+
+  result = list_set_length(s->inv, size);
+
+  return result;
+}
+
+P_ATTR
+NUM
+splist_len(CCR_MOD(splist *)s)
+{
+  return s->len;
+}
+
+P_ATTR
+List *
+splist_ls(CCR_MOD(splist *) s)
+{
+  return s->ls;
+}
+
+H_ATTR
+void
+reset_splist(splist *s)
+{
+  s->len = 0;
+}
+
+H_ATTR
+unsigned char
+add_to_splist(splist *s, NUM element)
+{
+  if (s->len >= list_length(s->ls)) {
+    fleprintf0("The length of the sparse list exceeds its size!\n");
+    print_splist(s);
+    return 1;
+  }
+
+  NUM *index_pointer = list_nth(s->ls, s->len);
+
+  *index_pointer = element;
+
+  NUM *element_pointer = list_nth(s->inv, element);
+  *element_pointer = s->len;
+
+  s->len += 1;
+
+  return 0;
+}
+
+H_ATTR
+unsigned char
+splist_is_member(splist *s, NUM element)
+{
+  NUM *index = list_nth(s->inv, element);
+
+  if (*index < 0 || *index >= s->len)
+    return 0;
+
+  NUM *element_pointer = list_nth(s->ls, *index);
+
+  return *element_pointer == element;
+}
+
+void
+print_splist(splist *s)
+{
+  printf("Printing a sparse list with size %lu:\n",
+         list_length(s->ls));
+
+  for (NUM i = 0; i < list_length(s->ls); i++) {
+    NUM *pointer = list_nth(s->ls, i);
+    printf("%ld, \t", *pointer);
+
+    pointer = list_nth(s->inv, i);
+    printf("%ld\n", *pointer);
+  }
+
+  printf("Printing terminated\n");
+}
+
+void
+destroy_splist(splist *s)
+{
+  destroy_list(s->ls, 2);
+  destroy_list(s->inv, 2);
+
+  free(s);
+}
-- 
cgit v1.2.3-18-g5258