Как исправить qsort-компаратор, вызывающий ошибку сегментации

Question

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

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <assert.h>
#include <ctype.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include "sort.h"
#include <sys/stat.h>

int compare(const void *r1, const void *r2) {
  return (strcmp(r1, r2));
}

//Function to compare strings in an array of strings for qsort
int main(int argc, char *argv[]) {
  FILE *file;
  file = fopen(argv[1], "r");
  struct stat fs;
  //exists only to get file size
  stat(argv[1], &fs);
  int file_size = fs.st_size;
  int number_of_records = file_size / 100;
  char AllRecords[file_size][100];
  fread(AllRecords, 100, file_size, file);
  fclose(file);
  int i = sizeof(AllRecords);
  //  int l = compare(AllRecords[0],AllRecords[1]);
  //  Test, current bug, calling qsort causes errors
  qsort(AllRecords, i, 100, compare);
  FILE *file2 = fopen(argv[2], "w");
  fwrite(AllRecords, 100, i, file2);
  fclose(file2);
  return (0);
}

Answer 1

Вы должны быть очень осторожны с размерами, которые вы используете.Этот код работает, исправляя различные проблемы с размером массивов.Обратите внимание, что существует предел размера массива, который вы можете создать в стеке.В системах Unix 1 МиБ имеет достаточный запас для ошибки (обычно лимит составляет 8 МиБ)в Windows ограничение обычно составляет 1 МБ, поэтому ограничение, наложенное здесь, вероятно, немного велико - возможно, (1000 * 1000) будет безопасным;может быть, меньшее значение будет лучше, например (1024 * 1024 * 15 / 16).

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>

#define MAX_FILE_SIZE (1024 * 1024)

static int compare(const void  *r1, const void *r2)
{
    return(strcmp(r1, r2));
}

int main(int argc, char *argv[])
{
    assert(argc == 3);
    FILE *file = fopen(argv[1], "r");
    struct stat fs;
    stat(argv[1], &fs);
    int file_size = fs.st_size;
    if (file_size > MAX_FILE_SIZE)
    {
        fprintf(stderr, "file %s is too big to be sorted by this program\n", argv[1]);
        exit(EXIT_FAILURE);
    }
    int number_of_records = file_size / 100;
    char AllRecords[number_of_records][100];
    fread(AllRecords, 100, file_size, file);
    fclose(file);
    qsort(AllRecords, number_of_records, 100, compare);
    FILE *file2 = fopen(argv[2], "w");
    fwrite(AllRecords, 100, number_of_records, file2);
    fclose(file2);
    return(0);
}

