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, Mar 26 '13 at 05:49
I'm just learning malloc/free/delete. Thanks for pointing this out. Please tell me why libc error is coming. — mohit, Mar 26 '13 at 05: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 Dorst, Mar 26 '13 at 05: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, Mar 26 '13 at 05:57
@GraphicsMuncher I think if he/she had googled `malloc`/`realloc`/`free`/`new` or `delete` and bothered to read about any of them, then he/she would not have needed to ask this question. — Michael Dorst, Mar 26 '13 at 06:00
This cannot be a _minimal_ example that can be run and still exhibits the problem, can it? — Thomas Padron-McCarthy, Mar 26 '13 at 06:00
@Tushar Thanks for guiding me for realloc. I want to learn malloc/free first. Then i think i should go for realloc. Is my comment logical? — mohit, Mar 26 '13 at 06:10
C and C++ are two different languages. Obviously you seem to be interested in an OO implementation of a queue data structure, that is veritable C++. Using `malloc`/`free` makes no sense at all, then. — Jens Gustedt, Mar 26 '13 at 06:12
http://stackoverflow.com/questions/10854210/behaviour-of-malloc-with-delete-in-c checked this ? — Charan Pai, Mar 26 '13 at 06:13
@JensGustedt yes OO for queue intention was there. But more focus is on resizing array feature without realloc. — mohit, Mar 26 '13 at 06:14
You are a C++ programmer. There is no reason to use malloc/free, especially since you don't want to use realloc. Use new[]/delete[]. Also learn the differences between malloc and new, and between free and delete. They are quite important. — john, Mar 26 '13 at 07:10
@john thanks for the advice. I will learn malloc/free for implementation the above logic in C and will use new/delele while implemetation it in C++. — mohit, Mar 26 '13 at 08:44

score 1 · Answer 1 · answered Mar 26 '13 at 06:00

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 '13 at 06:00

GraphicsMuncher

4,583
4
35
50

@pst (It _could_ also cause your machine to launch a malicious attack against The Pentagon in an attempt to obtain nuclear launch codes..) – Michael Dorst Mar 26 '13 at 06:05
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.
./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 Mar 26 '13 at 06:06

mohit · Answer 2 · 2013-03-26T09:05:36.107

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;
}

malloc / free for resizing array

2 Answers2