A doubly linked-list in C

[James Kuyper]

If the root is NULL, how am I supposed to use "root->next = p" ?

You don't; when you add the first element, you use root=p.

 

[BartC]

If the root is NULL, how am I supposed to use "root->next = p" ?

You don't. You need to use some logic to deal with the very first node:

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

Or something similar.

(This will extend the list in reverse order; to keep root pointing at the
oldest element, maintain a separate pointer to the last element.

Also, if root is a parameter to a function, you really need to pass &root,
and use *root above, so that it can be updated)

But you must have seen plenty of example code? And did empty lists make use
of dummy nodes? That would be something new to me.

 

[lawrence.jones]

Keith Thompson said:

So would I. Is Larry around? Perhaps he could expand.

I'm here, but I don't have much to add. We try to be very precise in
the actual text of the standard, but examples and footnotes are
intentionally written in a more casual (and, hopefully, more accessible)
style. The (mis)usage in 7.11.1.1 bothers me when taken out of context,
but in context the intent seems perfectly clear and a more precise
statement would, as Keith said, be much clumsier.

 

[Default User]

It means if I put an array inside a struct, then it will be passed as
a whole rather than a pointer ?

Yes. You can see for yourself by using the sizeof operator on such a
struct member.

2nd, if I try to access that array (member of struct), e.g. lets say I
pass it to function, then it will still be passed as pointer.

Pass what to a function? The array that is a member of the struct? As
it says above, it's never possible to pass an array to a function. You
can't even declare a parameter for that, so how could you?




Brian

 

[Keith Thompson]

It means if I put an array inside a struct, then it will be passed as
a *whole* rather than a pointer ?

Yes, unless you explicitly take the struct's address. Unlike array
expressions, struct expressions aren't implicitly converted to
pointers. And you can have parameters of struct (or union) type, and
you use "==" to assign struct or union values.

You can always achieve the effect of passing a struct by reference by
declaring the parameter as a pointer-to-struct, and passing the
address to the function. With structs, unlike with arrays, you can
choose either to pass the whole thing (by value), or to pass the
address.

2nd, if I try to access that array (member of struct), e.g. lets say I
pass it to function, then it will still be passed as pointer.

Just as for any other expression of array type, yes.

 

[Beej Jorgensen]

In C, try passing an array ***at all***. It can't be done, at least
not without tucking the array inside a struct or union.

I have a question on this... well, it's perhaps a more general question.

If a compiler detects that it's safe to do so, is it free to optimize
out the struct copy and use a pointer instead? Do any compilers do
this?

-Beej

 

[Beej Jorgensen]

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.

It is rarer, but not unheard-of:

http://en.wikipedia.org/wiki/Linked_list#Sentinel_nodes

Several profs I knew would teach linked lists with dummy nodes to spare
students some of the pain.

I personally never cared much for the dummy nodes either.

-Beej

 

[luserXtrog]

I have a question on this... well, it's perhaps a more general question.

If a compiler detects that it's safe to do so, is it free to optimize
out the struct copy and use a pointer instead?  Do any compilers do
this?

When do you imagine it could be safe to do this?

 

[Beej Jorgensen]

When do you imagine it could be safe to do this?

Well, the first thing that came to mind was any read-only situation:

void printbaz(struct foo f)
{
printf("%d\n", f.baz);
}

