pruning a linear singly linked list

**Nick Keighley** · Apr 23 '06, 10:51 AM

Re: pruning a linear singly linked list

Anando wrote:

this is an algorithm (programming technique) question rather
than a strictly C question. Therefore it would be better asked
on comp.programmin g
[color=blue]
> I have a linear singly linked list of 100 elements. I would like to
> prune it [i.e delete some nodes] such that only user specified elements
> (say only the elements 1, 13, 78 and 100 of the original list) survive
> after pruning.[/color]

life would be easier with a doubly linked list (that only takes another

100 pointer variables with your example). But if you have use a SLL
you'll need to walk two pointers down the list one to point at the
current
node one to point to its predessor. Then chop out the ones you want.
It may make more sense to seek out the required nodes (1, 13, 78, 100)
and copy them to a new list, then destroy the old.
[color=blue]
> Can somebody show me how to do this ? I am a scientist and not a
> computer engineer/student. This will help me develop an application in
> data analysis. I will be grateful for your advice.[/color]

--
Nick Keighley

We recommend, rather, that users take advantage of the extensions of
GNU C and disregard the limitations of other compilers. Aside from
certain supercomputers and obsolete small machines, there is less
and less reason ever to use any other C compiler other than for
bootstrapping GNU CC.
(Using and Porting GNU CC)

**Anando** · Apr 23 '06, 11:54 AM

Re: pruning a linear singly linked list

Hi

Thanks for your algorithm. I was thinking of the copy to new list and
destroy old list as well - but when I copied the data it was a shallow
copy (i.e the data in the structure was not copied). Is it possible to
use memcpy or something to copy - if so could you please give a small
example of copying an element such that the data is also copied ?

Many thanks,
Anand.

**Bill Pursell** · Apr 23 '06, 01:00 PM

gnu extensions

Nick Keighley' signature contains:
[color=blue]
> We recommend, rather, that users take advantage of the extensions of
> GNU C and disregard the limitations of other compilers. Aside from
> certain supercomputers and obsolete small machines, there is less
> and less reason ever to use any other C compiler other than for
> bootstrapping GNU CC.[/color]

I would love to see some discussions about this. I'm constantly
changing my mind about whether or not to use extensions. I most
recently decided to start using extensions, marking them with
__extension__, and stop worrying about it. But I keep worrying about
it. At the moment, the only extensions I'm using are trivial-- enums
with trailing commas, unnamed unions within structures (Am I correct in
calling that trivial?), and very rarely the typeof keyword. I work
exclusively with gcc, and although I'm trying to remain within
standards, the only enforcement mechanism I really have is -pedantic,
so for all I know all of my efforts to be completely standard are
wasted. I'd like to start using typeof more often, but am reluctant to
do so. Is there a way to deteremine which extensions are considered
more acceptable (ie more likely to be incorporated into the standard)
than others?

**Ben C** · Apr 23 '06, 02:25 PM

Re: gnu extensions

On 2006-04-23, Bill Pursell <bill.pursell@g mail.com> wrote:[color=blue]
>
> Nick Keighley' signature contains:
>[color=green]
>> We recommend, rather, that users take advantage of the extensions of
>> GNU C and disregard the limitations of other compilers. Aside from
>> certain supercomputers and obsolete small machines, there is less
>> and less reason ever to use any other C compiler other than for
>> bootstrapping GNU CC.[/color]
>
> I would love to see some discussions about this. I'm constantly
> changing my mind about whether or not to use extensions. I most
> recently decided to start using extensions, marking them with
> __extension__, and stop worrying about it. But I keep worrying about
> it. At the moment, the only extensions I'm using are trivial-- enums
> with trailing commas, unnamed unions within structures (Am I correct in
> calling that trivial?), and very rarely the typeof keyword. I work
> exclusively with gcc, and although I'm trying to remain within
> standards, the only enforcement mechanism I really have is -pedantic,[/color]

You can use -ansi with gcc, and also -std=c99 or -std=c89

**Flash Gordon** · Apr 23 '06, 03:15 PM

Re: gnu extensions

