does gdb lie?

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

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

Quote:

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