Doubly Linked Circular Linked List w/Pointer to Payload

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXLISTS 64

typedef struct llist {  /* list structure   */
    void *data;
    struct llist *prev, *next;
} llist;

typedef struct {    /* payload structure    */
    size_t n;
    size_t len;
    char *s;
} payld;

unsigned long llsize[MAXLISTS] = {0};       /* array for lists size     */
/* NOTE: llsize[0] used for example below.
 * for implementaion, you need to pass the
 * list number or list size as an argument
 * to properly implement the use of a
 * global for tracking list size. It is
 * a great efficiency improvemnt to not
 * iterate over every node to get the list
 * size each time it is required. Change to
 * dynamic array and pass list count index
 * as an argument. Otherwise see the separate
 * stuct implementaion containing list object
 * and additional list params: count, sizeof
 */

/* list funciton prototypes */
llist *createlist ();                       /* create/insert/read file  */
llist *create_node (void *data);
llist *insert_node (llist **list, void *data);
llist *read_file2list (llist **list, char *fname);

void free_node (llist *node);               /* delete node/delete list  */
void delete_list (llist **list);
void delete_node_fwd (llist **list, unsigned long num);
void delete_node (llist **list, unsigned long num);

unsigned long getszlist (llist *list);      /* get number of list nodes */

/* iteration fwd/rev that take function pointer
   to define the function operation and output */
void iterfnfwd (void fnc (llist *list), llist *list);
void iterfnrev (void fnc (llist *list), llist *list);

/* iteration fwd/rev that take function pointer
   and pointer to integer value to define the
   function operation and output and returns a
   pointer to a node and updates the value at i
   to its new value */
void *iterfnfwdvi (void* fnc (llist*, unsigned long*), llist *list, unsigned long *n);
void *iterfnrevvi (void* fnc (llist*, unsigned long*), llist *list, unsigned long *n);
void *getfnfwdvi (void* fnc (llist*, unsigned long*), llist *list, unsigned long *n);

/* functions to pass to list iterators */
/* void iterfn prototypes              */
void itf_printnode (llist *node);           /* print nodes by func ptr  */

/* functions to pass to list iterators */
/* void* iterfn prototypes with int *n */
void *itf_printnodev (llist *node, unsigned long *n);
void *itf_getszv (llist *node, unsigned long *n);
void *itf_getnodev (llist *node, unsigned long *n);
void *itf_getdata (llist *node, unsigned long *n);
void *itf_srchlen (llist *node, unsigned long *n);

/* general functions */
void chkhelp (char **a, const char *opts);

/* test program - reads all lines in file
   given as first argument or from stdin */
int main (int argc, char **argv) {

    char *fn = NULL;
    llist *ll = NULL;
    unsigned long i = 0;

    if (argc > 1) {             /* check for -h or --help and show usage    */
        chkhelp (argv, "[filename (stdin)] to read file or stdin into list");
        fn = argv[1];
    }

    read_file2list (&ll, fn);   /* read lines from file (or stdin) into list */
    if (!getszlist (ll)) {
        fprintf (stderr, "error: insufficient input.  usage: %s [filename (stdin)]\n",
                argv[0]);
        return 1;
    }

    /* printf the list forward */
    printf ("\n linked list read from '%s'\n\n", fn ? fn : "stdin");
    iterfnfwd (itf_printnode, ll);

    i = 0;  /* get the number of nodes in list through funciton pointer */
    printf ("\n list size: %lu  (by void *funciton pointer return)\n",
            *(unsigned long *)iterfnfwdvi (itf_getszv, ll, &i));
    /* get the number of nodes in list through global */
    printf (" list size: %lu  (by llsize)\n\n", llsize[0]);

    /* printf the list in reverse */
    printf (" iterating the file in reverse:\n\n");
    iterfnrev (itf_printnode, ll);  // iterate with funciton pointer

    /* find node 10 (11th node in list) */
    printf ("\n selecting node 10 (11th in list -- zero based):\n\n");
    i = 10;
    payld *pt = getfnfwdvi (itf_getdata, ll, &i);
    if (pt)
        printf (" %2zu - [%3zu]  %s  ( node %lu -- cast to payld*)\n\n", pt->n, pt->len, pt->s, i);

    i = 20; /* find all (nodes) holding strings >= 20 chars */
    printf (" searching list for strings >= %lu chars:\n\n", i);
    iterfnfwdvi (itf_srchlen, ll, &i);  // iterate with funciton pointer
    printf ("\n '%lu' rows >= 20 chars\n\n", i);

    /* delete the first two nodes in list (original list address) */
    printf (" deleting nodes 1, 2  -  (indexes 0,1)\n\n");
    delete_node (&ll, 0);
    delete_node (&ll, 0);

    /* confirm size reduction with both iteration and global */
    printf (" list size: %lu\n", getszlist (ll));
    printf (" list size: %lu  (by llsize)\n\n", llsize[0]);

    i = 20; /* find all (nodes) holding strings >= 20 chars */
    printf (" searching list for strings >= %lu chars:\n\n", i);
    iterfnfwdvi (itf_srchlen, ll, &i);  // iterate with funciton pointer
    printf ("\n '%lu' rows >= 20 chars\n\n", i);

    /* delete the first two nodes in list (original list address) */
    printf (" deleting node 12  -  (original index 14)\n\n");
    delete_node (&ll, 12);

    i = 20; /* find all (nodes) holding strings >= 20 chars */
    printf (" searching list for strings >= %lu chars:\n\n", i);
    iterfnfwdvi (itf_srchlen, ll, &i);  // iterate with funciton pointer
    printf ("\n '%lu' rows >= 20 chars\n\n", i);

    printf (" deleting all nodes in list\n");
    delete_list (&ll);

    /* confirm size reduction with both iteration and global */
    printf ("\n list size: %lu\n", getszlist (ll));
    printf (" list size: %lu  (by llsize)\n\n", llsize[0]);

    return 0;
}

