malloc / free for resizing array

Question

Queue.cpp

#include "Queue.h"
#include "Log.h"
void Queue::resize(int n)
{
  Log("[Resize] Req: %d ", n);
  DATA_TYPE *temp = (DATA_TYPE *) malloc(sizeof(DATA_TYPE) * n);
  int i, j;
  for(i = f, j = 0; i < r; i++, j++)
    *(temp + j) =  *(buffer + i);

  Log("Buf: %p ", buffer);
  free(buffer);
  buffer = temp;
  _buf_len = n;
  r = r - f;
  f = 0;
  Log("Buf new: %p \n", buffer);
}

void Queue::enqueue(DATA_TYPE c)
{ 
  if(N == _buf_len)
    resize(N * 2);

  buffer[r++] = c;
  N++; 
  Log("[Enqueue] D: %d N: %d BUF_LEN: %d \n", c, N, _buf_len);
}

DATA_TYPE Queue::dequeue(void)
{
   DATA_TYPE c = buffer[f++]; 
   N--;
   if(N > 0 && N == _buf_len / 4)
     N / 2 == 0 ? resize(1) : resize( N / 2);

   Log("[Dequeue] D: %d N: %d BUF_LEN: %d \n", c, N, _buf_len);
   return c;     
}

DATA_TYPE Queue::peek(void)
{
   return buffer[f]; 
}

bool Queue::isempty(void)
{
  return r == f;
}

int Queue::size(void)
{
  return N;
}

Queue::Queue(int n)
{
  buffer = (DATA_TYPE *) malloc(sizeof(DATA_TYPE) * n);
  f = r = 0;
  N = 0;
  _buf_len = n; 
}

Queue::Queue()
{
  buffer = (DATA_TYPE *) malloc(sizeof(DATA_TYPE));
  f = r = 0;
  N = 0;
  _buf_len = 1; 
} 


Queue::~Queue()
{
  free(buffer);
}

Queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include <stdlib.h>

typedef int DATA_TYPE;

class Queue
{ 

  public:
    Queue(int);
    Queue();
    ~Queue();   
    void enqueue(DATA_TYPE);
    DATA_TYPE dequeue(void);
    bool isempty(void);
        DATA_TYPE peek(void);
    int size(void);     
  private:
        int N;
        int _buf_len;
    int f;
    int r;
    DATA_TYPE *buffer;
    void resize(int);

};

#endif

Log.h

#ifndef LOG_H
#define LOG_H

#include "stdio.h"
#include "stdarg.h"
#define DEBUG

void Log(const char *, ...);
#endif

Log.cpp

#include "Log.h"

void Log(const char *frmt, ...)
{
  #ifdef DEBUG
  va_list ap;
  va_start(ap, frmt);
  vprintf(frmt, ap);
  va_end(ap);
  #endif
}

main.cpp

#include "Queue.h"

#include "stdio.h"
#include "ctype.h"
#include "string.h"

int main(int argc, char *argv[])
{
  Queue queue;
  ++argv;
  //--argc;
  while(--argc > 0)
  {
    if(strcmp(*argv, "-") != NULL)
      queue.enqueue(atoi(*argv));
    else 
       if(!queue.isempty())
         queue.dequeue();//printf("%d\n", queue.dequeue()); 
     ++argv;    
  }

  printf("\nItems left on queue: %d\n", queue.size());

  return 0;
}

The above mention code while running with

./a.out 12 23 34 56 11 22 33 44 55 66 77 88 - - - 34 56 - - - 123 67 56 78 - - 45 - 78 - 23 - 1256 - - 4