Ben C wrote:[color=blue]
> On 2006-04-23, Bill Pursell <bill.pursell@g mail.com> wrote:[color=green]
>> Nick Keighley' signature contains:
>>[color=darkred]
>>> We recommend, rather, that users take advantage of the extensions of
>>> GNU C and disregard the limitations of other compilers. Aside from
>>> certain supercomputers and obsolete small machines, there is less
>>> and less reason ever to use any other C compiler other than for
>>> bootstrapping GNU CC.[/color]
>> I would love to see some discussions about this. I'm constantly
>> changing my mind about whether or not to use extensions. I most
>> recently decided to start using extensions, marking them with
>> __extension__, and stop worrying about it. But I keep worrying about
>> it. At the moment, the only extensions I'm using are trivial-- enums
>> with trailing commas, unnamed unions within structures (Am I correct in
>> calling that trivial?), and very rarely the typeof keyword. I work
>> exclusively with gcc, and although I'm trying to remain within
>> standards, the only enforcement mechanism I really have is -pedantic,[/color]
>
> You can use -ansi with gcc, and also -std=c99 or -std=c89[/color]

If you want it to attempt to conform to the standard you need both -ansi
(or -std=c89 or -stdc=c99) and -pedantic, however even with that it
still doesn't conform to C99.

Personally I believe one should in general avoid extensions. There are
times when they are required or provide enough benefit to be work it,
but a lot of time they are not.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:

Intro to clc - clc-wiki

http://clc-wiki.net/wiki/Intro_to_clc

**Nick Keighley** · Apr 23 '06, 03:35 PM

Re: gnu extensions

Bill Pursell wrote:[color=blue]
> Nick Keighley' signature contains:[/color]
[color=blue][color=green]
> > We recommend, rather, that users take advantage of the extensions of
> > GNU C and disregard the limitations of other compilers. Aside from
> > certain supercomputers and obsolete small machines, there is less
> > and less reason ever to use any other C compiler other than for
> > bootstrapping GNU CC.[/color][/color]

my warped sense of humour catches up with again...

*I* find it amusing that GNU of all "organisati ons" would be
encouraging
the usage of non-standard extensions. We criticise Microsoft et al for
"extending" standards and hence locking customers in. The same applies
to GNU extensions (and I'm not entirely convinced the motives are any
purer)

[color=blue]
> I would love to see some discussions about this. I'm constantly
> changing my mind about whether or not to use extensions.[/color]

I'm at the "extensions are Evil, they rot your teeth, they make your
hair
fall out" end of the spectrum. To be more realistic extensions of some
sort
are always necessary in real world programs. I'd prefer libraries over
compiler extensions and try to confine such extensions to their own
module.
[color=blue]
> I most recently decided to start using extensions,[/color]

just the occaisional use isnt a problem after all you can give up any
time (like heroin :-) )
[color=blue]
> marking them with __extension__,[/color]

eek! That's an identifier in implementation space.
[color=blue]
> and stop worrying about it. But I keep worrying about
> it. At the moment, the only extensions I'm using are trivial-- enums
> with trailing commas, unnamed unions within structures (Am I correct in
> calling that trivial?),[/color]

One I had an argument about was a "flattened" union

So

union A
{
union B
{
int c;
}
};

(apologies if I got the syntax wrong I don't use unions...). With this
extension you could access c with both A.B.c and A.c. The other party
argued "well it's there and it's useful so why not use it?" to my "If
you
can avoid an extension then do so". I work on systems that can outlive
their hardware so I consider this a wise course.

[color=blue]
> and very rarely the typeof keyword. I work
> exclusively with gcc, and although I'm trying to remain within
> standards, the only enforcement mechanism I really have is -pedantic,
> so for all I know all of my efforts to be completely standard are
> wasted. I'd like to start using typeof more often, but am reluctant to
> do so. Is there a way to deteremine which extensions are considered
> more acceptable (ie more likely to be incorporated into the standard)
> than others?[/color]

I suppose you could take a look at the standard's comitee stuff. Bear
in mind
that a fair amount of C99 stuff is still not widely available

I recently revived an old program I wrote for Windows. The only problem

was I'd used Turbo C and just tucked in a few extensions... Microsoft
had also discontinued support for some calls. I did get it running
again
but things could have been smoother.

--
Nick Keighley

Programming should never be boring, because anything mundane and
repetitive should be done by the computer.
~Alan Turing

**Andrew Poelstra** · Apr 23 '06, 04:05 PM

Re: pruning a linear singly linked list

Anando wrote:[color=blue]
> Hi
>
> Thanks for your algorithm. I was thinking of the copy to new list and
> destroy old list as well - but when I copied the data it was a shallow
> copy (i.e the data in the structure was not copied). Is it possible to
> use memcpy or something to copy - if so could you please give a small
> example of copying an element such that the data is also copied ?
>
> Many thanks,
> Anand.
>[/color]

Please remember to quote the post above you; Usenet is not a message board.

Let's assume that you have a struct with 3 variables:
struct data {
int a;
int b;
int c;
}

And within your list you have a pointer to such a struct:
struct data *node;

To memcpy one of these nodes, you must:
1) Allocate the space:
struct data *cp_node = malloc (sizeof (struct data))
if (cp_node == NULL)
{
/* In case you can't get enough memory, do something here */
}

