Sunday, December 29, 2019

Example of Intrusive Singly Linked List

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



typedef struct list_item {
    int val;
    void *next;
} list_item;


typedef struct List {
    list_item *head;
    list_item *prev;
} List;


list_item *create_list_item(int val)
{
    list_item *p = (list_item *)malloc(sizeof(list_item));
    if (p)
    {
        p->val = val;
        p->next = NULL;
    }
    return p;
}


void add_list_item_into_node(List *list, int val)
{
    list_item *newlist_item = create_list_item(val);
    if (list->prev != NULL)
    {
        list->prev->next = newlist_item;
        list->prev = newlist_item;
    }
    else
    {
        list->head = newlist_item;
        list->prev = newlist_item;
        printf("FIRST! head==prev ? %d, %p\n", list->head==list->prev, list->head);
    }

    printf("%p added; head=%p, prev=%p\n", newlist_item, list->head, list->prev);
}


void init_list(List *l)
{
    l->head = l->prev = NULL;
}


void clear_list(List *l)
{
    list_item *p = l->head;
    while (p != NULL)
    {
        list_item *pn = (list_item *)p->next; 
        printf("Freeing %p, next p is=%p\n", p, pn);
        free(p);
        p = pn;
    }
    l->head = l->prev = NULL;
}


typedef void (*callback_t)(list_item *);

void print(list_item *p)
{
    printf("p=%p: val=%d\n", p, p->val);
}

void iterate(List *list, callback_t cbk)
{
    list_item *p = list->head;
    while (p)
    {
        cbk(p);
        p = p->next;
    }
}

int main()
{
    List mylist;
    init_list(&mylist);

    for(int i=0; i<10; ++i)
    {
        add_list_item_into_node(&mylist, i*2+1);
    }

   iterate(&mylist, print);

    // cleanup; starting from head
    printf("Cleaning up!\n");
    clear_list(&mylist);
    iterate(&mylist, print);

    printf("head = %p, prev=%p\n", mylist.head, mylist.prev);
}