Reversing a linked list

[henry eshbaugh]

What do you mean, it "isn't too bad"?

It's not unreadable. Sorry for not being clear.

It's not merely coding style.  The identifier "__reverse_list" is
reserved to the implementation.  Using it in your own code makes your
program's behavior undefined.

Nope. Here's an example C program:


void __foo(void)
{
return;
}

int main()
{
___foo();
return 0;
}

And here's the assembly generated by GCC:
.text
..globl ___foo
___foo:
LFB2:
pushq %rbp
LCFI0:
movq %rsp, %rbp
LCFI1:
leave
ret
LFE2:
..globl _main
_main:
LFB3:
pushq %rbp
LCFI2:
movq %rsp, %rbp
LCFI3:
movl $0, %eax
call ____foo
movl $0, %eax
leave
ret
LFE3:
.section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms
+live_support
EH_frame1:
.set L$set$0,LECIE1-LSCIE1
.long L$set$0
LSCIE1:
.long 0x0
.byte 0x1
.ascii "zR\0"
.byte 0x1
.byte 0x78
.byte 0x10
.byte 0x1
.byte 0x10
.byte 0xc
.byte 0x7
.byte 0x8
.byte 0x90
.byte 0x1
.align 3
LECIE1:
..globl ___foo.eh
___foo.eh:
LSFDE1:
.set L$set$1,LEFDE1-LASFDE1
.long L$set$1
LASFDE1:
.long LASFDE1-EH_frame1
.quad LFB2-.
.set L$set$2,LFE2-LFB2
.quad L$set$2
.byte 0x0
.byte 0x4
.set L$set$3,LCFI0-LFB2
.long L$set$3
.byte 0xe
.byte 0x10
.byte 0x86
.byte 0x2
.byte 0x4
.set L$set$4,LCFI1-LCFI0
.long L$set$4
.byte 0xd
.byte 0x6
.align 3
LEFDE1:
..globl _main.eh
_main.eh:
LSFDE3:
.set L$set$5,LEFDE3-LASFDE3
.long L$set$5
LASFDE3:
.long LASFDE3-EH_frame1
.quad LFB3-.
.set L$set$6,LFE3-LFB3
.quad L$set$6
.byte 0x0
.byte 0x4
.set L$set$7,LCFI2-LFB3
.long L$set$7
.byte 0xe
.byte 0x10
.byte 0x86
.byte 0x2
.byte 0x4
.set L$set$8,LCFI3-LCFI2
.long L$set$8
.byte 0xd
.byte 0x6
.align 3
LEFDE3:
.subsections_via_symbols


Note ".globl ___foo". Like I said, GCC generates assembly with
identifiers _[name], so you can prefix names with "__." So, again,
it's largely a coding style issue.

 

[Kleuskes & Moos]

What do you mean, it "isn't too bad"?

It's not unreadable. Sorry for not being clear.

It's not merely coding style.  The identifier "__reverse_list" is
reserved to the implementation.  Using it in your own code makes your
program's behavior undefined.

Nope. Here's an example C program:


void __foo(void)
{
return;
}

int main()
{
___foo();
return 0;
}

And here's the assembly generated by GCC:
.text
.globl ___foo
___foo:
LFB2:
pushq %rbp
LCFI0:
movq %rsp, %rbp
LCFI1:
leave
ret
LFE2:
.globl _main
_main:
LFB3:
pushq %rbp
LCFI2:
movq %rsp, %rbp
LCFI3:
movl $0, %eax
call ____foo
movl $0, %eax
leave
ret
LFE3:
.section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms
+live_support
EH_frame1:
.set L$set$0,LECIE1-LSCIE1
.long L$set$0
LSCIE1:
.long 0x0
.byte 0x1
.ascii "zR\0"
.byte 0x1
.byte 0x78
.byte 0x10
.byte 0x1
.byte 0x10
.byte 0xc
.byte 0x7
.byte 0x8
.byte 0x90
.byte 0x1
.align 3
LECIE1:
.globl ___foo.eh
___foo.eh:
LSFDE1:
.set L$set$1,LEFDE1-LASFDE1
.long L$set$1
LASFDE1:
.long LASFDE1-EH_frame1
.quad LFB2-.
.set L$set$2,LFE2-LFB2
.quad L$set$2
.byte 0x0
.byte 0x4
.set L$set$3,LCFI0-LFB2
.long L$set$3
.byte 0xe
.byte 0x10
.byte 0x86
.byte 0x2
.byte 0x4
.set L$set$4,LCFI1-LCFI0
.long L$set$4
.byte 0xd
.byte 0x6
.align 3
LEFDE1:
.globl _main.eh
_main.eh:
LSFDE3:
.set L$set$5,LEFDE3-LASFDE3
.long L$set$5
LASFDE3:
.long LASFDE3-EH_frame1
.quad LFB3-.
.set L$set$6,LFE3-LFB3
.quad L$set$6
.byte 0x0
.byte 0x4
.set L$set$7,LCFI2-LFB3
.long L$set$7
.byte 0xe
.byte 0x10
.byte 0x86
.byte 0x2
.byte 0x4
.set L$set$8,LCFI3-LCFI2
.long L$set$8
.byte 0xd
.byte 0x6
.align 3
LEFDE3:
.subsections_via_symbols


