A doubly linked-list in C

[arnuld]

This program compiles fine but has semantic error, I am unable to find it.
I am trying to learn Linked-List implementation in C:

WANTED: Values to be added to the First element.
PROBLEM: it always says first element has values, even when the first element has NULL values


/* A doubly linked list implementation in C. I add some values and then remove some. Each element is a struct and
* we use key to identify the element.
*
* VERISON 1.0
*
*/


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



enum {
SIZE_KEY = 10,
SIZE_VALUE = 20
};


struct KV_pair
{
char key[SIZE_KEY];
char value[SIZE_VALUE];
struct KV_pair* next;
struct KV_pair* prev;
};


void add_pair(struct KV_pair *const base, char* k, char* v );
struct KV_pair* add_element_to_list(struct KV_pair *const base, struct KV_pair* ps);
struct KV_pair* find_element(struct KV_pair *const base, struct KV_pair* f );

void print_pair(struct KV_pair *const );

int main(void)
{
struct KV_pair* baseElement = malloc( 1 * (sizeof *baseElement));

if( NULL == baseElement )
{
fprintf(stderr, "IN: %s, at %d, malloc() failed\n", __FILE__, __LINE__);
exit( EXIT_FAILURE );
}

memset(baseElement, '\0', sizeof(baseElement));

add_pair(baseElement, "k1", "v1");

print_pair(baseElement);


return 0;
}



void add_pair(struct KV_pair *const base, char* k, char* v )
{
struct KV_pair* s = malloc( 1 * sizeof(*s));

if( NULL == s )
{
fprintf(stderr, "IN: %s, at %d: malloc() failed\n", __FILE__, __LINE__);
}
else if( NULL == base->key )
{
struct KV_pair* temp = base;
printf("List is empty first element to add\n");
strcpy(temp->key, k);
strcpy(temp->value, v);
free(s);
s = NULL;
}
else
{
printf("List already has some elements\n");
strcpy(s->key, k);
strcpy(s->value, v);

if( add_element_to_list(base, s) )
{
printf("Element added\n");
}
else
{
printf("unable to add the element\n");
}
}
}


struct KV_pair* add_element_to_list(struct KV_pair *const base, struct KV_pair* ps)
{
struct KV_pair* b = find_element(base, ps);

if( b )
{
printf("IN: %s, at %d, Element already exists, can not add\n", __FILE__, __LINE__);
return ps;
}
else
{
printf("DUMMY addition, will write this part later\n");
return ps;
}

return NULL;
}


struct KV_pair* find_element(struct KV_pair *const base, struct KV_pair* f )
{
struct KV_pair* b = base;

if( b )
{
for( ; NULL != b; b = b->next )
{
if( 0 == strcmp(b->key, f->key) )
{
return b;
}
}
}

return NULL;
}


void print_pair(struct KV_pair *const base)
{
struct KV_pair* b = base;

for( ; NULL != b; b = b->next )
{
printf("Key = %s\n", b->key);
printf("Value = %s\n", b->value);
printf("----------\n");
}
}
===================== OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra doubley-LL.c
[arnuld@dune programs]$ ./a.out
List already has some elements
DUMMY addition, will write this part later
Element added
Key =
Value =

 

[Kaz Kylheku]

