¿Qué tan portátil es la función qsort_r reentrante en comparación con qsort?

5 minutos de lectura

¿Que tan portatil es la funcion qsort r reentrante en comparacion
dajobe

qsort_r() es la versión reentrante de qsort() que toma un argumento ‘thunk’ adicional y lo pasa a la función de comparación y me gustaría poder usarlo en código C portátil. qsort() es POSIX y en todas partes pero qsort_r() parece ser una extensión BSD. Como pregunta específica, ¿existe esto o tiene un equivalente en el tiempo de ejecución de Windows C?

Intenté escribir una versión portátil de qsort_r / qsort_s (llamada sort_r) que se muestra con un ejemplo. También puse este código en un repositorio de 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
}

Ejemplo de uso:

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

Compilar/ejecutar/salir:

$ 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

He probado en mac y linux. Actualice este código si detecta errores o mejoras. Eres libre de usar este código como quieras.

  • Hay un error: en mi entorno Clang 11 + macOS 10.15, el if (defined _GNU_SOURCE es verdadera y tiene prioridad sobre la #elif (defined __APPLE__entonces qsort_r se llama con los argumentos en el orden incorrecto. Reordenando el #if ramas para que la detección de Apple/BSD suceda primero soluciona esto.

    – chris

    24 de febrero de 2021 a las 14:10

¿Que tan portatil es la funcion qsort r reentrante en comparacion
Gabe

Para Windows usarías qsort_s: http://msdn.microsoft.com/en-us/library/4xc60xas(VS.80).aspx

Aparentemente, existe cierta controversia acerca de que BSD y GNU tienen versiones incompatibles de qsort_rasí que tenga cuidado al usarlo en el código de producción: http://sourceware.org/ml/libc-alpha/2008-12/msg00003.html

Por cierto, el _s significa “seguro” y el _r significa “reentrante”, pero ambos significan que hay un parámetro adicional.

No está especificado en ningún estándar de portabilidad. También creo que es un error llamarlo una versión “segura para subprocesos” de qsort. El estandar qsort es seguro para subprocesos, pero qsort_r efectivamente le permite pasar un cierre como su función de comparación.

Obviamente, en un entorno de subproceso único, puede lograr el mismo resultado con una variable global y qsort, pero este uso no será seguro para subprocesos. Un enfoque diferente para la seguridad de subprocesos sería usar datos específicos de subprocesos y hacer que su función de comparación recupere su parámetro de los datos específicos de subprocesos (pthread_getspecific con hilos POSIX, o __thread variables en gcc y el próximo estándar C1x).

  • Estás bien. No es seguro para subprocesos, es reentrante. Eso significa que es posible que aún lo necesite incluso en entornos de un solo subproceso.

    – Gabo

    29 de noviembre de 2010 a las 4:57

  • los qsort la función en sí es reentrante, o al menos debería estar en cualquier implementación sana. El problema es hacer funciones que quieren llamar qsort con una función de comparación que requiere un argumento reentrante.

    – R.. GitHub DEJA DE AYUDAR A ICE

    29 de noviembre de 2010 a las 5:11

  • Si, obviamente el qsort El algoritmo no requiere un estado global, por lo que es reentrante de facto y seguro para subprocesos. solo quise decir eso qsort_r está diseñado para su uso donde podría ser necesaria la reentrada y, por lo tanto, el uso de almacenamiento local de subprocesos no siempre logra el mismo resultado.

    – Gabo

    29 de noviembre de 2010 a las 5:23

  • Tiene razón, es reentrante y, de hecho, no me importa el enhebrado, solo necesito una función de comparación con un parámetro de datos de usuario adicional que pueda usar para acceder a otro estado.

    – dajobe

    29 de noviembre de 2010 a las 17:40

  • Y para Windows, también puede usar la API de almacenamiento local de subprocesos: TlsGetValue y amigos o el __declspec(thread) especificador de variables.

    – Adam Rosenfield

    29 de noviembre de 2010 a las 17:50

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad