From 4d02dcea167d7f45118510ff87217d590456c720 Mon Sep 17 00:00:00 2001 From: "@syxhe" Date: Mon, 24 Mar 2025 17:37:10 -0500 Subject: Rewrite the whole linked list implementation so it's not shit --- src/ll.c | 303 ++++++++++++++++++++++++++------------------------------------- 1 file changed, 126 insertions(+), 177 deletions(-) (limited to 'src/ll.c') diff --git a/src/ll.c b/src/ll.c index 4819226..4e018f2 100644 --- a/src/ll.c +++ b/src/ll.c @@ -7,199 +7,192 @@ typedef struct dll { void *data; - dlinkedlist_freecallback dfreecb; + dll_freecb freecb; struct dll *next; struct dll *prev; -} dllnode; -typedef struct dlinkedlist { +} dllnode; +typedef struct dlinked { + int size; dllnode *start; dllnode *end; - size_t size; + } dlinkedlist; -dllnode* dllnode_init(void *data, dlinkedlist_freecallback dfreecb) { + +dllnode* dllnode_init(void *data, dll_freecb fcb) { dllnode *n = xcalloc(1, sizeof(*n)); - n->next = NULL; - n->prev = NULL; n->data = data; - n->dfreecb = dfreecb; + n->freecb = fcb; + n->prev = NULL; + n->next = NULL; return n; } int dllnode_free(dllnode **n) { - if(!n) { - errno = EINVAL; - return -1; - } - if(!(*n)) { - errno = EINVAL; - return -1; - } + if(!n) + RETURNWERR(EINVAL, 1); + if(!(*n)) + RETURNWERR(EINVAL, 1); - if((*n)->dfreecb != NULL) - (*n)->dfreecb((*n)->data); + if((*n)->freecb != NULL) + (*n)->freecb((*n)->data); free(*n); *n = NULL; return 0; } -dlinkedlist * dlinkedlist_init(void) { +dlinkedlist* dlinkedlist_init(void) { dlinkedlist *ll = xcalloc(1, sizeof(*ll)); - - ll->start = NULL; ll->end = NULL; + ll->start = NULL; ll->size = 0; return ll; } int dlinkedlist_free(dlinkedlist **ll) { - if(!ll) { - errno = EINVAL; - return -1; - } - if(!(*ll)) { - errno = EINVAL; - return -1; - } - - dllnode *p = (*ll)->start, *n; - while(p != NULL) { - n = p->next; - dllnode_free(&p); - p = n; + if(!ll) + RETURNWERR(EINVAL, 1); + if(!(*ll)) + RETURNWERR(EINVAL, 1); + + for(dllnode *n; (*ll)->start != NULL;) { + n = (*ll)->start->next; + dllnode_free(&((*ll)->start)); + (*ll)->start = n; } - free(*ll); - (*ll) = NULL; + *ll = NULL; + return 0; } -int dlinkedlist_firstitem(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb) { - if(!ll) { - errno = EINVAL; - return -1; - } - if(ll->size != 0) - return 0; +int dlinkedlist_size(const dlinkedlist * const ll) { + if(!ll) + RETURNWERR(EINVAL, -1); + + return ll->size; +} - dllnode *n = dllnode_init(data, dfreecb); +int dlinkedlist_handlefirstnode(dlinkedlist * const ll, void *data, dll_freecb fcb) { + if(!ll) + RETURNWERR(EINVAL, 1); + if(ll->size > 0) + return 1; - ll->start = n; + // Need to handle adding the first element differently than other opers, so do it here + dllnode *n = dllnode_init(data, fcb); + // dllnode_init already sets n.prev and n.next to null, so no need to do so again + ll->end = n; + ll->start = n; ll->size = 1; - return 1; + return 0; } -int dlinkedlist_insert(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb) { - if(!ll) { - errno = EINVAL; - return -1; - } - if(dlinkedlist_firstitem(ll, data, dfreecb) > 0) +int dlinkedlist_xxxend(dlinkedlist * const ll, void *data, dll_freecb fcb, char op) { + if(!ll) + RETURNWERR(EINVAL, 1); + if(op != 'a' && op != 'p') + RETURNWERR(EINVAL, 1); + if(dlinkedlist_handlefirstnode(ll, data, fcb) == 0) return 0; - dllnode *n = dllnode_init(data, dfreecb); - n->prev = NULL; - n->next = ll->start; + dllnode *n = dllnode_init(data, fcb); + switch (op) { + case 'a': + n->prev = ll->end; + ll->end->next = n; + ll->end = n; + break; + + case 'p': + n->next = ll->start; + ll->start->prev = n; + ll->start = n; + break; + + default: + abort(); + } - ll->start->prev = n; - ll->start = n; ll->size++; - return 0; } -int dlinkedlist_append(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb) { - if(!ll) { - errno = EINVAL; - return -1; - } - if(dlinkedlist_firstitem(ll, data, dfreecb) > 0) - return 0; - - dllnode *n = dllnode_init(data, dfreecb); - n->prev = ll->end; - n->next = NULL; - - ll->end->next = n; - ll->end = n; - ll->size++; +int dlinkedlist_append(dlinkedlist * const ll, void *data, dll_freecb fcb) { + return dlinkedlist_xxxend(ll, data, fcb, 'a'); +} - return 0; +int dlinkedlist_prepend(dlinkedlist * const ll, void *data, dll_freecb fcb) { + return dlinkedlist_xxxend(ll, data, fcb, 'p'); } -dllnode *dlinkedlist_getnode(const dlinkedlist * const ll, size_t index) { - if(!ll) { - errno = EINVAL; - return NULL; - } - if(index >= ll->size) { - errno = EINVAL; - return NULL; - } +dllnode* dlinkedlist_getnode(const dlinkedlist * const ll, int index) { + if(!ll) + RETURNWERR(EINVAL, NULL); + if(index < 0 || index >= ll->size) + RETURNWERR(EINVAL, NULL); - // No need to loop if the desired indices are either the first or last if(index == 0) - return ll->start->data; + return ll->start; if(index == (ll->size - 1)) - return ll->end->data; + return ll->end; - int spoint = (index < (ll->size / 2)); + int spoint = (index <= (ll->size / 2)); dllnode *p = (spoint) ? ll->start : ll->end; - size_t i = (spoint) ? 0 : ll->size-1; + int i = (spoint) ? 0 : ll->size - 1; - // This should (theoretically) cut down on fetch times - for(; ((spoint) ? (i < index) : (i > index)) && p != NULL; ((spoint) ? i++ : i--), p = ((spoint) ? p->next : p->prev)); - - // old imp (above is untested) - // for(size_t i = 0; i < index && p != NULL; i++, p = p->next); + // This should (theoretically) be faster on average + for(; p != NULL && ((spoint) ? (i < index) : (i > index)); (spoint) ? i++ : i--, p = (spoint) ? p->next : p->prev); return p; } -void *dlinkedlist_get(const dlinkedlist * const ll, size_t index) { - dllnode *n = dlinkedlist_getnode(ll, index); - if(!n) - return NULL; +int dlinkedlist_insert(dlinkedlist * const ll, void *data, dll_freecb fcb, int index) { + if(!ll) + RETURNWERR(EINVAL, 1); + if(index < 0 || index >= ll->size) + RETURNWERR(EINVAL, 1); + + // Handle the special cases of appending or prepending + if(index == 0) + return dlinkedlist_prepend(ll, data, fcb); + if(index == (ll->size - 1)) + return dlinkedlist_append(ll, data, fcb); + + // Insert between 2 nodes + // If you're inserting at index 2, the new node becomes index 2, and the previous node at index 2 moves to index 3 - return n->data; -} + dllnode *new = dllnode_init(data, fcb); + dllnode *current = dlinkedlist_getnode(ll, index); + if(!current) + abort(); + + current->prev->next = new; + new->prev = current->prev; + new->next = current; + current->prev = new; -void *dlinkedlist_getfirst(const dlinkedlist * const ll) { - return dlinkedlist_get(ll, 0); + ll->size++; + return 0; } -void *dlinkedlist_getlast(const dlinkedlist * const ll) { - return dlinkedlist_get(ll, ll->size - 1); -} +int dlinkedlist_remove(dlinkedlist * const ll, int index) { + if(!ll) + RETURNWERR(EINVAL, 1); + if(index < 0 || index >= ll->size) + RETURNWERR(EINVAL, 2); -int dlinkedlist_remove(dlinkedlist * const ll, size_t index) { - if(!ll) { - errno = EINVAL; - return -1; - } - if(index >= ll->size) { - errno = EINVAL; - return -1; - } - dllnode *current = dlinkedlist_getnode(ll, index); - if(!current) { - /* gcc is halucinating an error where there isn't one, claiming that the size of the linked list could, somehow, magically - // grow in the time it takes to grab the desired node, and thus return NULL and cause a NULL Dereference. I am willing to - // be humble and state that the compiler is probably smarter than me, and there is MAYBE an edge case where is COULD occur, - // and thus I should do this check, but I'm unconvinced */ - errno = ENOTRECOVERABLE; - return -2; - } - - // Handle special cases of removing the start or end + if(!current) + abort(); + if(index == 0) { ll->start = current->next; ll->start->prev = NULL; @@ -207,13 +200,9 @@ int dlinkedlist_remove(dlinkedlist * const ll, size_t index) { ll->end = current->prev; ll->end->next = NULL; } else { - // Set the prior's next to the next, set the next's prior to the prior, delete the current one - dllnode *prev = current->prev; - dllnode *next = current->next; - prev->next = next; - next->prev = prev; + current->prev->next = current->next; + current->next->prev = current->prev; } - // Wow, I genuinely can't think of the last time I've needed to use an if-elif-else block dllnode_free(¤t); ll->size--; @@ -221,50 +210,10 @@ int dlinkedlist_remove(dlinkedlist * const ll, size_t index) { return 0; } -size_t dlinkedlist_size(const dlinkedlist * const ll) { - if(!ll) - RETURNWERR(EINVAL, -1); - - return ll->size; -} - -int dlinkedlist_isempty(const dlinkedlist * const ll) { - if(!ll) - RETURNWERR(EINVAL, -1); - - return (ll->size == 0); -} - - - - -// Sample code -#define COMPILE_SAMPLE -#ifdef COMPILE_SAMPLE - -#include -#include - -int genfree(void *data) { - free(data); - return 0; -} - -int main() { - dlinkedlist *dll = dlinkedlist_init(); - dlinkedlist_append(dll, (void*)strdup("THIS"), genfree); - dlinkedlist_append(dll, (void*)strdup("IS"), genfree); - dlinkedlist_append(dll, (void*)strdup("A"), genfree); - dlinkedlist_append(dll, (void*)strdup("STRING"), genfree); - - // This is crashing as of right now - char *retval; - for(int i = 0; i < dlinkedlist_size(dll); i++) - printf("%s ", (((retval = (char*)dlinkedlist_get(dll, i)) != NULL) ? retval : "null") ); - printf("\n"); - - dlinkedlist_free(&dll); +void* dlinkedlist_get(const dlinkedlist * const ll, int index) { + dllnode *n = dlinkedlist_getnode(ll, index); + if(!n) + return NULL; - return 0; -} -#endif \ No newline at end of file + return n->data; +} \ No newline at end of file -- cgit v1.2.3