c circular double linked-list: rev traverse gives different list-pointer address for same node

Question

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

related post 2: c circular double linked-list: traverses fwd/rev for end node gives different pointer address

In working with a circular double linked-list, I have, with help from stackoverflow, created a delete_node function that uses both forward or reverse iterations on the list to arrive at the node to be deleted. The function takes the address of the linked-list as the argument to facillitate the deletion (as opposed to a pointer reference to the list). The mix of forward and reverse iteration is simply for efficiency to prevent traversing the entire list to reach a node near the end when iterating in the forward direction or the beginning when iterating in reverse.

full source:
http://www.3111skyline.com/dl/dev/prg/src/testlld.c.txt
compile with:  gcc -Wall -o tlld testlld.com

void
delete_node (rec **list, int node)
{

// test that list exists
if (!*list) {
    fprintf (stdout,"%s(), The list is empty\n",__func__);
    return;
}

// get size of list
int szlist = getszlist (*list);

// test node < szlist
if (node >= szlist || node < 0) {
    fprintf (stderr, "%s(), Error: record to delete is out of range (%d)\n", __func__, node);
    return;
}

// find the node'th node with balanced search
// search fwd for 0->szlist/2, rev end->szlist/2
if (node != 0  && node >= szlist/2) {
    while (szlist - node++)
    list = &(*list)->prev;

    list = &(*list)->prev;  // hack to get correct list ptr before delete
    list = &(*list)->next;  // when traversing list in reverse
} else
    while (node--)
    list = &(*list)->next;

// create pointer to node to delete
rec *victim = *list;

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

free (victim);  // delete the node
}

However, I have run across a problem iterating in reverse where the pointer address reported upon reaching the desired node is different from the address reported for the same node when reached with forward iteration. In related post 2, this was explained by forward iteration leaving the poiter-to-the-node-pointer on (node - 1) and reverse iteration leaving it pointing (node + 1) while both node-pointers correctly pointed to (node). I'm not convinced that is the case.

The problem is easily seen by dumping the pointers after iterating in reverse to the wanted node, then iterating one additional step (node->prev) dumping the pointers again, then stepping back to the wanted node in the forward direction (node->next) and dumping the pointers again. The address reported for the node changes. Here is an example for node 30:

list pointer state after reverse iteration to node: 30
29 - prev: 0x605070  cur: 0x605100  next: 0x605078
30 - prev: 0x605100  cur: 0x605190  next: 0x605108
31 - prev: 0x605190  cur: 0x605108  next: 0x605198

list pointer state after next step to node: 29
28 - prev: 0x604fe0  cur: 0x605070  next: 0x604fe8
29 - prev: 0x605070  cur: 0x605100  next: 0x605078
30 - prev: 0x605100  cur: 0x605078  next: 0x605108

list pointer state after forward step to node: 30
29 - prev: 0x605070  cur: 0x605100  next: 0x605078
30 - prev: 0x605100  cur: 0x605078  next: 0x605108
31 - prev: 0x605190  cur: 0x605108  next: 0x605198

I do not get it! In the first block of 3 above, the list pointer for node 30 reached iterating in reverse reports its address as cur: 0x605190. This looks broken, like there is some problem with the code, but there isn't. Something is wrong however, because node 30 cur: != node 29 next:. Continuing one more step in reverse list = &(*list)->prev; gives the next block of addresses and the list pointer address has changed to cur: 0x605078. Huh? However, you can see the problem continues in reverse iteration by looking at the addresses for now nodes 29 & 28. The same issue that was a problem for node 30, now exists at node 29 (by virture of the additional step->prev).

Now moving back to node 30 with list = &(*list)->next; allows node 30 to be deleted using address 0x605078 and everything works fine. But I cannot get my head around why I can't just iterate to node 30 in reverse and have the delete work? Why does interating in reverse give a different address for node 30 0x605190 than if reaching it from the forward direction 0x605078.

Lastly, after the ->prev,->next steps, you can see the same type of problem between node 30 cur: 0x605078 and node 31 prev: 0x605190. Huh? (and that is the address originally reported for node 30 when reached iterating in reverse?? What is going on here?

The full source code is available. Simply compile with gcc -Wall -o tlld testlld.com. The code creates a 50 node linked-list to operate on. You can force the list to delete all nodes as a test with ./tlld {49..0}.

Answer 1

As I said in the last thread, the problem is that you are looking at the address of the pointer variables, rather than the value of the pointer variables (i.e. where the variables are pointing). You also don't want to update *list unless the entry being deleted is the first one. Your calling function is relying on textfile to point to the start of the list.

Here is an updated version of delete_node_debug based on the code I offered on the last thread. I just used victim instead of *list in the loop, which leaves *list pointing to the start of the list. Then at the end, you can check if you are removing the start of the list if victim == *list

void
  delete_node_debug (rec **list, int node)
{

  // test that list exists
  if (!*list) {
    fprintf (stdout,"%s(), The list is empty\n",__func__);
    return;
  }

  // get size of list
  int szlist = getszlist (*list);

  // test node < szlist
  if (node >= szlist || node < 0) {
    fprintf (stderr, "%s(), Error: record to delete is out of range (%d)\n", __func__,     node);
    return;
  }

  rec *victim = *list;
  // find the node'th node with balanced search
  // search fwd for 0->szlist/2, rev end->szlist/2
  if (node != 0  && node >= szlist/2) {
    while (szlist - node++)
      victim = victim->prev;
    fprintf (stderr, "\nlist pointer state after reverse iteration to node: %d\n",
      victim->lineno);
    psurround (&victim);
  } else
    while (node--)
      victim = victim->next;

  // non-self-reference node means just rewire
  if (victim != victim->next) {
    (victim->prev)->next = victim->next;
    (victim->next)->prev = victim->prev;
    // If we are deleting the first item, then we need to change the passed in pointer
    if (victim == *list)
      *list = victim->next;
  } else {      // deleted node was self-referenced. last node
    *list = NULL;
  }

  free (victim);  // delete the node
}

Also, change your debugging output function psurround to print out the pointer values, rather than the addresses of the pointer variables:

void
psurround (rec **list) {

    fprintf (stderr, "%2d - prev: %p  cur: %p  next: %p\n",
        (*list)->prev->lineno,
        (*list)->prev->prev,
        (*list)->prev,
        (*list)->prev->next);
    fprintf (stderr, "%2d - prev: %p  cur: %p  next: %p\n",
        (*list)->lineno, (*list)->prev, *list, (*list)->next);
    fprintf (stderr, "%2d - prev: %p  cur: %p  next: %p\n\n",
        (*list)->next->lineno,
        (*list)->next->prev,
        (*list)->next,
        (*list)->next->next);
}

In general, I think any time you have multiple &s and *s in the same term (like *&(*list)), you need to rethink what is going on.