¿C tiene un equivalente de std :: less de C ++?

26

Hace poco respondí una pregunta sobre el comportamiento indefinido de hacer p < qen C cuándo py qson punteros en diferentes objetos / matrices. Eso me hizo pensar: C ++ tiene el mismo comportamiento (indefinido) <en este caso, pero también ofrece la plantilla de biblioteca estándar std::lessque garantiza que devolverá lo mismo que <cuando se pueden comparar los punteros, y devuelve un orden consistente cuando no pueden.

¿C ofrece algo con una funcionalidad similar que permita comparar de forma segura punteros arbitrarios (con el mismo tipo)? Intenté mirar a través del estándar C11 y no encontré nada, pero mi experiencia en C es mucho menor que en C ++, por lo que podría haber pasado algo por alto fácilmente.

Angew ya no está orgulloso de SO
fuente
1
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Samuel Liew

Respuestas:

20

En implementaciones con un modelo de memoria plana (básicamente todo), la conversión a uintptr_tJust Work.

(Pero consulte ¿Deben las comparaciones de punteros estar firmadas o no en x86 de 64 bits? Para analizar si debe tratar los punteros como firmados o no, incluidos los problemas de formar punteros fuera de los objetos que es UB en C.)

Sin embargo, los sistemas con modelos de memoria no planos existen, y pensando en ellos puede ayudar a explicar la situación actual, como C ++ que tienen diferentes especificaciones de <frente std::less.


Parte del objetivo de los <punteros para separar objetos siendo UB en C (o al menos no especificado en algunas revisiones de C ++) es permitir máquinas extrañas, incluidos modelos de memoria no planos.

Un ejemplo bien conocido es el modo real x86-16 donde los punteros son segmentos: offset, formando una dirección lineal de 20 bits (segment << 4) + offset. La misma dirección lineal se puede representar mediante múltiples combinaciones seg: off diferentes.

C ++ std::lessen punteros en ISA extraños puede necesitar ser costoso , por ejemplo, "normalizar" un segmento: desplazamiento en x86-16 para tener un desplazamiento <= 15. Sin embargo, no hay una forma portátil de implementar esto. La manipulación requerida para normalizar a uintptr_t(o la representación de un objeto puntero) es específica de la implementación.

Pero incluso en sistemas donde C ++ std::lesstiene que ser costoso, <no tiene que serlo. Por ejemplo, suponiendo un modelo de memoria "grande" donde un objeto cabe dentro de un segmento, <puede comparar la parte de desplazamiento y ni siquiera molestarse con la parte del segmento. (Los punteros dentro del mismo objeto tendrán el mismo segmento, y de lo contrario es UB en C. C ++ 17 cambiado a simplemente "no especificado", lo que podría permitir omitir la normalización y solo comparar las compensaciones). Esto supone que todos los punteros a cualquier parte de un objeto siempre usa el mismo segvalor, nunca normalizando. Esto es lo que esperaría que requiera un ABI para un modelo de memoria "grande" en lugar de "enorme". (Ver discusión en comentarios ).

(Tal modelo de memoria podría tener un tamaño máximo de objeto de 64 kB, por ejemplo, pero un espacio de dirección total máximo mucho mayor que tiene espacio para muchos de esos objetos de tamaño máximo. ISO C permite que las implementaciones tengan un límite en el tamaño del objeto que sea inferior al el valor máximo (sin signo) size_tpuede representar, SIZE_MAXpor ejemplo, incluso en sistemas modelo de memoria plana, GNU C limita el tamaño máximo del objeto para PTRDIFF_MAXque el cálculo del tamaño pueda ignorar el desbordamiento firmado). Vea esta respuesta y discusión en los comentarios.

Si desea permitir objetos más grandes que un segmento, necesita un modelo de memoria "enorme" que tenga que preocuparse por desbordar la parte de desplazamiento de un puntero al hacer p++un bucle a través de una matriz, o al hacer indexación / aritmética de puntero. Esto conduce a un código más lento en todas partes, pero probablemente significaría que p < qfuncionaría para punteros a diferentes objetos, porque una implementación dirigida a un modelo de memoria "enorme" normalmente elegiría mantener todos los punteros normalizados todo el tiempo. Ver ¿Qué son los punteros cercanos, lejanos y enormes? - algunos compiladores reales de C para el modo real x86 tenían una opción para compilar para el modelo "enorme", donde todos los punteros predeterminados a "enorme" a menos que se declare lo contrario.

La segmentación x86 en modo real no es el único modelo de memoria no plano posible , es simplemente un ejemplo concreto útil para ilustrar cómo ha sido manejado por las implementaciones de C / C ++. En la vida real, las implementaciones extendieron ISO C con el concepto de punteros farvs. near, permitiendo a los programadores elegir cuándo pueden salirse con solo almacenar / pasar alrededor de la parte de desplazamiento de 16 bits, en relación con algún segmento de datos común.

Pero una implementación pura de ISO C tendría que elegir entre un modelo de memoria pequeño (todo excepto el código en el mismo 64 kB con punteros de 16 bits) o grande o enorme con todos los punteros de 32 bits. Algunos bucles podrían optimizar incrementando solo la parte de desplazamiento, pero los objetos de puntero no podrían optimizarse para ser más pequeños.


Si supieras cuál es la manipulación mágica para cualquier implementación dada, podrías implementarla en C puro . El problema es que diferentes sistemas usan direcciones diferentes y los detalles no están parametrizados por ninguna macros portátil.