(gcc 4.3.3 copies the whole thing on the stack in this case. Maybe
circumstances in which such an optimization were easy to detect are too
rare to bother with. Or maybe I'm just thinking lamely right now
because I'm tired.)

-Beej

 

[Phil Carmody]

I have a question on this... well, it's perhaps a more general question.

If a compiler detects that it's safe to do so, is it free to optimize
out the struct copy and use a pointer instead? Do any compilers do
this?

Well, if it's going to inline the function, it won't even bother
doing that!

Phil

 

[James Kuyper]

Well, the first thing that came to mind was any read-only situation:

void printbaz(struct foo f)
{
printf("%d\n", f.baz);
}

(gcc 4.3.3 copies the whole thing on the stack in this case. Maybe
circumstances in which such an optimization were easy to detect are too
rare to bother with. Or maybe I'm just thinking lamely right now
because I'm tired.)

If that function were made static, that might work under the as-if rule.
In fact, the compiler could probably get away with in-lining it, without
you having any need to tell it so (this is one of the points that was
made by those arguing against the need for the inline keyword).

However, as written, the function has external linkage. As such, it
might be called by a function in some other translation unit that knows
only the interface for printbaz(). When compiling that other translation
unit, the compiler won't know for certain what the definition of
printbaz() is, and therefore can't make changes in the way that
interface is handled that depend upon such knowledge.

In particular, code in another translation unit might define a function
pointer that could point at either printbaz() and needs_foo_copy(), both
of which have identical interfaces, and it must be able to call
whichever of the two functions the pointer currently points at, through
that pointer. The code that uses the function pointer to call to those
functions might be in yet another translation unit, in which there is no
information at all about printbaz().

 

[Richard Bos]

gcc's -Wwrite-strings option makes it non-conforming.

Does it? AIUI, it only swaps one consequence of undefined behaviour
(crashing upon writing to string literals) for another (allowing writing
to string literals).

Richard

 

[Keith Thompson]

Does it? AIUI, it only swaps one consequence of undefined behaviour
(crashing upon writing to string literals) for another (allowing writing
to string literals).

No, it internally changes the type of string literals from char[N] to
const char[N]. For most normal code, it will probably just get you
more optional warnings that you'd get without it, but there are cases
where it can cause gcc to fail to emit a required diagnostic for a
constraint violation.

A somewhat contrived example is:

const char (*p)[6] = &"hello";

Since &"hello" is of type char (*p)[6], and p is of type const char
(*p)[6], the types are incompatible and the initialization violates a
constraint. With "-Wwrite-strings", the constraint violation is not
diagnosed.

Now if "-Wwrite-strings" worked by setting an internal flag on the
string literal's type, rather than by changing the type to be const,
then it could emit additional diagnostics (which are always permitted)
while still recognizing that, say,
__STRING_LITERAL__ char (*p)[6]
and
const char (*p)[6]
are incompatible.

 

[Ian Collins]

Ian Collins wrote:
arnuld wrote:

FAQ says that in both cases a[3] or p[3] , the value is same but
compiler gets there differently. Now I have seen my friend using
char *p = "world" notation (for using it as ab array of const
characters). Is it fine or dangerous. Myself, I do const char a[]
= "wordl" all the time, I never ever use char* p notation to point
to some literal but I want to know whether char *p is a good idea
or not.
No, it is not because attempting to modify a string literal gives
you undefined behaviour. Use const char *p.
No, that doesn't help.

First you say it doesn't help,

... That 'const' only gives you the help of having the
compiler emit an error message (probably) when you try to write
into the string.

and then you admit that it does help. It is precisely because of the
help you just mentioned, that he gave this advice.

It doesn't help make the code work. It does help alerting you to
the why.

What utter drivel. How can the code not work if it doesn't compile?

 

[Ian Collins]

Here is FAQ 6.2:

char a[] = "hello";
car *p = "world";

FAQ says that in both cases a[3] or p[3] , the value is same but
compiler gets there differently. Now I have seen my friend using
char *p = "world" notation (for using it as ab array of const
characters). Is it fine or dangerous. Myself, I do const char a[]
= "wordl" all the time, I never ever use char* p notation to point
to some literal but I want to know whether char *p is a good idea
or not.

No, it is not because attempting to modify a string literal gives
you undefined behaviour. Use const char *p.

No, that doesn't help. In either case you can't write into the
string. That 'const' only gives you the help of having the
compiler emit an error message (probably) when you try to write
into the string.

So which part of doesn't help is that?

Where do you get "probably" from?

 

[Richard Tobin]

gcc's -Wwrite-strings option makes it non-conforming.

[/QUOTE]

Does it? AIUI, it only swaps one consequence of undefined behaviour
(crashing upon writing to string literals) for another (allowing writing
to string literals).

Are you confusing it with -fwritable-strings?

-- Richard

 

[Richard Bos]

Does it? AIUI, it only swaps one consequence of undefined behaviour
(crashing upon writing to string literals) for another (allowing writing
to string literals).

Are you confusing it with -fwritable-strings?[/QUOTE]

Ah - I believe you may have struck the pointy bit of steel on the flat
end using the large bit of steel on the wooden handle.

Richard

 

[David Thompson]

(e-mail address removed) wrote:

[ in a thread that mutated into whether C has pass-by-reference ]

No, Fortran passed everything (except arrays) by copy/restore. To pass
by reference, you had to decorate the formal paramter name with slashes:

SUBROUTINE SUB1(I, /J/) I passed by copy/restore, J by reference

Pass by copy/restore is similar to pass by value except that the final
value of the parameter is copied back into the argument when the
subroutine returns.

I think you must be remembering a dialect or even variant. I've never
seen syntax like that in any Fortran implementation, text, published
code, or standard back to 77. 66 was before I was playing close
attention, but the description of changes in 77 doesn't include any
such thing, and I can't imagine anything so fundamental going
unmentioned. Does the collective memory of c.l.f include this?

Since at least 77, Fortran's rules on 'argument association' have been
carefully written to allow either by-reference or copy-in-out at the
implementor's choice; a program which detects (or relies on) the
difference is nonstandard. F90 and later nearly specify (at least
very strongly hint at) certain cases involving new features, but
the normal 'ordinary data' cases remain implementor-choice.
It is true an implementor is more likely to choose copy for scalars
than arrays, at least actually or potentially large arrays, and
again F>=77 distinguishes between passing scalars and passing arrays
in ways that allow that choice, although without saying why.

(F>=90 also adds optional specification of INTENT IN/OUT/INOUT,
the first two of which *may* copy only one direction. F03 adds
optional explicit VALUE, and C 'interop' features that as one would
expect support the C method. Some compilers did (and do) have
extensions to specify by-ref/value and other calling conventions,
but always as extensions, and TTBOMLK always using either
(pseudo-)function syntax or comment(-like) syntax, not slashes.)

The only thing I know of that is even reasonably close is that
PL/I normally passes by-reference, but specifies that extra
*parentheses* around an argument mean it is first copied to a
temporary (and not copied back) giving the effect of by-value.

 

[glen herrmannsfeldt]

I think you must be remembering a dialect or even variant. I've never
seen syntax like that in any Fortran implementation, text, published
code, or standard back to 77.

That is what the OS/360 Fortran IV compilers do. There is one
documented case where pass by reference is needed, which is
the associated variable for direct access files. The DEFINE FILE
statement specifies for each unit number that will be used
for direct access, the number of records, the record length,
an indicator for formatted, unformatted, or both, and the
associated variable. After each read or write the associated
variable is set to the number of the next record, presumably
to make it easier to sequentially access direct access files.
If you pass this to a subroutine by value result it won't change
in that subroutine, so the pass by reference indicator is needed.

To me, it seems easier to remember the number of the next record,
but that is the way IBM did it.

66 was before I was playing close
attention, but the description of changes in 77 doesn't include any
such thing, and I can't imagine anything so fundamental going
unmentioned. Does the collective memory of c.l.f include this?

I don't know if VS Fortran supports this or not.

(snip)

The only thing I know of that is even reasonably close is that
PL/I normally passes by-reference, but specifies that extra
*parentheses* around an argument mean it is first copied to a
temporary (and not copied back) giving the effect of by-value.

PL/I will also make a copy if the argument type is declared,
and different (enough). If, for example, you passed a fixed
point variable to a subroutine expecting floating point, and
properly declared it (similar to C prototypes) the conversion
is done and the copy is passed. It is not copied back, though.

Parentheses are a specific case of the general rule that an
expression is evaluated and assigned to a modifiable temporary
variable. Constants are another case, presumably due to the
problems of modifying constants in Fortran programs.

-- glen

 

[Kenny McCormack]

Where are the CLC topicality police, when you need them? Why aren't
they all up in arms about this? Why aren't they going all:

Off topic. Not portable. Cant discuss it here. Blah, blah, blah.

On your ass???