Rewrite the whole linked list implementation so it's not shit

2 files changed, 136 insertions, 191 deletions

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(&current);
     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 <stdio.h>
-#include <string.h>
-
-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
diff --git a/src/ll.h b/src/ll.h
index 6e79ccd..6e4ccf9 100644
--- a/src/ll.h
+++ b/src/ll.h
@@ -1,22 +1,18 @@
 #ifndef __VXGG_REWRITE___LL_H___305861098005___
 #define __VXGG_REWRITE___LL_H___305861098005___
 
-#include <stddef.h>
+typedef int (*dll_freecb)(void*);
+typedef struct dlinked dlinkedlist;
 
-typedef int (*dlinkedlist_freecallback)(void*);
-typedef struct dlinkedlist dlinkedlist;
-
-dlinkedlist * dlinkedlist_init(void);
+dlinkedlist* dlinkedlist_init(void);
 int dlinkedlist_free(dlinkedlist **ll);
+int dlinkedlist_append(dlinkedlist * const ll, void *data, dll_freecb fcb);
+int dlinkedlist_prepend(dlinkedlist * const ll, void *data, dll_freecb fcb);
+int dlinkedlist_insert(dlinkedlist * const ll, void *data, dll_freecb fcb, int index);
+void* dlinkedlist_get(const dlinkedlist * const ll, int index);
+int dlinkedlist_remove(dlinkedlist * const ll, int 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);
-
-size_t dlinkedlist_size(const dlinkedlist * const ll);
-int dlinkedlist_isempty(const dlinkedlist * const ll);
+int dlinkedlist_size(const dlinkedlist * const ll);
+#define dlinkedlist_isempty(ll) (dlinkedlist_size((ll)) == 0)
 
 #endif
\ No newline at end of file