path: root/src/ll.c

#include "ll.h"
#include "shared.h"

#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;
}

dlinkedlist * dlinkedlist_init(void) {
    dlinkedlist *ll = xcalloc(1, sizeof(*ll));
    
    ll->start = NULL;
    ll->end = 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;
    }

    free(*ll);
    (*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;

    dllnode *n = dllnode_init(data, dfreecb);

    ll->start = n;
    ll->end = n;
    ll->size = 1;

    return 1;
}

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 = dllnode_init(data, dfreecb);
    n->prev = NULL;
    n->next = ll->start;

    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++;

    return 0;
}

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;

    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;
}

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);

    return 0;
}
#endif