Насколько переносимой является повторно введенная функция qsort_r по сравнению с qsort? - PullRequest
Новая
       21

Насколько переносимой является повторно введенная функция qsort_r по сравнению с qsort?

9 голосов
/ 29 ноября 2010

qsort_r() - это возвращающаяся версия qsort(), которая принимает дополнительный аргумент 'thunk' и передает его в функцию сравнения, и я хотел бы иметь возможность использовать ее в переносимом коде C. qsort() - это POSIX и везде, но qsort_r() кажется расширением BSD. Как конкретный вопрос, существует ли или имеет эквивалент во время выполнения Windows C?

Ответы [ 3 ]

8 голосов
/ 10 февраля 2013

Я попытался написать переносную версию qsort_r / qsort_s (называемую sort_r), показанную на примере.Я также поместил этот код в git-репо (https://github.com/noporpoise/sort_r)

struct sort_r_data
{
  void *arg;
  int (*compar)(const void *a1, const void *a2, void *aarg);
};

int sort_r_arg_swap(void *s, const void *aa, const void *bb)
{
  struct sort_r_data *ss = (struct sort_r_data*)s;
  return (ss->compar)(aa, bb, ss->arg);
}

void sort_r(void *base, size_t nel, size_t width,
            int (*compar)(const void *a1, const void *a2, void *aarg), void *arg)
{
  #if (defined _GNU_SOURCE || defined __GNU__ || defined __linux__)

    qsort_r(base, nel, width, compar, arg);

  #elif (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || \
         defined __FREEBSD__ || defined __BSD__ || \
         defined OpenBSD3_1 || defined OpenBSD3_9)

    struct sort_r_data tmp;
    tmp.arg = arg;
    tmp.compar = compar;
    qsort_r(base, nel, width, &tmp, &sort_r_arg_swap);

  #elif (defined _WIN32 || defined _WIN64 || defined __WINDOWS__)

    struct sort_r_data tmp = {arg, compar};
    qsort_s(*base, nel, width, &sort_r_arg_swap, &tmp);

  #else
    #error Cannot detect operating system
  #endif
}

Пример использования: 

#include <stdio.h>

/* comparison function to sort an array of int, inverting a given region
   `arg` should be of type int[2], with the elements
   representing the start and end of the region to invert (inclusive) */
int sort_r_cmp(const void *aa, const void *bb, void *arg)
{
  const int *a = aa, *b = bb, *p = arg;
  int cmp = *a - *b;
  int inv_start = p[0], inv_end = p[1];
  char norm = (*a < inv_start || *a > inv_end || *b < inv_start || *b > inv_end);
  return norm ? cmp : -cmp;
}

int main()
{
  /* sort 1..19, 30..20, 30..100 */
  int arr[18] = {1, 5, 28, 4, 3, 2, 10, 20, 18, 25, 21, 29, 34, 35, 14, 100, 27, 19};
  /* Region to invert: 20-30 (inclusive) */
  int p[] = {20, 30};
  sort_r(arr, 18, sizeof(int), sort_r_cmp, p);

  int i;
  for(i = 0; i < 18; i++) printf(" %i", arr[i]);
  printf("\n");
}

Компиляция / запуск / вывод: 

$ gcc -Wall -Wextra -pedantic -o sort_r sort_r.c
$ ./sort_r
 1 2 3 4 5 10 14 18 19 29 28 27 25 21 20 34 35 100

Я тестировал на Mac и Linux. Пожалуйста, обновите этот код, если вы заметите ошибки / улучшения. Вы можете использовать этот код по своему усмотрению.

7 голосов
/ 29 ноября 2010

Для Windows вы должны использовать qsort_s: http://msdn.microsoft.com/en-us/library/4xc60xas(VS.80).aspx

По-видимому, существуют некоторые противоречия по поводу несовместимых версий BSD и GNU qsort_r, поэтому будьте осторожны при использовании его в рабочем коде: http://sourceware.org/ml/libc-alpha/2008-12/msg00003.html

Кстати, _s означает «безопасный», а _r означает «входящий», но оба означают, что есть дополнительный параметр.

5 голосов
/ 29 ноября 2010

Не указано ни в одном стандарте мобильности.Также я думаю, что было бы ошибочно называть это «потокобезопасной» версией qsort.Стандарт qsort является поточно-ориентированным, но qsort_r позволяет эффективно передавать замыкание в качестве функции сравнения.

Очевидно, что в однопоточной среде вы можете достичь того же результата с помощью глобальной переменнойи qsort, но это использование не будет потокобезопасным.Другим подходом к безопасности потока будет использование данных, специфичных для потока, и ваша функция сравнения получит свой параметр из данных, специфичных для потока (pthread_getspecific с потоками POSIX или __thread переменных в gcc и следующем стандарте C1x).

...