在析构函数中尝试双重释放或损坏
Trie double free or corruption in destructor
我正在用 C++ 编写前缀树 class。树中的每个节点都有一个长度为27 Node*
的数组。这些是用来存放字母和空格的。我通过将所有字母转换为小写并将所有符号转换为空格来清理对树的任何输入。在析构函数中,我调用了一个名为 clear 的函数,它接受一个节点(首先是根节点)。编写单元测试时,它只会成功通过一个测试,而在前缀 class 上调用析构函数的第二个测试失败,并出现双重释放或损坏错误。我之前已经 运行 解决过这个问题,并且能够检测到问题并进行补救,但是我无法弄清楚是什么原因造成的,这里有一些代码:
节点结构:
const unsigned int B_FACTOR = 27; // a..z plus space
struct Node_t {
bool word;
Node_t *links[B_FACTOR];
Node_t(): word(false) {}
};
插入(public 和私有):
bool Prefix::insert(string thing) {
sanitize(thing);
if(!root) root = new Node_t();
if(thing == "") return true;
insertPrivate(thing, root);
return true;
}
void Prefix::insertPrivate(string input, Node_t *node) {
if(input == "") {
node->word = true;
return;
}
int idx = (int(input[0])-97) >= 0 ? (int(input[0])-97) : 26;
if(!node->links[idx]) node->links[idx] = new Node_t();
insertPrivate(input.substr(1, input.length()), node->links[idx]);
}
析构函数:
Prefix::~Prefix() {
clear(root);
}
清除:
void Prefix::clear(Node_t *node) {
if(!node) return;
cout << "On Node " << endl;
for (int i = 0; i < 26; ++i) {
clear(node->links[i]);
}
delete node;
}
单元测试:
void testInsert0() {
cout << "testInsert0" << endl;
Prefix a;
a.insert("a");
TS_ASSERT(a.isStored("a"));
}
void testInsert1() {
cout << "testInsert1" << endl;
Prefix b;
b.insert("dd");
TS_ASSERT_EQUALS(b.isStored("d"), false);
}
void testInsert2() {
cout << "testInsert2" << endl;
Prefix a;
a.insert("abcdef");
TS_ASSERT(!a.isStored("abcd"));
}
进行测试的输出是这样的:
Running cxxtest tests (4 tests).testInsert0
On Node
On Node
.testInsert1
Post test
On Node
On Node
On Node
On Node
On Node
*** Error in `./testrunner': double free or corruption (out): 0x00000000019652a0 ***
make: *** [test] Aborted (core dumped)
当我注释掉调用 clear 函数的析构函数中的代码时,一切正常(当然有很多内存错误)但是当析构函数处于活动状态时,它无法通过 2 个完整的单元测试它的能力。
这可能是不是所有变量都被初始化的情况,这导致了对 delete
的虚假调用。确保每个 link Node_t
结构在使用前都设置为 nullptr
。
另请查看 Valgrind,它在虚拟机中运行您的程序以检查常见的内存问题 - 这对于此类事情非常有用。
我正在用 C++ 编写前缀树 class。树中的每个节点都有一个长度为27 Node*
的数组。这些是用来存放字母和空格的。我通过将所有字母转换为小写并将所有符号转换为空格来清理对树的任何输入。在析构函数中,我调用了一个名为 clear 的函数,它接受一个节点(首先是根节点)。编写单元测试时,它只会成功通过一个测试,而在前缀 class 上调用析构函数的第二个测试失败,并出现双重释放或损坏错误。我之前已经 运行 解决过这个问题,并且能够检测到问题并进行补救,但是我无法弄清楚是什么原因造成的,这里有一些代码:
节点结构:
const unsigned int B_FACTOR = 27; // a..z plus space
struct Node_t {
bool word;
Node_t *links[B_FACTOR];
Node_t(): word(false) {}
};
插入(public 和私有):
bool Prefix::insert(string thing) {
sanitize(thing);
if(!root) root = new Node_t();
if(thing == "") return true;
insertPrivate(thing, root);
return true;
}
void Prefix::insertPrivate(string input, Node_t *node) {
if(input == "") {
node->word = true;
return;
}
int idx = (int(input[0])-97) >= 0 ? (int(input[0])-97) : 26;
if(!node->links[idx]) node->links[idx] = new Node_t();
insertPrivate(input.substr(1, input.length()), node->links[idx]);
}
析构函数:
Prefix::~Prefix() {
clear(root);
}
清除:
void Prefix::clear(Node_t *node) {
if(!node) return;
cout << "On Node " << endl;
for (int i = 0; i < 26; ++i) {
clear(node->links[i]);
}
delete node;
}
单元测试:
void testInsert0() {
cout << "testInsert0" << endl;
Prefix a;
a.insert("a");
TS_ASSERT(a.isStored("a"));
}
void testInsert1() {
cout << "testInsert1" << endl;
Prefix b;
b.insert("dd");
TS_ASSERT_EQUALS(b.isStored("d"), false);
}
void testInsert2() {
cout << "testInsert2" << endl;
Prefix a;
a.insert("abcdef");
TS_ASSERT(!a.isStored("abcd"));
}
进行测试的输出是这样的:
Running cxxtest tests (4 tests).testInsert0
On Node
On Node
.testInsert1
Post test
On Node
On Node
On Node
On Node
On Node
*** Error in `./testrunner': double free or corruption (out): 0x00000000019652a0 ***
make: *** [test] Aborted (core dumped)
当我注释掉调用 clear 函数的析构函数中的代码时,一切正常(当然有很多内存错误)但是当析构函数处于活动状态时,它无法通过 2 个完整的单元测试它的能力。
这可能是不是所有变量都被初始化的情况,这导致了对 delete
的虚假调用。确保每个 link Node_t
结构在使用前都设置为 nullptr
。
另请查看 Valgrind,它在虚拟机中运行您的程序以检查常见的内存问题 - 这对于此类事情非常有用。