1
なぜこのエラーが発生するのかを理解するのに役立ちます。私はエラーとコードを提供します。glibcエラーが発生するのはなぜですか？
**** Testing mergesort ****
Testing simple two-element merge:
OK
Testing 20-element merge (10 and 10): OK
Testing 21-element merge: OK
*** glibc detected *** ./assign3_test: free(): invalid next size (normal): 0x00000000013521c0 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x75bb6)[0x7fa0478cbbb6]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x6c)[0x7fa0478d095c]
./assign3_test[0x403a34]
./assign3_test[0x403506]
./assign3_test[0x402923]
./assign3_test[0x401fdb]
./assign3_test[0x4017c9]
./assign3_test[0x401cc4]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xfd)[0x7fa047874ead]
./assign3_test[0x400ca9]
======= Memory map: ========
00400000-00408000 r-xp 00000000 08:01 5511315 /home/cs/jpham/cs133_assign/assign3/assign3_test
00607000-00608000 rw-p 00007000 08:01 5511315 /home/cs/jpham/cs133_assign/assign3/assign3_test
01352000-01373000 rw-p 00000000 00:00 0 [heap]
7fa040000000-7fa040021000 rw-p 00000000 00:00 0
7fa040021000-7fa044000000 ---p 00000000 00:00 0
7fa047856000-7fa0479da000 r-xp 00000000 08:01 6559005 /lib/x86_64-linux-gnu/libc-2.13.so
7fa0479da000-7fa047bd9000 ---p 00184000 08:01 6559005 /lib/x86_64-linux-gnu/libc-2.13.so
7fa047bd9000-7fa047bdd000 r--p 00183000 08:01 6559005 /lib/x86_64-linux-gnu/libc-2.13.so
7fa047bdd000-7fa047bde000 rw-p 00187000 08:01 6559005 /lib/x86_64-linux-gnu/libc-2.13.so
7fa047bde000-7fa047be3000 rw-p 00000000 00:00 0
7fa047be3000-7fa047bf8000 r-xp 00000000 08:01 6553604 /lib/x86_64-linux-gnu/libgcc_s.so.1
7fa047bf8000-7fa047df8000 ---p 00015000 08:01 6553604 /lib/x86_64-linux-gnu/libgcc_s.so.1
7fa047df8000-7fa047df9000 rw-p 00015000 08:01 6553604 /lib/x86_64-linux-gnu/libgcc_s.so.1
7fa047df9000-7fa047e7a000 r-xp 00000000 08:01 6559009 /lib/x86_64-linux-gnu/libm-2.13.so
7fa047e7a000-7fa048079000 ---p 00081000 08:01 6559009 /lib/x86_64-linux-gnu/libm-2.13.so
7fa048079000-7fa04807a000 r--p 00080000 08:01 6559009 /lib/x86_64-linux-gnu/libm-2.13.so
7fa04807a000-7fa04807b000 rw-p 00081000 08:01 6559009 /lib/x86_64-linux-gnu/libm-2.13.so
7fa04807b000-7fa048163000 r-xp 00000000 08:01 9178929 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.17
7fa048163000-7fa048363000 ---p 000e8000 08:01 9178929 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.17
7fa048363000-7fa04836b000 r--p 000e8000 08:01 9178929 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.17
7fa04836b000-7fa04836d000 rw-p 000f0000 08:01 9178929 /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.17
7fa04836d000-7fa048382000 rw-p 00000000 00:00 0
7fa048382000-7fa0483a2000 r-xp 00000000 08:01 6558995 /lib/x86_64-linux-gnu/ld-2.13.so
7fa048586000-7fa04858b000 rw-p 00000000 00:00 0
7fa04859e000-7fa0485a1000 rw-p 00000000 00:00 0
7fa0485a1000-7fa0485a2000 r--p 0001f000 08:01 6558995 /lib/x86_64-linux-gnu/ld-2.13.so
7fa0485a2000-7fa0485a3000 rw-p 00020000 08:01 6558995 /lib/x86_64-linux-gnu/ld-2.13.so
7fa0485a3000-7fa0485a4000 rw-p 00000000 00:00 0
7fff84fb6000-7fff84fd7000 rw-p 00000000 00:00 0 [stack]
7fff84fed000-7fff84fee000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
Aborted
私はエラーがその関数の呼び出し中に発生していたかどうかを確認しようとしていたので、私は私のマージ機能をコメントアウト。私は関数がtest_merge（）関数を渡すことを知っていますが、何が起こったのかは分かりません。
#include <iostream>
using namespace std;
/*
* mergesort.cpp
* Implementation of a bitonic mergesort
*/
/* merge(input, size, output, asc)
Merge the two halves of the array input (which has size elements) into
output. If asc is true, then the output array should be in ascending order;
otherwise it should be descending.
*/
void merge(int* input, int size, int* output, bool output_asc) {
// Your merge implementation goes here
if(output_asc){
int i = 0, j = size-1, k = 0;
while(i < size/2 && j >= 0){
if(input[i] < input[j]){
output[k++] = input[i++];
}
else
output[k++] = input[j--];
}
while(i < size/2)
output[k++] = input[i++];
while(j >= 0)
output[k++] = input[j--];
}
else{
int i = size/2 -1, j = size/2, k = 0;
while(i >= 0 && j < size){
if(input[i] > input[j])
output[k++] = input[i--];
else
output[k++] = input[j++];
}
while(i >= 0)
output[k++] = input[i--];
while(j < size)
output[k++] = input[j++];
}
}
/* mergesort(input, size, output, asc)
Mergesort the input array (with size elements) into the output array. If
asc is true, the output array should be sorted ascending, otherwise it should
be descending.
*/
void mergesort(int *input, int size, int* output, bool output_asc) {
// Your mergesort implementation goes here
cout << "Flag" << endl;
/*if(size == 0){}
else if(size == 1){
output[0] = input[0];
}
else{
int* temp = new int[size];
int mid = size/2;
mergesort(input, mid, temp, output_asc);
mergesort(input + mid, size - mid, temp + mid, output_asc);
merge(temp, size, output, output_asc);
}*/
}
/* mergesort(input, size)
Sorts size elements in the array pointed to by input, using the MergeSort
algorithm. Output is returned as a newly allocated array, which the caller
is responsible for freeing.
*/
int* mergesort(int* input, int size) {
int* output = new int[size];
mergesort(input, size, output, true);
return output;
}
上記の実装プログラムが動作するかどうかを確認するためのテストファイルです。
/*
* assign3_test.cpp
* Test runner for assignment 3
*/
#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <vector>
using namespace std;
/* make_random_vector(len)
Returns a vector<int> of random values, where each entry is between 0 and
INT_MAX. The optional second parameter lets you specify the seed to be used
for the RNG.
*/
std::vector<int> make_random_vector(
std::size_t len,
int seed = 1)
{
std::default_random_engine generator(seed);
std::uniform_int_distribution<int> distribution;
auto gen = std::bind(distribution, generator);
// Fill with random values
std::vector<int> ret(len, 0);
for(std::size_t i = 0; i < len; ++i)
ret.at(i) = gen() % 100;
return ret;
}
/* make_random_permutation(len)
Returns a vector of length len containing a random permutation of the
integers 0...len-1. This can, of course, be used to randomly permute any
vector of length len.
*/
std::vector<unsigned> make_random_permutation(
std::size_t len,
int seed = 1)
{
std::default_random_engine generator(seed);
std::vector<unsigned> ret(len, 0);
// Initialize vector to 0...len-1
for(std::size_t i = 0; i < len; ++i)
ret.at(i) = i;
std::shuffle(ret.begin(), ret.end(), generator);
return ret;
}
/* These functions must be defined in the student's code */
void merge(int* input, int size, int* output, bool output_asc);
int* mergesort(int* input, int size);
void mergesort(int *input, int size, int* output, bool output_asc);
// Convenience function for using mergesort on vectors
int* mergesort(const vector<int>& data) {
return mergesort(const_cast<int*>(&data[0]), data.size());
}
/* is_sorted(data, size)
Returns true if the data is sorted ascending.
*/
bool is_sorted(int* data, int size) {
for(int* p = data + 1; p < data + size; ++p) {
if(*p < *(p-1))
return false;
}
return true;
}
bool is_permutation(int* input, int size, int* sorted) {
for(int i = 0; i < size; ++i) {
// Check if input[i] is in sorted
int elem = input[i];
bool found = false;
for(int j = 0; j < size; ++j)
if(sorted[j] == elem) {
found = true;
break;
}
if(!found)
return false;
// Check if sorted[i] is in input
elem = sorted[i];
found = false;
for(int j = 0; j < size; ++j)
if(input[j] == elem) {
found = true;
break;
}
if(!found)
return false;
}
return true;
}
/* out << vec
Convenience overload for printing vector<int>
*/
ostream& operator<<(ostream& out, const vector<int>& data) {
out << "{";
for(unsigned i = 0; i < data.size() - 1; ++i)
out << data[i] << ", ";
out << data.back() << "}";
return out;
}
/* random_growth(start,size,asc)
Generates a vector whose values start at start and either increase (if asc is
true) or decrease by random increments. The increment is in the range
0...8.
*/
void random_growth(int* data, int start, int size, bool asc) {
std::default_random_engine generator(17);
std::uniform_int_distribution<int> distribution(0,9);
auto rnd = std::bind(distribution, generator);
const int step = asc ? +1 : -1;
if(size > 0) {
data[0] = start;
for(int i = 1; i < size; ++i)
data[i] = data[i-1] + step * rnd();
}
}
/* test_merge()
Test the merge() function.
This basically just checks merge() to make sure that the output is merged
in the correct order. We also check things like merging small arrays
(size 0, 1, 2, and 3) since those are easy to get wrong. The system also
checks the amount of space allocated before and after this function is
called and will return false if anything has been malloc()'d.
*/
bool test_merge() {
cout << "Testing simple two-element merge: \n";
vector<int> v1 = { 1, 2 };
vector<int> vout = { -1, -1 };
// Merge asc.
merge(&v1[0], 2, &vout[0], true);
if(vout[0] != 1 || vout[1] != 2) {
cout << "FAILED: merge result was " << vout << ".\n";
return false;
}
// Merge desc.
merge(&v1[0], 2, &vout[0], false);
if(vout[0] != 2 || vout[1] != 1) {
cout << "FAILED: merge result was " << vout << ".\n";
return false;
}
cout << "OK\n";
// Generate asc-desc dataset for testing
cout << "Testing 20-element merge (10 and 10): ";
vector<int> data(20);
random_growth(&data[0], 0, 10, true);
random_growth(&data[10], 2, 10, false);
vector<int> dataout(20);
merge(&data[0], data.size(), &dataout[0], true);
if(!is_sorted(&dataout[0], data.size())) {
cout << "FAILED: merge did not produce sorted output : "
<< dataout << endl;
return false;
}
cout << "OK\n";
cout << "Testing 21-element merge: ";
data.resize(21);
random_growth(&data[0], 0, 10, true);
random_growth(&data[10], 2, 11, false);
dataout.resize(21);
merge(&data[0], data.size(), &dataout[0], true);
if(!is_sorted(&dataout[0], data.size())) {
cout << "FAILED: merge did not produce sorted output : "
<< dataout << endl;
return false;
}
cout << "OK\n";
return true;
}
/* test_mergesort()
Test mergesort on a variety of inputs.
*/
bool test_mergesort() {
cout << "Sorting empty sequence:";
vector<int> no_data;
int* no_data_sorted = mergesort(no_data);
// No data means nothing to check!
delete[] no_data_sorted;
cout << "OK\n";
vector<int> sizes = {2, 3, 4, 5, 7, 8, 15, 16, 19, 20, 50, 64, 100, 128};
for(int s : sizes) {
// Test sorting a vector of random data
vector<int> data = make_random_vector(s);
cout << "Sorting random vector of size " << s << ":\n" << data << "\n";
int* data_sorted = mergesort(data);
if(!is_sorted(data_sorted, data.size())) {
cout << "FAILED: result is not sorted:\n";
cout << "{";
for(int* i = data_sorted; i != data_sorted + data.size() - 1; ++i)
cout << *i << ", ";
cout << data_sorted[data.size() - 1] << "}\n";
return false;
}
else if(!is_permutation(&data[0], data.size(), data_sorted)) {
cout << "FAILED: result is not a permutation of the input sequence:\n";
cout << "{";
for(int* i = data_sorted; i != data_sorted + data.size() - 1; ++i)
cout << *i << ", ";
cout << data_sorted[data.size() - 1] << "}\n";
return false;
}
else
cout << "OK\n";
}
return true;
}
int main() {
cout << "**** Testing mergesort ****\n";
if(test_merge() &&
test_mergesort())
cout << "**** All tests passed! ****\n";
return 0;
}