list.c

#include <stdlib.h>
#include <stdio.h>
#include "list.h"

#ifdef DMALLOC
#include "dmalloc.h"
#endif

#ifdef DEBUG
#define PDEBUG(Args...) \
  do { fprintf(stderr, "mcwm: "); fprintf(stderr, ##Args); } while(0)
#define D(x) x
#else
#define PDEBUG(Args...)
#define D(x)
#endif

/*
 * Move element in item to the head of list mainlist.
 */
void movetohead(struct item **mainlist, struct item *item)
{
    if (NULL == item || NULL == mainlist || NULL == *mainlist)
    {
        return;
    }

    if (*mainlist == item)
    {
        /* item is NULL or we're already at head. Do nothing. */
        return;
    }

    /* Braid together the list where we are now. */
    if (NULL != item->prev)
    {
        item->prev->next = item->next;
    }

    if (NULL != item->next)
    {
        item->next->prev = item->prev;
    }

    /* Now we'at head, so no one before us. */
    item->prev = NULL;

    /* Old head is our next. */
    item->next = *mainlist;

    /* Old head needs to know about us. */
    item->next->prev = item;

    /* Remember the new head. */
    *mainlist = item;
}

/*
 * Create space for a new item and add it to the head of mainlist.
 *
 * Returns item or NULL if out of memory.
 */
struct item *additem(struct item **mainlist)
{
    struct item *item;

    if (NULL == (item = (struct item *) malloc(sizeof (struct item))))
    {
        return NULL;
    }

    if (NULL == *mainlist)
    {
        /* First in the list. */

        item->prev = NULL;
        item->next = NULL;
    }
    else
    {
        /* Add to beginning of list. */

        item->next = *mainlist;
        item->next->prev = item;
        item->prev = NULL;
    }

    *mainlist = item;

    return item;
}

void delitem(struct item **mainlist, struct item *item)
{
    struct item *ml = *mainlist;

    if (NULL == mainlist || NULL == *mainlist || NULL == item)
    {
        return;
    }

    if (item == *mainlist)
    {
        /* First entry was removed. Remember the next one instead. */
        *mainlist = ml->next;
    }
    else
    {
        item->prev->next = item->next;

        if (NULL != item->next)
        {
            /* This is not the last item in the list. */
            item->next->prev = item->prev;
        }
    }

    free(item);
}

void freeitem(struct item **list, int *stored,
              struct item *item)
{
    if (NULL == list || NULL == *list || NULL == item)
    {
        return;
    }

    if (NULL != item->data)
    {
        free(item->data);
        item->data = NULL;
    }

    delitem(list, item);

    if (NULL != stored)
    {
        (*stored) --;
    }
}

/*
 * Delete all elements in list and free memory resources.
 */
void delallitems(struct item **list, int *stored)
{
    struct item *item;
    struct item *next;

    for (item = *list; item != NULL; item = next)
    {
        next = item->next;
        free(item->data);
        delitem(list, item);
    }

    if (NULL != stored)
    {
        (*stored) = 0;
    }
}

void listitems(struct item *mainlist)
{
    struct item *item;
    int i;

    for (item = mainlist, i = 1; item != NULL; item = item->next, i ++)
    {
        printf("item #%d (stored at %p).\n", i, (void *)item);
    }
}

#if 0

void listall(struct item *mainlist)
{
    struct item *item;
    int i;

    printf("Listing all:\n");

    for (item = mainlist, i = 1; item != NULL; item = item->next, i ++)
    {
        printf("%d at %p: %s.\n", i, (void *)item, (char *)item->data);
        printf("  prev: %p\n", item->prev);
        printf("  next: %p\n", item->next);
    }
}

int main(void)
{
    struct item *mainlist = NULL;
    struct item *item1;
    struct item *item2;
    struct item *item3;
    struct item *item4;
    struct item *item;
    struct item *nextitem;
    int i;
    char *foo1 = "1";
    char *foo2 = "2";
    char *foo3 = "3";
    char *foo4 = "4";

    item1 = additem(&mainlist);
    if (NULL == item1)
    {
        printf("Couldn't allocate.\n");
        exit(1);
    }
    item1->data = foo1;
    printf("Current elements:\n");
    listall(mainlist);

    item2 = additem(&mainlist);
    if (NULL == item2)
    {
        printf("Couldn't allocate.\n");
        exit(1);
    }
    item2->data = foo2;
    printf("Current elements:\n");
    listall(mainlist);

    item3 = additem(&mainlist);
    if (NULL == item3)
    {
        printf("Couldn't allocate.\n");
        exit(1);
    }
    item3->data = foo3;
    printf("Current elements:\n");
    listall(mainlist);

    item4 = additem(&mainlist);
    if (NULL == item4)
    {
        printf("Couldn't allocate.\n");
        exit(1);
    }
    item4->data = foo4;
    printf("Current elements:\n");
    listall(mainlist);

    printf("----------------------------------------------------------------------\n");

    printf("Moving item3 to be after item2\n");
    movetonext(&mainlist, item2, item3);
    printf("Current elements:\n");
    listall(mainlist);

    printf("----------------------------------------------------------------------\n");

    printf("Moving head! item4 to be after item2\n");
    movetonext(&mainlist, item2, item4);
    printf("Current elements:\n");
    listall(mainlist);

    printf("----------------------------------------------------------------------\n");

    printf("Moving tail! item1 to be after item2\n");
    movetonext(&mainlist, item2, item1);
    printf("Current elements:\n");
    listall(mainlist);

    printf("----------------------------------------------------------------------\n");

    printf("Moving head to be after tail.\n");
    movetonext(&mainlist, item3, item2);
    printf("Current elements:\n");
    listall(mainlist);

    printf("Moving all the items after each other.\n");
    /* item3 is tail. work backwards. */
    for (item = mainlist, i = 1;
         item != NULL;
         item = item->next, i ++)
    {
        for (nextitem = item2; nextitem != NULL; nextitem = nextitem->prev)
        {
            movetonext(&mainlist, nextitem, item);
            printf("Current elements:\n");
            listall(mainlist);
        }
    }

    printf("----------------------------------------------------------------------\n");

#if 0
    movetohead(&mainlist, item2);
    printf("Current elements:\n");
    listall(mainlist);

    printf("----------------------------------------------------------------------\n");
#endif

    printf("Deleting item stored at %p\n", item3);
    delitem(&mainlist, item3);
    printf("Current elements:\n");
    listall(mainlist);

    puts("");

    delitem(&mainlist, item2);
    printf("Current elements:\n");
    listall(mainlist);

    puts("");

    delitem(&mainlist, item1);
    printf("Current elements:\n");
    listall(mainlist);

    puts("");

    printf("----------------------------------------------------------------------\n");

    exit(0);
}
#endif