void add_pair(struct KV_pair *const base, char* k, char* v )
{
struct KV_pair* s = malloc( 1 * sizeof(*s));

if( NULL == s )
{
fprintf(stderr, "IN: %s, at %d: malloc() failed\n", __FILE__, __LINE__);
}
else if( NULL == base->key )

This comparison will never be true because base->key is an array, not
a pointer.

{
struct KV_pair* temp = base;
printf("List is empty first element to add\n");
strcpy(temp->key, k);
strcpy(temp->value, v);
free(s);
s = NULL;

So this will never happen.

}
else
{
printf("List already has some elements\n");
strcpy(s->key, k);
strcpy(s->value, v);

if( add_element_to_list(base, s) )
{
printf("Element added\n");
}
else
{
printf("unable to add the element\n");
}

This block does nothing because add_element_to_list is an incomplete
stub. The KV_Pair pointed at by s is not added to the list, and is instead
leaked (the program loses its one and only pointer to that object).

===================== OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra doubley-LL.c
[arnuld@dune programs]$ ./a.out
List already has some elements

So this is the consequence of the silly base->key == NULL comparison that
is always false, since the pointer to the first element of an array is not
a null pointer.

DUMMY addition, will write this part later
Element added

THe element was not added, since that is not finished.

Key =
Value =

And so you end up with a list that contains only the based node. The key and
value arrays have been overwritten with zeros, so they are empty strings.

Machine does what you tell it, not what you want.

 

[arnuld]

This comparison will never be true because base->key is an array, not
a pointer.

:-\

and I thought when we access the values then arrays and pointers are same.
I am programming in C from last 6 months, I really don't understand how
long does it take to understand this pointer business and the
pointer-array business.

So this is the consequence of the silly base->key == NULL comparison
that is always false, since the pointer to the first element of an array
is not a null pointer.

I did a memset() on it. memset() fills an array with NULLs. '\0' is the
NULL


I am programming in C from last 6 months, I really don't understand how
long does it take to understand this pointer business and the
pointer-array business.

 

[BartC]

This program compiles fine but has semantic error, I am unable to find it.
I am trying to learn Linked-List implementation in C:

WANTED: Values to be added to the First element.
PROBLEM: it always says first element has values, even when the first
element has NULL values

struct KV_pair
{
char key[SIZE_KEY];
char value[SIZE_VALUE];
struct KV_pair* next;
struct KV_pair* prev;
};


void add_pair(struct KV_pair *const base, char* k, char* v );
struct KV_pair* add_element_to_list(struct KV_pair *const base, struct
KV_pair* ps);
struct KV_pair* find_element(struct KV_pair *const base, struct KV_pair*
f );

void print_pair(struct KV_pair *const );

int main(void)
{
struct KV_pair* baseElement = malloc( 1 * (sizeof *baseElement));

if( NULL == baseElement )
{
fprintf(stderr, "IN: %s, at %d, malloc() failed\n", __FILE__,
__LINE__);
exit( EXIT_FAILURE );
}

memset(baseElement, '\0', sizeof(baseElement));

I think you need sizeof(*baseElement) here, otherwise you might only clear 4
bytes instead of 40 for example. Or just use sizeof(struct KV_pair).

else if( NULL == base->key )

As already pointed out, you need to use base->key[0]==0, or
strcmp(base->key,"")==0. Or change KV_pair to store key/value strings in
allocated memory (then you don't have limits on their lengths, although
deleting is a bit more work).

Your linked list logic seems a little strange (to me): your empty linked
list starts with a dummy node containing empty key/value pairs. Normally
you'd start with a NULL root (baseEelement) which subsequently points to the
first element which is added.

(In add_pair(), you allocate space for a new element (s), then immediately
free it if this is the first element.)

Your malloc error checking code is comprehensive (and commendable) but it
does tend to obscure the logic (I wouldn't bother it myself, not until the
thing works, although the advice here might be different).

 

[Phil Carmody]

Incorrect.

Good start - 1 error in 1 word.

The -> operator has a higher precedence than ==.

Irrelevant. 1 error and 1 irrelevancy in 1 sentence and 1 word.

And base->key is an element of the array, not the complete
array.

Back to errors again. You're doing well. 2 errors and 1
irrelevancy in 2 sentences and 1 word.

And, btw, an implementation-dependent macro like
NULL on the left side of an operator is not terribly
suitable, either.

I'll call that an error too, as they can be perfectly
suitable, so a blanket statement that they're not is
false. 3 errors and 1 irrelevancy in 3 sentences and 1
word. Great pace - can you keep it up?

Owing to the operator precedence,

else if( base->key == NULL )

is equivalent.

Another irrelevancy. Not as good as an error, but still a
brave attempt. 3 errors and 2 irrelevancies in 4 sentences
and 1 word.

You need to keep the operator precedence rules in mind,
unless you want to use a lot of parens.

It's still irrelevant to the problem at hand. 3 errors and 3
irrelevancies in 5 sentences and 1 word.

base->key is an array of characters. Wherever it appears
in the course, if it cannot logically be interpreted as
that actual array (such as in a context like sizeof), then
it will be interpreted as a pointer to the address of the
first element of the array. If base points to a valid
object, then base->key can never be NULL. If base does not
point to a valid object, then base->key is an invalid
expression. If the OP wanted to check the character _at_
(the first slot of the array) base->key, he should have
dereferenced it with either * or [].

Phil

 

[Kaz Kylheku]

Simply passing the reference does not say anything about the
contents of the struct or array. C decouples the semantics
of passing on the reference from the actual contents of the
struct or array. And so this is intended.

I missed an announcement here. Is there a competition to post the dumbest
article that shows a lack of C knowledge, yet manages to use the words
``decouple'', ``semantics'' and ``portable''?

Aha, trolling.

I'll try to illustrate these cases

I recommend watercolor, or /washable/ crayons.

 

[Flash Gordon]

Simply passing the reference does not say anything about the
contents of the struct or array. C decouples the semantics
of passing on the reference from the actual contents of the
struct or array. And so this is intended.

C does not have the concept of passing a reference. It has the concept
of passing a value and, if you want to consider it a separate concept,
passing a pointer value.

The struct definition was
struct KV_pair
{
char key[SIZE_KEY];
char value[SIZE_VALUE];
struct KV_pair* next;
struct KV_pair* prev;
};

The function declarations were
void add_pair(struct KV_pair *const base, char* k, char* v );
struct KV_pair* add_element_to_list(struct KV_pair *const base, struct
KV_pair* ps);
struct KV_pair* find_element(struct KV_pair *const base, struct KV_pair*
f );

void print_pair(struct KV_pair *const );

So base is a pointer to a struct KV_pair, and base->key is the array key
in the struct. So base could be a null pointer, in which case evaluating
base->key is undefined behaviour, but if base is a valid pointer it is
impossible for base->key to be a null pointer or compare equal to one.

The else clause above only tests whether base->key has a
memory area associated with it.

No, it doesn't. See above.

To get the actual beginning character of base->key you would
need *base->key, equivalent to base->key[0],

No, in almost all situations base->key will give you the address of the
first element, your suggestion will always give you the contents of the
first element.

but those are
dependent on the semantics of a * types and more portable to
use a subscript and leave the pointer addition to the
compiler.

<snip more stuff based on misconceptions>

What are you talking about?

If in every case the program previously contained the
statement,

base -> key = NULL;

<snip>

If it did then the compiler would be required to issue a diagnostic, and
I strongly suspect that almost all compilers would abort the compilation
with an error.

Because as a macro, NULL can expand to 0, 0L, ((void *)0),

Yes, but irrelevant.

((void *)(*fn)()),

Not that though.

or just about any other construct that
refers to a zero memory location,

It has nothing to do with a zero memory location.

depending on the compiler,
C dialect, and the machine.

On ALL implementations it is a constant expression with a value of 0 or
such an expression cast to void*

A compiler should be
able to accomplish the type cast to a char * array, but
often there are machine dependent factors.

No, there are no machine dependent factors. It is REQUIRED to work.

If, above, base
were not a single scalar address, the construct would almost
certainly not be valid without some serious type casting.

What are you talking about? We know exactly what type it is, the only
other considerations are whether it contains a null pointer and whether
it contains a valid pointer.

Since NULL, as a simple scalar, is less dependent on
alignment issues,

Allignment issues are completely irrelevant.

it is easier to (or at least more
intuitive) to let the base->key, which can potentially have
various alignments in memory, dictate the scalar types and
alignments that == is going to need for either operand. And
the assumption that macro NULL expands correctly in all contexts,
while reasonable with most compilers, is not always certain.

You seem to have severe problems with your understanding of the
situation. NULL is required to expand correctly, and the rest of what
you are saying seems to be based on misconceptions as well.

In this case, certainly. I'd also say that a non-trivial program
would need to check for unforseen cases. (Maybe not to the point
of unplugging the hard drive in the middle of a run, but nearly.)

Again, irrelevant to the issues at hand.

 

[Keith Thompson]

:-\

and I thought when we access the values then arrays and pointers are same.
I am programming in C from last 6 months, I really don't understand how
long does it take to understand this pointer business and the
pointer-array business.

About as long as it takes to read and understand section 6 of the
comp.lang.c FAQ, <http://www.c-faq.com>.

The relationship between arrays and pointers in C really isn't all
that complicated. Arrays and pointers are two very different things.
The trouble is that certain C constructs almost seem to conspire to
confuse them, making it *seem* like they're the same thing in certain
contexts. You just have to learn to understand a piece of code that
uses arrays and pointers in terms of what's actually going on, rather
than just looking at the syntax.

Arrays are not pointers.
Pointers are not arrays.
Read section 6 of the FAQ.

I did a memset() on it. memset() fills an array with NULLs. '\0' is the
NULL

Nope. (Others have explained this.)

 

[jameskuyper]

Simply passing the reference does not say anything about the
contents of the struct or array. C decouples the semantics
of passing on the reference from the actual contents of the
struct or array. And so this is intended.

The else clause above only tests whether base->key has a
memory area associated with it.

If base is a dereferencable pointer to a struct KV_pair object, there
must be a memory area associated with base->key; otherwise, the
behavior is undefined, rendering the test meaningless.

To get the actual beginning character of base->key you would
need *base->key, equivalent to base->key[0], but those are
dependent on the semantics of a * types and more portable to
use a subscript and leave the pointer addition to the
compiler.

The standard defines (6.5.2.1p2) the behavior of base->key[0] as being
equivalent to *(base->key + 0), and it defines the behavior of pointer
addition (6.5.6p8) such that base->key+0 is the same as base->key, so
if base->key[0] does not have the same behavior as *base->key, the
implementation is non-conforming.

... If base itself is an array of pointer,

The type of 'base' is "struct KV_pair *"; that's not an array of
pointers, that's a pointer; possibly to a single struct KV_pair
object, possibly to a member of an array.

If base were an array of pointer, then the expression base->key would
be a constraint violation; you can only apply the -> operator to
pointers to structures (6.5.2.3p1), not to arrays; not even if those
arrays contain pointers to structures.

....

I'll try to illustrate these cases, if you'll please excuse
the lecture.

If in every case the program previously contained the
statement,

base -> key = NULL;

base->key is an array, and is therefore not a modifiable lvalue
(6.3.2.1p1) so it cannot be set equal to NULL. Such code would be a
constraint violation (6.5.16p2).

then the test above would be valid (The program would also
need to free () the memory pointed to by base -> key).

Since key is an array member of the struct pointed at by "base", the
only way to free() the memory pointed at by base->key would be to free
() the memory associated with the object pointed at by "base".

However, if the program previously had the statement

strcpy (base -> key, "");

or

base -> key[0] = '\0';

Then the test would not always be valid, because base->key still
would have a memory area associated with it.

If base->key did not already have a memory area associated with it,
both of those constructs would have undefined behavior. If it did have
a memory area associated with it, writing data into that memory would
have no affect on whether or not such a memory area was associated
with data->key.

....

Because as a macro, NULL can expand to 0, 0L, ((void *)0),
((void *)(*fn)()), or just about any other construct that
refers to a zero memory location, depending on the compiler,
C dialect, and the machine.

Referring to a zero memory location is not one of the requirements for
being a null pointer constant. The requirements are "An integer
constant expression with the value 0, or such an expression cast to
type void *" (6.3.2.3p3). The expansion of NULL is implementation-
dependent, but the fact that it must be a null pointer constant is
specified by the standard, and every legitimate use of NULL depends
only upon the fact that it is a null pointer constant.

You don't specify what fn is; if it's a macro, there's a possibility
that that ((void *)(*fn)()) might qualify as a null pointer constant.
However, as the identifier of either a function or an object, it runs
afoul of the requirement that an integer constant expression "shall
only have operands that are integer constants, enumeration constants,
character constants, sizeof expressions whose results are integer
constants, and floating constants that are the immediate operands of
casts." If 'fn' were any of those things, then *fn would be a
constraint violation. If it's not one of those things, NULL is not
allowed to expand into ((void *)(*fn)()).

Furthermore, 'fn' is not a reserved name. As a result, strictly
conforming code is allowed to give it a definition, and the
implemenation is not. It's trivial to give fn a defintion that makes
((void *)(*fn)()) unambiguously not a null pointer constant, and
therefore not a permitted expansion for the NULL macro.

... A compiler should be
able to accomplish the type cast to a char * array, but
often there are machine dependent factors.

Regardless of any of the machine-dependent factors you're concerned
with, NULL is required to be a null pointer constant (7.17p3). When
occurring in a context such as the one above, a null pointer constant
is required to be converted the same type as base->key (6.9.5p5),
which is a pointer type (6.3.2.1p3). A null pointer constant converted
to a pointer type, becomes a null pointer of that type (6.3.2.3p3). A
null pointer is required to compare unequal to any pointer which
points at an actual object (6.5.9p6). If base->key has defined
behavior, then base->key is an actual object, and the expression base-

key == NULL is therefore guaranteed to evaluate to 'false'.

... If, above, base
were not a single scalar address, the construct would almost
certainly not be valid without some serious type casting.

If that were true, it would render the implementation non-conforming.

....

alignment issues, it is easier to (or at least more
intuitive) to let the base->key, which can potentially have
various alignments in memory, dictate the scalar types and
alignments that == is going to need for either operand.

It does. That's what the standard specifies for null pointer constants
(6.9p5).

... And
the assumption that macro NULL expands correctly in all contexts,
while reasonable with most compilers, is not always certain.

It's certain on conforming compilers.

 

[CBFalconer]

This program compiles fine but has semantic error, I am unable to
find it. I am trying to learn Linked-List implementation in C:

WANTED: Values to be added to the First element.
PROBLEM: it always says first element has values, even when the
first element has NULL values

Write down the structure of the list when empty, with 1 item, with
2 items. For example, there is always something to mark the
existence of the list:

typedef struct marker {datum *next; datum *prev;} marker;
typedef struct datum {marker mark; foo /* actual data */} datum;

marker list = {NULL, NULL); /* empty - nothing more */

Now what does a list with one item look like?

list: ptr ptr /* both ptrs point to datum */
datum /* whose marker component points are NULL

Now try two elements. Remember list is always known to everybody.

list ptr1 ptr2 /* no longer the same */
datum #1 /* pointed to by ptr1 */
/* its marker ptrs are next to datum#2, prev to NULL */
datum #2 /* pointed to by ptr2 */
/* marker ptrs are next to NULL, prev to datum#1 */

Now work out how the list appears with three items in it. Make
sure you can always tell when you get to the end (or beginning) of
the list. Check the operations needed to insert an item at the
beginning, end, middle. Same to delete items.

You can write lots of code from that. The details of what the list
holds are controlled by foo. Other things are detailed, and you
can create code to manipulate, search, insert, delete, whatever.

 

[CBFalconer]

.... snip ...

C does not have the concept of passing a reference. It has the
concept of passing a value and, if you want to consider it a
separate concept, passing a pointer value.

Disagree. It has the concept, but it isn't named a 'reference'.
It is implemented by passing a pointer (by value) to the item to be
'referenced'.

Note the additional flexibility. That pointer itself can be
'referenced'. The code using that 2nd level of referencing can
access the first pointer (with one *) or the original item (with
two *s). You can't play these games with languages that have
fundamental references.

 

[Kaz Kylheku]

Disagree. It has the concept, but it isn't named a 'reference'.

From C99:

A pointer type may be derived from a function type, an object type, or an
incomplete type, called the referenced type. A pointer type describes an
object whose value provides a reference to an entity of the referenced type.
A pointer type derived from the referenced type T is sometimes called
"pointer to T". The construction of a pointer type from a referenced type is
called "pointer type derivation"

 

[Ben Pfaff]

Here's my favorite null pointer constant

('-'-'-')

Here's my least favorite null pointer constant:
x
given
enum { x, y, z };
Always seems like it should give a type mismatch error when I
accidentally pass it as a function argument of pointer type but,
of course, it does not.

 

[Phil Carmody]

it will be interpreted as a pointer to the address of the

Either 'pointer to' or 'address', not both.

Phil

 

[Phil Carmody]

rkiesling said:

So?

Oh, I missed that bit. What's this "zero memory location"
that he's refering to? I can't find it mentioned in the
usual references.

Phil

 

[Phil Carmody]

C does not have the concept of passing a reference.

Oh yes it does!

It has the concept
of passing a value and, if you want to consider it a separate concept,
passing a pointer value.

Such pointer passing is *explicitly* described as passing a reference.
The concept is passing by reference, the technique used for passing
by reference is passing a pointer by value.

Phil

 

[Ian Collins]

Here's my least favorite null pointer constant:
x
given
enum { x, y, z };
Always seems like it should give a type mismatch error when I
accidentally pass it as a function argument of pointer type but,
of course, it does not.

Another area where C++ is a "safer C"!

 

[Phil Carmody]

Another area where C++ is a "safer C"!

C++ pushers will say anything to defend their sick religion!

;-)

Phil

 

[Ian Collins]

C++ pushers will say anything to defend their sick religion!

Humbug!

 

[Flash Gordon]

From C99:

A pointer type may be derived from a function type, an object type, or an
incomplete type, called the referenced type. A pointer type describes an
object whose value provides a reference to an entity of the referenced type.
A pointer type derived from the referenced type T is sometimes called
"pointer to T". The construction of a pointer type from a referenced type is
called "pointer type derivation"

OK, it has a concept of a reference (just as it has the concept of an
object) but it isn't what a lot of people mean when they talk about
references, just as a lot of people don't mean object in the C standard
sense when they talk about objects.