Одной из проблем является генерация выборочных данных.Я использовал генератор случайных данных для генерации 99-символьных «строк», оканчивающихся нулевыми байтами (чтобы сравнение строк имело строки с нулевыми концами.

Ввод:

LLWNMGWMIQECKYLWFFIHWSZVYBQLLYTDAXNQNCQRBJZMZNFMMNCBAFYIIXUKXEBGSQHIYVCDVWCUHLXLOCOETLRPZRSGWDERQAZ
YNWEULRIMNODDAKABCKVAXTWLMPFOFIGRIJLKPVTWCFJGXAZEWKZFWCIZVQZYPADMBQOOHITVPEVWOIUSZISJOQTHQHCXEADIHW
YSHUYAQTPVTBKKHXQQXZMJIQVJRFJSNZSXKMHNJRAPNYWVSJRIHVHUBJJJAMRVBJZWWEACTUXLDXEFIDALHJBOKXJBAQJFABKLR
UWXIJELISTPAFXSKEGQHHJYPKWGLBXJSQWFHCAPRJTLQHRZEEEJAELOMKDAQIDIBZKZMCYNCMVLTXDUKLYGEIBVXTXNKPOUGMQE
NFUVXYBDQYMIEVWEQUYPTEASNSOQHZRLLLKXSBSQJFJBNRLSPUELCYTWDLLMTQKKHWFVFCQXNEBBMAPASRZSIOELSZGGFDDWJSK
OXQGGDODECBRVSXUAMZSLIHUJRAUFGMMORRBBGHECQLRWSVZGZWTSSBJVPTTRUIDJVGKTFGJFMSOHHTBIAEFIMUSYXMJAIRIZTU
XRRQOOBLDYLQQMKVFSOIZNTXAARKUZRBFCAEJDGCZGXHUTWHHOHERWPKOLDBCEHCUXPHVJMEUEJVTUDCQFXWAEWMPZPROKSOKAE
LURFJLTYKIIWTMWJLXZGOGCPMMRWZEOCSODVRSQDFTMJJILCIZNQWITWFJSCSAZTTJBYEGAWXBAYGQVQOMQTKTEHGUTOOMOCFAZ
NGBPRHOEICRLXPVTMHULNYJNNRJYVZDDGHDFHJFKELHUGGYWHSMBPCRTAAVHOKAITDPTPGWOOMSHHGLRNVQBMTHCFCPQGDRTCAV
ZJRHMYEPSWTRPGNFZMGPHOSFAFADGTDMISIWGSOCLSYGBURDJEKYYYLZXHHXIYYUVTYNXYBKJLSPNVXIKDZNSIZDITIOWGODJNL

Преобразовано с использованием tr '\0' '\n' (или наоборот для преобразования новых строк в нулевые байты).

Вывод:

LLWNMGWMIQECKYLWFFIHWSZVYBQLLYTDAXNQNCQRBJZMZNFMMNCBAFYIIXUKXEBGSQHIYVCDVWCUHLXLOCOETLRPZRSGWDERQAZ
LURFJLTYKIIWTMWJLXZGOGCPMMRWZEOCSODVRSQDFTMJJILCIZNQWITWFJSCSAZTTJBYEGAWXBAYGQVQOMQTKTEHGUTOOMOCFAZ
NFUVXYBDQYMIEVWEQUYPTEASNSOQHZRLLLKXSBSQJFJBNRLSPUELCYTWDLLMTQKKHWFVFCQXNEBBMAPASRZSIOELSZGGFDDWJSK
NGBPRHOEICRLXPVTMHULNYJNNRJYVZDDGHDFHJFKELHUGGYWHSMBPCRTAAVHOKAITDPTPGWOOMSHHGLRNVQBMTHCFCPQGDRTCAV
OXQGGDODECBRVSXUAMZSLIHUJRAUFGMMORRBBGHECQLRWSVZGZWTSSBJVPTTRUIDJVGKTFGJFMSOHHTBIAEFIMUSYXMJAIRIZTU
UWXIJELISTPAFXSKEGQHHJYPKWGLBXJSQWFHCAPRJTLQHRZEEEJAELOMKDAQIDIBZKZMCYNCMVLTXDUKLYGEIBVXTXNKPOUGMQE
XRRQOOBLDYLQQMKVFSOIZNTXAARKUZRBFCAEJDGCZGXHUTWHHOHERWPKOLDBCEHCUXPHVJMEUEJVTUDCQFXWAEWMPZPROKSOKAE
YNWEULRIMNODDAKABCKVAXTWLMPFOFIGRIJLKPVTWCFJGXAZEWKZFWCIZVQZYPADMBQOOHITVPEVWOIUSZISJOQTHQHCXEADIHW
YSHUYAQTPVTBKKHXQQXZMJIQVJRFJSNZSXKMHNJRAPNYWVSJRIHVHUBJJJAMRVBJZWWEACTUXLDXEFIDALHJBOKXJBAQJFABKLR
ZJRHMYEPSWTRPGNFZMGPHOSFAFADGTDMISIWGSOCLSYGBURDJEKYYYLZXHHXIYYUVTYNXYBKJLSPNVXIKDZNSIZDITIOWGODJNL

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

Answer 2

Устранение различных проблем за один раз.

file_size - это не количество записей, ожидаемое в file, number_of_records - это ожидаемое количество записей.

i не должен быть ни байтовым размером AllRecords, ни количеством элементов в AllRecords[], но количеством элементов, успешно прочитанных из fread().

//char AllRecords[file_size][100];
//fread(AllRecords, 100, file_size, file);
//int i = sizeof(AllRecords);

char AllRecords[number_of_records][100];
int i = fread(AllRecords, 100, number_of_records, file);`

qsort(AllRecords, i, 100, compare); // This is OK

Надеюсь number_of_records == i, но дерьмо случается при чтении файлов.Возвращаемое значение от fread() является лучшим показателем.

Answer 3

Функция qsort требует двух числовых параметров: nitems и size.Первый - это количество предметов.Я думаю, что вы сохранили это в number_of_records.Второй - это размер одной записи, которую вы используете буквально 100.

Вместо передачи i, который является общим размером в байтах всего массива, попробуйте передать number_of_records:

qsort(AllRecords, number_of_records, 100, compare);