Есть ли в C эквивалент std :: less из C ++?

Недавно я отвечал на вопрос о неопределенном поведении p < qв C, когда pи qесть указатели на разные объекты / массивы. Это заставило меня задуматься: <в этом случае C ++ имеет такое же (неопределенное) поведение , но также предлагает стандартный шаблон библиотеки, std::lessкоторый гарантированно возвращает то же самое, что и <при сравнении указателей, и возвращает некоторое согласованное упорядочение, когда они не могут.

Предлагает ли C что-то с аналогичной функциональностью, которая позволила бы безопасно сравнивать произвольные указатели (с тем же типом)? Я попытался просмотреть стандарт C11 и ничего не нашел, но мой опыт в C на порядки меньше, чем в C ++, поэтому я мог легко что-то упустить.

На реализациях с плоской моделью памяти (в основном все), приведение к uintptr_tJust Work.

(Но посмотрите, должны ли сравнения указателей быть подписанными или неподписанными в 64-битном x86? Для обсуждения того, следует ли вам рассматривать указатели как подписанные или нет, включая вопросы формирования указателей вне объектов, которые обозначены как UB в C.)

Но системы с неплоскими моделями памяти существуют, и размышления о них могут помочь объяснить текущую ситуацию, например, C ++ имеет разные спецификации для и <против std::less.

Часть точки < указателей на то, чтобы разделить объекты, являющиеся UB в C (или, по крайней мере, не определенные в некоторых ревизиях C ++), состоит в том, чтобы учесть странные машины, включая неплоские модели памяти.

Хорошо известным примером является реальный режим x86-16, где указатели являются сегментами: смещение, образуя 20-битный линейный адрес через (segment << 4) + offset. Один и тот же линейный адрес может быть представлен несколькими различными комбинациями сегментов.

C ++ std::lessдля указателей на странных ISA может быть дорогостоящим , например, «нормализовать» сегмент: смещение на x86-16, чтобы иметь смещение <= 15. Однако нет никакого портативного способа реализовать это. Манипуляции, необходимые для нормализации uintptr_t(или объектного представления объекта указателя), зависят от реализации.

Но даже в системах, где C ++ std::lessдолжен быть дорогим, <не должен быть. Например, предполагая «большую» модель памяти, в которой объект помещается в один сегмент, <можно просто сравнить смещенную часть и даже не беспокоиться с частью сегмента. (Указатели внутри одного и того же объекта будут иметь один и тот же сегмент, а в противном случае это UB в C. C ++ 17 заменен на просто «неопределенный», что может все же позволить пропустить нормализацию и просто сравнить смещения.) Это предполагает, что все указатели на любую часть объекта всегда использовать одно и то же segзначение, никогда не нормализуя. Это то, что вы ожидаете от ABI для «большой» модели в отличие от «огромной» модели памяти. (См. Обсуждение в комментариях ).

(Такая модель памяти может иметь максимальный размер объекта, например, 64 КБ, но гораздо большее максимальное общее адресное пространство, в котором есть место для многих таких объектов максимального размера. ISO C позволяет реализациям иметь ограничение на размер объекта, которое меньше, чем Максимальное значение (без знака) size_tможет представлять, SIZE_MAXнапример, даже в системах с плоской памятью, GNU C ограничивает максимальный размер объекта, PTRDIFF_MAXчтобы вычисление размера могло игнорировать переполнение со знаком.) См. этот ответ и обсуждение в комментариях.

Если вы хотите разрешить объекты размером больше сегмента, вам нужна «огромная» модель памяти, которая должна беспокоиться о переполнении смещенной части указателя при выполнении p++цикла по массиву или при выполнении арифметики индексирования / указателя. Это повсеместно приводит к более медленному коду, но, вероятно, p < qбудет означать, что это может сработать для указателей на разные объекты, потому что реализация, нацеленная на «огромную» модель памяти, обычно предпочитает поддерживать все указатели нормализованными все время. Посмотрите, что рядом, далеко и огромные указатели? - некоторые реальные компиляторы C для реального режима x86 имели возможность компилировать для «огромной» модели, где все указатели по умолчанию установлены в «огромный», если не указано иное.

