Wiki CC3301

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
===== Punteros a funciones =====

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:

<code>
  /* 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);
  }
</code>

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.

=== Primer ejemplo de uso ===

El siguiente programa utiliza la función anterior para ordenar líneas lexicográficamente los parámetros recibos desde la línea de comandos.  Por ejemplo:

<code>
% ordenar juan pedro diego
diego
juan
pedro
</code>

Esta es la solución usando qsort:

<code>
  int mistrcmp(void *p1, void *p2) {
    char *s1= (char*)p1;
    char *s2= (char*)p2;
    return strcmp(s1, s2);
  }
               
  int main(int argc, char **argv) {
    int j;

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

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

=== Segundo ejemplo de uso ===

Esto no es elegante pero permite usar directamente la función strcmp, sin tener que definir mistrcmp.

<code>
  int (*compare)(void *, void *)= (int (*)(void *, void*)) strcmp; /* Ver nota */
  qsort((void**)argv, 1, argc-1, compare);
</code>

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:

<code>
  int h(int x, double y);
  int (*f)(double x, int k)= (int (*)(double x, int k)) h;
</code>

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:

<code>
  int n= (*f)(3.14, 1);
  int m= (*f)(3, 1.5);
</code>

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 más o menos eficiente, es:

<code>
  typedef int (*Comparator)(void *, void *);

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

Lo cual es más legible.

=== Tercer ejemplo de uso ===

Este ejemplo ordena los strings por valor numérico:

<code>
  int numcmp(void *s1, void *s2) /* compara numéricamente */ {
    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]);
  }
</code>

Estudie en los [[http://users.dcc.uchile.cl/~lmateu/CC3301/apuntes/LenguajeC/#19|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.

==== Ordenar un arreglo de enteros ====

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

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

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:

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

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

<code>
  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;
  }
</code>

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>
  /* Este programa solo funciona en plataformas de 32 bits, no cuando son de 64 bits */
  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.

=== Forma portable ===

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:

<code>
  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;
  }
</code>

En Windows de 64 bits el tipo long es de 32 bits como
se explica [[http://stackoverflow.com/questions/384502/what-is-the-bit-size-of-long-on-64-bit-windows|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.

==== Ejercicios ====

  * Resuelva la pregunta 3 parte i.- del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/ex-131.pdf|examen de 2013/1]].
  * Resuelva la pregunta 1 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/c2-131.pdf|control 2 de 2013/1]].  Pruebe su solución usando el archivo [[http://users.dcc.uchile.cl/~lmateu/CC3301/download/colapri.zip|colapri.zip]].  Para la parte a.- complete el archivo p1a.c.  Verifique el resultado con el comando "make test-p1a".  Luego resuelva la parte b.- en el archivo ordenar.c y verifique su funcionamiento con el comando "make test-p1b".