Doubly linked list

[Joe Estock]

I'm attempting to sort a doubly linked list at the time that an item is
added. When I add the items in increasing order everything works
correctly, however when I add them in reverse order the correlation is
messed up. The list, however, is sorted except for element 0 (or
whatever value was the first to be added). I've been working on this
most of the night so maybe I am overlooking something. Any help would be
much appreciated. Below is a minimal example that can be compiled (sorry
for the length of the code, however I couldn't make it any smaller).

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

enum { false, true };

typedef int bool;

struct dll_t
{
int val;
struct dll_t *next;
struct dll_t *prev;
};

#define compare(x, y) memcmp(x, y, sizeof(x))

#define icompare(x, y) ((x) - (y))

bool add_node_value(struct dll_t **dll, int val);

int main(void)
{
struct dll_t *dll;
struct dll_t *p;
int i;

dll = NULL;

/* this works perfectly */
/*for(i = 0; i < 10; i++)
add_node_value(&dll, i);*/

/* this does not */
for(i = 9; i > -1; i--)
add_node_value(&dll, i);

printf("walking\n");

for(p = dll; p; p = p->next)
{
printf("%d (p: %d n: %d)\n", p->val,
p->prev == NULL ? -1 : p->prev->val,
p->next == NULL ? -1 : p->next->val);
}

return(0);
}

bool add_node_value(struct dll_t **dll, int val)
{
struct dll_t *tmp;
struct dll_t *p;

tmp = malloc(sizeof(*tmp));
tmp->next = NULL;
tmp->val = val;

if(*dll == NULL)
{
tmp->prev = NULL;
*dll = tmp;
return(true);
}

p = *dll;
printf("icompare(%d, %d) = %d\n",
val, p->val, icompare(val, p->val));

if(icompare(tmp->val, p->val) > 0)
{
/* tmp->val is larger - insert tmp after p */
for(p = *dll; (val > p->val) && p != NULL; p = p->next)
{
if(p->next == NULL)
break;
}

tmp->prev = p;
tmp->next = p->next;
p->next = tmp;

printf("p->prev: %d p->val: %d p->next: %d\n",
p->prev == NULL ? -1 : p->prev->val, p->val,
p->next == NULL ? -1 : p->next->val);
}
else
{
/* tmp->val is smaller - insert p before tmp */
for(p = *dll; (tmp->val < p->val) && p != NULL; p = p->next)
{
if(p->next == NULL)
break;
}

/* this is where the problem is */
tmp->prev = (*dll);
tmp->next = (*dll)->next;
(*dll)->next = tmp;

printf("p->prev: %d p->val: %d p->next: %d\n",
p->prev == NULL ? -1 : p->prev->val, p->val,
p->next == NULL ? -1 : p->next->val);
}

return(true);
}

 

[Ulrich Eckhardt]

struct dll_t
{
int val;
struct dll_t *next;
struct dll_t *prev;
};

#define compare(x, y) memcmp(x, y, sizeof(x))
#define icompare(x, y) ((x) - (y))

Those look at the very least suspicious.

bool add_node_value(struct dll_t **dll, int val);

What does the returnvalue mean?

bool add_node_value(struct dll_t **dll, int val)
{
struct dll_t *tmp;
struct dll_t *p;

tmp = malloc(sizeof(*tmp));
tmp->next = NULL;
tmp->val = val;

if(*dll == NULL)
{
tmp->prev = NULL;
*dll = tmp;
return(true);
}

Just as a note, I would not have initialised tmp->next to NULL right after
malloc() but here when it's clear that it's the first element of the list.

p = *dll;
printf("icompare(%d, %d) = %d\n",
val, p->val, icompare(val, p->val));

OK, here you use memcmp() over the whole structure, including two pointers
that should not be significant and and possible padding bytes. Overall,
this makes the outcome of icompare() meaningless.

[snipped insertion]

And here you sort the element into the list based on insignificant and
meaningless values.

return(true);

return is not a function.

cheers

Uli

 

[Joe Estock]

Those look at the very least suspicious.

How so? icompare is quite obvious...if x - y is negative then x < y,
otherwise if x - y is zero then x == y, otherwise x > y. They don't look
at all suspicious to me.

What does the returnvalue mean?

Success or failure. Hence they reason for bool.

Just as a note, I would not have initialised tmp->next to NULL right after
malloc() but here when it's clear that it's the first element of the list.

I don't see any benifit from changing it that way other than
clarification of the code, perhaps. Advice noted.

OK, here you use memcmp() over the whole structure, including two pointers
that should not be significant and and possible padding bytes. Overall,
this makes the outcome of icompare() meaningless.

Not correct and not correct. icompare does not get expanded to memcmp();
that's compare that you are thinking of. The outcome of icompare is in
fact not meaningless.

[snipped insertion]

And here you sort the element into the list based on insignificant and
meaningless values.

According to you they are meaningless values, however you should have
left at least the relevant code to which you were replying to intact in
case my original article expires before someone reading this has a
chance to look at it.

return is not a function.

I know that. I've used return in this fashion for the past several
years. Old habits die hard. Since it is not functionally different
either way, it's a matter of preference.

cheers

Uli

Thanks for attempting to help me understand what is going on, however I
am still just as clueless as I was when I first posted this.

Joe

 

[CBFalconer]

I'm attempting to sort a doubly linked list at the time that an
item is added. When I add the items in increasing order everything
works correctly, however when I add them in reverse order the
correlation is messed up. The list, however, is sorted except for
element 0 (or whatever value was the first to be added). I've been
working on this most of the night so maybe I am overlooking
something. Any help would be much appreciated. Below is a minimal
example that can be compiled (sorry for the length of the code,
however I couldn't make it any smaller).

I fixed your descending problem and your walking problem
(surprise!). When you look at the fixes I think you will see the
ascending insert also has problems. Don't forget to consider the
equality cases.

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

enum { false, true };

typedef int bool;

struct dll_t
{
int val;
struct dll_t *next;
struct dll_t *prev;
};

#define compare(x, y) memcmp(x, y, sizeof(x))

#define icompare(x, y) ((x) - (y))

bool add_node_value(struct dll_t **dll, int val);

int main(void)
{
struct dll_t *dll;
struct dll_t *p;
int i;

dll = NULL;

/* this works perfectly */
/*for(i = 0; i < 10; i++)
add_node_value(&dll, i);*/

/* this does not */
for(i = 9; i > -1; i--)
add_node_value(&dll, i);

printf("walking\n");

p = dll;
while (p && p->prev) p = p->prev; /* find smallest */
while (p) {
printf("%d (p: %2d n: %2d)\n",
p->val,
p->prev == NULL ? -1 : p->prev->val,
p->next == NULL ? -1 : p->next->val);
p = p->next;
}

/* for(p = dll; p; p = p->next)
{
printf("%d (p: %d n: %d)\n", p->val,
p->prev == NULL ? -1 : p->prev->val,
p->next == NULL ? -1 : p->next->val);
}
*/
return(0);
}

bool add_node_value(struct dll_t **dll, int val)
{
struct dll_t *tmp;
struct dll_t *p;

tmp = malloc(sizeof(*tmp));
tmp->next = NULL;
tmp->val = val;

if(*dll == NULL)
{
tmp->prev = NULL;
*dll = tmp;
return(true);
}

p = *dll;
printf("icompare(%d, %d) = %d\n",
val, p->val, icompare(val, p->val));

if(icompare(tmp->val, p->val) > 0)
{
/* tmp->val is larger - insert tmp after p */
for(p = *dll; (val > p->val) && p != NULL; p = p->next)
{
if(p->next == NULL)
break;
}

tmp->prev = p;
tmp->next = p->next;
p->next = tmp;

printf("p->prev: %d p->val: %d p->next: %d\n",
p->prev == NULL ? -1 : p->prev->val, p->val,
p->next == NULL ? -1 : p->next->val);
}
else
{
/* tmp->val is smaller - insert p before tmp */
/* for(p = *dll; (tmp->val < p->val) && p != NULL; p = p->next)
{
if(p->next == NULL)
break;
}
*/
/* this is where the problem is */
/* tmp->prev = (*dll);
tmp->next = (*dll)->next;
(*dll)->next = tmp;
*/

while (p->prev && (icompare(tmp->val, p->val) <= 0))
p = p->prev;

tmp->prev = p->prev;
tmp->next = p;
p->prev = tmp;
if (tmp->prev) tmp->prev->next = tmp;

printf("p->prev: %d p->val: %d p->next: %d\n",
p->prev == NULL ? -1 : p->prev->val, p->val,
p->next == NULL ? -1 : p->next->val);
}

return(true);
}

Now build a separate callable list display mechanism, and build the
lists by inserting random values, which you can get from rand().
Note that your dll variable points somewhere within the list, not
to either end. Consider end effects, including the empty list.

--
Some informative links:
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

 

[Ulrich Eckhardt]

How so? icompare is quite obvious...if x - y is negative then x < y,
otherwise if x - y is zero then x == y, otherwise x > y. They don't look
at all suspicious to me.

There are two things that strike me as dangerous here
1. they are macros
This could have the reason that they need to be generic, i.e. work with
different types but often they can be replaced with static inline
functions that protect you from side-effects.
2. they don't add much
In particular the second one would be much better spelled out, so you can
immediately see what they are for. Anyhow, that point is mostly one of
taste, though some people would even question the first one.

Not correct and not correct. icompare does not get expanded to memcmp();
that's compare that you are thinking of. The outcome of icompare is in
fact not meaningless.

Right, I was wrong. This uses the integer comparison while the really
dangerous memcmp() comparison is in fact unused here. Sorry, I think I
just saw what I wanted to see....

BTW: you should return false when malloc() returns NULL.

Uli

 

[Keith Thompson]

#define icompare(x, y) ((x) - (y))

If the subtraction overflows, this invokes undefined behavior.
Consider icompare(MIN_INT, MAX_INT).

And your calls to icompare:

printf("icompare(%d, %d) = %d\n",
val, p->val, icompare(val, p->val));

if(icompare(tmp->val, p->val) > 0)
{

[...]

would be much clearer if you just compared the values directly:

if (tmp->val > p->val)
{
...
}

You also use printf to display the result of the call to icompare; if
you like, you can do that too:

printf("(%d > %d) = %d\n",
val, p->val, val > p->val);

 

[Barry Schwarz]

I'm attempting to sort a doubly linked list at the time that an item is
added. When I add the items in increasing order everything works
correctly, however when I add them in reverse order the correlation is
messed up. The list, however, is sorted except for element 0 (or
whatever value was the first to be added). I've been working on this
most of the night so maybe I am overlooking something. Any help would be
much appreciated. Below is a minimal example that can be compiled (sorry
for the length of the code, however I couldn't make it any smaller).

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

enum { false, true };

typedef int bool;

struct dll_t
{
int val;
struct dll_t *next;
struct dll_t *prev;
};

#define compare(x, y) memcmp(x, y, sizeof(x))

You don't use this and it wouldn't work for negative numbers.

#define icompare(x, y) ((x) - (y))

bool add_node_value(struct dll_t **dll, int val);

int main(void)
{
struct dll_t *dll;
struct dll_t *p;
int i;

dll = NULL;

/* this works perfectly */
/*for(i = 0; i < 10; i++)
add_node_value(&dll, i);*/

/* this does not */
for(i = 9; i > -1; i--)
add_node_value(&dll, i);

printf("walking\n");

for(p = dll; p; p = p->next)
{
printf("%d (p: %d n: %d)\n", p->val,
p->prev == NULL ? -1 : p->prev->val,
p->next == NULL ? -1 : p->next->val);
}

return(0);
}

bool add_node_value(struct dll_t **dll, int val)
{
struct dll_t *tmp;
struct dll_t *p;

tmp = malloc(sizeof(*tmp));

You should check for success.

tmp->next = NULL;
tmp->val = val;

if(*dll == NULL)
{
tmp->prev = NULL;
*dll = tmp;
return(true);
}

p = *dll;
printf("icompare(%d, %d) = %d\n",
val, p->val, icompare(val, p->val));

While it is true that val and tmp->val are equal here, if you are
going to print out debugging information like this it ought to match
what your code is testing. Your test will be against tmp->val.

if(icompare(tmp->val, p->val) > 0)
{
/* tmp->val is larger - insert tmp after p */
for(p = *dll; (val > p->val) && p != NULL; p = p->next)

p is already set to *dll.

Your previous test was against tmp->val, this test is against val. You
should be consistent to avoid problems if you ever modify the code.

Your test expression is in the wrong order. When you reach the end of
the list and p becomes NULL, you attempt to dereference it before you
check to see if it is NULL.

But then you avoid the problem with the test in the next two lines so
this one is redundant.

{
if(p->next == NULL)
break;
}

tmp->prev = p;
tmp->next = p->next;
p->next = tmp;

printf("p->prev: %d p->val: %d p->next: %d\n",
p->prev == NULL ? -1 : p->prev->val, p->val,
p->next == NULL ? -1 : p->next->val);

All the p-> here should be tmp-> since you want to see the newly
inserted node along with its predecessor and successor. The code you
have will show the new node, the preceding node, and the one before
that (in the reverse order). For debugging purposes, you don't know
that the successor node has a value greater than the new node.

}
else
{
/* tmp->val is smaller - insert p before tmp */

you seem to have forgotten about equals which is processed by this
code also.

for(p = *dll; (tmp->val < p->val) && p != NULL; p = p->next)

This is backwards. If tmp->val < p->val, you want to look at p->prev,
not p->next. However, since you list is in ascending order and you
have already established that tmp->val < first element, the only
option is to put tmp at the head of the list. All the code in this
else block (except the debug printf) should be replaced with the
changes noted below.

{
if(p->next == NULL)
break;
}

/* this is where the problem is */

There are two problems. The loop above is backwards and you want to
replace the three following with
tmp->next = p;
p->prev = tmp;
*dll = tmp;

tmp->prev = (*dll);
tmp->next = (*dll)->next;
(*dll)->next = tmp;

printf("p->prev: %d p->val: %d p->next: %d\n",
p->prev == NULL ? -1 : p->prev->val, p->val,
p->next == NULL ? -1 : p->next->val);

All the p-> here should be tmp-> since you want to see the newly
inserted node along with its non-existent predecessor and successor.

}

return(true);
}

Remove del for email