CODEWITHSUNDEEP
carraysstructsegmentation-faultsegment
WoodPecker
WoodPecker

Reputation: 19

qsort Segmentation Fault structs

So, my first question here, please be patient with me:

My task is to sort an array of structs (name, surname and another struct for the birthday, which consists of the year, month, day). I have to sort by birthdate and by using qsort. My problem is, I looked up everything about qsort but i am not quite sure if my implementation is correct since I am new to C. I can create the executable program but it is not giving my any result only Segmentation Fault.

Here is my Code:

#include <stdio.h>
#include <stdlib.h>

typedef int (*compfn) (const void*, const void*);

typedef struct {
    unsigned year, month, day;
} date_t;

typedef struct {
    char name[32];
    char surname[32];
    date_t birthday;
}person_t;

typedef struct {
    unsigned n;
    unsigned cap;
    person_t *arr;
} persons_t;


int compare(person_t *a, person_t *b){
  if(a->birthday.year!=b->birthday.year){
    return a->birthday.year-b->birthday.year;
  }else{
    if(a->birthday.month!=b->birthday.month){
      return a->birthday.month-b->birthday.month;
    }else{
      return a->birthday.day-b->birthday.day;
    }
  }
}

int main(int argc, char* argv[])
{
    if (argc <= 1) {
        fprintf(stderr, "syntax: %s <inputfile>\n", argv[0]);
        return 1;
    }

    FILE* f = fopen(argv[1], "rt");
    if (f == NULL) {
        fprintf(stderr, "cannot open file %s\n", argv[1]);
        return 1;
    }

    persons_t persons;
    persons.n = 0;
    persons.cap = 0;
    persons.arr = NULL;

    person_t p;
    while (fscanf(f, "%s %s %4u-%2u-%2u", p.name, p.surname,
            &p.birthday.year, &p.birthday.month, &p.birthday.day) == 5) {

        if (persons.n == persons.cap) {
            persons.cap = persons.cap == 0 ? 1 : 2 * persons.cap;
            persons.arr = realloc(persons.arr, persons.cap * sizeof(persons.arr[0]));
        }

        persons.arr[persons.n++] = p;
    }

    int nitems = persons.cap*sizeof(persons.arr[0]);
    int size = sizeof(persons.arr[0]);
    qsort(persons.arr, nitems, size, (compfn)compare);
    for (unsigned i = 0; i < persons.n; i++) {
        person_t *p = persons.arr + i;
        printf("%s %s %4u-%2u-%2u\n",
                p->name, p->surname,
                p->birthday.year, p->birthday.month, p->birthday.day);
    }



    fclose(f);
    return 0;
}

I hope someone can help me, Thanks in advance ;)

Upvotes: 0

Views: 778

Answers (2)

autistic
autistic

Reputation: 15642

As far as _t-suffixed identifiers go, according to the C standard they're reserved for the implementation (e.g. your compiler, and/or your standard library). It's very possible that your implementation already has a date_t type, and your code might be causing some kind of mischief. If you wish to avoid subtly and dangerously clashing identifiers wreaking all sorts of havoc, it's probably best to avoid them. Not to worry, you could always use '_s' to denote a struct type instead!

Whenever you're declaring a variable that represents an index within an array, use size_t as the type!

int compare(person_t *a, person_t *b){

...

qsort(persons.arr, nitems, size, (compfn)compare);

According to the qsort manual, the argument given as the comparator function should be an int (*compar)(const void *, const void *), and that's what you've given since you've cast to (compfn). As far as qsort is aware that function accepts two const void * arguments, which might differ in representation to person_t * arguments. This could certainly cause segfaults. Don't lie about the type of compare. Change it to look more like:

int compare(const void *x, const void *y) {
    const person_s *a = x, *b = y;
    /* ... */
}

... and you won't need the cast or the typedef.

Next, onto return values for that function. I have used implementations where-by lexically illogical return values cause segmentation faults. For example, if a <= b and b <= c, then a <= c, but your code doesn't guarantee this. In fact, using your code it is possible that a <= b, b <= c and a > c. I recommend making sure your code guarantees correspondence between the return value and lexical order. You can do so by returning 1 for greater than, 0 for equal to or -1 for less than.

#define lexical_order(x,y) ((x > y) - (x < y))
int compare(const void *x, const void *b){
  const person_s *a = x, *b = y;
  return a->birthday.year != b->birthday.year   ? lexical_order(a->birthday.year,  b->birthday.year)
       : a->birthday.month != b->birthday.month ? lexical_order(a->birthday.month, b->birthday.month)
                                                : lexical_order(a->birthday.day,   b->birthday.day);
}

I'm sure you're aware that you should be checking the return value of realloc... For example:

void *temp = realloc(persons.arr, persons.cap * sizeof(persons.arr[0]));
if (temp == NULL) {           /* If we don't check return value prior *
                               * to assigning to persons.arr, we      *
                               * might leak some memory...            */
    puts("Error in realloc");
    free(persons.arr);
    exit(-1);
}
persons.arr = temp;

Finally, and most importantly (this is probably your error), are you sure about this?

int nitems = persons.cap*sizeof(persons.arr[0]);

If you mean to pass this as the number of items to qsort (which is usual), then I think that should be:

size_t nitems = persons.n;

P.S. In case you missed it the second time, you should probably audit your code to make sure you're using size_t to store array indexes only.

P.P.S. Don't forget to free(persons); at the end of your program, so you don't end up with reports of memory leaks when you use valgrind...

P.P.P.S. valgrind is awesome!

Upvotes: 1

A.S.H
A.S.H

Reputation: 29332

So you are allocating our array by doubling its size whenever needed, using persons.cap, but you are not filling all its elements, are you?

From your code, the actual number of persons is nitems = persons.n, not persons.cap. What if you retry your code with nitems=persons.n?

If you have unfilled elements in your array, it means the strings inside them are arbitrary (i.e person.name), so probably not null-terminated, and the crash will occur when you try to display them.

Upvotes: 1

Related Questions