Универсальный массив элементов swap в C - PullRequest
Новая
       4

Универсальный массив элементов swap в C

0 голосов
/ 28 мая 2018

Теперь я понял, что во многих моих кодах у меня будет 2 или 3 функции, подобные этой: 

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

Каждая со своим собственным типом указателя.Что мне интересно, так это если есть способ поменять местами два элемента массива, например, независимо от типа массива?

Ответы [ 2 ]

0 голосов
/ 28 мая 2018

В дополнение к замечательному ответу Джонатана Леффлера, если вы используете gcc, вы можете сделать это как макрос: 

#define SWAP(a,b) \
  ({  __auto_type _store = (a); \
    (a) = (b); \
    (b) = _store; })

, это использует расширение __auto_type C, чтобы избежать необходимости указывать тип, но это неработа над компилятором evry см. https://gcc.gnu.org/onlinedocs/gcc/Typeof.html.

Он также немного загрязняет пространство имен, так как определяет переменную _store

0 голосов
/ 28 мая 2018

Да, но вы должны сообщить коду swap, насколько велики элементы: 

void generic_swap(void *v1, void *v2, size_t size)
{
    char temp[size];
    memmove(temp, v1, size);
    memmove(v1, v2, size);
    memmove(v2, temp, size);
}

При этом используется VLA (массив переменной длины - функция C99 и дополнительная функция C11)для временного пространства.Размер локального массива temp контролируется во время выполнения параметром функции size.Если вы не доверяете своим пользователям не запрашивать обмен нескольких мегабайт данных, вы можете вместо этого использовать динамическое выделение памяти или только динамическое выделение памяти, если размер больше, скажем, 1 килобайт.

Либо: 

void generic_swap(void *v1, void *v2, size_t size)
{
    size_t chunk = (size > 1024) ? 1024 : size;
    size_t offset = 0;
    char *s1 = v1;
    char *s2 = v2;
    char  temp[chunk];
    while (size > 0)
    {
        size_t length = (size > chunk) ? chunk : size;
        memmove(temp, s1 + offset, length);
        memmove(s1 + offset, s2 + offset, length);
        memmove(s2 + offset, temp, length);
        size -= length;
        offset += length;
    }
}

Или: 

void generic_swap(void *v1, void *v2, size_t size)
{
    void *v3 = malloc(size);
    if (v3 != 0)
    {
        memmove(v3, v1, size);
        memmove(v1, v2, size);
        memmove(v2, v3, size);
        free(v3);
    }
}

Версия цикла позволяет избежать накладных расходов при динамическом выделении памяти и не будет намного медленнее, чем копирование всего за три операции.Существуют различные способы настройки кода цикла - см. Также комментарии от rici о других способах оптимизации, которые вы можете найти, если обнаружите, что код подкачки являетсягорлышко бутылки.Вы можете выбрать меньший размер, чем 1024 байта;64 или 128 также могут быть выполнимыми, и вам не обязательно нужен VLA в функции.

Чтобы поменять местами два целых числа: 

int i = 37;
int j = 99;

swap_generic(&i, &j, sizeof(i));

Чтобы поменять местами два массива char:

char data[80] = "A tabloid writer's nightmare on steroids";
char info[80] = "Obsequiousness will get you nowhere fast";

swap_generic(data, info, sizeof(data));

и т. Д.Обратите внимание, что массивы должны быть одинакового размера - или, точнее, размер, который вы указываете, должен соответствовать размеру меньшего массива, чтобы быть безопасным.

Вы можете использовать memcpy() вместо memmove() если вы счастливы жить опасно - хотя опасность в этом контексте ограничена.(Если вы меняете объект на себя, вы вызываете неопределенное поведение. В противном случае это безопасно.) Использование memmove() всегда работает;использование memcpy() обычно работает.Я предпочитаю «всегда», а не «в основном».

Испытание проводов для трех алгоритмов

Компилировать, например: 

gcc -O3 -g -std=c11 -Wall -Wextra -Werror -DUSE_GENSWAP_3 swap89.c -o swap89

