我试图在二叉树中交换两个节点A
,B
以便它们实际存储在内存中的位置发生变化,但树拓扑没有改变。我添加了与父节点交换节点的特殊处理,但它似乎仍然不起作用。我将 Valgrind 与 vgdb 一起使用,以便我可以捕获内存错误并获得一致的地址。如果我有一棵树
78
\
40
/ \
5c c5
然后我尝试交换A=40
,B=5c
链接搞砸了。具体来说,40->right
。在它()上设置一个观察点watch -l
,我发现它40->right
被设置为5c->right
(NULL
)memcpy
,但它也被更改为A
以后,if(a_l.left == b){
这显然是不可能的。在我使用movq
而不是movb
在组装之前,我有一个观察点报告了这样的错误行,但我很确定这次我的尺寸是正确的,因为我一开始没有,而且它没有通过任何交换,但我修复了它,现在它通过了大约十几个。我在每次操作后都会检查树,所以错误就在这里。这是我可以管理的最简单的演示:
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef struct avl_node avl_node;
struct avl_node{
avl_node *left, *right, *parent;
signed char balance;
char data[];
};
avl_node *avl_root(avl_node *n){
while(n && n->parent){
n = n->parent;
}
return n;
}
inline static int avl_check_links(avl_node *n){
if(!n)return 1;
if(n->left){
if(n->left->parent != n){
return 0;
}
if(!avl_check_links(n->left)){
return 0;
}
}
if(n->right){
if(n->right->parent != n){
return 0;
}
if(!avl_check_links(n->right)){
return 0;
}
}
return 1;
}
void avl_swap_nodes(avl_node *a, avl_node *b, size_t size){
avl_node a_l = *a, b_l = *b;
char tmp[sizeof(avl_node) + size];
memcpy(tmp, a, sizeof(avl_node) + size);
memcpy(a, b, sizeof(avl_node) + size);
memcpy(b, tmp, sizeof(avl_node) + size);
if(a_l.left){
a_l.left->parent = b;
}
if(a_l.right){
a_l.right->parent = b;
}
if(b_l.left){
b_l.left->parent = a;
}
if(b_l.right){
b_l.right->parent = a;
}
if(a_l.parent){
if(a_l.parent->left == a){
a_l.parent->left = b;
}else{
a_l.parent->right = b;
}
}
if(b_l.parent){
if(b_l.parent->left == b){
b_l.parent->left = a;
}else{
b_l.parent->right = a;
}
}
if(a_l.parent == b){
if(b_l.left == a){
b->left = a_l.left;
a->left = b;
}else{
b->right = a_l.right;
a->right = b;
}
a->parent = b_l.parent;
b->parent = a;
}else if(b_l.parent == a){//GDB stops here on a watch -l a->right
if(a_l.left == b){
a->left = b_l.left;
b->left = a;
}else{
a->right = b_l.right;
b->right = a;
}
b->parent = a_l.parent;
a->parent = b;
}
assert(avl_check_links(avl_root(a)));
assert(avl_check_links(avl_root(b)));
}
int main(void){
avl_node a, b, c, d;
a = (avl_node){.right=&b};
b = (avl_node){.left=&c, .right=&d, .parent=&a};
c = (avl_node){.parent=&b};
d = (avl_node){.parent=&b};
assert(avl_check_links(avl_root(&a)));
avl_swap_nodes(&b, &c, 0);
}
为什么 GDB 会停在错误的行上?我认为这可能与我使用 vgdb 的事实有关:当我单步执行时它也会跳过一些行。另外,为什么要a->right
第二次更改?谢谢你。
gcc -g -o main main.c
您可以通过执行, valgrind --vgdb=yes --vgdb-error=0 ./main&
, gdb main
, tar rem | vgdb
, b avl_swap_nodes
, c
,来使该文件与合理的最新版本的 gcc、gdb 和 valgrind 一起运行,然后通过反复执行 then或thenwatch -l a->right
来巧妙地摆脱 vgdb 进程。c
Ctrl-d
kill
Ctrl-d