2) Copy it over:
memcpy (cp_node, node, sizeof(struct node);

**Laurijssen** · Apr 23 '06, 04:25 PM

Re: gnu extensions

"Nick Keighley" <nick_keighley_ nospam@hotmail. com> wrote in message
news:1145805824 .815972.191430@ j33g2000cwa.goo glegroups.com.. .[color=blue]
> *I* find it amusing that GNU of all "organisati ons" would be
> encouraging
> the usage of non-standard extensions. We criticise Microsoft et al for
> "extending" standards and hence locking customers in. The same applies
> to GNU extensions (and I'm not entirely convinced the motives are any
> purer)[/color]

many extensions in gcc indeed, i guess gcc being non commercial makes it not
evil :)

**jacob navia** · Apr 23 '06, 05:44 PM

Re: gnu extensions

Nick Keighley a écrit :[color=blue]
> Bill Pursell wrote:
>
> I'm at the "extensions are Evil, they rot your teeth, they make your
> hair
> fall out" end of the spectrum.[/color]

Yes but, as you say in the next line:
[color=blue]
> To be more realistic extensions of some
> sort
> are always necessary in real world programs.[/color]

There you are. Extensions ARE needed, and all languages and improvements
of software were born as extensions of some other stuff.

The C language?

Was an "extension" of BCPL, :-)

C++?

Extension of C

Etc etc.