O tal vez no: podría implicar buscar algo desde una tabla de segmentos especial o algo así, por ejemplo, como el modo protegido x86 en lugar del modo real donde la parte del segmento de la dirección es un índice, no un valor que se debe cambiar. Puede configurar segmentos parcialmente superpuestos en modo protegido, y las partes del selector de segmento de las direcciones ni siquiera se ordenarán necesariamente en el mismo orden que las direcciones base del segmento correspondiente. Obtener una dirección lineal desde un puntero seg: off en modo protegido x86 podría implicar una llamada al sistema, si el GDT y / o LDT no se asignan a páginas legibles en su proceso.

(Por supuesto, los sistemas operativos principales para x86 usan un modelo de memoria plana, por lo que la base del segmento siempre es 0 (excepto para el almacenamiento local de subprocesos que usa fso gssegmentos), y solo la parte de "desplazamiento" de 32 bits o 64 bits se usa como puntero .)

Puede agregar código manualmente para varias plataformas específicas, por ejemplo, asumir de forma predeterminada plano o #ifdefalgo para detectar el modo real x86 y dividirlo uintptr_ten mitades de 16 bits para seg -= off>>4; off &= 0xf;luego combinar esas partes nuevamente en un número de 32 bits.

Peter Cordes
fuente
¿Por qué sería UB si el segmento no es igual?
Bellota
@ Bellota: quería decir que al revés; fijo. los punteros en el mismo objeto tendrán el mismo segmento, de lo contrario, UB.
Peter Cordes
Pero, ¿por qué crees que es UB en cualquier caso? (lógica invertida o no, en realidad tampoco me di cuenta)
Bellota
p < qes UB en C si apuntan a diferentes objetos, ¿no? Lo p - qse.
Peter Cordes
1
@Acorn: De todos modos, no veo un mecanismo que genere alias (diferente seg: apagado, misma dirección lineal) en un programa sin UB. Entonces, no es como si el compilador tuviera que hacer todo lo posible para evitar eso; cada acceso a un objeto usa el segvalor de ese objeto y un desplazamiento que es> = el desplazamiento dentro del segmento donde comienza ese objeto. C hace que UB haga mucho de cualquier cosa entre punteros a diferentes objetos, incluyendo cosas como tmp = a-by luego b[tmp]acceder a[0]. Esta discusión sobre el alias de puntero segmentado es un buen ejemplo de por qué esa elección de diseño tiene sentido.
Peter Cordes
17

Una vez intenté encontrar una forma de evitar esto y encontré una solución que funciona para la superposición de objetos y, en la mayoría de los demás casos, suponiendo que el compilador hace lo "habitual".

¿Primero puede implementar la sugerencia en Cómo implementar memmove en el estándar C sin una copia intermedia? y luego, si eso no funciona emitir a uintptr(un tipo de envoltura para cualquiera uintptr_to unsigned long longdependiendo de si uintptr_testá disponible) y obtener un resultado exacto más probable (aunque probablemente no importaría de todos modos):

#include <stdint.h>
#ifndef UINTPTR_MAX
typedef unsigned long long uintptr;
#else
typedef uintptr_t uintptr;
#endif

int pcmp(const void *p1, const void *p2, size_t len)
{
    const unsigned char *s1 = p1;
    const unsigned char *s2 = p2;
    size_t l;

    /* Check for overlap */
    for( l = 0; l < len; l++ )
    {
        if( s1 + l == s2 || s1 + l == s2 + len - 1 )
        {
            /* The two objects overlap, so we're allowed to
               use comparison operators. */
            if(s1 > s2)
                return 1;
            else if (s1 < s2)
                return -1;
            else
                return 0;
        }
    }

    /* No overlap so the result probably won't really matter.
       Cast the result to `uintptr` and hope the compiler
       does the "usual" thing */
    if((uintptr)s1 > (uintptr)s2)
        return 1;
    else if ((uintptr)s1 < (uintptr)s2)
        return -1;
    else
        return 0;
}
SS Anne
fuente
5

¿C ofrece algo con una funcionalidad similar que permita comparar de forma segura punteros arbitrarios?

No


Primero consideremos solo los apuntadores de objetos . Los punteros de función traen otro conjunto de preocupaciones.

2 punteros p1, p2pueden tener diferentes codificaciones y apuntar a la misma dirección, por lo que p1 == p2aunque memcmp(&p1, &p2, sizeof p1)no sea 0. Dichas arquitecturas son raras.

Sin embargo, la conversión de estos punteros a uintptr_tno requiere el mismo resultado entero que conduce a (uintptr_t)p1 != (uinptr_t)p2.

(uintptr_t)p1 < (uinptr_t)p2 en sí es un código legal, por lo que no puede proporcionar la funcionalidad esperada.


Si el código realmente necesita comparar punteros no relacionados, forme una función auxiliar less(const void *p1, const void *p2)y realice allí el código específico de la plataforma.

Quizás:

// return -1,0,1 for <,==,> 
int ptrcmp(const void *c1, const void *c1) {
  // Equivalence test works on all platforms
  if (c1 == c2) {
    return 0;
  }
  // At this point, we know pointers are not equivalent.
  #ifdef UINTPTR_MAX
    uintptr_t u1 = (uintptr_t)c1;
    uintptr_t u2 = (uintptr_t)c2;
    // Below code "works" in that the computation is legal,
    //   but does it function as desired?
    // Likely, but strange systems lurk out in the wild. 
    // Check implementation before using
    #if tbd
      return (u1 > u2) - (u1 < u2);
    #else
      #error TBD code
    #endif
  #else
    #error TBD code
  #endif 
}
chux - Restablece a Monica
fuente