Qsort with array of struct changes the content of the struct

Question

I'm writing a small code to test qsort on an array that is not completely filled.

But whenever I run it, the data is completely erased for some random int.

I don't understand why, I looked at this question and their code ran fine but I don't get why mine won't.

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

#include <time.h>

struct proc {
    long unsigned int user_time;
    long unsigned int system_time;
    char *name;
    int pid;
};


static int compare(const void * a, const void * b)
{
  const struct proc *p1 = a;
  const struct proc *p2 = b;

  if ((p1->system_time + p1->user_time) > (p2->user_time + p2->system_time))
    return -1;
  else if ((p1->system_time + p1->user_time) == (p2->user_time + p2->system_time))
    return 0;
  else
    return 1;
}

int main()
{
    int used_size = 0;
    srand ( time(NULL) );
    struct proc **processes = malloc(sizeof(struct proc*) * 20 + 1);
    for (int i = 0; i < 20; i++) {
        processes[i] = malloc(sizeof(struct proc));
        processes[i]->user_time = 0;
        processes[i]->system_time = 0;
        processes[i]->name = NULL;
        processes[i]->pid = -1;
    }

    for (int i = 0; i < 14; i++)
    {
        processes[i]->user_time = rand()%10;
        processes[i]->system_time = 0;
        processes[i]->pid = i*2;
        used_size++;
    }

    for (int i = 0; i < used_size;i++)
    {
        printf("%d %lu \n",i,processes[i]->user_time);
    }

    printf("\n\n\n");
    qsort(processes, used_size, sizeof(struct proc *), compare);

    for (int i = 0; i < used_size;i++)
    {
        printf("%d %d \n",i,processes[i]);
    }


}

The compare function is supposed to return a negative, zero or positive value. Yours only returns zero or one. If it is called as compare(a, b) and returns a negative number, it must return a positive number when called as compare(b, a) — your does not. This is a basic requirement of all compare functions for qsort(). Additionally, your function is for comparing structures via pointers to structures (when sorting an array of structures). You're actually sorting an array of pointers to structures; you need a different function that expects to be passed a pointer to a pointer. — Jonathan Leffler
– Jonathan Leffler, Commented Feb 15, 2017 at 15:47
Your compare function has some issues... it's supposed to return a negative/zero/positive for less/equal/greater, but because of the ! can only return 1 or 0... and the arguments would be pointers to the elements in the array that are being compared, which themselves are pointers to the structs (in your setup)... so they should be pointers to pointers, though you treat them as though they point to the structs directly. — Dmitri
– Dmitri, Commented Feb 15, 2017 at 15:48

drov · Accepted Answer · 2017-02-16 14:06:58Z

0

Thanks to Dmitri :

the arguments would be pointers to the elements in the array that are being compared, which themselves are pointers to the structs (in your setup)... so they should be pointers to pointers, though you treat them as though they point to the structs directly.

The problem was in the "compare" function :

static int compare(const void * a, const void * b)
{
    const struct proc *p1 = *(struct proc **)a;
    const struct proc *p2 = *(struct proc **)b;
    // 0ull to prevent int overflow
    if ((0ull + p1->system_time + p1->user_time) > (0ull + p2->user_time + p2->system_time))
        return -1;
    else if ((0ull + p1->system_time + p1->user_time) == (0ull + p2->user_time + p2->system_time))
        return 0;
    else
        return 1;
}

edited Feb 16, 2017 at 14:06

answered Feb 15, 2017 at 15:58

drov

1433 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

chux Over a year ago

Detail: You may want a re-write to avoid overflow with system and user time addition. A simply solution when unsigned long long is wider, would extend the integer math as in (0ull + p1->system_time + p1->user_time) > (0ull + p2->user_time + p2->system_time)

Jonathan Leffler Over a year ago

@chux: there aren't that many programs around that will exceed 68 CPU years of execution time.

chux Over a year ago

@JonathanLeffler True not a great concern, but when it is a concern, it can be costly. Apparently successful code gets used for every expanding applications. A EUR 630 million mistake was caused by an undetected math overflow because the code assumed "physically limited or that there was a large margin of error".

Collectives™ on Stack Overflow

Qsort with array of struct changes the content of the struct

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related