C tem um equivalente de std :: less do C ++?

26

Recentemente, eu estava respondendo uma pergunta sobre o comportamento indefinido de fazer p < qem C quando pe qsão ponteiros para diferentes objetos / matrizes. Isso me fez pensar: C ++ tem o mesmo comportamento (indefinido) <nesse caso, mas também oferece o modelo de biblioteca padrão std::lessque garante a mesma coisa que <quando os ponteiros podem ser comparados e retorna uma ordem consistente quando não pode.

C oferece algo com funcionalidade semelhante que permita comparar com segurança ponteiros arbitrários (do mesmo tipo)? Tentei examinar o padrão C11 e não encontrei nada, mas minha experiência em C é uma ordem de magnitude menor que em C ++, para que eu pudesse ter perdido algo facilmente.

Angew não está mais orgulhoso de SO
fonte
11
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Samuel Liew

Respostas:

20

Nas implementações com um modelo de memória plana (basicamente tudo), a conversão para uintptr_tJust Work.

(Mas consulte As comparações de ponteiros devem ser assinadas ou não assinadas no x86 de 64 bits? Para discutir se você deve tratar os ponteiros como assinados ou não, incluindo problemas de formação de ponteiros fora dos objetos que são UB em C.)

Mas sistemas com modelos de memória não-planos existem, e pensar sobre eles podem ajudar a explicar a situação atual, como C ++ ter especificações diferentes para <vs. std::less.


Parte do objetivo dos <ponteiros para separar objetos sendo UB em C (ou pelo menos não especificados em algumas revisões de C ++) é permitir máquinas estranhas, incluindo modelos de memória não plana.

Um exemplo conhecido é o modo real x86-16, em que os ponteiros são segmentados: offset, formando um endereço linear de 20 bits via (segment << 4) + offset. O mesmo endereço linear pode ser representado por várias combinações diferentes seg: off.

C ++ std::lessem ponteiros em ISAs estranhos pode precisar ser caro , por exemplo, "normalizar" um segmento: deslocamento em x86-16 para deslocamento <= 15. No entanto, não há uma maneira portátil de implementar isso. A manipulação necessária para normalizar um uintptr_t(ou a representação de objeto de um objeto ponteiro) é específica da implementação.

Mas mesmo em sistemas onde o C ++ std::lessprecisa ser caro, <não precisa ser. Por exemplo, supondo um modelo de memória "grande" em que um objeto se encaixe em um segmento, <basta comparar a parte deslocada e nem mesmo se preocupar com a parte do segmento. (Ponteiros dentro do mesmo objeto terão o mesmo segmento e, caso contrário, o UB no C. C ++ 17 foi alterado para meramente "não especificado", o que ainda pode permitir ignorar a normalização e apenas comparar compensações.) Isso pressupõe que todos os ponteiros de qualquer parte de um objeto sempre use o mesmo segvalor, nunca normalizando. Isso é o que você esperaria de uma ABI para um modelo de memória "grande" em oposição a "grande". (Veja a discussão nos comentários ).

(Esse modelo de memória pode ter um tamanho máximo de objeto de 64 kiB, por exemplo, mas um espaço de endereço total máximo muito maior, com espaço para muitos desses objetos de tamanho máximo. O ISO C permite que as implementações tenham um limite no tamanho do objeto menor que o o valor máximo (não assinado) size_tpode representar, SIZE_MAXpor exemplo, mesmo em sistemas de modelo de memória plana, o GNU C limita o tamanho máximo do objeto para PTRDIFF_MAXque o cálculo do tamanho ignore o estouro assinado.) Consulte esta resposta e discussão nos comentários.

Se você deseja permitir objetos maiores que um segmento, precisa de um modelo de memória "enorme" que precise se preocupar em exceder a parte deslocada de um ponteiro ao fazer um p++loop através de uma matriz ou ao fazer uma aritmética de indexação / ponteiro. Isso leva a códigos mais lentos em todos os lugares, mas provavelmente significaria que p < qfuncionaria para ponteiros para objetos diferentes, porque uma implementação direcionada a um modelo de memória "enorme" normalmente escolheria manter todos os ponteiros normalizados o tempo todo. Consulte O que há perto, longe e grandes indicadores? - alguns compiladores C reais para o modo real x86 tiveram uma opção de compilar para o modelo "enorme", onde todos os ponteiros assumiram o padrão de "enorme", a menos que declarado o contrário.

A segmentação em modo real x86 não é o único modelo de memória não plana possível , é apenas um exemplo concreto útil para ilustrar como ele foi tratado pelas implementações de C / C ++. Na vida real, as implementações estenderam o ISO C com o conceito de ponteiros farvs. near, permitindo que os programadores escolham quando podem simplesmente armazenar / passar pela parte offset de 16 bits, relativa a algum segmento de dados comum.