/* allocate & copy data to node
   NOTE: function requires custimization based
   on the struct definition of payld */
llist *create_node (void *data)
{
    llist *node = NULL;

    node = malloc (sizeof *node);
    node-> data = malloc (sizeof (payld));

    if (!node || !node-> data) return NULL;

    if (data) {
        memcpy (node->data, data, sizeof (payld));
        payld *p = (payld *) data;
        payld *np = (payld *) node->data;
        if (!(np->s = strdup (p-> s))) {
#ifdef DEBUG
            fprintf (stderr, "%s() error: payload allocation failed.\n",
                    __func__);
#endif
            free_node (node);
            return NULL;
        }
    }

    return node;
}

/* insert node into list */
llist *insert_node (llist **list, void *data)
{
    llist *node = NULL;
    if (!(node = create_node (data))) return NULL;


    if (!*list) {                       /* if empty, create first node  */
    node-> next = node;
    node-> prev = node;
        *list = node;                   /* insert as new first node     */
    } else {
        if (*list == (*list)-> next) {  /* list only contains 1 node    */
            (*list)-> next = node;      /* insert as next node          */
            node-> prev = *list;
        }
        else
        {
            (*list)->prev->next = node; /* cir list, just ins as last   */
            node->prev = (*list)->prev; /* no need to iterate to end    */
        }
        node-> next = *list;            /* circular - next is first     */
        (*list)-> prev = node;          /* list->prev is node           */
    }

    return *list;                       /* return list */
}

/* read list from file fname and add to list
   NOTE: function requires custimization based
   on the struct definition of payld */
llist *read_file2list (llist **list, char *fname)
{
    FILE *fp = NULL;
    if (fname) {
        if (!(fp = fopen (fname, "r"))) {
            fprintf (stderr, "%s() error: file open failed for '%s'\n",
                    __func__, fname);
            return NULL;
        }
    }
    else
        fp = stdin;

    /* allocate and initialize all variables */
    char *ln = NULL;            /* NULL forces getline to allocate  */
    size_t n = 0;               /* ln size (0 - getline chooses)    */
    size_t idx = 0;             /* line number index                */
    ssize_t nchr = 0;           /* number of chars actually read    */

    while ((nchr = getline (&ln, &n, fp)) != -1)    /* read file    */
    {
        while (nchr > 0 && (ln[nchr-1] == '\n' || ln[nchr-1] == '\r'))
            ln[--nchr] = 0;     /* strip newline or carriage rtn    */

        payld pld = { 0, 0, NULL }; /* static initialization struct */

        pld.n = idx;
        pld.len = nchr;
        pld.s = ln;
        insert_node (list, &pld);           /* add node to list     */
        idx++;
        llsize[0] += 1;
    }

    if (fp != stdin) fclose (fp);           /* close file/free line */
    if (ln) free (ln);

    return *list;
}

/* free dynamically allocated payload, then node */
void free_node (llist *node)
{
    if (!node) return;

    if (node-> data) {
        payld *p = (payld *)node-> data;
        if (p-> s)
            free (p-> s);
        free (node-> data);
    }

    free (node);
}

/* free memory for all nodes in list */
void delete_list (llist **list)
{
    llist *iter = (*list)-> next;
    llist *np = NULL;
    while (iter != *list)
    {
        np = iter-> next;
        if (iter) free_node (iter);
        iter = np;
    }
    if (iter) free_node (iter);
    *list = NULL;
    if (llsize[0]) llsize[0] = 0;
}

