[LCP]linked list question

[Joachim Bauernberger]

Hi Mike,
On Tuesday 02 April 2002 16:20, you wrote:
<snip> 
>     WHAT precisely do you intend. There are MULTIPLE (very different)
> problems which can properly described as "reversing a list". 
Especially
> when you use the word "recursively".
> 

Sorry for being not really clear.
Maybe I'll try to explain what my program does first.
I wrote something that is supposed to parse email messages in all sort 
of formats. (MIME, UU, plain rfc822, etc ...)
Because of the many formats and ways a mail can look like, the parser 
should just go over the mail trying to recognize whatever it can and 
simply "accept" the rest as is.
I split the mail that I receive from the MTA into seperate structs. 
Those are later on being used in case the message should be rebuilt. 
Every mail will have a header and maybe a body. Every body might 
contain several attachment. Since I don't know how many Attachments the 
mail contains I use a linked list in order to process every message.
Now I found that when allocating new nodes it would be quickest to add 
them on the head-end rather than the tail-end. Obviously with the 
disadvantage, of the nodes appearing in reverse.
So I thought the quickest way to reverse the list would be recursively 
reversing the pointers as it is done in this function:

static void
rreverse_mbody(mbody_t ** mb)
{
    mbody_t *first=NULL;
    mbody_t *last=NULL;

    if (*mb==NULL) return;
    first = *mb;
    last = first->bnext;
    if (last==NULL) return;
    rreverse_mbody(&last);
    first->bnext->bnext = first;
    first->bnext = NULL;
    *mb = last;
    return;
}

This should be much more efficient than reversing the last n-1 elements 
of the list and then iterating all the way down to the new tail and put 
the old head node there. It should get the head node in the right 
place without extra iteration.

> a) Did you mean the "recursively" to refer to WHAT you intend to do or
> HOW you intend to do it? In the former case you mean something like
> "reverse a list and all its sublists" so a list (A (B C D) (E F))
> becomes ( (F E) (D C B) A) but if only reversal at the top level was
> meant becomes ((E F) (B C D) A).

Yes because the structure mbody_t may contain other linked lists 
(sub_mbody_t).
For that I wrote a reverse_sub_mbody() function that does the same as 
the above but reverses lists of type sub_mbody_t instead of mbody_t

> 
> b) Did you mean do as a "function" (ie: return a new list with the
> original list left unchanged) or was this to be a "reversal in place"?
> In the former case your "process" will involve allocating either as 
many
> new nodes as the original list contained or as many as exist at the 
top
> level (refer back to "a").

No. This is what I want to avaoid since I have all the information I 
need to rebuild the message in the structures already. The structures 
were first filled while parsing the message of course ...


> 
>     What I am really trying to say by this is that the FIRST thing you
> should always do is be absolutely clear about what your program is
> SUPPOSED to do because there is no way you can get the code right 
until
> you have accomplished that. In other words, you might be able to code 
it
> and test your code and everything looks all right but since it isn't
> actually doing what was intended the whole larger program (of which 
this
> is a component) may fail to work.

I agree.

Regards,
Joachim

> 
> Mike
> 
> 
> _______________________________________________
> This is the Linux C Programming List
> :  http://lists.linux.org.au/listinfo/linuxcprogramming List
> 
> 

-- 
Disclaimer:
By sending an email to ANY of my addresses you are agreeing that: 
1) I am by definition, "the intended recipient" 
2) All information in the email is mine to do with as I see fit and 
make such financial profit, political mileage, or good joke as it lends 
itself to. In particular, I may quote it on usenet. 
3) I may take the contents as representing the views of your company. 
4) This overrides any disclaimer or statement of confidentiality that 
may be included on your message.