[Enqueue] D: 12 N: 1 BUF_LEN: 10 <br>
[Enqueue] D: 23 N: 2 BUF_LEN: 10 <br>
[Enqueue] D: 34 N: 3 BUF_LEN: 10 <br>
[Enqueue] D: 56 N: 4 BUF_LEN: 10 <br>
[Enqueue] D: 11 N: 5 BUF_LEN: 10 <br>
[Enqueue] D: 22 N: 6 BUF_LEN: 10 <br>
[Enqueue] D: 33 N: 7 BUF_LEN: 10 <br>
[Enqueue] D: 44 N: 8 BUF_LEN: 10 <br>
[Enqueue] D: 55 N: 9 BUF_LEN: 10 <br>
[Enqueue] D: 66 N: 10 BUF_LEN: 10 <br>
[Resize] Req: 20 Buf: 0xb7f010 Buf new: 0xb7f030  <br>
[Enqueue] D: 77 N: 11 BUF_LEN: 20 <br>
[Enqueue] D: 88 N: 12 BUF_LEN: 20 <br>
[Dequeue] D: 12 N: 11 BUF_LEN: 20 <br>
[Dequeue] D: 23 N: 10 BUF_LEN: 20 <br>
[Dequeue] D: 34 N: 9 BUF_LEN: 20 <br>
[Enqueue] D: 34 N: 10 BUF_LEN: 20 <br>
[Enqueue] D: 56 N: 11 BUF_LEN: 20 <br>
[Dequeue] D: 56 N: 10 BUF_LEN: 20 <br>
[Dequeue] D: 11 N: 9 BUF_LEN: 20 <br>
[Dequeue] D: 22 N: 8 BUF_LEN: 20 <br>
[Enqueue] D: 123 N: 9 BUF_LEN: 20 <br>
[Enqueue] D: 67 N: 10 BUF_LEN: 20 <br>
[Enqueue] D: 56 N: 11 BUF_LEN: 20 <br>
[Enqueue] D: 78 N: 12 BUF_LEN: 20 <br>
[Dequeue] D: 97 N: 11 BUF_LEN: 20 <br>
[Dequeue] D: 0 N: 10 BUF_LEN: 20 <br>
[Enqueue] D: 45 N: 11 BUF_LEN: 20 <br>
[Dequeue] D: 12 N: 10 BUF_LEN: 20 <br>
[Enqueue] D: 78 N: 11 BUF_LEN: 20 <br>
[Dequeue] D: 23 N: 10 BUF_LEN: 20 <br>
[Enqueue] D: 23 N: 11 BUF_LEN: 20 <br>
[Dequeue] D: 77 N: 10 BUF_LEN: 20 <br>
[Enqueue] D: 1256 N: 11 BUF_LEN: 20 <br>
[Dequeue] D: 88 N: 10 BUF_LEN: 20 <br>
[Dequeue] D: 34 N: 9 BUF_LEN: 20 <br>
[Enqueue] D: 4 N: 10 BUF_LEN: 20 <br>

Items left on queue: 10
*** glibc detected *** ./a.out: free(): invalid next size (fast): 0x0000000000b7f030 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x7e626)[0x7fc65d098626]
./a.out[0x400bac]
./a.out[0x400c88]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xed)[0x7fc65d03b76d]
./a.out[0x4006c9]
======= Memory map: ========
00400000-00402000 r-xp 00000000 08:06 1969214                            /home/mohit/learnc/algoritms/a.out
00601000-00602000 r--p 00001000 08:06 1969214                            /home/mohit/learnc/algoritms/a.out
00602000-00603000 rw-p 00002000 08:06 1969214                            /home/mohit/learnc/algoritms/a.out
00b7f000-00ba0000 rw-p 00000000 00:00 0                                  [heap]
7fc65cd20000-7fc65ce19000 r-xp 00000000 08:06 2756166                    /lib/x86_64-linux-gnu/libm-2.15.so
7fc65ce19000-7fc65d018000 ---p 000f9000 08:06 2756166                    /lib/x86_64-linux-gnu/libm-2.15.so
7fc65d018000-7fc65d019000 r--p 000f8000 08:06 2756166                    /lib/x86_64-linux-gnu/libm-2.15.so
7fc65d019000-7fc65d01a000 rw-p 000f9000 08:06 2756166                    /lib/x86_64-linux-gnu/libm-2.15.so
7fc65d01a000-7fc65d1cd000 r-xp 00000000 08:06 2756134                    /lib/x86_64-linux-gnu/libc-2.15.so
7fc65d1cd000-7fc65d3cc000 ---p 001b3000 08:06 2756134                    /lib/x86_64-linux-gnu/libc-2.15.so
7fc65d3cc000-7fc65d3d0000 r--p 001b2000 08:06 2756134                    /lib/x86_64-linux-gnu/libc-2.15.so
7fc65d3d0000-7fc65d3d2000 rw-p 001b6000 08:06 2756134                    /lib/x86_64-linux-gnu/libc-2.15.so
7fc65d3d2000-7fc65d3d7000 rw-p 00000000 00:00 0 
7fc65d3d7000-7fc65d3ec000 r-xp 00000000 08:06 2756155                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fc65d3ec000-7fc65d5eb000 ---p 00015000 08:06 2756155                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fc65d5eb000-7fc65d5ec000 r--p 00014000 08:06 2756155                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fc65d5ec000-7fc65d5ed000 rw-p 00015000 08:06 2756155                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fc65d5ed000-7fc65d6cf000 r-xp 00000000 08:06 3678116                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.16
7fc65d6cf000-7fc65d8ce000 ---p 000e2000 08:06 3678116                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.16
7fc65d8ce000-7fc65d8d6000 r--p 000e1000 08:06 3678116                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.16
7fc65d8d6000-7fc65d8d8000 rw-p 000e9000 08:06 3678116                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.16
7fc65d8d8000-7fc65d8ed000 rw-p 00000000 00:00 0 
7fc65d8ed000-7fc65d90f000 r-xp 00000000 08:06 2756114                    /lib/x86_64-linux-gnu/ld-2.15.so
7fc65dae6000-7fc65daeb000 rw-p 00000000 00:00 0 
7fc65db0b000-7fc65db0f000 rw-p 00000000 00:00 0 
7fc65db0f000-7fc65db10000 r--p 00022000 08:06 2756114                    /lib/x86_64-linux-gnu/ld-2.15.so
7fc65db10000-7fc65db12000 rw-p 00023000 08:06 2756114                    /lib/x86_64-linux-gnu/ld-2.15.so
7fff2987b000-7fff2989c000 rw-p 00000000 00:00 0                          [stack]
7fff299b0000-7fff299b1000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted

