does gdb lie?

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

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.

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.

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.

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

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

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.

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.

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