LINUX.ORG.RU

где qsort_r?

 ,


0

1

В man qsort он есть. Я добавил #define _GNU_SOURCE в компилирцемый файл. На вякий случа компилрую (gcc) как gcc -std=gnu99 02-SortLetters.d.

gcc мне говорит:

~/.../search/steven >>> gcc -std=gnu99 02-SortLetters.c
02-SortLetters.c:40:5: warning: implicit declaration of function 'qsort_r' is invalid in C99 [-Wimplicit-function-declaration]

шланг говорит:

~/.../search/steven >>> clang 02-SortLetters.c           
02-SortLetters.c:40:5: warning: implicit declaration of function 'qsort_r' is invalid in C99 [-Wimplicit-function-declaration]

Ответ на: комментарий от BackDoorLover

Ситуация такая: в stdlib от MS аналогичная функция - это qsort_s.

Ouch. У них в компараторе первым аргументом идет контекст, у GNU – последним. Зато у обоих контекст в саму функцию qsort передается после компаратора. А в BSD – qsort_r принимает контекст перед компаратором.

Ну и ладно, не было еще таких проблем, которые бы не решал

#if defined(_GNU_SOURCE)
#elif defined(_MSC_VER)
#elif defined(__FreeBSD__) || defined(__NetBSD__) || defined(__OpenBSD__) // WTF
#else
#error "Fuck off"
#endif
anonymous ()
Ответ на: комментарий от anonymous

Ну и как это решает qsort_r/qsort_s разницы? #ifdef’ов там насовать? Это тестовое задание при приеме на работу, поэтому не мне говорить «fuck off». Я, наверное, сделаю вторую версию, более уродливую с qsort и глобальными данными. Хотя лучше всего было бы (псевдокод):

#if defined(_GNU_SOURCE) || defined(__FreeBSD__)...
   qsort_r...
#elif defined(_MSC_VER)
   qsort_s...
#else
#error "Blabla"
#endif

Но у меня компиоятора vc.exe нету, может существует online?

dissident ★★ ()
Ответ на: комментарий от SkyMaverick

Ну так он же вроде написал собственный qsort_r. Не, это перебор. Проще:

#if defined(WINDOWS)
    qsort_s...
#else if defined(LINUX)
    qsort_r
#else
#error "Your platform is not supported"
#endif

Но я повторяюсь, да это и anonymous первый предложил.

dissident ★★ ()
Ответ на: комментарий от dissident

Ну так он же вроде написал собственный qsort_r.

Я опять ступил. Вернее он действительно написал свой sort на случай:

/* no qsort_r in glibc before 2.8, need to use nested qsort */
sort_r_simple(base, nel, width, compar, arg);``c

Очень сложно выходит. Я просто сделаю вторую версию с глобальным void *arg и qsort(). Мол если у вас Вижуал Студия и не компилируется, то берите эту версию, но она гаже.

dissident ★★ ()
Последнее исправление: dissident (всего исправлений: 2)
Ответ на: комментарий от LongLiveUbuntu

Что мне обернуть? Передавать в qsort() вместо элементов для сравнения структуры с элементами для сравнения и указателем на данные, необходимые для сортировки?

До появления qsort_r() эта проблема (когда для сортировки необходимы были дополнительные данные) решалась вынесением дополнительных данных в глобальную переменную. Я так и сделаю в версии 2 на случай если они Turbo C++ компилируют. Первую версию тоже им вышлю. Там 4 задачи, одна забористей другой. В последней вообще очередь команд и трэд нужен. А в предыдущей BFS в графе - но это как раз фигня.

То, что я не сообразил, что системным хидерам надо знать откуда-то предоставлять ли qsort_r() или нет и потому #define должен быть перед #include - ну почему-то не пришло сразу в голову. Решил спросить у любимого блож^Wресурсика.

dissident ★★ ()
Последнее исправление: dissident (всего исправлений: 1)
Ответ на: комментарий от dissident

Если прям уж нужен этот qsort_r/qsort_s вот небольшая портяночка. Думал, как бы сгладить различия между прототипами как самой функции qsort, так и ее компаратора на разных платформах. Конечно же с помощью макросов:

#include <stdlib.h>
#include <string.h> // strcmp
#include <stdio.h>

