Reversing a linked list

[David Resnick]

If I need an identifier like "strength" or ENGLAND. which is in the
reserved namespace but very unlikely for an implementation to actually
use, I just use it, rather than having SCOTLAND, WALES, IRELAND and
EnGLAND, or whatever subterfuge is necessary.

My inclination is to say that is in the same line of reasoning that
causes decisions like
char buf[250];
is big enough for any file name. Very unlikely that one will be
bigger than that, right? I'd rather not guess what is "very unlikely"
when stepping in the implementations namespace. Make enough "very
unlikely" decisions and eventually one happens. But each to their
own...

-David

 

[Keith Thompson]

You think the linux kernel links to glibc? So you believe that
kernel code could just include a call to, say strtok(), and
that would get resolved to glibc's implementation?

[...]

I didn't see anything in what henry eshbaugh wrote that implies
that the Linux kernel links to glibc. He was merely refuting
(correctly, I believe) someone else's claim that the kernel is part
of a C implementation.

 

[ImpalerCore]

If I need an identifier like "strength" or ENGLAND. which is in the
reserved namespace but very unlikely for an implementation to actually
use, I just use it, rather than having SCOTLAND, WALES, IRELAND and
EnGLAND, or whatever subterfuge is necessary.

Of course one can get more verbose by adding a prefix, like REGION_ if
strict adherence is necessary. But I tend to have the same attitude
as you for those kinds of identifiers.

From this discussion, it's obvious that eshbaugh is a part of the
rebel alliance, and a *traitor*. He has not fully succumbed to the
"standard" side of the force ... yet (cue Imperial March).

(I'll never join you!!!)

 

[Ben Bacarisse]

If I need an identifier like "strength" or ENGLAND. which is in the
reserved namespace but very unlikely for an implementation to actually
use, I just use it, rather than having SCOTLAND, WALES, IRELAND and
EnGLAND, or whatever subterfuge is necessary.

My inclination is to say that is in the same line of reasoning that
causes decisions like
char buf[250];
is big enough for any file name. Very unlikely that one will be
bigger than that, right? I'd rather not guess what is "very unlikely"
when stepping in the implementations namespace. Make enough "very
unlikely" decisions and eventually one happens. But each to their
own...

It doesn't "feel" the same to me at all. From even a formal point of
view, ENGLAND is perfectly OK in a translation using that does not
include errno.h (and even if you do, provided you #undef it first). And

#undef strength /* in case I ever include string.h */
static strength(int x) { ... }

is also perfectly valid. Being less formal about it, just using these
sorts of identifiers[1] is not likely to go wrong in the same horrid
way that a buffer overrun can (assuming that is what you are referring
to -- a safe read into a buffer that is not big enough is rather
different).

I prefer to avoid using these names at all (even when the standard
assures me it's OK in the specific instance) but when I see them in
other people's code, it certainly feels different to seeing a short
buffer.

I don't extend this feeling to the __ prefix. Using that is a very odd
choice indeed since it the "most reserved" of all the reserved name
forms -- reserved for any use in any way regardless of any includes. __
may even (and probably does) introduce keywords into the language.

[1] Every time I read the standard I am reminded of reserved names
(subject to #includes) that I'd forgotten about. Today's are:

PRIX_FIXE
INTEGER_C
SIGNATURE

 

[Ben Bacarisse]

You think the linux kernel links to glibc? So you believe that
kernel code could just include a call to, say strtok(), and
that would get resolved to glibc's implementation?

[...]

I didn't see anything in what henry eshbaugh wrote that implies
that the Linux kernel links to glibc. He was merely refuting
(correctly, I believe) someone else's claim that the kernel is part
of a C implementation.

This is tangential to the issue of reserved identifiers, but I've always
thought of the kernel as part of a C implementation. A (possibly naive)
reading of this definition:

3.12
1 implementation

particular set of software, running in a particular translation
environment under particular control options, that performs
translation of programs for, and supports execution of functions in,
a particular execution environment

seems to support that view. I would have said that the kernel (of the
compiler's target system, of course) "supports execution of functions
in, a particular execution environment".

 

[David Resnick]

My inclination is to say that is in the same line of reasoning that
causes decisions like
char buf[250];
 is big enough for any file name.  Very unlikely that one will be
bigger than that, right?  I'd rather not guess what is "very unlikely"
when stepping in the implementations namespace.  Make enough "very
unlikely" decisions and eventually one happens.  But each to their
own...

It doesn't "feel" the same to me at all.  From even a formal point of
view, ENGLAND is perfectly OK in a translation using that does not
include errno.h (and even if you do, provided you #undef it first).  And

  #undef strength /* in case I ever include string.h */
  static strength(int x) { ... }

is also perfectly valid.  Being less formal about it, just using these
sorts of identifiers[1] is not likely to go wrong in the same horrid
way that a buffer overrun can (assuming that is what you are referring
to -- a safe read into a buffer that is not big enough is rather
different).

I prefer to avoid using these names at all (even when the standard
assures me it's OK in the specific instance) but when I see them in
other people's code, it certainly feels different to seeing a short
buffer.

I don't extend this feeling to the __ prefix.  Using that is a very odd
choice indeed since it the "most reserved" of all the reserved name
forms -- reserved for any use in any way regardless of any includes.  __
may even (and probably does) introduce keywords into the language.

[1] Every time I read the standard I am reminded of reserved names
(subject to #includes) that I'd forgotten about.  Today's are:

  PRIX_FIXE
  INTEGER_C
  SIGNATURE

I agree that not all decisions about 'issue "x" is unlikely so I'll
not code in a way to avoid it' are equal. And runtime issues (short
buffers) are generally quite a bit worse than compile time conflicts
due to poorly chosen (or reserved) names. But hitting a compile time
conflict with a 3rd party package that uses reserved identifiers in
its headers or exports symbols in the system namespace would be vexing
to me. I guess I like the simple rule of not stepping into the
system's namespace to the best of my ability. Some of the rules (like
__) are obvious. I didn't know about those you listed above, btw, so
had a quick look at the standard and found them. It would be nice if
gcc had an option to poke you about using reserved identifiers in non-
system code, but don't see such in its docs (-pedantic doesn't do
it).

 

[Ben Bacarisse]

But hitting a compile time
conflict with a 3rd party package that uses reserved identifiers in
its headers or exports symbols in the system namespace would be vexing
to me.

That's something I did not consider. I was (rather narrowly) thinking
of my private code. If it's code you can't change, it is going to much
more annoying.

It would be nice if
gcc had an option to poke you about using reserved identifiers in non-
system code, but don't see such in its docs (-pedantic doesn't do
it).

I don't think there is one. It would be a very useful warning.

 

[Ben Bacarisse]

I have two problems with that:

and now, so do I.

1 The comment should be
/* in case I ever include string.h or stdlib.h */

2 If strength is the name of a function in string.h
and string.h is included,
then that #undef will not allow you redefine strength..

Both excellent points. Thanks. I should have said that strength
is fine provided it does not have external linkage and neither of the
headers you cite are included.

 

[James Kuyper]

Guess what: the Linux kernal is part of a C implementation. The key
reason why you're not supposed to use these names is because they ARE
supposed to use them. They're NOT supposed to use the names that are
reserved for your use.

The Linux kernel is _not_ a C implementation. Glibc is a C
implementation.

You think the linux kernel links to glibc? So you believe that
kernel code could just include a call to, say strtok(), and
that would get resolved to glibc's implementation?

[...]

I didn't see anything in what henry eshbaugh wrote that implies
that the Linux kernel links to glibc. He was merely refuting
(correctly, I believe) someone else's claim that the kernel is part
of a C implementation.

The kernel contains part of a C implementation at least as much
as glibc does. Henry magically disappeared the word "part of" in
his response. 'is' was perhaps overstating the claim, ...

I hadn't even noticed that confusion on his part.

... but there
is undeniably C implementation in the linux kernel (e.g. in the
include and lib directories).

The relevant question is not whether it's part of the implementation,
but whether identifiers used in the kernel could interfere with names
used in ordinary C code. Quite frankly, I have no idea, since I've never
had to deal with the kernel directly. A quick web search didn't resolve
that question in my mind: I didn't get too few hits, but rather way too
many, and I couldn't find one that clearly addressed that issue. I'm a
little surprised that no one other than Henry has directly commented on
that - I'm not inclined to take his opinions on the matter as gospel.

It was my annoyance at Henry's pig-headedness which led me to make the
mistake of speaking authoritatively on a subject on which I am not at
all an authority; I regretted that mistake within minutes of sending the
message.

 

[Phil Carmody]

...
The relevant question is not whether it's part of the implementation,
but whether identifiers used in the kernel could interfere with names
used in ordinary C code.

They cannot any more than identifiers in different userspace
programs can interfere with each other. However, identifiers
in separate libraries can interfere with each other, and with
the program they're being loaded into.

Phil

 

[Michael Press]

Well, no, it wouldn't. The cost of checking whether a linked list
terminates in a cycle is of the same order as the cost of reversing
the list. One could even integrate cycle checking into the reversal
code. If one does that one could also reverse a cycle terminated
linked list by defining the new head as the node that joined the
cycle. I don't suppose you would want to do that but it could be done
cheaply enough.

Here is the canonical linked list reversal.

struct ure
{
struct ure *link;
int data;
};

struct ure *list_head = NULL;

...

/* Build up the linked list. */

...

{
struct ure *tail;

tail = list_head;
list_head = NULL;
for(; tail != NULL; tail = next)
{
struct ure *next;

next = tail->link;
tail->link = list_head;
list_head = tail;
}
}

Given a linked list with a loop, this code terminates;
reversing the cycle, and leaving invariant the
transient and the node that has two nodes pointing at it.

list_head -> a -> b -> c -> d -> e -> c

list_head -> NULL | tail -> a -> b -> c -> d -> e -> c
list_head -> a -> NULL | tail -> b -> c -> d -> e -> c
list_head -> b -> a -> NULL | tail -> c -> d -> e -> c
list_head -> c -> b -> a -> NULL | tail -> d -> e -> c
list_head -> d -> c -> b -> a -> NULL | tail -> e -> c
list_head -> e -> d -> c -> b -> a -> NULL | tail -> c
list_head -> c -> e -> d -> c | tail -> b -> a -> NULL
list_head -> b -> c -> e -> d -> c | tail -> a -> NULL
list_head -> a -> b -> c -> e -> d -> c | tail -> NULL


We can analyze a linked list with a loop in O(1) space
and O(n) time. This is done in three stages using two
separate variables to traverse the list:

Leader
Follower

In Stage 1 we need to test for a NULL that will show
that the linked list is NULL terminated, and prevent
dereferencing NULL.

Stage 1:
L <- list_head
F <- list_head
At each step F traverses one node, and L traverses two
nodes. Eventually we have F = L, and F and L are
pointing at a node in the cycle.

Stage 2:
Save the value of L, then let L traverse nodes until L
is back at its saved value. Now we know the value of c,
the length of the cycle.

Stage 3:
L <- list_head
F <- list_head
Let L traverse c nodes. Now L and F step in tandem, one
node each for each step until L = F. Now L and F point
at the node that has two nodes pointing at it.

 

[Tim Rentsch]

It's a coding style issue. I use them for internal functions.

"coding style" is not a term ordinarily used to describe deliberate
adoption of practices that, according to the C standard, have undefined
behavior.

And it's not just me. You know who else happens to do that? The small
army of Linux kernel programmers.

Guess what: the Linux kernal is part of a C implementation. [snip]

No, it isn't. A Linux _distribution_ may include parts of
a C implmentation, but just the kernel does not.

 

[Tim Rentsch]

"coding style" is not a term ordinarily used to describe deliberate
adoption of practices that, according to the C standard, have undefined
behavior.

I used a term where you didn't expect to see it. Deal with it.

Guess what: the Linux kernal is part of a C implementation. The key
reason why you're not supposed to use these names is because they ARE
supposed to use them. They're NOT supposed to use the names that are
reserved for your use.

The Linux kernel is _not_ a C implementation. Glibc is a C
implementation.

You think the linux kernel links to glibc? So you believe that
kernel code could just include a call to, say strtok(), and
that would get resolved to glibc's implementation?

[...]

I didn't see anything in what henry eshbaugh wrote that implies
that the Linux kernel links to glibc. He was merely refuting
(correctly, I believe) someone else's claim that the kernel is part
of a C implementation.

This is tangential to the issue of reserved identifiers, but I've always
thought of the kernel as part of a C implementation. A (possibly naive)
reading of this definition:

3.12
1 implementation

particular set of software, running in a particular translation
environment under particular control options, that performs
translation of programs for, and supports execution of functions in,
a particular execution environment

seems to support that view. I would have said that the kernel (of the
compiler's target system, of course) "supports execution of functions
in, a particular execution environment".

That's for things like the standard library. A kernel _provides_
an execution environment, but nothing in it is particular or specific
to C. Rather, it is part of a system that may support a conforming
implemention, as mentioned in 1 p2 (last bullet item).

 

[Tim Rentsch]

"coding style" is not a term ordinarily used to describe deliberate
adoption of practices that, according to the C standard, have undefined
behavior.

I used a term where you didn't expect to see it. Deal with it.

Guess what: the Linux kernal is part of a C implementation. The key
reason why you're not supposed to use these names is because they ARE
supposed to use them. They're NOT supposed to use the names that are
reserved for your use.

The Linux kernel is _not_ a C implementation. Glibc is a C
implementation.

You think the linux kernel links to glibc? So you believe that
kernel code could just include a call to, say strtok(), and
that would get resolved to glibc's implementation?

[...]

I didn't see anything in what henry eshbaugh wrote that implies
that the Linux kernel links to glibc. He was merely refuting
(correctly, I believe) someone else's claim that the kernel is part
of a C implementation.

The kernel contains part of a C implementation at least as much
as glibc does. Henry magically disappeared the word "part of" in
his response. 'is' was perhaps overstating the claim, but there
is undeniably C implementation in the linux kernel (e.g. in the
include and lib directories).

A Linux distribution can include parts of a C implementation;
a Linux kernel does not.

 

[Phil Carmody]

"coding style" is not a term ordinarily used to describe deliberate
adoption of practices that, according to the C standard, have undefined
behavior.

I used a term where you didn't expect to see it. Deal with it.

Guess what: the Linux kernal is part of a C implementation. The key
reason why you're not supposed to use these names is because they ARE
supposed to use them. They're NOT supposed to use the names that are
reserved for your use.

The Linux kernel is _not_ a C implementation. Glibc is a C
implementation.

You think the linux kernel links to glibc? So you believe that
kernel code could just include a call to, say strtok(), and
that would get resolved to glibc's implementation?

[...]

I didn't see anything in what henry eshbaugh wrote that implies
that the Linux kernel links to glibc. He was merely refuting
(correctly, I believe) someone else's claim that the kernel is part
of a C implementation.

The kernel contains part of a C implementation at least as much
as glibc does. Henry magically disappeared the word "part of" in
his response. 'is' was perhaps overstating the claim, but there
is undeniably C implementation in the linux kernel (e.g. in the
include and lib directories).

A Linux distribution can include parts of a C implementation;
a Linux kernel does not.

The one I maintain for ${DAYJOB} does. And as I pull from Greg KH's
tree, I think I can speak for his one too, and almost certainly Linus's.
Did you have some other Linux kernel in mind?.

Phil

 

[Tim Rentsch]

"coding style" is not a term ordinarily used to describe deliberate
adoption of practices that, according to the C standard, have undefined
behavior.

I used a term where you didn't expect to see it. Deal with it.

Guess what: the Linux kernal is part of a C implementation. The key
reason why you're not supposed to use these names is because they ARE
supposed to use them. They're NOT supposed to use the names that are
reserved for your use.

The Linux kernel is _not_ a C implementation. Glibc is a C
implementation.

You think the linux kernel links to glibc? So you believe that
kernel code could just include a call to, say strtok(), and
that would get resolved to glibc's implementation?

[...]

I didn't see anything in what henry eshbaugh wrote that implies
that the Linux kernel links to glibc. He was merely refuting
(correctly, I believe) someone else's claim that the kernel is part
of a C implementation.

The kernel contains part of a C implementation at least as much
as glibc does. Henry magically disappeared the word "part of" in
his response. 'is' was perhaps overstating the claim, but there
is undeniably C implementation in the linux kernel (e.g. in the
include and lib directories).

A Linux distribution can include parts of a C implementation;
a Linux kernel does not.

The one I maintain for ${DAYJOB} does. And as I pull from Greg KH's
tree, I think I can speak for his one too, and almost certainly Linus's.
Did you have some other Linux kernel in mind?.

I think we're talking about two different things. What I
think you are talking about is maintaining (part of) a C
implementation as part of Linux kernel /sources/. What I am
talking about is a Linux kernel /executable/, ie, a boot
image. Certainly I can believe that you work on, eg,
various standard header files, as part of work on kernel
source files. However, that has no bearing on whether (part
of) a C implemention is provided by a Linux boot image;
normally all the various C-implementation parts are just
files scattered around the file system of a distribution --
nothing comes directly out of the actual boot image.

It's possible of course that some of the C implementation source
files you work on get shipped along with the boot image, to make
up part of an implementation in that distribution (using
"shipped" and "distribution" as appropriate to your environment).
That still doesn't make them part of the boot image, even if it
happens to be true that both sets of source files were worked on
in concert and simultaneously. All that matters is where the
various pieces of an implementation come from, and normally all
those pieces come out of the file system of the distribution, not
out of the kernel boot image.

Does that make more sense now?

 

[Phil Carmody]

I think we're talking about two different things. ....
Does that make more sense now?

It does, yes; thanks for the clarification.

Phil
--

I'd argue that there is much evidence for the existence of a God.

Pics or it didn't happen.
-- Tom (/. uid 822)