此功能遍历树t
并搜索具有某些属性的节点。找到节点后,会将它们添加到结果中。
在遍历结束时,结果应存储指向所有匹配节点的指针。 num应该存储结果的长度。
我收到一个我无法修复的AddressSanitizer: stack-buffer-overflow
错误。 每次添加一个节点时,我都会将结果的大小增加1并在最后存储该节点。我已经检查了结果!= NULL。不知何故,*result[(int)(*num)]
越界。
非常感谢您的帮助!谢谢。
void get_by_attribute(struct tree *t, char *attr, struct node **nodes, size_t *num) {
int capacity = 10
struct node **queue = malloc(sizeof(*queue) * capacity);
queue[0] = t->root;
int qI = 1;
int next = 0;
*num = 0;
*nodes = NULL;
while (next < qI) {
struct node *cur = queue[next];
if (strcmp(cur->attribute, attr) == 0) {
*nodes = realloc(*nodes, sizeof(struct node) * (*num + 1));
if (*nodes == NULL) {
// handle error
}
*nodes[*num] = *cur;
*num += 1;
}
for (int i = 0; i < cur->num_children; i++) { // add children to queue
queue[qI] = &cur->children[i];
if (qI == capacity - 1) { // must resize.
struct node **tmp = realloc(queue, sizeof(struct node) * (capacity + 10));
if (tmp == NULL) {
// handle error
} else {
queue = tmp;
capacity += 10;
}
}
qI++;
}
next++;
}
free(queue);
}
您在以下位置有运算符优先级错误:*nodes[*num] = *cur;
后缀一元运算符的绑定要强于前缀一元运算符。您必须写:
(*nodes)[*num] = *cur;
使用局部变量struct node *node
并仅在需要时才存储更新的值,因此出错的可能性较小。它可以让您处理realloc()
故障,而不会像目前这样导致内存泄漏。
还请注意struct node **tmp = realloc(queue, sizeof(struct node) * (capacity + 10));
中的大小不正确。队列是一个指针数组。您应该使用此:
struct node **tmp = realloc(queue, sizeof(*queue) * (capacity + 10));
realloc()
是非常容易出错的功能。应谨慎使用系统模式,进行故障测试并适当清除错误。
[get_by_attribute()
应该在所有情况下都测试内存分配失败,释放所有分配的内存并返回错误代码并一致地更新计算值。
这里是修改后的版本:
// find all nodes with a given attribute name.
// returns 0 for success and a negative error code on error.
// if successful, stores a pointer to an array of nodes on `*nodesp`
// and its number of elements in `*nump`
int get_by_attribute(struct tree *t, const char *attr, struct node **nodesp, size_t *nump) {
int capacity;
struct node **queue;
int qI, next, num;
struct node *nodes;
*nump = num = 0;
*nodesp = nodes = NULL;
capacity = 10;
queue = malloc(sizeof(*queue) * capacity);
if (queue == NULL)
return -1;
queue[0] = t->root;
next = 0;
qI = 1;
while (next < qI) {
struct node *cur = queue[next++];
if (strcmp(cur->attribute, attr) == 0) {
struct node *tmp = realloc(nodes, sizeof(*nodes) * (num + 1));
if (tmp == NULL) {
free(nodes);
free(queue);
return -2;
}
nodes = tmp;
nodes[num++] = *cur;
}
for (int i = 0; i < cur->num_children; i++) { // add children to queue
if (qI == capacity) { // must resize.
struct node **tmp = realloc(queue, sizeof(*queue) * (capacity + 10));
if (tmp == NULL) {
free(nodes);
free(queue);
return 3;
}
queue = tmp;
capacity += 10;
}
queue[qI++] = &cur->children[i];
}
}
free(queue);
*nodesp = nodes;
*nump = num;
return 0;
}
最后一点:您使用队列的方法将按照与树中节点总数成比例的大小分配和重新分配该队列。如果树很大,那么当next
达到给定阈值时,可能值得转移队列:
if (next == 100) {
memmove(queue, queue + 100, sizeof(*queue) * (qI - next));
qI -= next;
next = 0;
}