does gdb lie?

This is a discussion on does gdb lie? within the C Programming forums, part of the General Programming Boards category; oh man, am i having problems today! I have the following function as part of a red black tree program ...

  1. #1
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40

    does gdb lie? pointers to data changing on me...

    oh man, am i having problems today! I have the following function as part of a red black tree program I am writing. The program is not qorking quite right. It compiles fine with gcc, no errors. But I found an issue with GDB in the following code.
    Code:
        208 // This function performs a left rotation on nodes
        209
        210 void leftrotate(struct node** root, struct node** newnode)
        211 {
        212   struct node* y;
        213
        214   y=(*newnode)->right;
        215   (*newnode)->right=y->left;
        216   if(y->left)
        217     y->left->parent=(*newnode);
        218   (y->parent)=((*newnode)->parent);
        219   if(!(*newnode)->parent)
        220     (*root)=y;
        221   else
        222   {
        223     if(*newnode == (*newnode)->parent->left)
        224       (*newnode)->parent->left=y;
        225     else
        226       (*newnode)->parent->right=y;
        227   }
        228   y->left=*newnode;
        229   (*newnode)->parent=y;
        230
        231   return;
        232 }
    ... GDB output

    Code:
    Breakpoint 1, leftrotate (root=0xbffff6cc, newnode=0x804a410) at main.c:214
    214       y=(*newnode)->right;
    (gdb) p newnode->parent->data
    $1 = 9
    (gdb) p newnode->data
    $2 = 12
    (gdb) step
    215       (*newnode)->right=y->left;
    (gdb)
    216       if(y->left)
    (gdb)
    218       (y->parent)=((*newnode)->parent);
    (gdb) p newnode->parent->data
    $3 = 9
    (gdb) p newnode->data
    $4 = 12
    (gdb) p y->data
    $5 = 16
    (gdb) step
    219       if(!(*newnode)->parent)
    (gdb) p newnode->parent->data
    Cannot access memory at address 0x0
    (gdb) p newnode->data
    $6 = 9
    (gdb) p y->data
    $7 = 16
    I don't understand why the newnode->data and newnode->parent->data seem to move one level up the tree since I'm not doing anything to the node the newnode poiter points at. Am I correct that GDB doesn't execute the line that it is showing you until you step? I just don't see why my values are changing here as the only thing I tried to do was point y's parent pointer to same thing newnode's parent pointer points at...
    Does GDB tell lies? Sorry if I'm becoming a nuisance. Oh, below is my tree at this point... a little sloppy. Sorry.
    Thanks for any help!
    dinjas

    Code:
     
                     root
                         |
                         V
    
                         9
                       /    \
                     3      12
                    /         \
                   2         16
                              \
                              19
    Last edited by dinjas; 03-09-2005 at 01:00 PM. Reason: [1]make title more descriptive [2]correct tree
    straight off the heap

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,823
    Code:
        216   if(y->left)
        217     y->left->parent=(*newnode);
        218   (y->parent)=((*newnode)->parent);
    Well your complete lack of braces, and dubious indentation makes it really hard to figure out what you really intended to happen. As it stands, the 2nd line is NOT part of the if.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40
    Please forgive my dubiousness.
    Code:
     // This function performs a left rotation on nodes
        
    void leftrotate(struct node** root, struct node** newnode)
    {
       struct node* y;
        
       y=(*newnode)->right;
       (*newnode)->right=y->left;
    
       if(y->left)
       {
           y->left->parent=(*newnode);
       }
       
       (y->parent)=((*newnode)->parent);
       
       if(!(*newnode)->parent)
       {
           (*root)=y;
       }
       else
       {
           if(*newnode == (*newnode)->parent->left)
           {
               (*newnode)->parent->left=y;
           }
           else
           {
               (*newnode)->parent->right=y;
           }
       }
       
       y->left=*newnode;
       (*newnode)->parent=y;
       return;
    }
    my struct looks like
    Code:
    struct node
    {
        int data;
        char color;
        struct node* parent;
        struct node* left;
        struct node* right;
    };
    it couldn't be a problem with my dereferencing could it? I just don't understand why the newnode pointer changes right there.
    straight off the heap

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,823
    Did you specify any -O options when compiling?

    Whilst gdb will happily allow you to debug optimised code, it will do some very strange things from time to time to reflect what the optimiser did to the code rather than follow what you actually wrote. The code ultimately will do the right thing, but it sure is weird to follow at times.

    If you want each line to mean each line as it were, then don't turn on the optimiser.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40
    no, I didn't use the -O option. I did however notice my function is being called with the wrong values. So, I guess I'll fix that and then see if I'm still having this problem afterwards. Hopefully it'll just go away.
    (pretty good stategy huh?) Thanks for your time, I know this one isn't the most fun to try to make sense of.

    dinjas
    straight off the heap

  6. #6
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40
    ok, so I was passing in the correct values after all. Let me reillustrate my problem here.
    here's the code with the problem line (I think) in red... the function is called with root->data and x->data both == 1.
    Code:
     208 // This function performs a left rotation on nodes
        209
        210 void leftrotate(struct node** root, struct node** x)
        211 {
        212   struct node* y;
        213
        214   y = (*x)->right;
        215   (*x)->right = y->left;
        216   if(y->left)
        217   {
        218       y->left->parent = (*x);
        219   }
        220   (y->parent) = ((*x)->parent);
        221   if(!(*x)->parent)
        222   {
        223      (*root) = y;
        224   }
        225   else
        226   {
        227      if(*x == (*x)->parent->left)
        228      {
        229         (*x)->parent->left = y;
        230      }
        231      else
        232      {
        233         (*x)->parent->right = y;
        234      }
        235   }
        236   y->left = *x;
        237   (*x)->parent = y;
        238
        239   return;
        240 }
    here's what my tree looks like when the function is called, and what it should look like afterwards...
    Code:
    when called:                                       what I need after:
     1                                                                  2
      \                                                                / \
       2                                                              1  3
        \
         3
    my struct is:
    Code:
    struct node
    {
        int data;
        char color;
        struct node* parent;
        struct node* left;
        struct node* right;
    };
    And finally, my gdb output with the suspect line in red again and other lines of importance in teal.
    Code:
    Breakpoint 1, leftrotate (root=0xbffff6cc, x=0x804a3c8) at main.c:214
    214       y = (*x)->right;
    (gdb) p x->data
    $8 = 1
    (gdb) step
    215       (*x)->right = y->left;
    (gdb) p x->data
    $9 = 1
    (gdb) p y->data
    $10 = 2
    (gdb) step
    216       if(y->left)
    (gdb)
    220       (y->parent) = ((*x)->parent);
    (gdb) p x->data
    $11 = 1
    (gdb) p y->data
    $12 = 2
    (gdb) step
    221       if(!(*x)->parent)
    (gdb) p x->data
    Cannot access memory at address 0x0
    (gdb) p y->data
    $13 = 2
    ??? I know from my previous example that x is getting moved one step up the tree, which is to NULL in this case, but why? Obviously, when I run the next line
    Code:
    if(!(*x)->parent)
    I get a seg fault since x doesn't point to anything.
    Sorry about reposting all of this, I just thought it would be better to state things more clearly and all in one spot. Thanks again
    dinjas
    straight off the heap

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I get a seg fault since x doesn't point to anything.
    Well I guess you should add some better error checking then, huh?
    Code:
    if( x == NULL )
        ...don't dereference it...
    else
    if( (*x)->parent == NULL )
        ...whatever...
    Or maybe:
    Code:
    if( x != NULL && ... )
    At any rate, you know why it's segfaulting, so put in some checks to keep that from happening.

    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40
    Point well taken, but if the purpose of my function is to manipulate what x points at, x points at something coming into the function, and I don't reassign x's pointer to anything else or get rid of what it does point at ... I shouldn't have to worry about it disappearing...should I?
    I moved my problem line into the else statement to cover my arse.
    But now, x disappears after excecuting line 223...
    Code:
        210 void leftrotate(struct node** root, struct node** x)
        211 {
        212   struct node* y;
        213
        214   y = (*x)->right;
        215   (*x)->right = y->left;
        216   if(y->left)
        217   {
        218       y->left->parent = (*x);
        219   }
        220   if(!(*x)->parent)
        221   {
        222      *root = y;
        223      y->parent = NULL;
        224   }
        225   else
        226   {
        227      (y->parent) = ((*x)->parent);
        228      if(*x == (*x)->parent->left)
        229      {
        230         (*x)->parent->left = y;
        231      }
        232      else
        233      {
        234         (*x)->parent->right = y;
        235      }
        236   }
        237   y->left = *x;
        238   (*x)->parent = y;
        239
        240   return;
        241 }
    gdb output...
    Code:
    220       if(!(*x)->parent)
    (gdb) p x->data
    $4 = 1
    (gdb) p x->right->data
    Cannot access memory at address 0x0
    // this is right, x->right should be NULL here
    (gdb) step
    222          *root = y;
    (gdb) p x->data
    $5 = 1
    (gdb) step
    223          y->parent = NULL;
    (gdb) p x->data
    $6 = 1
    // x is still here
    (gdb) step
    //just executed line 223
    237       y->left = *x;
    (gdb) p x->data
    Cannot access memory at address 0x0
    //x is gone?
    Can it possibly be a dereferencing issue? Whatever it is, it's a little beyond my understanding.
    straight off the heap

  9. #9
    Registered User dinjas's Avatar
    Join Date
    Feb 2005
    Location
    Vancouver, Washington
    Posts
    40
    ok! I realized that I didn't need to pass my second argument in as a struct node** because a struct node* would do the trick. Now it works ...finally. Apparently I don't fully understand the ramifications of dealing with the double pointers. I need to study up on it a little more so I know when I'm messing with addresses, when I'm messing with values, and when I'm potentially reassinging things.
    Thanks to everyone who took the time to peruse my code!
    dinjas
    straight off the heap

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. buffered vs unbuffered question
    By Overworked_PhD in forum Linux Programming
    Replies: 6
    Last Post: 07-04-2008, 05:57 PM
  2. Memory allocation error
    By cunnus88 in forum C++ Programming
    Replies: 5
    Last Post: 01-25-2008, 04:24 PM
  3. Contiguous Array version of Linked List
    By ampersand11 in forum C Programming
    Replies: 19
    Last Post: 10-07-2007, 04:05 AM
  4. Dynamically allocating memory...
    By Junior89 in forum C++ Programming
    Replies: 28
    Last Post: 05-08-2007, 11:17 PM
  5. Too much output in GDB
    By MacNilly in forum Tech Board
    Replies: 0
    Last Post: 09-13-2006, 01:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21