I've been doing a DSA course online and this is my attempt at a solution for one of the problems. I acknowledge that I know very little about C++ and I shouldn't be messing around with structs and pointers at all, but I've been trying this for a while in order to learn a bit on my own and I can't seem to figure out what is wrong.
Problem Statement: Given a set of n segments {[a 0 , b 0 ], [a 1 , b 1 ], . . . , [a n−1 , b n−1 ]} with integer coordinates on a line, find the minimum number m of points such that each segment contains at least one point. That is, find a set of integers X of the minimum size such that for any segment [a i , b i ] there is a point x ∈ X such that a i ≤ x ≤ b i .
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <unistd.h>
std::vector<int> output;
struct linedata
{
int start;
int end;
bool covered = false;
struct linepoint* sloc = (struct linepoint*)malloc(sizeof(struct linepoint*));
struct linepoint* eloc = (struct linepoint*)malloc(sizeof(struct linepoint*));
};
struct linepoint
{
int coord;
bool start;
struct linedata* refer = (struct linedata*)malloc(sizeof(struct linedata*));
struct linepoint* selfrefer = (struct linepoint*)malloc(sizeof(struct linepoint*));
};
bool linesort(struct linepoint a, struct linepoint b)
{
struct linepoint* atemp = (struct linepoint*)malloc(sizeof(struct linepoint*));
atemp = a.selfrefer;
struct linepoint* btemp = (struct linepoint*)malloc(sizeof(struct linepoint*));
btemp = b.selfrefer;
std::cout << a.selfrefer << " " << b.selfrefer << "\n";
if(a.coord < b.coord)
{
if(a.start == true)
{
atemp -> refer -> sloc = btemp;
}
if(a.start == false)
{
atemp -> refer -> eloc = btemp;
}
if(b.start == true)
{
btemp -> refer -> sloc = atemp;
}
if(b.start == true)
{
btemp -> refer -> sloc = atemp;
}
std::swap(b.selfrefer -> coord, a.selfrefer -> coord);
std::swap(b.selfrefer -> start, a.selfrefer -> start);
std::swap(b.selfrefer -> refer, a.selfrefer -> refer);
std::swap(b.selfrefer -> selfrefer, a.selfrefer -> selfrefer);
return false;
}
if((a.coord == b.coord) && (a.start > b.start))
{
if(a.start == true)
{
a.selfrefer -> refer -> sloc = b.selfrefer;
}
if(a.start == false)
{
a.selfrefer -> refer -> eloc = b.selfrefer;
}
if(b.start == true)
{
b.selfrefer -> refer -> sloc = a.selfrefer;
}
if(b.start == true)
{
b.selfrefer -> refer -> sloc = a.selfrefer;
}
std::swap(b.selfrefer -> coord, a.selfrefer -> coord);
std::swap(b.selfrefer -> start, a.selfrefer -> start);
std::swap(b.selfrefer -> refer, a.selfrefer -> refer);
std::swap(b.selfrefer -> selfrefer, a.selfrefer -> selfrefer);
return false;
}
return false;
}
int rescan(int point, struct linedata lines[], struct linepoint points[], int scanlength, bool tosort)
{
output.push_back(point);
int removed = 0;
for(int i = 0; i < scanlength; i++)
{
if((lines[i].covered == false) && (lines[i].start <= point) && (lines[i].end >= point))
{
lines[i].covered = true;
lines[i].sloc -> coord = INT_MAX - lines[i].start;
lines[i].eloc -> coord = INT_MAX - lines[i].end;
removed = removed + 1;
}
}
if(tosort == true)
{
std::sort(points, points+2*scanlength, linesort);
}
return removed;
}
int main(void)
{
int num;
std::cin >> num;
int left = 0;
int track = 0;
struct linedata lines[num];
struct linepoint points[2*num];
struct linepoint* indexor[2*num];
for(int i = 0; i < num; i++)
{
std::cin >> lines[i].start >> lines[i].end;
points[2*i].coord = lines[i].start;
points[2*i].start = true;
points[2*i + 1].coord = lines[i].end;
points[2*i + 1].start = false;
lines[i].sloc = &points[2*i];
lines[i].eloc = &points[2*i + 1];
points[2*i].selfrefer = &points[2*i];
points[2*i + 1].selfrefer = &points[2*i + 1];
left = left + 1;
if(lines[i].start == lines[i].end)
{
left = left - rescan(lines[i].start, lines, points, i + 1, false);
}
}
for(int i = 0; i < 2*num; i++)
{
std::cout << i << " " << points[i].coord << " " << points[i].start << " " << sizeof(&points[i]) << " " << &points[i] << "\n";
}
std::sort(points, points+2*num, linesort);
while(left)
{
for(int i = 0; i < left; i++)
{
if(points[i].start == true)
{
std::cout << "loop part 1: " << left << " " << i << "\n";
for(int i = 0; i < 2*num; i++)
{
std::cout << i << " " << points[i].coord << " " << points[i].start << "\n";
}
sleep(1);
track = track + 1;
continue;
}
if((track != 0) && (points[i].start == false))
{
left = left - rescan(points[i].coord, lines, points, num, true);
std::cout << "loop part 2: " << left << " " << i << "\n";
for(int i = 0; i < 2*num; i++)
{
std::cout << i << " " << points[i].coord << " " << points[i].start << "\n";
}
sleep(1);
track = 0;
continue;
}
}
}
std::cout << output.size() << "\n";
for(int i = 0; i < output.size(); i++)
{
std::cout << output.at(i) << " ";
}
std::cout << "\n";
}
The code behaves unpredictably, to say the least. I'm pretty sure there's some undefined condition in my code and both libasan and valgrind complain about invalid writes in the linesort function. Seeing how the invalid writes are of size 8, I think the writes are pertaining to me exchanging memory addresses to cross-reference linepoint and linedata structs. But seeing how it errors out randomly, I don't know what is causing it to behave like this.
This is from a couple of libasan runs
4
4 7
1 3
2 5
5 6
0 4 1 8 0x7ffe0c863880
1 7 0 8 0x7ffe0c863898
2 1 1 8 0x7ffe0c8638b0
3 3 0 8 0x7ffe0c8638c8
4 2 1 8 0x7ffe0c8638e0
5 5 0 8 0x7ffe0c8638f8
6 5 1 8 0x7ffe0c863910
7 6 0 8 0x7ffe0c863928
0x7ffe0c863898 0x7ffe0c863880
0x7ffe0c863898 0x7ffe0c863880
0x7ffe0c8638b0 0x7ffe0c863880
=================================================================
==188113==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001a0 at pc 0x562db1500d54 bp 0x7ffe0c8635e0 sp 0x7ffe0c8635d0
WRITE of size 8 at 0x6020000001a0 thread T0
#0 0x562db1500d53 in linesort(linepoint, linepoint) /home/kevin/Downloads/Week3_5.cpp:37
#1 0x562db1502ac0 in bool __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>::operator()<linepoint*, linepoint*>(linepoint*, linepoint*) /usr/include/c++/10/bits/predefined_ops.h:156
#2 0x562db1502ac0 in void std::__insertion_sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1846
#3 0x562db1500341 in void std::__final_insertion_sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1891
#4 0x562db1500341 in void std::__sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1977
#5 0x562db1500341 in void std::sort<linepoint*, bool (*)(linepoint, linepoint)>(linepoint*, linepoint*, bool (*)(linepoint, linepoint)) /usr/include/c++/10/bits/stl_algo.h:4892
#6 0x562db1500341 in main /home/kevin/Downloads/Week3_5.cpp:137
#7 0x7febd76450b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#8 0x562db150063d in _start (/home/kevin/Downloads/5+0x363d)
0x6020000001a0 is located 8 bytes to the right of 8-byte region [0x602000000190,0x602000000198)
allocated by thread T0 here:
#0 0x7febd7abc517 in malloc (/lib/x86_64-linux-gnu/libasan.so.6+0xb0517)
#1 0x562db14ff7e9 in linepoint::linepoint() /home/kevin/Downloads/Week3_5.cpp:18
#2 0x562db14ff7e9 in main /home/kevin/Downloads/Week3_5.cpp:112
#3 0x7febd76450b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
SUMMARY: AddressSanitizer: heap-buffer-overflow /home/kevin/Downloads/Week3_5.cpp:37 in linesort(linepoint, linepoint)
Shadow bytes around the buggy address:
0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff8000: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8010: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8020: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
=>0x0c047fff8030: fa fa 00 fa[fa]fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8040: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8050: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==188113==ABORTING
5
2 6
8 19
2 5
1 2
56 981
0 2 1 8 0x7ffdc275be20
1 6 0 8 0x7ffdc275be38
2 8 1 8 0x7ffdc275be50
3 19 0 8 0x7ffdc275be68
4 2 1 8 0x7ffdc275be80
5 5 0 8 0x7ffdc275be98
6 1 1 8 0x7ffdc275beb0
7 2 0 8 0x7ffdc275bec8
8 56 1 8 0x7ffdc275bee0
9 981 0 8 0x7ffdc275bef8
0x7ffdc275be38 0x7ffdc275be20
0x7ffdc275be38 0x7ffdc275be20
0x7ffdc275be50 0x7ffdc275be20
0x7ffdc275be50 0x7ffdc275be38
0x7ffdc275be68 0x7ffdc275be20
0x7ffdc275be68 0x7ffdc275be50
0x7ffdc275be80 0x7ffdc275be20
0x7ffdc275be80 0x7ffdc275be68
=================================================================
==188263==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000260 at pc 0x558343333d54 bp 0x7ffdc275ba80 sp 0x7ffdc275ba70
WRITE of size 8 at 0x602000000260 thread T0
#0 0x558343333d53 in linesort(linepoint, linepoint) /home/kevin/Downloads/Week3_5.cpp:37
#1 0x55834333568d in bool __gnu_cxx::__ops::_Val_comp_iter<bool (*)(linepoint, linepoint)>::operator()<linepoint, linepoint*>(linepoint&, linepoint*) /usr/include/c++/10/bits/predefined_ops.h:238
#2 0x55834333568d in void std::__unguarded_linear_insert<linepoint*, __gnu_cxx::__ops::_Val_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, __gnu_cxx::__ops::_Val_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1826
#3 0x558343335af6 in void std::__insertion_sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1854
#4 0x558343333341 in void std::__final_insertion_sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1891
#5 0x558343333341 in void std::__sort<linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)> >(linepoint*, linepoint*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(linepoint, linepoint)>) /usr/include/c++/10/bits/stl_algo.h:1977
#6 0x558343333341 in void std::sort<linepoint*, bool (*)(linepoint, linepoint)>(linepoint*, linepoint*, bool (*)(linepoint, linepoint)) /usr/include/c++/10/bits/stl_algo.h:4892
#7 0x558343333341 in main /home/kevin/Downloads/Week3_5.cpp:137
#8 0x7f4b800a50b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#9 0x55834333363d in _start (/home/kevin/Downloads/5+0x363d)
0x602000000260 is located 8 bytes to the right of 8-byte region [0x602000000250,0x602000000258)
allocated by thread T0 here:
#0 0x7f4b8051c517 in malloc (/lib/x86_64-linux-gnu/libasan.so.6+0xb0517)
#1 0x5583433327e9 in linepoint::linepoint() /home/kevin/Downloads/Week3_5.cpp:18
#2 0x5583433327e9 in main /home/kevin/Downloads/Week3_5.cpp:112
#3 0x7f4b800a50b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
SUMMARY: AddressSanitizer: heap-buffer-overflow /home/kevin/Downloads/Week3_5.cpp:37 in linesort(linepoint, linepoint)
Shadow bytes around the buggy address:
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff8000: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8010: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8020: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8030: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
=>0x0c047fff8040: fa fa 00 fa fa fa 00 fa fa fa 00 fa[fa]fa 00 fa
0x0c047fff8050: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8060: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
0x0c047fff8070: fa fa 00 fa fa fa 00 fa fa fa fa fa fa fa fa fa
0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==188263==ABORTING
I've used g++ 10 with the -O2 flag turned on. I'm running on Ubuntu 20.04. I would appreciate any help or guidance regarding this. Once again, I am very inexperienced in C++ and I might be doing things horribly wrong.
