0

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

ログ.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;
}

で実行中の上記の言及コード

./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

~Queue()質問: free(buffer) が呼び出されたときにこのエラーが発生するのはなぜですか?

「free（buffer）の代わりにバッファを削除する」という元の質問を編集しました。

4

2 に答える 2

1

あなたのエラーは、 への呼び出しと へmallocの呼び出しを混在させているという事実に起因していますdelete。

解決策: で割り当てたものはすべてmalloc、 で割り当てを解除しfreeます。あなたが作成したものはすべて、newあなたで破壊しdeleteます。ここで目撃したように、混合して一致させると、未定義の動作が発生します。これは、間違いなくバグとエラーを意味します。

代わりにこれを試してください：

free(buffer);
于 2013-03-26T06:00:46.777 に答える
1

私の問題は解決しました。論理エラーです。Valgrind を使用して、根本的な原因を突き止めました。問題: 関数 enqueue() で (N == _buf_len) 中に論理エラーが発生しました。条件をもう 1 つ追加する必要があります (N == _buf_len || r == _buf_len)。
たとえば、Buf_len = 8 (32 バイトの malloc)、r = 8、n = 5 の場合、enqueue が再度呼び出された場合、オブジェクトを境界、つまり buffer[8] に挿入しようとしました。デストラクタでブロックを解放しようとすると、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;
}

于 2013-03-26T08:42:53.713 に答える