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.

1 files changed, 36 insertions, 0 deletions

diff --git a/src/splist.h b/src/splist.h
new file mode 100644
index 0000000..e6be624
--- /dev/null
+++ b/src/splist.h
@@ -0,0 +1,36 @@
+#ifndef SPLIST_H
+#define SPLIST_H
+#include "util.h"
+#include "list.h"
+
+/* A sparse list is a list with its "inverse list".  This can be used
+   to determine if a number belongs to a sparse list at constant
+   time. */
+
+typedef struct splist_s splist;
+
+splist *new_splist();
+
+/* A sparse list is of fixed size. */
+unsigned char init_splist(splist *s, NUM size);
+
+P_ATTR NUM splist_len(CCR_MOD(splist *) s);
+
+/* NOTE: The returned list is owned by the original splist, so don't
+   destroy that list or do anything that should not be done. */
+P_ATTR List *splist_ls(CCR_MOD(splist *) s);
+
+/* We assume that elements of a sparse list are of type NUM. */
+unsigned char add_to_splist(splist *s, NUM element);
+
+/* resetting a sparse list means to set its length to 0 */
+void reset_splist(splist *s);
+
+/* Constant time operation */
+unsigned char splist_is_member(splist *s, NUM element);
+
+void print_splist(splist *s);
+
+void destroy_splist(splist *s);
+
+#endif