Mas uma implementação ISO C pura teria que escolher entre um modelo de memória pequeno (tudo, exceto código no mesmo 64kiB com ponteiros de 16 bits) ou grande ou enorme, com todos os ponteiros de 32 bits. Alguns loops podem otimizar incrementando apenas a parte de deslocamento, mas os objetos ponteiros não podem ser otimizados para serem menores.


Se você soubesse qual era a manipulação mágica para qualquer implementação, poderia implementá-la em C puro . O problema é que sistemas diferentes usam endereços diferentes e os detalhes não são parametrizados por macros portáteis.

Ou talvez não: isso pode envolver a procura de algo em uma tabela de segmento especial ou algo assim, por exemplo, como o modo protegido x86, em vez do modo real, onde a parte do segmento do endereço é um índice, não um valor a ser mudado. Você pode configurar segmentos parcialmente sobrepostos no modo protegido, e as partes dos endereços do seletor de segmentos não seriam necessariamente ordenadas na mesma ordem que os endereços base do segmento correspondente. Obter um endereço linear de um ponteiro seg: off no modo protegido x86 pode envolver uma chamada do sistema, se o GDT e / ou LDT não estiverem mapeados em páginas legíveis em seu processo.

(É claro que os sistemas operacionais convencionais para x86 usam um modelo de memória simples, de modo que a base do segmento seja sempre 0 (exceto para armazenamento local de segmentos usando fsou gssegmentos), e apenas a parte "deslocamento" de 32 ou 64 bits é usada como ponteiro .)

Você pode adicionar manualmente o código para várias plataformas específicas, por exemplo, por padrão, supor flat ou #ifdefalgo para detectar o modo real x86 e dividir uintptr_tem metades de 16 bits para seg -= off>>4; off &= 0xf;depois combinar essas partes novamente em um número de 32 bits.

Peter Cordes
fonte
Por que seria UB se o segmento não é igual?
Acorn
@ Acorn: Significou dizer o contrário; fixo. ponteiros para o mesmo objeto terão o mesmo segmento, senão UB.
Peter Cordes
Mas por que você acha que é UB em qualquer caso? (invertido a lógica ou não, na verdade, eu não notei qualquer um)
Acorn
p < qé UB em C se eles apontam para objetos diferentes, não é? Eu sei que p - qé.
Peter Cordes
11
@ Acorn: Enfim, não vejo um mecanismo que gere aliases (seg: off diferentes, mesmo endereço linear) em um programa sem UB. Portanto, não é como se o compilador tivesse que se esforçar para evitar isso; todo acesso a um objeto usa o segvalor desse objeto e um deslocamento que é> = o deslocamento no segmento em que esse objeto é iniciado. C torna UB fazer muito de qualquer coisa entre ponteiros para objetos diferentes, incluindo coisas como tmp = a-be depois b[tmp]acessar a[0]. Essa discussão sobre aliasing de ponteiro segmentado é um bom exemplo de por que essa escolha de design faz sentido.
Peter Cordes
17

Uma vez tentei encontrar uma maneira de contornar isso e encontrei uma solução que funciona para sobrepor objetos e, na maioria dos outros casos, supondo que o compilador faça a coisa "usual".

Você pode primeiro implementar a sugestão em Como implementar o memmove no padrão C sem uma cópia intermediária? e, se isso não funcionar, é convertido em uintptr(um tipo de invólucro para um uintptr_tou unsigned long longdependendo do que uintptr_testá disponível) e obtém um resultado exato mais provável (embora provavelmente não importe de qualquer maneira):

#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
fonte
5

C oferece algo com funcionalidade semelhante que permitiria comparar com segurança ponteiros arbitrários.

Não


Primeiro, vamos considerar apenas os ponteiros do objeto . Ponteiros de função trazem um conjunto totalmente diferente de preocupações.

2 ponteiros p1, p2podem ter codificações diferentes e apontar para o mesmo endereço, p1 == p2mesmo que memcmp(&p1, &p2, sizeof p1)não seja 0. Essas arquiteturas são raras.

No entanto, a conversão desses ponteiros para uintptr_tnão requer o mesmo resultado inteiro que leva a (uintptr_t)p1 != (uinptr_t)p2.

(uintptr_t)p1 < (uinptr_t)p2 em si é um código bem legal, pode não fornecer a funcionalidade esperada.


Se o código realmente precisar comparar ponteiros não relacionados, forme uma função auxiliar less(const void *p1, const void *p2)e execute o código específico da plataforma.

Possivelmente:

// 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 - Restabelecer Monica
fonte