singly_linked_list.c

/*
 *  singly_linked_list.c
 *  
 *  Demo of singly-linked list using simplified Process struct
 *
 *  I made this for the 2019 KPMG Lunch and Learn series entitled, 
 *  "A heuristic approach to coding in C on Windows"
 */

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

struct Node
{
    struct Node * Next;
};
// can't have self-reference in definition if we use typedef initially
typedef struct Node Node;

typedef struct
{
    Node * First;
    Node * Last;
} LinkedList;

/* HELPER FUNCTIONS */

void list_init(LinkedList * list)
{
    list->First = 0;
    list->Last = 0;
}

char list_empty(LinkedList * list)
{
    return 0 == list->First;
}

Node * list_head(LinkedList * list)
{
    return list->First;
}

Node * next_node(Node * node)
{
    return node->Next;
}

void list_push_back(LinkedList * list, Node * node)
{
    if (list_empty(list))
    {
        list->First = node;
        list->Last = node;
    }
    else
    {
        list->Last->Next = node;
        list->Last = node;
    }

    node->Next = 0;
}

Node * list_pop_front(LinkedList * list)
{
    Node * node = list->First;
    list->First = list->First->Next;
    return node;
}

/* IMPLEMENTATION */
typedef struct
{
    Node Header;
    int Pid;
    char Name[32];
} Process;

int main()
{
    // declare linked list of processes
    LinkedList processes;

    // allocate memory for 3 processes
    // cast void* to Process* since address of Process is address of Node values (Header)
    Process * p0 = (Process *) malloc(sizeof(Process));
    Process * p1 = (Process *) malloc(sizeof(Process));
    Process * p2 = (Process *) malloc(sizeof(Process));
    
    // validate whether each pointer is valid (i.e., not NULL) before using
    if (!p0 || !p1 || !p2)
    {
        printf("ERROR: Unable to allocate sufficient memory!\n");
        return 1;
    }

    // must use strncopy_s to safely populate char[] buffer and not overflow buffer
    // however, this code unsafely ignores the potential error return value(s)!

    // set p0 values
    p0->Pid = 761;
    strncpy_s(p0->Name, sizeof(p0->Name), "svchost.exe", sizeof(p0->Name)-1);

    // set p1 values
    p1->Pid = 1151;
    strncpy_s(p1->Name, sizeof(p0->Name), "calc.exe", sizeof(p1->Name)-1);

    // set p2 values
    p2->Pid = 2256;
    strncpy_s(p2->Name, sizeof(p0->Name), "notepad.exe", sizeof(p2->Name)-1);

    // initialize list of processes
    list_init(&processes);

    // push each process onto back of processes linked list
    // works because start address of process is same as Node (Header)
    list_push_back(&processes, &p0->Header);
    list_push_back(&processes, &p1->Header);
    list_push_back(&processes, &p2->Header);

    // iterate over processes
    printf("PID\tProcess Name\n"); // titles (prettify output)
    /*
     *  Explanation of each element of for loop:
     *    1. Initializer: Get first process in list of processes
     *    2. Test Condition: Check if process has a valid address (0 == false)
     *    3. Expression: Advance list to next process
     */
    for (Process * p = (Process *) list_head(&processes); p; p = (Process *) next_node(&p->Header))
    {
        printf("%d\t%s\n", p->Pid, p->Name);
    }

    // free memory used by processes list before ending program
    printf("\n"); // print extra newline to prettify output
    while (!list_empty(&processes))
    {
        Process * p = (Process *) list_pop_front(&processes);
        printf("Popping process with PID %d off the list and freeing its memory.\n", p->Pid);
        free(p);
    }

    return 0;
}