Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Can't figure this code (http://www.velocityreviews.com/forums/t957616-cant-figure-this-code.html)

janus 02-14-2013 09:18 PM

Can't figure this code
 
int TokenList_init(TokenList * tl, Lexer * lex)
{
IG_ASSERT(tl, "TokenList should be defined.");
IG_ASSERT(lex, "Lexer should be defined.");
tl->m_head = NULL;
Token * tok;
do
{
tok = (Token *) malloc(sizeof(Token));
Lexer_read(lex, tok);
tok->m_next = NULL;
if (NULL == tl->m_head) {
tl->m_head = tok;
tl->m_tail = tok;
}
else {
tl->m_tail->m_next = tok;
tl->m_tail = tok;
}
}
while (LEXER_EOF != tok -> m_type);

typedef struct TokenList
{
Token * m_head;
Token * m_tail;
Token * m_curr;
} TokenList;

typedef struct Token
{
int m_type; // an int representing the type of symbol
igstr * m_value; // the string value of the token
int m_line; // the line the token was found at
int m_column; // the column the token was found at
struct Token * m_next; // for later use
} Token;


I am studying the above code I stumbled on. I feel that this is wrong:
tl->m_tail->m_next = tok;
tl->m_tail = tok;

It should be:
tl->m_tail->m_next = tok;

and at the end of the loop we should have
tl->m_tail = tok;

Eric Sosman 02-14-2013 10:03 PM

Re: Can't figure this code
 
On 2/14/2013 4:18 PM, janus wrote:
>[... building a linked list; this is the crucial bit ...]
> tok->m_next = NULL;
> if (NULL == tl->m_head) {
> tl->m_head = tok;
> tl->m_tail = tok;
> }
> else {
> tl->m_tail->m_next = tok;
> tl->m_tail = tok;
> }
> [...]
>
> I am studying the above code I stumbled on. I feel that this is wrong:
> tl->m_tail->m_next = tok;
> tl->m_tail = tok;
>
> It should be:
> tl->m_tail->m_next = tok;
>
> and at the end of the loop we should have
> tl->m_tail = tok;


The first time the loop body executes, it creates a list
of one Token. That Token is the first in the list (so m_head
points at it) and the last in the list (so m_tail points at
it, too).

Each additional trip through the loop adds a new Token to
the end of the list. Specifically, it adds the new Token just
after the token that used to be the last one, that is, just
after the token m_tail points at. And after that new Token has
been added, what Token is at the end? The newly-added one, which
is why the code changes m_tail to point at it.

If you left m_tail unchanged until after the loop, then the
first trip through the loop would behave just as it does now,
leaving you with both m_head and m_tail pointing at what I'll
call Token1, and Token1's m_next field equal to NULL. After
the second trip you'd have m_head and m_tail *still* pointing
at Token1, Token1's m_next pointing at Token2, and Token2's
m_next equal to NULL. Each trip through the loop adds the new
Token just after the m_tail token; clear? Okay, now for the
third trip: You'll have m_head and m_tail still pointing to
Token1, Token1's m_next field pointing to Token3, and Token3's
m_next equal to NULL. Who's pointing at Token2 now? Nobody!
Token2 has been lost, and there is no way to find it any more.
Go around again to add Token4, and you'll lose Token3. At the
end, you'll have a situation like:

m_head } --> Token1
m_tail } m_next --> TokenN
m_next == NULL

Lost in the bit bucket:
Token2 Token3 Token4 ...
m_next == NULL m_next == NULL m_next == NULL

--
Eric Sosman
esosman@comcast-dot-net.invalid

janus 02-18-2013 11:22 PM

Re: Can't figure this code
 
On Thursday, February 14, 2013 11:03:33 PM UTC+1, Eric Sosman wrote:
> On 2/14/2013 4:18 PM, janus wrote:
>
> >[... building a linked list; this is the crucial bit ...]

>
> > tok->m_next = NULL;

>
> > if (NULL == tl->m_head) {

>
> > tl->m_head = tok;

>
> > tl->m_tail = tok;

>
> > }

>
> > else {

>
> > tl->m_tail->m_next = tok;

>
> > tl->m_tail = tok;

>
> > }

>
> > [...]

>
> >

>
> > I am studying the above code I stumbled on. I feel that this is wrong:

>
> > tl->m_tail->m_next = tok;

>
> > tl->m_tail = tok;

>
> >

>
> > It should be:

>
> > tl->m_tail->m_next = tok;

>
> >

>
> > and at the end of the loop we should have

>
> > tl->m_tail = tok;

>
>
>
> The first time the loop body executes, it creates a list
>
> of one Token. That Token is the first in the list (so m_head
>
> points at it) and the last in the list (so m_tail points at
>
> it, too).
>
>
>
> Each additional trip through the loop adds a new Token to
>
> the end of the list. Specifically, it adds the new Token just
>
> after the token that used to be the last one, that is, just
>
> after the token m_tail points at. And after that new Token has
>
> been added, what Token is at the end? The newly-added one, which
>
> is why the code changes m_tail to point at it.
>
>
>
> If you left m_tail unchanged until after the loop, then the
>
> first trip through the loop would behave just as it does now,
>
> leaving you with both m_head and m_tail pointing at what I'll
>
> call Token1, and Token1's m_next field equal to NULL. After
>
> the second trip you'd have m_head and m_tail *still* pointing
>
> at Token1, Token1's m_next pointing at Token2, and Token2's
>
> m_next equal to NULL. Each trip through the loop adds the new
>
> Token just after the m_tail token; clear? Okay, now for the
>
> third trip: You'll have m_head and m_tail still pointing to
>
> Token1, Token1's m_next field pointing to Token3, and Token3's
>
> m_next equal to NULL. Who's pointing at Token2 now? Nobody!
>
> Token2 has been lost, and there is no way to find it any more.
>
> Go around again to add Token4, and you'll lose Token3. At the
>
> end, you'll have a situation like:
>
>
>
> m_head } --> Token1
>
> m_tail } m_next --> TokenN
>
> m_next == NULL
>
>
>
> Lost in the bit bucket:
>
> Token2 Token3 Token4 ...
>
> m_next == NULL m_next == NULL m_next == NULL
>
>
>
> --
>
> Eric Sosman
>
> esosman@comcast-dot-net.invalid




Thanks so much!!!


All times are GMT. The time now is 05:31 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.