/* free memory for specific node (zero based) */
void delete_node_fwd (llist **list, unsigned long node)
{
    /* validate list exists */
    if (!*list) {
    fprintf (stderr, "%s(), The list is empty\n",__func__);
    return;
    }

    /* get size of list */
    unsigned long szlist = getszlist (*list);

    /* test node < szlist */
    if (node >= szlist) {
    fprintf (stderr, "%s() error: record to delete is out of range (%lu)\n",
                __func__, node);
    return;
    }

    /* find the node'th node    */
    while (node--)
    list = &(*list)->next;

    /* create pointer to node to delete */
    llist *victim = *list;

    /* for non-self-referenced nodes - just rewire pointers     */
    if (victim != victim->next) {
    (victim->prev)->next = victim->next;
    (victim->next)->prev = victim->prev;
    *list = victim->next;
    } else {      /* deleted node self-referenced - last node   */
    *list = NULL;
    }

    if (llsize[0]) llsize[0]-= 1;   /* maintian global count    */

    /* free node memory    */
    free_node (victim);
}

/* free memory for specific node (zero based)
   (balanced search in only 1/2 list w/node) */
void delete_node (llist **list, unsigned long node)
{

    /* validate list exists */
    if (!*list) {
    fprintf (stderr, "%s()  list is empty\n", __func__);
    return;
    }

    /* get size of list */
    // int szlist = getszlist (*list);
    unsigned long szlist = llsize[0];

    /* test node < szlist */
    if (node >= szlist) {
    fprintf (stderr, "%s() error: record to delete is out of range (%lu)\n",
                __func__, node);
    return;
    }

    /* find the node'th node with balanced search
       search fwd for 0->szlist/2, rev end->szlist/2 */
    if (node != 0  && node >= szlist/2) {
    while (szlist - node++)
        list = &(*list)->prev;

    list = &(*list)->prev; /* hack to get correctly bracket ptr before */
    list = &(*list)->next; /* delete when traversing list in reverse   */
    } else
    while (node--)
        list = &(*list)->next;

    /* create pointer to node to delete */
    llist *victim = *list;

    /* for non-self-referenced nodes - just rewire pointers     */
    if (victim != victim->next) {
    (victim->prev)->next = victim->next;
    (victim->next)->prev = victim->prev;
    *list = victim->next;
    } else {      /* deleted node self-referenced - last node   */
    *list = NULL;
    }

    if (llsize[0]) llsize[0]-= 1;   /* maintian global count    */

    /* free node memory    */
    free_node (victim);
}

/* get list info functions */
unsigned long getszlist (llist *list) {

    const llist *iter = list;   // second copy to iterate list
    register unsigned long cnt = 0;

    if (iter ==  NULL) {
#ifdef DEBUG
    fprintf (stderr, "%s(), The list is empty\n", __func__);
#endif
    return cnt;
    }

    for (; iter; iter = (iter->next != list ? iter->next : NULL))
        cnt++;

    return cnt;
}

/* iteration fwd/rev that take function pointer
   to define the function operation and output */
void iterfnfwd (void fnc (llist *list), llist *list)
{
    if (list ==  NULL) {
#ifdef DEBUG
    fprintf (stderr, "%s()  list is empty\n", __func__);
#endif
    return;
    }

    llist *iter = list; /* create pointer to iterate list   */

    do
    {
        fnc (iter);
        iter = iter->next;
    } while (iter != list);
}

void iterfnrev (void fnc (llist *list), llist *list)
{
    if (list ==  NULL) {
#ifdef DEBUG
    fprintf (stderr, "%s()  list is empty\n", __func__);
#endif
    return;
    }

    llist *iter = list-> prev; /* create pointer to last iterate list   */

    do
    {
        fnc (iter);
        iter = iter->prev;
    } while (iter != list->prev);
}

void *iterfnfwdvi (void *fnc (llist*, unsigned long*), llist *list, unsigned long *n)
{
    if (list ==  NULL) {
#ifdef DEBUG
    fprintf (stderr, "%s()  list is empty\n", __func__);
#endif
    return NULL;
    }

    llist *iter = list; /* create pointer to iterate list   */
    void *rtn = NULL;   /* create poiner for fnc return     */
    unsigned long nbegin = *n;
    size_t cnt = 0;

    for (; iter; iter = (iter->next != list ? iter->next : NULL))
    {
        if ((rtn = fnc (iter, n))) cnt++;
    }

    if (*n == nbegin) *n = cnt;  /* if ptr *n unchanged rtn cnt  */

    return rtn;
}

