3

Можно ли как то реализовать функцию swap которая не будет привязана к определенному типу?

7
  • для свапа нужно знать размер типа. Без него будет всё странно. На С++ можно. Если размер типа фиксирован тоже. Через свой врапер - легко.
    – pavel
    Commented 31 мая 2018 в 18:32
  • 4
    Функцию - нельзя. Можно - макрос. Commented 31 мая 2018 в 18:41
  • А подробнее можно?
    – user297341
    Commented 31 мая 2018 в 19:16
  • 1
    @NewView: Почему именно void **? А чем плох просто void *? Commented 31 мая 2018 в 21:27
  • 1
    @NewView: Во-первых, так нельзя &a - это char **, а не void **, т.е. типы несовместимы. Во-вторых, автор хотел функцию для обмена "чего угодно", а не только указателей. В-третьих, чего вы хотите добиться через void **c = a - не ясно вообще. Commented 1 июн. 2018 в 1:31

4 ответа 4

4

Вроде тут ничего хитрого:

void Swap(void * const p_left, void * const p_right, size_t const bytes_count)
{
    size_t byte_index;
    for(byte_index = 0; bytes_count != byte_index; ++byte_index)
    {
        uint8_t * const p_left_byte = ((uint8_t *) p_left) + byte_index;
        uint8_t * const p_right_byte = ((uint8_t *) p_right) + byte_index;
        uint8_t const tmp = *p_left_byte;
        *p_left_byte = *p_right_byte;
        *p_right_byte = tmp;
    }
}
3
  • Не в обиду, соберите, превратите в ассемблер и посмотрите количество процессорных тиков с такой реализацией, будете шокированы, как минимум..:)
    – NewView
    Commented 31 мая 2018 в 21:43
  • 1
    ага, конечно - godbolt.org/g/CPhfq1 - компиляторы сейчас достаточно умные и делают очень красивый код.
    – KoVadim
    Commented 1 июн. 2018 в 14:48
  • Спасибо, незнал об этом сайте, наглядно.
    – NewView
    Commented 1 июн. 2018 в 15:44
1
Ну в c99 можно еще проще!
void swap(void *a, void *b, size_t size)
{
    char temp[size]; // std=c99
    memcpy(temp, b,    size);
    memcpy(b,    a,    size);
    memcpy(a,    temp, size);
}
3
  • 3
    Памяти в стеке многовато скушает (вроде бы)
    – andreymal
    Commented 31 мая 2018 в 20:50
  • size надо знать, и копирование это лишние телодвижения при быстром свапе, можно использовать atomic built in функции (разный синтаксис у разных компиляторов, есть уневерсальные врапперы)
    – NewView
    Commented 31 мая 2018 в 21:41
  • Вам ОС не даст такое сделать на практике.
    – 0andriy
    Commented 2 июн. 2018 в 8:20
0

вот собственно рабочий пример. В комментариях я допустил ошибку, жаль не поправить, void *c это одинарная ссылка. приведу тут правильный код функции swap:

#define __swap_wrapper(A,B) __swap((void**)&A, (void**)&B)

void __swap(void **a, void **b) {
    void *c = *a;
    *a = *b; *b = c;
}

__swap_wrapper - враппер для удобства описания, чтоб код не захламлять. можно также использовать intrinsics (gcc) с memory barrier, итд

Измененный вариант

Измененный вариант, с макросами определения типа и копированием данных, макросы базовых типов, все приводить не стал, можно добавлять по собственному вкусу, заточено под сборку gcc.


Макрос и функции:

#define __swap_wrapper(A,B) __extension__ \
    (__builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), int[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const int[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), unsigned int[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const unsigned int[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), short[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const short[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), unsigned short[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const unsigned short[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), long[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const long[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), unsigned long[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const unsigned long[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), long long[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const long long[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), unsigned long long[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), unsigned const long long[]), __swap(A, B, sizeof(A), sizeof(B)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), char*), __swap_p((void**)&A, (void**)&B), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const char*), __swap_p((void**)&A, (void**)&B), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), char[]), __swap(A, B, (sizeof(A) - 1), (sizeof(B) - 1)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const char[]), __swap(A, B, (sizeof(A) - 1), (sizeof(B) - 1)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), unsigned char*), __swap_p((void**)&A, (void**)&B), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const unsigned char*), __swap_p((void**)&A, (void**)&B), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), unsigned char[]), __swap(A, B, (sizeof(A) - 1), (sizeof(B) - 1)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const unsigned char[]), __swap(A, B, (sizeof(A) - 1), (sizeof(B) - 1)), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), void*), __swap_p((void**)&A, (void**)&B), \
            __builtin_choose_expr( \
        __builtin_types_compatible_p(__typeof__(A), const void*), __swap_p((void**)&A, (void**)&B), \
    __swap(A, B, sizeof(*A), sizeof(*B)))))))))))))))))))))))))))))


void __swap_p(void **a, void **b) {
    void *c = *a;
    *a = *b; *b = c;
}

void __swap(void *a, void *b, size_t na, size_t nb)
{
    if ((!na) || (na != nb)) { return; }

    char *va = (char*)a,
         *vb = (char*)b;

    if (va == vb) { return; }

    __builtin_prefetch(va + na, 1, 1);
    __builtin_prefetch(vb + nb, 1, 1);

    while (na--)
    {
        va[na] ^= vb[na];
        vb[na] ^= va[na];
        va[na] ^= vb[na];
    }
}

ну и собственно рабочий пример (изменен).

P.S. на досуге глянул и объединил обе функции, так же расширил типы на массивы. Как мне кажется,вполне юзабельно.

15
  • Эта функция нормально работает, если ее применять к переменным размером с указатель. Если меньше - свапается смежная память, если больше - последние байты не свапаются. Commented 1 июн. 2018 в 2:02
  • 2
    Это функция обмен местами указателей void *. Все остальное она может менять местами лишь "на везении". Более того, попытка менять местами что-либо другое будет грубым нарушением правил strict aliasing, то есть работать это в общем случае не будет. Commented 1 июн. 2018 в 2:37
  • Конечно, это обмен местами указателей void *, собственно что от неё и требуется, по сути. 'что либо другое' не меняется, меняются местами именно указатели. Вопрос то был можно или нет свапить указатели независимо от типа, ответ можно. Далее надо смотреть где и с какими данными её преминять, естественно этот подход подойдёт не везде и фактически он не изменяет источники, меняются только указатели, что правильно, и правил strict aliasing оно именно по этому и не нарушает.
    – NewView
    Commented 1 июн. 2018 в 8:03
  • Если бы автор привёл пример кода, где отражен тип данных и ситуацию в которой необходим свап данных, тогда можно было бы рассматривать предметное решение, пока это прикладная теория :)
    – NewView
    Commented 1 июн. 2018 в 8:21
  • 1
    @NewView: Такая функция позволяет свапить только указатели void * и совместимые с ними по объектному представлению указатели, т.е. например char *. Свапить указатели int * такой функцией формально нельзя. Commented 1 июн. 2018 в 14:48
0

Как сделал я:

void swap_s(char *a, char *b, size_t n)
{
    char tmp;
    for (int i=0; i<n; i++) {
        tmp = *a;
        *a = *b;
        *b = tmp;
        a++;
        b++;
    }
}

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.