Можно ли как то реализовать функцию swap которая не будет привязана к определенному типу?
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;
}
}
-
Не в обиду, соберите, превратите в ассемблер и посмотрите количество процессорных тиков с такой реализацией, будете шокированы, как минимум..:)– NewViewCommented 31 мая 2018 в 21:43
-
1ага, конечно - godbolt.org/g/CPhfq1 - компиляторы сейчас достаточно умные и делают очень красивый код.– KoVadimCommented 1 июн. 2018 в 14:48
-
Ну в 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
-
size надо знать, и копирование это лишние телодвижения при быстром свапе, можно использовать atomic built in функции (разный синтаксис у разных компиляторов, есть уневерсальные врапперы)– NewViewCommented 31 мая 2018 в 21:41
-
вот собственно рабочий пример. В комментариях я допустил ошибку, жаль не поправить, 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. на досуге глянул и объединил обе функции, так же расширил типы на массивы. Как мне кажется,вполне юзабельно.
-
Эта функция нормально работает, если ее применять к переменным размером с указатель. Если меньше - свапается смежная память, если больше - последние байты не свапаются. Commented 1 июн. 2018 в 2:02
-
2Это функция обмен местами указателей
void *
. Все остальное она может менять местами лишь "на везении". Более того, попытка менять местами что-либо другое будет грубым нарушением правил strict aliasing, то есть работать это в общем случае не будет. Commented 1 июн. 2018 в 2:37 -
Конечно, это обмен местами указателей void *, собственно что от неё и требуется, по сути. 'что либо другое' не меняется, меняются местами именно указатели. Вопрос то был можно или нет свапить указатели независимо от типа, ответ можно. Далее надо смотреть где и с какими данными её преминять, естественно этот подход подойдёт не везде и фактически он не изменяет источники, меняются только указатели, что правильно, и правил strict aliasing оно именно по этому и не нарушает.– NewViewCommented 1 июн. 2018 в 8:03
-
Если бы автор привёл пример кода, где отражен тип данных и ситуацию в которой необходим свап данных, тогда можно было бы рассматривать предметное решение, пока это прикладная теория :)– NewViewCommented 1 июн. 2018 в 8:21
-
1@NewView: Такая функция позволяет свапить только указатели
void *
и совместимые с ними по объектному представлению указатели, т.е. напримерchar *
. Свапить указателиint *
такой функцией формально нельзя. Commented 1 июн. 2018 в 14:48
Как сделал я:
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++;
}
}
void **
? А чем плох простоvoid *
?&a
- этоchar **
, а неvoid **
, т.е. типы несовместимы. Во-вторых, автор хотел функцию для обмена "чего угодно", а не только указателей. В-третьих, чего вы хотите добиться черезvoid **c = a
- не ясно вообще.