Сегментация реального режима x86 - не единственная возможная модель неплоской памяти , это просто полезный конкретный пример, иллюстрирующий, как она обрабатывается реализациями C / C ++. В реальной жизни реализации расширяли ISO C концепцией farпротив nearуказателей, позволяя программистам выбирать, когда им удастся просто сохранить / передать 16-битную часть смещения относительно некоторого общего сегмента данных.

Но для реализации в чистом ISO C придется выбирать между маленькой моделью памяти (все, кроме кода в том же 64-килобайтном формате с 16-разрядными указателями) или большой или огромной, причем все указатели являются 32-разрядными. Некоторые циклы можно оптимизировать, увеличивая только смещенную часть, но объекты указателя нельзя оптимизировать, чтобы они были меньше.

Если бы вы знали, что такое магическая манипуляция для любой конкретной реализации, вы могли бы реализовать ее в чистом C . Проблема в том, что разные системы используют разные адресации, а детали не параметризуются никакими переносимыми макросами.

Или, может быть, нет: это может включать поиск чего-либо из специальной таблицы сегментов или что-то подобное, например, например, защищенный режим x86 вместо реального режима, где сегментная часть адреса является индексом, а не значением, которое нужно сдвинуть влево. Вы можете установить частично перекрывающиеся сегменты в защищенном режиме, и части адресов сегмента селектора не обязательно будут упорядочены в том же порядке, что и соответствующие базовые адреса сегментов. Для получения линейного адреса из указателя seg: off в защищенном режиме x86 может потребоваться системный вызов, если GDT и / или LDT не отображаются на читаемые страницы вашего процесса.

(Конечно, основные операционные системы для x86 используют плоскую модель памяти, поэтому база сегмента всегда равна 0 (за исключением использования локального хранилища потока fsили gsсегментов), и только 32-битная или 64-битная часть «смещения» используется в качестве указателя .)

Вы можете вручную добавить код для различных конкретных платформ, например, по умолчанию предположить, #ifdefчто он плоский или что-то для обнаружения реального режима x86, и разбить его uintptr_tна 16-битные половины, чтобы seg -= off>>4; off &= 0xf;затем объединить эти части обратно в 32-битное число.

Однажды я попытался найти способ обойти это, и я нашел решение, которое работает для перекрывающихся объектов, и в большинстве других случаев предполагая, что компилятор делает «обычную» вещь.

Сначала вы можете реализовать предложение в разделе Как реализовать memmove в стандарте C без промежуточной копии? и затем, если это не сработает, приведите к uintptr(тип-обертка для одного uintptr_tили unsigned long longзависит от того uintptr_t, доступен ли он) и получите наиболее вероятный точный результат (хотя это, вероятно, не имеет значения в любом случае):

#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;
}

Предлагает ли C что-то с аналогичной функциональностью, которая позволила бы безопасно сравнивать произвольные указатели.

нет

Сначала давайте рассмотрим только объектные указатели . Указатели на функции вызывают целый ряд других проблем.

2 указателя p1, p2могут иметь разные кодировки и указывать на один и тот же адрес, такp1 == p2 хотя memcmp(&p1, &p2, sizeof p1)это не 0. Такие архитектуры встречаются редко.

Все же преобразование этих указателей в uintptr_t не требует того же самого целочисленного результата, приводящего к (uintptr_t)p1 != (uinptr_t)p2.

(uintptr_t)p1 < (uinptr_t)p2 Сам по себе вполне законный кодекс, может не обеспечивать ожидаемую функциональность.

Если код действительно должен сравнивать несвязанные указатели, создайте вспомогательную функцию less(const void *p1, const void *p2)и выполните там код, специфичный для платформы.

Может быть:

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