Note ".globl ___foo". Like I said, GCC generates assembly with
identifiers _[name], so you can prefix names with "__." So, again, it's
largely a coding style issue.

Nope. It's a question of namespaces and the fact that your compiler/libs
may use '__foo' for some other purpose. Besides, empirical arguments aren't
the way to go debating standards.

-------------------------------------------------------------------------------
______________________________________
/ I hope I bought the right relish ... \
\ zzzzzzzzz ... /
--------------------------------------
\
\
___
{~._.~}
( Y )
()~*~()
(_)-(_)
-------------------------------------------------------------------------------

 

[Keith Thompson]

It's not unreadable. Sorry for not being clear.


Yup.

Here's an example C program:


void __foo(void)
{
return;
}

int main()
{
___foo();
return 0;
}

You define your function as "__foo" and call it as "___foo()". Was that
a typo?

And here's the assembly generated by GCC: [96 lines deleted]


Note ".globl ___foo". Like I said, GCC generates assembly with
identifiers _[name], so you can prefix names with "__." So, again,
it's largely a coding style issue.

I never said it wouldn't work with whatever implementation you
happen to be using. I didn't even say it would fail under *any*
implementation. I said that the behavior is undefined.

Identifiers starting with "__" are reserved to the implementation.
If you define such an identifier yourself, your code's behavior
is undefined. Among the infinitely many possible manifestations
of undefined behavior is that your code behaves just as you intend
it to. Another possibility is that your implementation has chosen
to use the name "__foo" for its own purposes, and that attempting
to use it yourself causes a conflict.

By not defining your own identifiers starting with an underscore,
you remove that risk.

 

[henry eshbaugh]

It's not unreadable. Sorry for not being clear.

Yup.

      Here's an example C program:

void __foo(void)
{
   return;
}

int main()
{
   ___foo();
   return 0;
}

You define your function as "__foo" and call it as "___foo()".  Was that
a typo? Yup.

And here's the assembly generated by GCC:

[96 lines deleted]

Note ".globl ___foo". Like I said, GCC generates assembly with
identifiers _[name], so you can prefix names with "__." So, again,
it's largely a coding style issue.

I never said it wouldn't work with whatever implementation you
happen to be using.  I didn't even say it would fail under *any*
implementation.  I said that the behavior is undefined.

Technically, the entire compilation process is undefined. .

I can't afford any compilers that aren't free, but be my guest to test
it out and let me know if there are compilers that do that.

I don't see why; it would break a lot of code and be overall pretty
pointless.

 

[henry eshbaugh]

Nope. It's a question of namespaces and the fact that your compiler/libs
may use '__foo' for some other purpose. Besides, empirical arguments aren't
the way to go debating standards.

My compiler and libraries don't. But if you can find any that do
reserve it, please let me know.

But compilers don't chop off pieces of the symbol to add underscores;
I don't see where you get the idea that they do.

 

[James Kuyper]

What do you mean, it "isn't too bad"?

It's not unreadable. Sorry for not being clear.

It's not merely coding style. �The identifier "__reverse_list" is
reserved to the implementation. �Using it in your own code makes your
program's behavior undefined.

Nope. Here's an example C program:


void __foo(void)
{
return;
}

int main()
{
___foo();
return 0;
}

