问题描述
我已经实现了一种压缩算法(使用霍夫曼编码)，该算法使用节点的优先级队列(定义的结构i).现在，当我只在linux或visual studio中运行代码时，一切正常.当我在Visual Studio中检查内存泄漏时，没有给出任何信息.
I have implemented a compression algorithm (using huffman coding) which uses a priority queue of nodes (a struct i defined). Now, when i just run the code in linux or in visual studio, everything works fine. When I check for memory leaks in visual studio, none are given.
现在的问题是，当我使用valgrind分析程序时，它以信号11(sigsegv)终止.遇到的第一个错误是方法delete min中的大小为4的无效读取".此后的其他错误包括:地址是在大小为453的块中释放0字节，大小为4的无效写入，无效的释放，删除或重新分配.
The problem now is, when I use valgrind to analyse my program, it terminates with signal 11 (sigsegv). The first error encountered is an 'invalid read of size 4' in the method delete min. Other errors after that are: Adress is 0 bytes inside a block of size 453 freed, invalid write of size 4, invalid free,delete or realloc.
有人可以给我建议我可能会犯哪种错误吗?我已经在互联网上搜索了几个小时，但是找不到我在做什么(特别是因为它在不使用valgrind时才有效).或提示如何调试并找出导致读取错误的原因.
Can anyone give me advice about what kind of error I possibly could have made? I've been searching the internet for hours, but cannot find what i'm doing wrong (especially since it just works when not using valgrind). Or tips how to debug and find out what's causing the read error.
非常感谢！
这里是一些代码，以防有人想对其进行审查，但是我想潜入此特定代码并不是那么容易.
Here is the code in case somebody would want to review it, but I guess that's not that easy to just dive in this specific code.
我猜想这与代码的优先级队列有关:
I'm guessing it has something to do with the priority queue of the code:
我做霍夫曼部分的部分->每次删除2个最小节点，并将两个和之和加为一个节点.
The part where I do the huffman part -> every time delete the 2 minimal nodes and add the sum of both back as one node.
while(queue->size > 1){
node* n1 = delete_min(queue);
node* n2 = delete_min(queue); // all the errors are encountered in this call
node* temp = (node*) calloc(sizeof(node),1);
temp->amount = n1->amount + n2->amount;
insert_node(queue,temp);
n1->parent = temp;
n2->parent = temp;
temp->left = n1;
temp->right = n2;
}
这是优先级队列的delete_min和insert_node方法:
Here is are the delete_min and insert_node methods for the priority queue:
void insert_node(priority_queue* p_queue, node* x){
int i = p_queue->size;
if(i == 0){
p_queue->queue = (node**) malloc(sizeof(node*));
}
else{
p_queue->queue = (node**) realloc(p_queue->queue,sizeof(node*)*(p_queue->size+1));
}
p_queue->queue[p_queue->size] = x;
while(i>=0 && p_queue->queue[i]->amount < p_queue->queue[(i-1)/2]->amount){
node* temp = p_queue->queue[i];
p_queue->queue[i] = p_queue->queue[(i-1)/2];
p_queue->queue[(i-1)/2] = temp;
i = (i-1)/2;
}
p_queue->size++;
}
node* delete_min(priority_queue* p_queue){
node** queue = p_queue->queue;
node* min = queue[0];
if(p_queue->size>1){
int r = 0;
int current = 1; //left child of root
queue[0] = queue[p_queue->size-1];
queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->size));
while(current < p_queue->size){
//in case of 2 children, check if current needs to be right or left child
if(current < p_queue->size-1 && queue[current] > queue[current+1]){
current++;
}
if(queue[current] < queue[r]){
node* temp = queue[r];
queue[r] = queue[current];
queue[current] = temp;
r = current;
current = 2 * current;
}
else{
break;
}
current++;
}
}
else{
free(queue);
p_queue->size--;
}
return min;
}
添加了valgrind输出:
Added the valgrind output:
Invalid read of size 4
==1893== at 0x80498E0: delete_min (huffman.c:331)
==1893== by 0x80492DA: huffman_encode (huffman.c:196)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893== Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893== at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893== by 0x8049922: delete_min (huffman.c:335)
==1893== by 0x80492CC: huffman_encode (huffman.c:195)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893==
==1893== Invalid read of size 4
==1893== at 0x8049901: delete_min (huffman.c:333)
==1893== by 0x80492DA: huffman_encode (huffman.c:196)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893== Address 0x441db64 is 444 bytes inside a block of size 452 free'd
==1893== at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893== by 0x8049922: delete_min (huffman.c:335)
==1893== by 0x80492CC: huffman_encode (huffman.c:195)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893==
==1893== Invalid write of size 4
==1893== at 0x8049906: delete_min (huffman.c:333)
==1893== by 0x80492DA: huffman_encode (huffman.c:196)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893== Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893== at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893== by 0x8049922: delete_min (huffman.c:335)
==1893== by 0x80492CC: huffman_encode (huffman.c:195)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893==
==1893== Invalid free() / delete / delete[] / realloc()
==1893== at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893== by 0x8049922: delete_min (huffman.c:335)
==1893== by 0x80492DA: huffman_encode (huffman.c:196)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893== Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893== at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893== by 0x8049922: delete_min (huffman.c:335)
==1893== by 0x80492CC: huffman_encode (huffman.c:195)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893==
==1893== Invalid read of size 4
==1893== at 0x8049A0E: delete_min (huffman.c:337)
==1893== by 0x80492DA: huffman_encode (huffman.c:196)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893== Address 0x0 is not stack'd, malloc'd or (recently) free'd
==1893==
==1893==
==1893== Process terminating with default action of signal 11 (SIGSEGV)
==1893== Access not within mapped region at address 0x0
==1893== at 0x8049A0E: delete_min (huffman.c:337)
==1893== by 0x80492DA: huffman_encode (huffman.c:196)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
第331行是delete_min中的行，其中:node * min = queue [0];
Line 331 is the line in delete_min of: node* min = queue[0];
问题已解决.在接受的答案中，解释其原因.只需正确分配重新分配的值，即可在delete_min中解决所有问题.
The problem is solved now. In the accepted answer, the reason why is explained. Just assigning the realloced value correct, in delete_min solved all issues.
//realloc queue and assign new value to local queue var
p_queue->queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->grootte));
queue = p_queue->queue;
推荐答案
我将向您解释第一个错误.
I'll explain the first error to you.
==1893== Invalid read of size 4
==1893== at 0x80498E0: delete_min (huffman.c:331)
==1893== by 0x80492DA: huffman_encode (huffman.c:196)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
在第331行，您可能正在为尚未分配给自己的程序的部分内存读取一个(无符号的)int.
At line 331, you're probably reading an (unsigned) int, in a part of the memory you haven't allocated for your own program.
==1893== Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893== at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893== by 0x8049922: delete_min (huffman.c:335)
==1893== by 0x80492CC: huffman_encode (huffman.c:195)
==1893== by 0x8049DDE: encode_file (main.c:94)
==1893== by 0x8049BBE: main (main.c:32)
==1893==
此部分提供有关您尝试读取的内存部分的更多信息.它说您已经使用了内存，但是reallox释放了它.这意味着您正在从旧指针读取已分配的部分内存.
This part gives more information about the part of memory you tried to read. It says you've already used the memory, but reallox freed it. That means you're reading from an old pointer to a part of memory you've realloccated.
您应该确保使用指针realloc返回，而不是旧的.
You should make sure you use the pointer realloc returns, and not the old one.
在valgrind外部运行时不会崩溃的原因是，在大多数情况下，内存的同一部分将由realloc分配.因此，指针保持不变，因此您的代码将起作用.但是，有时，realloc将决定移动部分内存，然后您的代码将崩溃. Valgrind试图为此警告您.
The reason this doesn't crash when running outside valgrind, is that most of the time, the same part of memory will be allocated by realloc. So the pointer remains the same, and as such your code will work. However, sometimes, realloc will decide to move the part of the memory, and then your code will crash. Valgrind's trying to warn you for this.
使用返回的指针时，其余错误可能会得到解决.
The rest of the errors will probably be solved when you're using the returned pointer.
这篇关于Valgrind:大小为4的无效读取-> sigsegv，无需valgrind即可在Visual Studio中正常运行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！