c circular double linked-list delete_node - iterate traverses deleted node on first pass after delete

Question

All, in GNU c, I have a circular doubly linked-list I am trying to implement a delete_node function on. It works fine for all nodes except node 0. It does delete (free()) node 0, but the first time the list is traversed after deleting node 0, it is still present for the first pass causing the conditional to stopping the iteration to fail. The basics of the implementation are:

struct record
{
    char *line;
    int lineno;
    int linetype;
    struct record *prev;
    struct record *next;
};

typedef struct record rec;

void
iterfwd (rec *list) {

    rec *iter = list;   // second copy to iterate list

    if (iter ==  NULL) {
        fprintf (stdout,"%s(), The list is empty\n",__func__);
    } else {
        do {
            printf ("%2d - prev: %p  cur: %p  next: %p\n", iter->lineno, iter->prev, iter, iter->next);
        iter = iter->next;
        } while (iter != list);
    }
}

void
delete_node (rec *list, int num) {

    rec *iter = list;   // second copy to iterate list
    int cnt = 0;
    int found = 0;

    if (iter ==  NULL) {
        fprintf (stdout,"%s(), The list is empty\n",__func__);
    } else {
        // traverse list forward (check cnt == num, else if end -> Out Of Range)
        do {
            if (cnt == num) {
                found=1;
                (iter->prev)->next = iter->next;
                (iter->next)->prev = iter->prev;
                free (iter);
                break;
            }
            iter = iter-> next;
            cnt++;
            } while (iter != list);

            if (found != 1) {
            fprintf (stderr, "%s(), Error: record to delete is out of range (%d)\n", __func__, num);
        }
    }
}

int main (int argc, char *argv[]) {
    struct record *textfile = NULL; // instance of record, pointer to list
    int node = 0;
    node = (argc >= 2) ? atoi (argv[1]) : 0;
    textfile = fillrecord ();  // fill textfile circular linked-list
    iterfwd (textfile);
    delete_node (textfile, node);
    iterfwd (textfile);
    return 0;
}

A complete listing is here: http://www.3111skyline.com/dl/dev/prg/src/ll-double-cir.c.txt

The list is filled with 50 records of data for testing and I have inserted printf statements to confirm the pointer operations. Deleting any node except node 0 works as expected (the following is the pointer addresses for iter->prev, iter, iter->next for the affected rows [pre- and post- delete] for a deletion of node 10):

 9 - prev: 0x603490  cur: 0x603520  next: 0x6035b0
10 - prev: 0x603520  cur: 0x6035b0  next: 0x603640  <-- delete_node
11 - prev: 0x6035b0  cur: 0x603640  next: 0x6036d0

 9 - prev: 0x603490  cur: 0x603520  next: 0x603640
10 - prev: 0x603520  cur: 0x6035b0  next: 0x603640  <-- (node deleted)
11 - prev: 0x603520  cur: 0x603640  next: 0x6036d0

On the next traverse of the list, all works as expected:

 7 - prev: 0x603370  cur: 0x603400  next: 0x603490
 8 - prev: 0x603400  cur: 0x603490  next: 0x603520
 9 - prev: 0x603490  cur: 0x603520  next: 0x603640
11 - prev: 0x603520  cur: 0x603640  next: 0x6036d0
12 - prev: 0x603640  cur: 0x6036d0  next: 0x603760

However, if node 0 is deleted, the delete_node properly handles the pointers:

49 - prev: 0x604b10  cur: 0x604ba0  next: 0x603010
 0 - prev: 0x604ba0  cur: 0x603010  next: 0x6030a0  <-- delete_node
 1 - prev: 0x603010  cur: 0x6030a0  next: 0x603130

49 - prev: 0x604b10  cur: 0x604ba0  next: 0x6030a0
 0 - prev: 0x604ba0  cur: 0x603010  next: 0x6030a0  <-- (node deleted)
 1 - prev: 0x604ba0  cur: 0x6030a0  next: 0x603130

