Segmentation fault at qsort's compare functor

Question

I have the following struct, composed by a pointer to the next Point (nextPoint), the point's height (realHeight) and a 3D coordinate (point) from the OpenCV library, which has 3 parameters (x,y,z) :

typedef struct _cloudPoint {
    double realHeight;
    cv::Point3f point;
    _cloudPoint* nextPoint;
} cloudPoint;

And then, I need to sort a vector of cloudPoint, that I pass by pointer to a function. So i have this function's input argument:

std::vector<cloudPoint>* cPointsVector

Inside my function, I wish to sort the cPointsVector vector, using qsort, and this compare functor:

int cmp_unique(const void* _pa_, const void* _pb_) {
     Segmentation::cloudPoint* pa = (Segmentation::cloudPoint*)_pa_;
     Segmentation::cloudPoint* pb = (Segmentation::cloudPoint*)_pb_;

     if (pa->point.x > pb->point.x) {
          return -1;
     }
     else {
          if (pa->point.y > pb->point.y) {
               return -1;
          }
          else {
               if (pa->point.z > pb->point.z) {
                    return -1;
               }
          }
    }
    return 1;
}

So, to call qsort I use:

qsort(cPointsVector, cPointsVector->size(), sizeof(cloudPoint), cmp_unique);

But in the middle of the sorting process, it gives me an Segmentation fault on the functor's first if :

if (pa->point.x > pb->point.x) {

By just analysing my code, or I'm performing some incorrect memory access inside the compare functor, or the cPointsVector is being badly filled, but neither the hypotesis make sence, since I allways use non-Null cloudPoint's, with non-Null OpenCV coordinate points.

Thanks in advance

@PaulMcKenzie Because I'm upgrading some of my code from c to c++, and wanted to be sure that everything is performing as it's supposed before upgrading from c to c++ functions. Do you think this could be the source of my problem? I will switch and update you with the results. — Diogo, Nov 21 '19 at 18:23
There are almost no good reasons to use a pointer to a `vector`. You may be making this overly hard on yourself. Recommendation: Don't try to program in C++ the way you would program in C. It looks tempting, but it will cause you more problems than it's worth. — user4581301, Nov 21 '19 at 18:23
@user4581301 I use a pointer to vector because I need to change the values inside the vector, and I can't change it if I pass the vector instead of a pointer to it. — Diogo, Nov 21 '19 at 18:25
@Diogo -- As soon as you saw `qsort`, you should have immediately switched to `std::sort`. `std::sort(cPointsVector.begin(), cPointsVector.end(), your_predicate);`. No casting need be done, intuitive, and it probably runs faster than `qsort`. — PaulMcKenzie, Nov 21 '19 at 18:26
@Diogo That is a relief. Normally this happens because the `vector` was dynamically allocated. Still, you can do it a bit better (and all but eliminate the possibility of a null `vector`) by passing the `vector` by reference. — user4581301, Nov 21 '19 at 18:27
*I use a pointer to vector...* -- C++ has something called a `reference`, which does not exist in C. — PaulMcKenzie, Nov 21 '19 at 18:27
Also, it is undefined behavior to start your identifiers with underscores, like `_pa_`. In addition, is this what you are looking for: `std::sort(cPointsVector->begin(), cPointsVector->end(), [](Segmentation::cloudPoint* s1, Segmentation::cloudPoint *s2) { return std::tie(s1->point.x, s1->point.y, s1->point.z) > std::tie(s2->point.x, s2->point.y, s2->point.z); });`? — PaulMcKenzie, Nov 21 '19 at 18:32
Thanks for the suggestions @PaulMcKenzie. But why do you say it's an undefined behaviour using `_pa_`, I get no compilation/linker errors. — Diogo, Nov 21 '19 at 18:35
Identifiers starting with underscores are reserved for the compiler implementation. You risk clashing with a name that the compiler is internally using. — PaulMcKenzie, Nov 21 '19 at 18:36
Expanding on Paul's comment about underscores. It's a bit more complicated than he suggests, so you have two choices: [Know the rules](https://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier) or never use a leading underscore. I prefer the first because leading underscores are only the first surprise. You are never allowed to use two underscores in a row anywhere in an identifier. — user4581301, Nov 21 '19 at 18:42
@PaulMcKenzie I do not think it is UB in this case. Local identifiers with one underscore and not starting with capital letter is fine. Though `_cloudPoint ` is UB as it is in global. — Slava, Nov 21 '19 at 19:29
Note: you should not use `typedef struct` in C++ (it is terrible idiom even in C, but that is different story) — Slava, Nov 21 '19 at 19:32

score 1 · Accepted Answer · edited Nov 21 '19 at 18:27

1

Try call it like this:

qsort(&(*cPointsVector)[0], cPointsVector->size(), sizeof(cloudPoint), cmp_unique);

or

qsort(cPointsVector->data(), cPointsVector->size(), sizeof(cloudPoint), cmp_unique);

When you pass cPointsVector to qsort, you pass a pointer to a vector object, instead of pointer to a first element of a vector. Remember, a vector in C++ is not a C array. It is an object, that encapsulates a C array that has a different address from vector's address.

edited Nov 21 '19 at 18:27

donjuedo

2,475
18
28

answered Nov 21 '19 at 18:21

273K

29,503
10
41
64

Thank you very much, this worked perfectly. Still, when I run the original code, the functor is performed about 300 times before a segmentation fault. Why? – Diogo Nov 21 '19 at 18:31
1

@Diogo pure dumb luck. While the program was rampaging through random memory, it simply didn't run into any conditions that caused a crash. Likely what finally took the program down is it ran off the end of the stack. Never ever count on a crash. The term for what you had here is [Undefined Behaviour](https://en.cppreference.com/w/cpp/language/ub) and the the results of undefined behaviour are , well, undefined. – user4581301 Nov 21 '19 at 18:35
@user4581301 Thanks for the answer – Diogo Nov 21 '19 at 18:37
1

You should provide proper solution using `std::sort()` as well as this is a workaround and may soon have UB when non POD is used. – Slava Nov 21 '19 at 19:29

score 0 · Answer 2 · answered Nov 22 '19 at 14:57

Even though you want to use qsort, this is the way you should eventually accomplish sorting using std::sort:

std::sort(cPointsVector->begin(), cPointsVector->end(), 
          [](Segmentation::cloudPoint* s1, Segmentation::cloudPoint *s2) 
{ 
    return std::tie(s1->point.x, s1->point.y, s1->point.z) > 
           std::tie(s2->point.x, s2->point.y, s2->point.z); 
});

Note that there is no C-style casting that is done, as std::sort is type-safe.

The lambda function basically does what your qsort comparison was attempting to do, and that is to sort by (x,y,z) in descending order.

The std::tie is a simple way to do the cascading if statements, comparing x's with x's, y's wth y's, etc.

Segmentation fault at qsort's compare functor

2 Answers2