При запуске с Valgrind , код получает чистый счет здоровья.

Код: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if !defined(USE_GENSWAP_1) && !defined(USE_GENSWAP_2) && !defined(USE_GENSWAP_3)
#define USE_GENSWAP_1
#endif

extern void generic_swap(void *v1, void *v2, size_t size);

#ifdef USE_GENSWAP_1
void generic_swap(void *v1, void *v2, size_t size)
{
    char temp[size];
    memmove(temp, v1, size);
    memmove(v1, v2, size);
    memmove(v2, temp, size);
}
#endif

#ifdef USE_GENSWAP_2
void generic_swap(void *v1, void *v2, size_t size)
{
    size_t chunk = (size > 1024) ? 1024 : size;
    size_t offset = 0;
    char *s1 = v1;
    char *s2 = v2;
    char  temp[chunk];
    while (size > 0)
    {
        size_t length = (size > chunk) ? chunk : size;
        memmove(temp, s1 + offset, length);
        memmove(s1 + offset, s2 + offset, length);
        memmove(s2 + offset, temp, length);
        size -= length;
        offset += length;
    }
}
#endif

#ifdef USE_GENSWAP_3
void generic_swap(void *v1, void *v2, size_t size)
{
    void *v3 = malloc(size);
    if (v3 != 0)
    {
        memmove(v3, v1, size);
        memmove(v1, v2, size);
        memmove(v2, v3, size);
        free(v3);
    }
}
#endif

static size_t min_len(size_t x, size_t y) { return (x < y) ? x : y; }

static void dump_long_buffer(const char *tag, size_t length, char buffer[length])
{
    int maxpadlen = strlen(tag) + sizeof(" = ") - 1;
    printf("%s = ", tag);
    size_t offset = 0;
    int padlen = 0;
    while (length > 0)
    {
        int linelen = min_len(length, 80 - maxpadlen - sizeof("[]\n"));
        printf("%*s[%.*s]\n", padlen, "", linelen, buffer + offset);
        offset += linelen;
        length -= linelen;
        padlen = maxpadlen;
    }
}

int main(void)
{
    int i = 37;
    int j = 99;

    printf("i = %d; j = %d\n", i, j);
    generic_swap(&i, &j, sizeof(i));
    printf("i = %d; j = %d\n", i, j);

    char data[80] = "A tabloid writer's nightmare on steroids";
    char info[80] = "Obsequiousness will get you nowhere fast";

    printf("data = [%s]\ninfo = [%s]\n", data, info);
    generic_swap(data, info, sizeof(data));
    printf("data = [%s]\ninfo = [%s]\n", data, info);

    char maxibuff1[2560];
    char maxibuff2[2560];

    for (size_t k = 0; k < sizeof(maxibuff1); k++)
    {
        maxibuff1[k] = k % 64 + '!';
        maxibuff2[k] = 'z' - k % 64;
    }

    /* The aligned output is mostly the result of serendipity */
    dump_long_buffer("maxibuff1", sizeof(maxibuff1), maxibuff1);
    dump_long_buffer("maxibuff2", sizeof(maxibuff2), maxibuff2);
    generic_swap(maxibuff1, maxibuff2, sizeof(maxibuff1));
    dump_long_buffer("maxibuff1", sizeof(maxibuff1), maxibuff1);
    dump_long_buffer("maxibuff2", sizeof(maxibuff2), maxibuff2);

    return 0;
}

Пример вывода (результат одинаков для каждого алгоритма): 

i = 37; j = 99
i = 99; j = 37
data = [A tabloid writer's nightmare on steroids]
info = [Obsequiousness will get you nowhere fast]
data = [Obsequiousness will get you nowhere fast]
info = [A tabloid writer's nightmare on steroids]
maxibuff1 = [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
            [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
…
            [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
maxibuff2 = [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
            [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
…
            [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
maxibuff1 = [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
            [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
…
            [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
maxibuff2 = [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
            [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
…
            [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...