Refactor a bunch of the linked list implementation

3 files changed, 154 insertions, 56 deletions

diff --git a/src/Makefile b/src/Makefile
index 4a0d316..d12eb72 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -20,11 +20,11 @@ BINARIES := main encryption
 
 all: main
 
-main: main.o shared.o
+main: main.o shared.o ll.o arena.o
 
-ll.o: ll.c ll.h
-main.o: main.c
-arena.o: arena.c arena.h
+ll.o: ll.c ll.h shared.h
+main.o: main.c shared.h
+arena.o: arena.c arena.h shared.h
 shared.o: shared.c shared.h
 
 encryption: encryption.c encryption.h shared.o shared.h
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 <stddef.h>
 #include <stdlib.h>
+#include <errno.h>
+
+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(&current);
+    ll->size--;
+
+    return 0;
 }
\ No newline at end of file
diff --git a/src/ll.h b/src/ll.h
index 5e47bd9..f5846fb 100644
--- a/src/ll.h
+++ b/src/ll.h
@@ -1,35 +1,19 @@
-#ifndef __VXGG_REWRITE___SHARED_H___28542989122405___
-#define __VXGG_REWRITE___SHARED_H___28542989122405___
+#ifndef __VXGG_REWRITE___LL_H___305861098005___
+#define __VXGG_REWRITE___LL_H___305861098005___
 
 #include <stddef.h>
 
-typedef struct dll {
-    void *data;
-    int (*dfreecb)(void*);
+typedef int (*dlinkedlist_freecallback)(void*);
+typedef struct dlinkedlist dlinkedlist;
 
-    struct dll *next;
-    struct dll *prev;
-} dllnode;
-
-typedef struct {
-    dllnode *start;
-    dllnode *end;
-    size_t size;
-} dlinkedlist;
-
-// Initialize a dlinkedlist
 void dlinkedlist_init(dlinkedlist **ll);
-
-// Free a dlinkedlist and its elements
 void dlinkedlist_free(dlinkedlist **ll);
 
-// Insert an element to the beginning of the list
-int dlinkedlist_insert(dlinkedlist * const ll, void *data, int (*dfreecb)(void*));
-
-// Insert an element to the end of the list
-int dlinkedlist_append(dlinkedlist * const ll, void *data, int (*dfreecb)(void*));
-
-// Get the element from a dlinkedlist at index
-dllnode *dlinkedlist_get(const dlinkedlist * const ll, size_t index);
+int dlinkedlist_insert(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb);
+int dlinkedlist_append(dlinkedlist * const ll, void *data, dlinkedlist_freecallback dfreecb);
+void *dlinkedlist_get(const dlinkedlist * const ll, size_t index);
+void *dlinkedlist_getfirst(const dlinkedlist * const ll);
+void *dlinkedlist_getlast(const dlinkedlist * const ll);
+int dlinkedlist_remove(dlinkedlist * const ll, size_t index);
 
 #endif
\ No newline at end of file