C singly-linked circular linked-list example

/* Simple example of a singly-linked circular linked list.
 * This example will read any text file and store a dynamically
 * allocated list of nodes containing the each line and line number.
 * compile with:
 *
 *    gcc -Wall -Wextra -o yourprogname sourcefile.c
 *
 * use:
 *
 *    ./yourprogname somefile.txt [node2delete (default: 2, zero based)]
 *
 * The example reads somefile.txt into the list, prints the list to stdout,
 * deletes the zero based node 'node2delete' (default 2 - (e.g. the 3rd line)),
 * and prints the new list to stdout. The example then frees all memory
 * allocated to the list and exits.
 *
 * For informational purposes, the optional DEBUG definition can be
 * added to the compile string which, in addition to the information above,
 * will print the list pointer addresses for each node. (e.g. node, node->next).
 * Simply compile the code with:
 *
 *    gcc -Wall -Wextra -o yourprogname sourcefile.c -DDEBUG
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* list struct to hold line & line number */
typedef struct lline {
    size_t num;
    char *line;
    struct lline *next;
} lline;

/* allocate & populate node */
lline *create_node (char *s, size_t n);

/* insert node into list */
lline *insert_node (lline **list, char *s, size_t n);

/* read data from file fname and add to list */
lline *read_file2list (lline **list, char *fname);

/* return the number of nodes in list */
size_t getszlist (lline *list);

/* print all nodes in list */
void print_list (lline *list);

/* print all node pointers in list */
void print_list_p (lline *list);

/* free memory allocated to lline list node */
void free_node (lline *node);

/* (zero-based) delete of nth node */
void delete_node (lline **list, size_t nth);

/* delete lline list & free allocated memory */
void delete_list (lline *list);

int main (int argc, char **argv)
{
    if (argc < 2 ) {                        /* validate input / usage  */
        fprintf (stderr, "error: insufficient input, usage: %s filename [node2delete]\n", argv[0]);
        return 1;
    }

    char *fname = argv[1];
    lline *book1 = NULL;                    /* create new list pointer */


    if (!read_file2list (&book1, fname)) {  /* read file into list      */
        fprintf (stderr, "error: read of file '%s' returned no list.\n", fname);
        return 1;
    }

    printf ("\n Read '%zd' records from file: %s\n\n", getszlist (book1), fname);

    print_list (book1);                     /* print list (all nodes)   */
#ifdef DEBUG
    printf ("\n list node pointer addresses:\n\n");
    print_list_p (book1);
#endif
    int nth = (argc > 2) ? atoi (argv[2]) : 2;
    printf ("\n Deleting node: %d\n\n", nth);
    delete_node (&book1, nth);

    print_list (book1);                     /* print list (confirm del) */
#ifdef DEBUG
    printf ("\n list node pointer addresses:\n\n");
    print_list_p (book1);
#endif

    delete_list (book1);                    /* free list memory in use  */

    return 0;
}

/* allocate & populate node */
lline *create_node (char *s, size_t n)
{
    lline *node = NULL;

    node = malloc (sizeof *node);
    if (!node) return NULL;

    node-> line = s ? strdup (s) : strdup (""); /* allow empty line */
    node-> num = n;

    return node;
}

/* insert node into list */
lline *insert_node (lline **list, char *s, size_t n)
{
    lline *node = NULL;
    if (!(node = create_node (s, n))) return NULL;


    if (!*list) {                       /* if empty, create first node  */
    node-> next = 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          */
        }
        else
        {
            lline *iter = *list;        /* second copy to iterate list  */
            for (; iter->next != *list; iter = iter->next) ; /* to end  */
            iter-> next = node;         /* insert at end of list        */
        }
        node-> next = *list;            /* circular - next is first     */
    }

    return *list;                       /* return list */
}

/* read list from file fname and add to list */
lline *read_file2list (lline **list, char *fname)
{
    FILE *fp = fopen (fname, "r");
    if (!fp) {
        fprintf (stderr, "%s() error: file open failed for '%s'\n", __func__, fname);
        return NULL;
    }

    /* allocate and initialize all variables */
    char *ln = NULL;            /* NULL forces getline to allocate  */
    size_t n = 0;               /* max chars to read (0 - no limit) */
    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    */

        insert_node (list, ln, idx++);      /* add line to list     */
    }

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

    return *list;
}

