From 510b10b96b546fcc6c6b6be85050305ddd192a41 Mon Sep 17 00:00:00 2001 From: JSDurand 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.h | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100644 src/splist.h (limited to 'src/splist.h') 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 -- cgit v1.2.3-18-g5258