From 7083f1d8f72d4e45a82fd40cd4822356429f0e23 Mon Sep 17 00:00:00 2001 From: "@syxhe" Date: Mon, 24 Mar 2025 15:02:03 -0500 Subject: Refactor a bunch of the linked list implementation --- src/ll.c | 166 +++++++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 140 insertions(+), 26 deletions(-) (limited to 'src/ll.c') diff --git a/src/ll.c b/src/ll.c index b42f631..ae62e89 100644 --- a/src/ll.c +++ b/src/ll.c @@ -3,6 +3,49 @@ #include #include +#include + +typedef struct dll { + void *data; + dlinkedlist_freecallback dfreecb; + + struct dll *next; + struct dll *prev; +} dllnode; + +typedef struct dlinkedlist { + dllnode *start; + dllnode *end; + size_t size; +} dlinkedlist; + +dllnode* dllnode_init(void *data, dlinkedlist_freecallback dfreecb) { + dllnode *n = xcalloc(1, sizeof(*n)); + n->next = NULL; + n->prev = NULL; + n->data = data; + n->dfreecb = dfreecb; + + return n; +} + +int dllnode_free(dllnode **n) { + if(!n) { + errno = EINVAL; + return -1; + } + if(!(*n)) { + errno = EINVAL; + return -1; + } + + if((*n)->dfreecb != NULL) + (*n)->dfreecb((*n)->data); + free(*n); + *n = NULL; + + return 0; +} void dlinkedlist_init(dlinkedlist **ll) { (*ll) = xcalloc(1, sizeof(**ll)); @@ -18,11 +61,7 @@ void dlinkedlist_free(dlinkedlist **ll) { dllnode *p = (*ll)->start, *n; while(p != NULL) { n = p->next; - - if(p->dfreecb != NULL) - p->dfreecb(p->data); - free(p); - + dllnode_free(&p); p = n; } @@ -31,17 +70,15 @@ void dlinkedlist_free(dlinkedlist **ll) { return; } -int dlinkedlist_firstitem(dlinkedlist * const ll, void *data, int (*dfreecb)(void*)) { - if(!ll) +int dlinkedlist_firstitem(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb) { + if(!ll) { + errno = EINVAL; return -1; + } if(ll->size != 0) return 0; - dllnode *n = xcalloc(1, sizeof(*n)); - n->next = NULL; - n->prev = NULL; - n->data = data; - n->dfreecb = dfreecb; + dllnode *n = dllnode_init(data, dfreecb); ll->start = n; ll->end = n; @@ -50,15 +87,15 @@ int dlinkedlist_firstitem(dlinkedlist * const ll, void *data, int (*dfreecb)(voi return 1; } -int dlinkedlist_insert(dlinkedlist * const ll, void *data, int (*dfreecb)(void*)) { - if(!ll) +int dlinkedlist_insert(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 = xcalloc(1, sizeof(*n)); - n->data = data; - n->dfreecb = dfreecb; + dllnode *n = dllnode_init(data, dfreecb); n->prev = NULL; n->next = ll->start; @@ -69,15 +106,15 @@ int dlinkedlist_insert(dlinkedlist * const ll, void *data, int (*dfreecb)(void*) return 0; } -int dlinkedlist_append(dlinkedlist * const ll, void *data, int (*dfreecb)(void*)) { - if(!ll) +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 = xcalloc(1, sizeof(*n)); - n->data = data; - n->dfreecb = dfreecb; + dllnode *n = dllnode_init(data, dfreecb); n->prev = ll->end; n->next = NULL; @@ -88,12 +125,89 @@ int dlinkedlist_append(dlinkedlist * const ll, void *data, int (*dfreecb)(void*) return 0; } -dllnode *dlinkedlist_get(const dlinkedlist * const ll, size_t index) { - if(index >= ll->size) +dllnode *dlinkedlist_getnode(const dlinkedlist * const ll, size_t index) { + if(!ll) { + errno = EINVAL; return NULL; + } + if(index >= ll->size) { + errno = EINVAL; + return NULL; + } + + // No need to loop if the desired indices are either the first or last + if(index == 0) + return ll->start->data; + if(index == (ll->size - 1)) + return ll->end->data; - dllnode *p = ll->start; - for(size_t i = 0; i < index && p != NULL; i++, p = p->next); + int spoint = (index < (ll->size / 2)); + dllnode *p = (spoint) ? ll->start : ll->end; + size_t 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); return p; +} + +void *dlinkedlist_get(const dlinkedlist * const ll, size_t index) { + dllnode *n = dlinkedlist_getnode(ll, index); + if(!n) + return NULL; + + return n->data; +} + +void *dlinkedlist_getfirst(const dlinkedlist * const ll) { + return dlinkedlist_get(ll, 0); +} + +void *dlinkedlist_getlast(const dlinkedlist * const ll) { + return dlinkedlist_get(ll, ll->size - 1); +} + +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(index == 0) { + ll->start = current->next; + ll->start->prev = NULL; + } else if(index == (ll->size - 1)) { + 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; + } + // 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--; + + return 0; } \ No newline at end of file -- cgit v1.2.3