/* return the number of nodes in list */
size_t getszlist (lline *list) {

    const lline *iter = list;  /* pointer to iterate list  */
    register int cnt = 0;

    if (iter ==  NULL) {
    fprintf (stdout,"%s(), The list is empty\n",__func__);
    return 0;
    }

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

/* print all nodes in list */
void print_list (lline *list) {

    const lline *iter = list;  /* pointer to iterate list  */

    if (iter ==  NULL) {
    fprintf (stderr,"%s() warning: empty list.\n",__func__);
    return;
    }

    for (; iter; iter = (iter->next != list ? iter->next : NULL))
        printf (" %5zu : %s\n", iter-> num, iter-> line);
}

/* print all nodes pointers in list */
void print_list_p (lline *list) {

    const lline *iter = list;  /* pointer to iterate list  */
    size_t i = 0;

    if (iter ==  NULL) {
    fprintf (stderr,"%s() warning: empty list.\n",__func__);
    return;
    }

    for (; iter; iter = (iter->next != list ? iter->next : NULL)) {
        printf (" node (%3zu) : %p    node-> next (%3zu) : %p\n",
                i, iter, (iter->next == list) ? 0 : i+1, iter-> next);
        i++;
    }
}

/* free all dynamically allocated members, then node */
void free_node (lline *node)
{
    if (!node) return;

    if (node-> line) free (node-> line);

    free (node);
}

/* (zero-based) delete of nth node */
void delete_node (lline **list, size_t nth)
{
    /* test that list exists */
    if (!*list) {
    fprintf (stderr,"%s() warning: empty list.\n",__func__);
    return;
    }

    /* get list size */
    size_t szlist = getszlist (*list);

    /* validate node to delete */
    if (nth >= szlist) {
    fprintf (stderr, "%s(), error: invalid node (%zu). allowed: (0 <= nth <= %zu)\n",
                __func__, nth, szlist-1);
    return;
    }

    /* create node pointers */
    lline *victim = *list;
    lline *prior = victim;

    /* if nth 0, prior is last, otherwise node before victim */
    if (nth == 0) {
        for (; prior->next != *list; prior = prior->next) ;
    } else {
        while (nth-- && victim-> next != *list) {
            prior = victim;
            victim = victim-> next;
        }
    }

    /* non-self-reference node, rewire next */
    if (victim != victim->next) {
    prior-> next = victim-> next;

    /* if deleting node 0, change list pointer address */
    if (victim == *list)
        *list = victim->next;
    } else {  /* if self-referenced, last node, delete list */
    *list = NULL;
    }

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

/* delete lline list */
void delete_list (lline *list)
{
    if (!list) return;

    /*  Since list is being deleted, you can delete nodes beginning
     *  with any node (e.g. 'list' or 'list-> next'). It is probably
     *  better form to leave the beginning address as the last node
     *  to delete. Both methods shown below with the code to delete
     *  beginning with the first node commented with '//'.
     */
    // lline *iter = list;  /* pointer to iterate list  */
    lline *iter = list-> next; /* pointer to iterate list  */
    lline *np = NULL;          /* save next addr, to avoid invalid read */

    // while (iter->next != list)
    while (iter != list)
    {
        np = iter-> next;
        if (iter) free_node (iter);
            iter = np;
    }

    if (iter) free_node (iter);

    /* Additional notes on iteration techniques for delete

       for loop is fine for iteration, but when deleting list it
       results in invalid read on iter = iter->next after free (iter)
       unless a next pointer is used. The following will not work:

    for (; iter; iter = (iter->next != list ? iter->next : NULL))
        if (iter) free_node (iter);

       But this will:

    for (; iter; iter = (iter != list ? np : NULL))
    {
        np = iter-> next;
        if (iter) free_node (iter);
    }
    */
}