title: Valgrind: invalid read of size 4 -> sigsegv, works fine without valgrind and in visual studio
body: <p>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. </p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Many Thanks!</p>
  
  <p>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.</p>
  
  <p>I'm guessing it has something to do with the priority queue of the code:</p>
  
  <p>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.</p>
  
  <pre><code>while(queue-&gt;size &gt; 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-&gt;amount = n1-&gt;amount + n2-&gt;amount;
      insert_node(queue,temp);
      n1-&gt;parent = temp;
      n2-&gt;parent = temp;
      temp-&gt;left = n1;
      temp-&gt;right = n2;
  }
  </code></pre>
  
  <p>Here is are the delete_min and insert_node methods for the priority queue:</p>
  
  <pre><code>void insert_node(priority_queue* p_queue, node* x){
      int i = p_queue-&gt;size;
      if(i == 0){
          p_queue-&gt;queue = (node**) malloc(sizeof(node*));
      }
      else{
          p_queue-&gt;queue = (node**) realloc(p_queue-&gt;queue,sizeof(node*)*(p_queue-&gt;size+1));
      }
      p_queue-&gt;queue[p_queue-&gt;size] = x;
  
      while(i&gt;=0 &amp;&amp; p_queue-&gt;queue[i]-&gt;amount &lt; p_queue-&gt;queue[(i-1)/2]-&gt;amount){
          node* temp = p_queue-&gt;queue[i];
          p_queue-&gt;queue[i] = p_queue-&gt;queue[(i-1)/2];
          p_queue-&gt;queue[(i-1)/2] = temp;
          i = (i-1)/2;
      }
      p_queue-&gt;size++;
  }
  
  node* delete_min(priority_queue* p_queue){
      node** queue = p_queue-&gt;queue;
      node* min = queue[0];
  
      if(p_queue-&gt;size&gt;1){
          int r = 0;
          int current = 1; //left child of root
  
          queue[0] = queue[p_queue-&gt;size-1];
          queue = (node**) realloc(queue,sizeof(node*)*(--p_queue-&gt;size));
          while(current &lt; p_queue-&gt;size){
              //in case of 2 children, check if current needs to be right or left child
              if(current &lt; p_queue-&gt;size-1 &amp;&amp; queue[current] &gt; queue[current+1]){
                  current++;
              } 
              if(queue[current] &lt; 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-&gt;size--;
      }
      return min;
  }
  </code></pre>
  
  <p>EDIT: Added the valgrind output:</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>Line 331 is the line in delete_min of: node* min = queue[0];</p>
  
  <p>EDIT:</p>
  
  <p>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.</p>
  
  <pre><code>//realloc queue and assign new value to local queue var
  p_queue-&gt;queue = (node**) realloc(queue,sizeof(node*)*(--p_queue-&gt;grootte));
  queue = p_queue-&gt;queue;
  </code></pre>