diff options
author | JSDurand <mmemmew@gmail.com> | 2022-02-05 17:30:11 +0800 |
---|---|---|
committer | JSDurand <mmemmew@gmail.com> | 2022-02-05 17:30:11 +0800 |
commit | 510b10b96b546fcc6c6b6be85050305ddd192a41 (patch) | |
tree | 997d6c3f2c0a1ad6e27127d54a94655527e57864 /src/splist.c | |
parent | 3fb5430080199a6d92a63f8259fe4a88df9b83ba (diff) |
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.
Diffstat (limited to 'src/splist.c')
-rw-r--r-- | src/splist.c | 141 |
1 files changed, 141 insertions, 0 deletions
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); +} |