Qsort с массивом структуры изменяет содержимое структуры

Я пишу небольшой код для проверки qsort на не полностью заполненном массиве.

Но всякий раз, когда я его запускаю, данные полностью стираются для какого-то случайного int.

Я не понимаю почему, я просмотрел этот вопрос, и их код работал нормально, но Я не понимаю, почему мой не будет.

#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]);
    }


}

person drov    schedule 15.02.2017    source источник
comment
Функция сравнения должна возвращать отрицательное, нулевое или положительное значение. Ваш возвращает только ноль или один. Если он вызывается как compare(a, b) и возвращает отрицательное число, то при вызове как compare(b, a) он должен возвращать положительное число, а ваш — нет. Это основное требование для всех функций сравнения для qsort(). Кроме того, ваша функция предназначена для сравнения структур через указатели на структуры (при сортировке массива структур). На самом деле вы сортируете массив указателей на структуры; вам нужна другая функция, которая ожидает передачи указателя на указатель.   -  person Jonathan Leffler    schedule 15.02.2017
comment
У вашей функции сравнения есть некоторые проблемы... она должна возвращать отрицательное/ноль/положительное значение для меньшего/равного/большего, но из-за того, что ! может возвращать только 1 или 0... и аргументы будут указателями на элементы в сравниваемый массив, который сам по себе является указателем на структуры (в вашей настройке)... поэтому они должны быть указателями на указатели, хотя вы относитесь к ним так, как будто они указывают на структуры напрямую.   -  person Dmitri    schedule 15.02.2017


Ответы (1)


Спасибо Дмитрию:

аргументы будут указателями на сравниваемые элементы массива, которые сами по себе являются указателями на структуры (в вашей настройке)... поэтому они должны быть указателями на указатели, хотя вы относитесь к ним так, как будто они указывают на структуры напрямую.

Проблема была в функции "сравнить":

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;
}
person drov    schedule 15.02.2017
comment
Подробности: Вы можете захотеть переписать, чтобы избежать переполнения с добавлением системного и пользовательского времени. Простое решение, когда unsigned long long шире, расширило бы целочисленную математику, как в (0ull + p1->system_time + p1->user_time) > (0ull + p2->user_time + p2->system_time) - person chux - Reinstate Monica; 15.02.2017
comment
@chux: не так много программ, время выполнения которых превышает 68 лет процессора. - person Jonathan Leffler; 15.02.2017
comment
@JonathanLeffler Правда, это не большая проблема, но когда это вызывает беспокойство, это может быть дорогостоящим. По-видимому, удачный код используется для каждого расширяющегося приложения. ошибка на сумму 630 миллионов евро была вызвана необнаруженным математическим переполнением, поскольку код предполагался физически ограниченным. или что была большая погрешность. - person chux - Reinstate Monica; 15.02.2017