[snip][color=blue]
>
> One I had an argument about was a "flattened" union
>
> So
>
> union A
> {
> union B
> {
> int c;
> }
> };
>
> (apologies if I got the syntax wrong I don't use unions...). With this
> extension you could access c with both A.B.c and A.c.[/color]

This is a very useful extension, one that I have included also in the
lcc-win32 compiler. As you can see useful extensions are that: USEFUL
and they tend to be copied by other compiler, and eventually they make
it into the standard, if the commitee agrees on "existing practice"...

The other party[color=blue]
> argued "well it's there and it's useful so why not use it?" to my "If
> you
> can avoid an extension then do so". I work on systems that can outlive
> their hardware so I consider this a wise course.
>[/color]

It is a stupid course because:

If you change the layout of the structures you have to modify ALL THOSE
LINES in your code that access that particular field!!!!!

Instead of all that work, your code A.c still works NO MATTER WHERE in
the structure you change the layout!

You understand now?

Extensions are NOT just evil stuff that compiler writers find out to
"lock their users in" but are USEFUL for certain situations!

jacob

**Keith Thompson** · Apr 23 '06, 07:55 PM

Re: gnu extensions

"Bill Pursell" <bill.pursell@g mail.com> writes:[color=blue]
> Nick Keighley' signature contains:
>[color=green]
>> We recommend, rather, that users take advantage of the extensions of
>> GNU C and disregard the limitations of other compilers. Aside from
>> certain supercomputers and obsolete small machines, there is less
>> and less reason ever to use any other C compiler other than for
>> bootstrapping GNU CC.[/color]
>
> I would love to see some discussions about this. I'm constantly
> changing my mind about whether or not to use extensions. I most
> recently decided to start using extensions, marking them with
> __extension__, and stop worrying about it. But I keep worrying about
> it. At the moment, the only extensions I'm using are trivial-- enums
> with trailing commas, unnamed unions within structures (Am I correct in
> calling that trivial?), and very rarely the typeof keyword.[/color]
[snip]

C99 allows a trailing comma on an enumerator list.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

**jacob navia** · Apr 23 '06, 08:25 PM

Re: gnu extensions

Keith Thompson a écrit :
[color=blue]
> C99 allows a trailing comma on an enumerator list.
>[/color]

What was before an extension is now in the standard.

Why?

Because people used the extension, and didn't have the conservative
attitude is promoted here, where any innovation is treated as an heresy,
even in the most trivial cases.

jacob

**Richard Heathfield** · Apr 23 '06, 08:45 PM

Re: gnu extensions

jacob navia said:
[color=blue]
> Keith Thompson a écrit :
>[color=green]
>> C99 allows a trailing comma on an enumerator list.
>>[/color]
>
> What was before an extension is now in the standard.
>
> Why?[/color]

No idea. It's a completely pointless extension. The only reason I can think
of for it is consistency with the equally pointless trailing comma on an
initialiser list.
[color=blue]
>
> Because people used the extension, and didn't have the conservative
> attitude is promoted here, where any innovation is treated as an heresy,
> even in the most trivial cases.[/color]

No, innovation's great, and it gives you extra choice. But not everybody
innovates in the same way. The conservative attitude promoted here is based
on the fact that using extensions brings with it a portability cost. If you
decide you want to go ahead and use the extensions anyway and let the cost
be hanged, well, that's up to you - and there are newsgroups dealing with
questions about the extensions of particular implementations . Lots of them.
Please let us keep /one/ newsgroup where such extensions are /not/ topical
- pretty please? With sugar on?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk

email: rjh at above domain (but drop the www, obviously)

**Arthur J. O'Dwyer** · Apr 23 '06, 08:55 PM

Re: gnu extensions

On Sun, 23 Apr 2006, Bill Pursell wrote:[color=blue]
> Nick Keighley' signature contains:[color=green]
>> We recommend, rather, that users take advantage of the extensions of
>> GNU C and disregard the limitations of other compilers. Aside from
>> certain supercomputers and obsolete small machines, there is less
>> and less reason ever to use any other C compiler other than for
>> bootstrapping GNU CC.[/color]
>
> I would love to see some discussions about this. I'm constantly
> changing my mind about whether or not to use extensions. I most
> recently decided to start using extensions, marking them with
> __extension__,[/color]

As someone else said, "eek!" But I'm not sure what you mean;
do you mean using the comment string /*__extension__*/ as standard
documentation, the way some people use /*FALLTHROUGH*/ and I
personally use /* Todo fixme bug hack */? Or do you mean naming
your functions things like

fft(x) /* the standard, slow version */
fft__extension_ _(x) /* the speedy version */

Either of those seems reasonable, although the latter IMHO is a
bad idea.
[color=blue]
> and stop worrying about it. But I keep worrying about
> it. At the moment, the only extensions I'm using are trivial-- enums
> with trailing commas, unnamed unions within structures (Am I correct in
> calling that trivial?),[/color]

If you mean

enum foo { x, y, z, } bar;

struct baz {
union /* unnamed */ {
int i;
double j;
} a;
int b;
};

those are both standard features of C, not extensions. If you mean

struct {
union {
int i; /* henceforth "quux.i" */
double j; /* henceforth "quux.j" */
} /* unnamed */;
int b;
} quux;

that's just wrong and evil, and I didn't even know any implementors
had stooped that low. (For one thing, it means that modifying 'quux.i'
will invalidate 'quux.j', even though they're both syntactically
fields in a struct --- which violates the C "object model" and
generally screws with the maintainer's brain.)
[color=blue]
> and very rarely the typeof keyword.[/color]

'typeof' seems nice, but other than writing SUPER ULTRA FAST!!1!
macros to swap two values of arbitrary type, I've never seen a
real-world use for it. :)
[color=blue]
> I work
> exclusively with gcc, and although I'm trying to remain within
> standards, the only enforcement mechanism I really have is -pedantic,
> so for all I know all of my efforts to be completely standard are
> wasted. I'd like to start using typeof more often, but am reluctant to
> do so. Is there a way to deteremine which extensions are considered
> more acceptable (ie more likely to be incorporated into the standard)
> than others?[/color]

Given that the C99 standard still isn't being taught in school, widely
used, or added to GCC, after 7 years, I'm guessing that we may have
reached the point where "likely to be incorporated into the standard"
and "acceptable " are totally different things. As far as I'm concerned,
"acceptable " means either "works in Visual Studio" or "works in ISO C90",
depending on your job description. C99 has nothing to do with it --- let
alone future standards!

my $.02,
-Arthur

**Mark McIntyre** · Apr 23 '06, 08:55 PM

Re: gnu extensions

On Sun, 23 Apr 2006 22:09:47 +0200, in comp.lang.c , jacob navia
<jacob@jacob.re mcomp.fr> wrote:
[color=blue]
>What was before an extension is now in the standard.[/color]

Yup.
[color=blue]
>Why?
>Because people used the extension, and didn't have the conservative
>attitude is promoted here, where any innovation is treated as an heresy,
>even in the most trivial cases.[/color]

Or possibly even, because people didn't have MASSIVE chips on their
shoulders about being repeatedly asked not to go on about wildly
offtopic stuff in a group dedicated to a particular topic.

Perhaps you ought to stop making such a complete fool of yourself.
Mark McIntyre
--
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

pruning a linear singly linked list

pruning a linear singly linked list

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment