Wiki CC3301

No existen variables de tipo “función”, pero es posible tener una variable que es un puntero a una función. Esto es especialmente útil como parámetros para funciones. El siguiente es un ejemplo de un función de ordenamiento genérico, es decir permite ordenar objetos de acuerdo a un criterio definido por una función que se se recibe como parámetro:

  /* ordena datos de cualquier tipo usando Quicksort */

  void swap(void *v[], int i, int j) {
    void *aux;

    aux= v[i];
    v[i]= v[j];
    v[j]= aux;
  }

  void qsort(void *a[], int left, int right,
             int (*compare)(void *, void *)) {
    int i, last;

    if (left>=right)
      return;

    swap(a, left, (left+right)/2);
    last= left;

    /*
      +--+-----------+--------+--------------+
      |  |///////////|\\\\\\\\|              |
      +--+-----------+--------+--------------+
      left        last         i         right
    */

    for (i= left+1; i<=right; ++i)
      if ((*compare)(a[i], a[left])<0)
        swap(a, ++last, i);
    swap(a, left, last);

    qsort(a, left, last-1, compare);
    qsort(a, last+1, right, compare);
  }

La declaración int (*compare)(void *, void *) es para declarar un puntero a una función. Esto se lee de la siguiente forma. Dados 2 punteros a cualquier tipo p y q, la expresion (*compare)(p, q) es de tipo int.

El siguiente programa utiliza la función anterior para ordenar líneas lexicográficamente:

  #include <stdio.h>
  #include <string.h>

  void qsort(void *a[], int left, int right,
             int (*compare)(void *, void *));
             
  int main(int argc, char **argv) {
    int j;
    int (*compare)(void *, void *)= (int (*)(void *, void*)) strcmp; /* Ver nota */

    qsort((void**)argv, 1, argc-1, compare);

    for (j= 1; j<argc; ++j)
      printf("%s\n", argv[j]);
  }

La expresión (int (*)(void *, void*)) es un cast. Se necesita para compatibilizar strcmp con el tipo de la variable asignada. Si se pasa directamente strcmp a qsort, el compilador podría reclamar conflicto de tipos. Este cast es correcto en este caso porque todos los parámetros de la función son punteros y sabemos que un cast entre punteros no realiza ninguna conversión. ¡Pero cuidado! Los efectos son impredecibles si los parámetros no son punteros. Por ejemplo el siguiente cast seguramente llevará a resultados impredescibles:

  int h(int x, double y);
  int (*f)(double x, int k)= (int (*)(double x, int k)) h;

Si no se coloca el cast, el compilador reclama porque no hay concordancia de tipos. Con el cast, el compilador no reclama, pero al invocar f mediante:

  int n= (*f)(3.14, 1);
  int m= (*f)(3, 1.5);

En ningún caso la función h recibirá algo parecido a los argumentos usados en estas invocaciones. El error ocurre porque en este caso los argumentos de la función sí requieren conversión de tipo (entero a real o viceversa), pero debido al cast de funciones el compilador no realizará ninguna conversión.

Otra forma de lograr lo mismo, aunque no es ni mejor ni peor eficiencia es:

  typedef int (*Comparator)(void *, void *);

  void qsort(void *a[], int left, int right, Comparator compare) {
    ...
  }
  
  int main() {
    ...
    Comparator compare= (Comparator)strcmp;
    ...
  }

Lo cual es mucho más legible.

Por último también se puede usar una función de comparación de strings propia que reciba como parámetros punteros a void:

  int mistrcmp(void *p1, void *p2) {
    char *s1= (char*)p1;
    char *s2= (char*)p2;
    return strcmp(s1, s2);
  }

Ahora se puede llamar a qsort especificando como comparador mistrcmp sin tener que aplicar un complicado cast:

    qsort((void**)argv, 1, argc-1, mistrcmp);