And here's the assembly generated by GCC:
.text
.globl ___foo
___foo: ....
Note ".globl ___foo". Like I said, GCC generates assembly with
identifiers _[name], so you can prefix names with "__." So, again,
it's largely a coding style issue.

What does it matter what GCC does? "undefined behavior" has a very
specific meaning in the C standard, and it doesn't mean "will fail when
compiled using gcc".

You cannot determine whether the behavior of a piece of code is
undefined by compiling it with one particular implementation, because
one permissible consequence of compiling code with undefined behavior is
that it will compile without a error or warning message, and produce
exactly the results that you mistakenly thought it was required to produce.

You cannot determine whether the behavior is undefined by compiling it
with a dozen different compilers, or even with every single compiler
that's ever been written, because it's permissible for code with
undefined behavior to coincidentally happen to work fine with every
single compiler in existence.

The one and only way to determine whether the behavior is defined is to
compare the code with the standard, and find out whether it meets the
requirements imposed by the standard for defined behavior. Keith has
already cited for you the parts of the standard which specify
requirements violated by your code.

Because the behavior is undefined, it is permissible for a fully
conforming implementation to use __foo() for some purpose other than the
one you used it for, and for that other purpose to have side effects
that you never dreamed of. It would be perfectly permissible, for
instance, for an implementation to treat __foo() as a predefined
function-like macro, and to replace every occurrence of __foo() in your
code with the expansion of that macro.

 

[James Kuyper]

My compiler and libraries don't. But if you can find any that do
reserve it, please let me know.

It's not the compiler that reserves those symbols, nor the libraries;
they merely use the reservation that's already been made. It's the C
standard that reserved those symbols.

But compilers don't chop off pieces of the symbol to add underscores;
I don't see where you get the idea that they do.

He expressed no such idea.

 

[Geoff]

A recursive function is a lot more readable, plus more elegant.

void reverse_list(ListElement *head)
{
if (head == NULL) return;

__reverse_list(head->next, head);

return;
}

void __reverse_list(ListElement *next, ListElement *this)
{
if (this == NULL) return;

if (next->next) __reverse_list(next, next->next);

next->next = this;
return;
}

Where did you acquire this ugly habit of prefixing your functions with
double underscores? The point of reserving double underscore prefixed
names is to avoid name collisions with the internal name space of the
compiler implementation and libraries. You defeat that purpose when
you use them in your application code.

 

[James Kuyper]

Technically, the entire compilation process is undefined. .

Not as far as the C standard is concerned. The C standard says that
"undefined behavior" is behavior "for which this international standard
imposes no requirements". That standard imposes LOTs of requirements on
the translation process as a whole (which corresponds to the combination
of compilation of linking).

I can't afford any compilers that aren't free, but be my guest to test
it out and let me know if there are compilers that do that.

There's no need for testing; read and understand the reservations
established by the C standard - make sure to never violate them, and you
code will (if it contains no other problems) work as specified by that
standard when translated and executed by a standard-conforming
implementation of C.

Ignore those reservations, and your code might or might not mysteriously
malfunction. If you want to take that risk, feel free to do so, but why
would you want to? What benefit do you gain? Do you get a thrill from
breaking the rules?

I don't see why; it would break a lot of code and be overall pretty
pointless.

The point is to give implementations of C a set of identifiers that they
are free to use without breaking your code, and to give you a set of
identifiers that you are free to use without breaking the
implementation. It serves essentially the same purpose as the dividers
on the highway that prevent traffic heading south from running into
traffic heading north; if you cross those dividers, you might be
perfectly safe, or you might cause a high-speed front-end collision.
Your chances of survival are a lot higher using reserved words in C than
crossing to the wrong side of a highway - but the risks are nonetheless
perfectly real.

 

[James Kuyper]

....
... It's impossible to do it in O(1) time,

Compare the last words in those two sentences, and then think about it
for a while.

 

[James Kuyper]

It is quite clear from his post that he understands the difference.

Not to me. It read to me like something that was intended to contradict
the previous claim. I've just tried re-reading it on the assumption that
he did understand the difference, and it come across as a complete
non-sequitur. I've seen people post non-sequiturs before, so I'll
concede that it's entirely possible that's what he did.

 

[Ben Bacarisse]