#if defined(_GNU_SOURCE)
#define MY_QSORT_CMP(func, a, b, data) int func(const void *a, const void *b, void *data)
#define myQsort qsort_r
#elif defined(_MSC_VER)
#define MY_QSORT_CMP(func, a, b, data) int func(void *data, const void *a, const void *b)
#define myQsort qsort_s
#elif defined(__FreeBSD__)
#define MY_QSORT_CMP(func, a, b, data) int func(void *data, const void *a, const void *b)
#define myQsort(arr, count, size, cmp, data) qsort_r(arr, count, size, data, cmp)
#else
#error "TODO"
#endif

MY_QSORT_CMP(cmp, i, j, string); // прототип (если нужен)

MY_QSORT_CMP(cmp, _i, _j, string)
{
	const size_t i = *(const size_t*)_i;
	const size_t j = *(const size_t*)_j;
	return strcmp((const char*)string + i, (const char*)string + j);
}

int main(void)
{
	char string[] = "banana";
	size_t array[] = { 0, 1, 2, 3, 4, 5, 6 };

	myQsort(array, sizeof(string), sizeof(array[0]), cmp, string);

	for (size_t i = 0; i < sizeof(string); ++i)
	{
		printf("%s$\n", string + array[i]);
	}
	return 0;
}

Проверял только на Linux’е, остальное подправишь если тебе нужно.

Ну, а вообще если qsort_r использовать не обязательно, то можно написать свою функции сортировки. Я долго не мог понять быструю сортировку, пока не наткнулся на публикацию Бентли «Engineering a sort function», даже такое днище, как я смогло понять. Плюс если заглянуть в исходники gcc stl (хитрость в том чтобы читать через #include <algorithm> и g++ -E вместо непропроцессированого кода, по краней мере, мне так легче), то можно увидеть, что они используют IntroSort (быстрая сортировка, которая убегает с позором под крыло к Пирамидальной сортировке при достижении определенной глубины рекурсии), а также для сортировки маленьких массивов (< 16 что ли, не помню) используют сортировку вставками.

Это я к тому, что написать свою довольно неплохую реализацию алгоритма сортировки, используя эти два источника вполне по силам (бонус – компилятор сможет заинлайнить, если захочет, конечно, твой компаратор, и не будет извращений с указателями на функции). Плюс если тебе известна природа твоих входных данных, можешь попробовать какую-нибудь вариацию поразрядной сортировки.

TLDR: Извращаться с qsort_r/qsort_s можно, но не обязательно.

anonymous ()
Ответ на: комментарий от anonymous

Относительно портяночки: там же вроде последовательность разная элеметов? Относительно иного:

  • Спасибо за статью, если найду прочитаю
  • qsort - это все же не STL, там может быть не такое днище
  • Я недавно писал код под микроконтроллер stm32. Да, там я использовал C++. Но только для группировки кода в виде классов. Никаких инклюдов. А вот это вообще прелесть: http://www.nadler.com/embedded/newlibAndFreeRTOS.html. Оказывается sprintf() использует malloc(). Вообще достаточно вызвать что угодно из STL, как запускается столько г..на, что я уверен, что ни в одном серьезном проекте (марсоход там какой, медицинский прибор, ракета, адронный коллайдер) никто никогда к STL близко не подойдет. И потом там MISRA. Она, конечно, чушь голимая для выколачивания бабла, но есть одно достоинство. Стоит тебе заинклюдить <smth.h> и использовать из него void wtf(), как весь void wtf(), как и все, что он использует надо будет править под MISRA-Religion. А такой х..ней никто не станет заниматься.
dissident ★★ ()
Ответ на: комментарий от dissident

Относительно портяночки: там же вроде последовательность разная элеметов?

Есть два различия – в прототипе функции qsort_r/qsort_s (положение аргумента ctx, у меня это data), и в прототипе компаратора, который определяет пользователь и потом передает в функцию. Первое отличие решается макросом myQsort (своего рода адаптор или обертка), второе отличие решается с помощью макроса MY_QSORT_CMP. Да, маленький недостаток в том, что теперь пользователю придется все свои компараторы объявлять через этот макрос:

// Вместо этого
int compare_strings(const void *s1, const void *s2, void *data)
{
// ...
}

// Пишем это
MY_QSORT_CMP(compare_strings, s1, s2, data)
{
// ...
}

qsort - это все же не STL, там может быть не такое днище

Не, я просто имел в виду, что можно просто глянуть, как оно реализовано в stl, все таки проверенная временем, «боевая» реализация, чтобы убедиться, что не боги горшки обжигают.

anonymous ()