Este ejemplo ordena los strings por valor numérico:

  int numcmp(void *s1, void *s2) /* compara numricamente */ {
    int i1, i2;

    i1= atoi((char*)s1);
    i2= atoi((char*)s2);

    return i1<i2? -1 : i1==i2 ? 0 : 1;
  }

  int main(int argc, char **argv) {
    int j;

    qsort((void**)argv, 1, argc-1, numcmp);

    for (j= 1; j<argc; ++j)
      printf("%s\n", argv[j]);
  }

Estudie en los apuntes de Patricio Poblete un programa que recibe la opción “-n” para seleccionar el criterio de ordenamiento numérico, mientras que por omisión ordena alfabéticamente.

¿Cómo se podría usar qsort para ordenar un arreglo de enteros? Por ejemplo tenemos este arreglo:

  int a[6]= {3, 7, 8, 10, 1, 2};

Hay 2 formas: la elegante y la abreviada. Primero veamos la elegante. En teoría no podemos usar directamente el arreglo de enteros porque qsort recibe un arreglo de punteros, no enteros. Entonces tenemos que fabricar un arreglo adicional que contenga punteros a los enteros:

  int *ap[6]= { &a[0], &a[1], &a[2], &a[3], &a[4], &a[5] };

Y ahora programamos la función de comparación y el main:

  int intcmp(void *p1, void *p2) {
    int i1= *(int*)p1;
    int i2= *(int*)p2;
    if (i1<i2)
      return -1;
    else if (i1==i2)
      return 0;
    else
      return 1;
  }
  
  int main() {
    int i;
    qsort((void**)ap, 0, 5, intcmp); /* Ojo: ordena el arreglo ap, no a */
    for (i= 0; i<6; i++)
      printf("%d\n", *ap[i]);
    return 0;
  }

El cast (void**)ap es necesario porque el tipo de ap es int** pero qsort requiere void**.

La forma abreviada de ordenar un arreglo de enteros es hacerle creer a qsort que los enteros son punteros.

  int a[6]= {3, 7, 8, 10, 1, 2};
  
  int intcmp(void *p1, void *p2) {
    int i1= (int)p1; /* ¡la direccion almacenada es el entero! */
    int i2= (int)p2;
    if (i1<i2)
      return -1;
    else if (i1==i2)
      return 0;
    else
      return 1;
  }

  int main() {
    int i;
    qsort((void**)ap, 0, 5, intcmp);
    for (i= 0; i<6; i++)
      printf("%d\n", a[i]); /* esta vez si ordena a */
    return 0;
  }

Este truco solo funciona en arquitecturas en donde int sea del mismo tamaño que un puntero, i.e. x86 de 32 bits. No funcionará en amd64 por ejemplo. Esta es una de las tantas razones por las que los programas que corren correctamente en x86, al compilarlos en una arquitectura de 64 bits, ya no funcionan.

La siguiente solución debería funcionar en todas las plataformas. El tructo está en vestir los enteros como punteros en el arreglo que recibe qsort:

  void *a[6]= {(void*)3, (void*)7, (void*)8, (void*)10, (void*)1, (void*)2};
  
  int longcmp(void *p1, void *p2) {
    long i1= (long)p1; /* la direccion almacenada es el entero! */
    long i2= (long)p2;
    if (i1<i2)
      return -1;
    else if (i1==i2)
      return 0;
    else
      return 1;
  }

  int main() {
    int i;
    qsort(a, 0, 5, longcmp);
    for (i= 0; i<6; i++)
      printf("%ld\n", (long)a[i]); /* esta vez si ordena a */
    return 0;
  }

En Windows de 64 bits el tipo long es de 32 bits como se explica acá y por lo tanto no coincide con el tamaño de un puntero. Esto podría significar que el compilador entregue algún warning. Pero a pesar del warning el ordenamiento debería hacerse correctamente.

Enfín, el autor de este documento no recomienda escribir este tipo de código, pero sí entenderlo porque hay abundante código del legado que recurre a este tipo de trucos y por lo tanto es importante ser capaz de modificarlo si se requieren cambios.

• Resuelva la pregunta 3 parte i.- del examen de 2013/1.
• Resuelva la pregunta 1 del control 2 de 2012/2.