Can't figure this code

Discussion in 'C Programming' started by janus, Feb 14, 2013.

  1. janus

    janus Guest

    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;
    janus, Feb 14, 2013
    #1
    1. Advertising

  2. janus

    Eric Sosman Guest

    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
    d
    Eric Sosman, Feb 14, 2013
    #2
    1. Advertising

  3. janus

    janus Guest

    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
    >
    > d




    Thanks so much!!!
    janus, Feb 18, 2013
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?TWljaGVsbGUgU3RvbmU=?=

    Error in designer? Or in code? Can't figure

    =?Utf-8?B?TWljaGVsbGUgU3RvbmU=?=, Apr 25, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    272
    =?Utf-8?B?TWljaGVsbGUgU3RvbmU=?=
    Apr 25, 2004
  2. Arthur J. O'Dwyer
    Replies:
    6
    Views:
    319
    Richard Heathfield
    Sep 6, 2003
  3. Programmer Dude
    Replies:
    10
    Views:
    512
    Programmer Dude
    Sep 10, 2003
  4. Taras_96
    Replies:
    3
    Views:
    311
    Taras_96
    Jan 29, 2008
  5. Jim Gibson

    Re: Can't figure this code out

    Jim Gibson, Feb 2, 2009, in forum: C Programming
    Replies:
    19
    Views:
    558
    Kenny McCormack
    Mar 10, 2009
Loading...

Share This Page