But then on the fist attempt to traverse the list after deletion, node 0 appears on the first pass causing the iterator conditions 'while (iter != list)' to fail and become stuck in a loop:

 0 - prev: 0x604ba0  cur: 0x603010  next: 0x6030a0
 1 - prev: 0x604ba0  cur: 0x6030a0  next: 0x603130
 2 - prev: 0x6030a0  cur: 0x603130  next: 0x6031c0
 3 - prev: 0x603130  cur: 0x6031c0  next: 0x603250
 4 - prev: 0x6031c0  cur: 0x603250  next: 0x6032e0
<snip>
47 - prev: 0x6049f0  cur: 0x604a80  next: 0x604b10
48 - prev: 0x604a80  cur: 0x604b10  next: 0x604ba0
49 - prev: 0x604b10  cur: 0x604ba0  next: 0x6030a0
 1 - prev: 0x604ba0  cur: 0x6030a0  next: 0x603130
 2 - prev: 0x6030a0  cur: 0x603130  next: 0x6031c0
 3 - prev: 0x603130  cur: 0x6031c0  next: 0x603250

As shown above, after the iterator traverses 0-49, the deleted node 0 disappears and it begins traversing properly 1-49 again, but at that point it is in a loop because the conditional (iter != list) is always true (node 0 disappears preventing iter from ever equaling list). This is a pure circular list, there are no HEAD or TAIL nodes set to null, the end->next points to the beginning of the list and the first->prev points to the end. What is the trick to having the delete_node() function work for node 0 such that the first iteration after delete starts with 1 and not the old 0 that then disappears?

Answer 1

You're not modifying the caller's pointer when requesting the very node it points to as the delete request. The following, a cut down version of some of your code, demonstrates one way to do this:

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

typedef struct record rec;
struct record
{
    int data;
    rec *prev, *next;
};

void delete_node (rec ** pp, int num)
{
    if (!*pp)
        return;

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

    // setup victim
    rec *victim = *pp;

    // non-self-reference node means just rewire
    if (victim && (victim != victim->next))
    {
        victim->prev->next = victim->next;
        victim->next->prev = victim->prev;
        *pp = victim->next;
    }
    else
    {   // deleted node was self-referenced. last node
        *pp = NULL;
    }
    free(victim);
}

void iterfwd(const rec* list)
{
    const rec *p = list;
    printf("list: %p\n", list);
    if (p)
    {
        for (; p; p = (p->next != list ? p->next : NULL))
            printf("prev: %p, self:%p, next:%p, data = %d\n", p->prev, p, p->next, p->data);
    }
    puts("");
}

void insert(rec **pp, int data)
{
    // setup new node
    rec *newp = malloc(sizeof(*newp));
    newp->data = data;

    if (!*pp)
    {
        newp->next = newp->prev = newp;
        *pp = newp;
    }
    else
    {   // insert between prev and head.
        newp->next = *pp;
        (*pp)->prev->next = newp;
        newp->prev = (*pp)->prev;
        (*pp)->prev = newp;
    }
}

int main()
{
    rec *list = NULL;
    int i;

    for (i=1; i<=5; ++i)
        insert(&list, i);
    iterfwd(list);

    // delete fourth node (0-based)
    delete_node(&list, 3);
    iterfwd(list);

    // delete first node (0-based)
    delete_node(&list, 0);
    iterfwd(list);

    // delete first node (0-based)
    delete_node(&list, 0);
    iterfwd(list);

    // delete first node (0-based)
    delete_node(&list, 0);
    iterfwd(list);

    // delete first node (0-based)
    delete_node(&list, 0);
    iterfwd(list);

    return 0;
}

Output (obviously system dependent)

Note how the passed-in pointer (pass by address) is modified when requesting the 0-element is removed.

list: 0x100103af0
prev: 0x100103b70, self:0x100103af0, next:0x100103b10, data = 1
prev: 0x100103af0, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b50, data = 3
prev: 0x100103b30, self:0x100103b50, next:0x100103b70, data = 4
prev: 0x100103b50, self:0x100103b70, next:0x100103af0, data = 5

list: 0x100103af0
prev: 0x100103b70, self:0x100103af0, next:0x100103b10, data = 1
prev: 0x100103af0, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103af0, data = 5

list: 0x100103b10
prev: 0x100103b70, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103b10, data = 5

list: 0x100103b30
prev: 0x100103b70, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103b30, data = 5

list: 0x100103b70
prev: 0x100103b70, self:0x100103b70, next:0x100103b70, data = 5

list: 0x0