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.

Otra forma de hacer esto mismo:

  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''. === Forma abreviada === La forma abreviada de ordenar un arreglo de enteros es hacerle creer a qsort que los enteros son punteros. <code> 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; } </code> 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. Pero en Linux/amd64 se puede haceer que funcione declarando a como arreglo de long, no de int.