Question: Why I'm getting this error when ~Queue() has been called for free(buffer)

I have edited the original question which was "delete buffer instead of free(buffer)".

Why are you mixing and matching the C++ style delete operator with the C style malloc function? — Tushar
– Tushar, Commented Mar 26, 2013 at 5:49
I'm just learning malloc/free/delete. Thanks for pointing this out. Please tell me why libc error is coming. — mohit
– mohit, Commented Mar 26, 2013 at 5:50
You're learning malloc/free/delete? You should be learning either malloc/free or new/delete, but not malloc/free/delete. Be warned that whoever is teaching you is teaching you wrong. — Michael Francis
– Michael Francis, Commented Mar 26, 2013 at 5:56
@pst The glibc report says free. I think if he knew what to do, like you do, he wouldn't have asked this question. — GraphicsMuncher
– GraphicsMuncher, Commented Mar 26, 2013 at 5:57
This cannot be a minimal example that can be run and still exhibits the problem, can it? — Thomas Padron-McCarthy
– Thomas Padron-McCarthy, Commented Mar 26, 2013 at 6:00

GraphicsMuncher · Accepted Answer · 2013-03-26 06:00:46Z

1

Your error is stemming from the fact that you're mixing calls to malloc with calls to delete.

Solution: Everything you allocate with malloc, you deallocate with free. Everything you create with new you destroy with delete. If you mix and match you get undefined behavior, which most assuredly means bugs and errors, as you have witnessed here.

Try this instead:

free(buffer);

answered Mar 26, 2013 at 6:00

GraphicsMuncher

4,6514 gold badges38 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Michael Francis Over a year ago

@pst (It could also cause your machine to launch a malicious attack against The Pentagon in an attempt to obtain nuclear launch codes..)

mohit Over a year ago

Thanks GraphicsMuncher. I tried with free(buffer) .What I noticed, when dequeue commands are less probable than enqueue commands, I always face this issue. But when Enqueue & Dequeue commands are equally probable I never have this issue. e.g. <br>./a.out 12 23 34 56 11 22 33 44 55 66 77 88 - - - 34 56 - - - - - - - - - - 123 67 56 78 - - 45 - 78 - 23 - 1256 - - 4

mohit · Accepted Answer · 2013-03-26 09:05:36Z

I got my problem solved. It's a Logical error. Using Valgrind i got the root cause. Issue: function enqueue() has logical error during (N == _buf_len), i need to add one more conditon (N == _buf_len || r == _buf_len).
e.g. When Buf_len = 8 (malloc for 32 bytes), r = 8, n = 5, and if enqueue has been called again, I tried to insert the object at boundary i.e buffer[8]. and when at destructor, I tried to free the block, it points to memory outside which was allocated by malloc.


void Queue::enqueue(DATA_TYPE c)
{ 
  if(N == 0)
    resize(1);
  else
    if(N == _buf_len || r == _buf_len)
      resize(N * 2);
  buffer[r++] = c;
  N++; 
  Log("[Enqueue] D: %d N: %d BUF_LEN: %d R: %d F: %d BUFFER: %p\n", c, N, _buf_len, r, f, buffer);
}

DATA_TYPE Queue::dequeue(void)
{
   DATA_TYPE c = buffer[f++]; 
   N--;
   if(N > 0 && N == _buf_len / 4)
     _buf_len / 2 == 0 ? resize(1) : resize( _buf_len / 2); 
   Log("[Dequeue] D: %d N: %d BUF_LEN: %d R: %d F: %d BUFFER: %p\n", c, N, _buf_len, r, f, buffer);
   return c;
}

Collectives™ on Stack Overflow

malloc / free for resizing array

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related