But it's not a non sequitur. He's elaborating on Willem's comment on
Ben's preference for recursion.

Eh? How did you get that from this thread? My "readable, elegant,
correct; pick any two" was facetious. I can't see how it can be taken
as a preference for recursion.

<snip>

 

[Keith Thompson]

      Here's an example C program:

void __foo(void)
{
   return;
}

int main()
{
   ___foo();
   return 0;
}

You define your function as "__foo" and call it as "___foo()".  Was that
a typo? Yup. [...]

So, again,
it's largely a coding style issue.

I never said it wouldn't work with whatever implementation you
happen to be using.  I didn't even say it would fail under *any*
implementation.  I said that the behavior is undefined.

Technically, the entire compilation process is undefined. .

So what?

The specific compilation process is not defined by the language
standard. The language itself is. That's why the language standard
exists.

I can't afford any compilers that aren't free, but be my guest to test
it out and let me know if there are compilers that do that.

I don't see why; it would break a lot of code and be overall pretty
pointless.

The only code it would break is already broken.

It's completely pointless to use identifiers starting with "__".
By doing so, you risk colliding with identifiers used by the
implementation. By using identifiers that start with letters,
you avoid that risk -- at no cost.

I don't *care* whether any compilers use the name "__foo" internally,
because I don't define reserved identifiers in my own code.

Exactly what benefit do you get by calling your own function "__foo"
(rather than, say, "foo__")?

You have a choice between writing code with well defined behavior and
writing code with undefined behavior. Why do you chose the latter?

 

[Kenny McCormack]

You have a choice between writing code with well defined behavior and
writing code with undefined behavior. Why do you chose the latter?

Speaking for the OP:

Just to piss you off!

And it works!

 

[Willem]

Keith Thompson wrote:
) Exactly what benefit do you get by calling your own function "__foo"
) (rather than, say, "foo__")?
)
) You have a choice between writing code with well defined behavior and
) writing code with undefined behavior. Why do you chose the latter?

The most benign reason I can think of is that he's used to another language
where starting with underscores signifies that that function is not to be
used by other modules (usually when the language doesn't know the concept
of 'static functions'). Like Perl, for example.

Although they usually use a single underscore, not a double one.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Malcolm McLean]

The most benign reason I can think of is that he's used to another language
where starting with underscores signifies that that function is not to be
used by other modules (usually when the language doesn't know the concept
of 'static functions').  Like Perl, for example.

I don't see an important difference between

/* call only in this file */
static int foo();

and

/* restricted to this module in another language */
function _foo[]

 

[henry eshbaugh]

The only code it would break is already broken.

It's completely pointless to use identifiers starting with "__".
By doing so, you risk colliding with identifiers used by the
implementation.  By using identifiers that start with letters,
you avoid that risk -- at no cost.

I don't *care* whether any compilers use the name "__foo" internally,
because I don't define reserved identifiers in my own code.

Exactly what benefit do you get by calling your own function "__foo"
(rather than, say, "foo__")?

You have a choice between writing code with well defined behavior and
writing code with undefined behavior.  Why do you chose the latter?

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

And it's not just me. You know who else happens to do that? The small
army of Linux kernel programmers. Have you ever read the source? It's
full of __init functions, __exit functions, __deprecated logic, and
__[name] all over the bloody place. Take, for example (from the root
of the kernel tree) drivers/xen/xenbus/xenbus_probe.c (copied and
pasted from grep):


../xen/xenbus/xenbus_probe.c: __ATTR_RO(nodename),
../xen/xenbus/xenbus_probe.c: __ATTR_RO(devtype),
../xen/xenbus/xenbus_probe.c: __ATTR_RO(modalias),
../xen/xenbus/xenbus_probe.c: __ATTR_NULL

or xenbus_client.c:


../xen/xenbus/xenbus_client.c: path = kvasprintf(GFP_NOIO | __GFP_HIGH,
pathfmt, ap);
../xen/xenbus/xenbus_client.c:__xenbus_switch_state(struct
xenbus_device *dev,
../xen/xenbus/xenbus_client.c: return __xenbus_switch_state(dev, state,
0);

drivers/xen/xen-pciback/vpci.c:
../xen/xen-pciback/vpci.c: .init = __xen_pcibk_init_devices,
../xen/xen-pciback/vpci.c: .free = __xen_pcibk_release_devices,
../xen/xen-pciback/vpci.c: .find = __xen_pcibk_get_pcifront_dev,
../xen/xen-pciback/vpci.c: .publish = __xen_pcibk_publish_pci_roots,
../xen/xen-pciback/vpci.c: .release = __xen_pcibk_release_pci_dev,
../xen/xen-pciback/vpci.c: .add = __xen_pcibk_add_pci_dev,
../xen/xen-pciback/vpci.c: .get = __xen_pcibk_get_pci_dev,

drivers/xen/xen-pciback/pci_stub.c:
../xen/xen-pciback/pci_stub.c:static int __devinit
pcistub_match_one(struct pci_dev *dev,
../xen/xen-pciback/pci_stub.c:static int __devinit pcistub_match(struct
pci_dev *dev)
../xen/xen-pciback/pci_stub.c:static int __devinit
pcistub_init_device(struct pci_dev *dev)
../xen/xen-pciback/pci_stub.c:static int __init
pcistub_init_devices_late(void)
../xen/xen-pciback/pci_stub.c:static int __devinit pcistub_seize(struct
pci_dev *dev)
../xen/xen-pciback/pci_stub.c:static int __devinit pcistub_probe(struct
pci_dev *dev,
../xen/xen-pciback/pci_stub.c:static int __init pcistub_init(void)
../xen/xen-pciback/pci_stub.c:static int __init xen_pcibk_init(void)
../xen/xen-pciback/pci_stub.c:static void __exit
xen_pcibk_cleanup(void)

I think that's enough for now.

The point is, it's not some bizarre coding style choice I made. It's
used by an army of highly skilled programmers (kernel code is
PAINFUL.) These people know what they're doing, more so than you or I.
And they use it.

 

[henry eshbaugh]

Keith Thompson wrote:

) Exactly what benefit do you get by calling your own function "__foo"
) (rather than, say, "foo__")?
)
) You have a choice between writing code with well defined behavior and
) writing code with undefined behavior.  Why do you chose the latter?

The most benign reason I can think of is that he's used to another language
where starting with underscores signifies that that function is not to be
used by other modules (usually when the language doesn't know the concept
of 'static functions').  Like Perl, for example.

Although they usually use a single underscore, not a double one.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Actually, my first language was Python, but I've spent most of my time
programming working in C.

 

[Geoff]

The point is, it's not some bizarre coding style choice I made. It's
used by an army of highly skilled programmers (kernel code is
PAINFUL.) These people know what they're doing, more so than you or I.
And they use it.

Some others here may choose to disagree about whether the Linux kernel
coders know more about the C language and what the C standard says
about application name spaces than they do, but:

You should not imitate code in the kernel without knowing specifically
and exactly why they use a particular convention. They may be calling
internal functions of the C runtime library (CRT) where your code MUST
not. This is what is meant by "the implementation". The kernel must be
closely tied to the CRT because the CRT is part and parcel to the way
the kernel supports user applications.

Copying coding conventions where you do not understand the rationale
has a name: Cargo Cult

Kernel code is kernel code and user code is user code. By using kernel
conventions in your USER name space programs you are creating a
potential name space collision.

Using leading underscores is not an indicator of a good programmer,
quite the contrary, it is an indication of a novice C programmer who
is emulating a style he does not understand because he copy-pasted or
has been browsing the CRT sources and has seen the style used and
doesn't understand that the convention is RESERVED to the CRT.

The C standard requires that you don't use leading underscores in your
names for a very specific reason. Just don't do it.

 

[Keith Thompson]

You haven't answered this question.

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

[snip]

C99 7.1.3p1:

All identifiers that begin with an underscore and either an
uppercase letter or another underscore are always reserved for any
use.

All identifiers that begin with an underscore are always reserved
for use as identifiers with file scope in both the ordinary and tag
name spaces.

[more reserved identifiers omitted]

No other identifiers are reserved. If the program declares or
defines an identifier in a context in which it is reserved (other
than as allowed by 7.1.4), or defines a reserved identifier as a
macro name, the behavior is undefined.

The behavior of your program is undefined because you used the name
"__foo". It would have been well defined if you hadn't done that.

I've give you the facts; what you do with them is up to you.