void *iterfnrevvi (void *fnc (llist*, unsigned long*), llist *list, unsigned long *n)
{
    if (list ==  NULL) {
#ifdef DEBUG
    fprintf (stderr, "%s()  list is empty\n", __func__);
#endif
    return NULL;
    }

    llist *iter = list-> prev;  /* pointer to last to iterate list  */
    void *rtn = NULL;           /* create poiner for fnc return     */
    unsigned long nbegin = *n;
    size_t cnt = 0;

    for (; iter; iter = (iter->prev != list->prev ? iter->prev : NULL))
    {
        if ((rtn = fnc (iter, n))) cnt++;
        // rtn = fnc (iter, n);
    }

    if (*n == nbegin) *n = cnt;  /* if ptr *n unchanged rtn cnt  */

    return rtn;
}

/* RENAME: to something reflecting this is balanced search for node 'n' */
void *getfnfwdvi (void *fnc (llist*, unsigned long*), llist *list, unsigned long *n)
{
    if (list ==  NULL) {
#ifdef DEBUG
    fprintf (stderr, "%s()  list is empty\n", __func__);
#endif
    return NULL;
    }

    if (*n == 0)        /* request first node, call/return  */
        return fnc (list, n);

    /*  need to save global list size to be able to do efficient
        balanced search. If calling getszlist() iterates over
        the list once to get sz, the you save nothing with the
        balance search, you may as well just iterate once to
        find the node in question, unless the fnc code is so
        big a full iter of the list makes sense.

        llsize[0] is list size  (maybe use struct?)
    */

    // int szlist = getszlist (*list);
    unsigned long szlist = llsize[0];

    /* validate node > 0 && < szlist */
    if (*n >= llsize[0]) {
#ifdef DEBUG
    fprintf (stderr, "%s() error: record to delete is out of range (%lu)\n",
                __func__, *n);
#endif
    return NULL;
    }

    llist *iter = list; /* create pointer to iterate list   */
    void *rtn = NULL;   /* create poiner for fnc return     */
    register unsigned long node = *n;

    /* find the node'th node with balanced search
       search fwd for 0->szlist/2, rev end->szlist/2 */
    if (*n >= szlist/2) {
        while (szlist - node++)
            iter = iter-> prev;

        iter = iter-> prev; /* hack to get correctly bracket ptr before */
        iter = iter-> next; /* delete when traversing list in reverse   */
    }
    else {
        while (node--)
            iter = iter-> next;
    }

    rtn = fnc (iter, n);

    return rtn;
}

/* void print nodes by function pointer */
void itf_printnode (llist *node)
{
    if (!node)
        return;

    payld *p = (payld *)node-> data;

#ifdef DEBUG
    printf (" %2zu - prev: %p  cur: %p  next: %p\n",
            p->n, node->prev, node, node->next);
#else
    printf (" %2zu - [%3zu]  %s\n", p->n, p->len, p->s);
#endif
}

/* void* print nodes by function pointer */
void *itf_printnodev (llist *node, unsigned long *n)
{
    if (!node) return NULL;
    (*n)++;

    payld *p = (payld *)node-> data;

#ifdef DEBUG
    printf (" %2zu - prev: %p  cur: %p  next: %p\n",
            p->n, node->prev, node, node->next);
#else
    printf (" %2zu - [%3zu]  %s\n", p->n, p->len, p->s);
#endif
    return node;
}

/* simple funciton to return list length through n
   while using a funciton pointer with iterator  */
void *itf_getszv (llist *node, unsigned long *n)
{
    if (!node) return NULL;
    (*n)++;

    return n;
}

void *itf_getnodev (llist *node, unsigned long *n)
{
    if (!node) return NULL;

    payld *p = (payld *)node-> data;
    if (p-> n == (size_t)*n) {
        printf ("  %2zu - [%3zu]  %s  ( %s() )\n\n", p->n, p->len, p->s, __func__);
        return p;
    }
    return NULL;
}

/* return a pointer to data for node n (zero based) */
void *itf_getdata (llist *node, unsigned long *n)
{
    if (!node) return NULL;
    if (*n ==0) *n = 0; /* prevent unused */
    return node->data;
}

/* search list for strings >= n */
void *itf_srchlen (llist *node, unsigned long *n)
{
    if (!node) return NULL;

    payld *p = (payld *)node-> data;

    if (p-> len >= (size_t)*n) {
        printf (" %2zu - [%3zu]  %s\n", p->n, p->len, p->s);
        return p;
    }

    return NULL;
}

/* check argv[1] for -h or --help request */
void chkhelp (char **a, const char *opts)
{
    if ((*a[1] == '-' && *(a[1] + 1) == 'h') ||
        (*(a[1] + 1) == '-' && *(a[1] + 2) == 'h'))
    {
        fprintf (stderr, " usage: %s %s\n", a[0], opts);
        exit (0);
    }
}