C 置换与 memcpy 问题

Question

给定一个任意类型的数组(在本例中为整数)和一个 Map，该 Map 告诉应该在数组中交换哪些索引。我正在尝试进行干净的交换，但遇到了我使用 memcpy 的方式的问题。

这是我目前所拥有的:

目标:给定 [1,3,-1,2] 的数据数组和 [[0,3],[3,2],[2,1],[1,0]] 的映射，一个干净的排列是 [3,-1,2,1]。

我当前的实现:0 3 -1 2...我想我在某处有一个差一错误。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAP_SIZE 4

typedef struct MapEntry {
    int indexFrom;
    int indexTo;
} MapEntry;

typedef MapEntry * Map;

int permute(void *data, int nblobs, int szblob, const Map map);

void build_map(Map);
void build_data(int *);
int is_map_valid(Map);
void print_map(Map);
int is_valid(Map);

int map_comparator(const void * a, const void * b);

int main(int argc, char const *argv[])
{
    int nblobs, * data, i;
    size_t szblob;
    Map map = (Map)malloc(sizeof(Map));
    data = (int *) malloc(sizeof(int) * 4);

    build_map(map);

    data[0] = 1;
    data[1] = 3;
    data[2] = -1;
    data[3] = 2;

    nblobs = 4;
    szblob = sizeof(int);

    if (!permute(data, nblobs, szblob, map)) {
        printf("Invalid Map\n");
        return 0;
    }

    i = 0;
    for (i = 0; i < szblob; ++i) {
        printf("%d ", data[i]);
    }

    return 0;
}

void print_map(Map map){
    int i;
    for (i = 0; i < MAP_SIZE; ++i) {
        printf("[%d - %d]\n", map[i].indexFrom, map[i].indexTo);
    }
}

int map_comparator(const void *a, const void *b)
{
    const MapEntry *s1 = a;
    const MapEntry *s2 = b;
    if (s2->indexFrom != s1->indexFrom) {
        return s1->indexFrom - s2->indexFrom;
    } else {
        return s1->indexTo - s2->indexTo;
    }
}

int is_map_valid(Map map) {
    int i,j;
    for (i = 1; i < MAP_SIZE; ++i){
        j = i - 1;
        if (map[j].indexFrom == map[i].indexFrom)
            return 0;
        if (map[j].indexTo == map[i].indexTo)
            return 0;
    }
    return 1;
}

int is_valid(Map map) {
    qsort(map, MAP_SIZE, sizeof(MapEntry), map_comparator);
    if (!is_map_valid(map)) return 0;
    return 1;
}


int permute(void *data, int nblobs, int szblob, const Map map){
    int i, tmpFrom, tmpTo;
    void * a = (void *)malloc(szblob);
    char *p = data;

    /* check if map has duplicate keys */
    /* sort the list, then check whether or not the map is valid */
    if (!is_valid(map)) return 0;
    /* where issues occur */

    for (i = 0; i < nblobs; ++i){

        tmpFrom = map[i].indexFrom;

        tmpTo = map[i].indexTo;

        memcpy(a, &p[tmpFrom*szblob], szblob);

        memcpy(&p[tmpFrom*szblob], &p[tmpTo*szblob], szblob);

        memcpy(&p[tmpTo*szblob], a, szblob);

    }

    return 1;

}
/* build mapping */
void build_map(Map map){
    map[0].indexFrom = 0;
    map[0].indexTo = 3;
    map[1].indexFrom = 3;
    map[1].indexTo = 2;
    map[2].indexFrom = 2;
    map[2].indexTo = 1;
    map[3].indexFrom = 1;
    map[3].indexTo = 0;

}

Answer 1

您是默认启用的非标准 GCC 扩展的受害者，并且 allows pointer arithmetics通过将 void 或函数的大小视为 1，在指向 void 的指针和指向函数的指针上。可以通过使用 -std 选项指定 C 标准(例如 C99)来禁用此扩展 -例如，-std=c99(详见 gcc manual page)。或者，您可以通过指定 -Wpointer-arith 选项要求 gcc 针对此类情况发出警告。

回到问题，考虑当你写&data[tmpFrom]时会发生什么。获取 data 指向的地址，然后将 tmpFrom 字节添加到该地址。您想要的是添加 tmpFrom * sizeof(int) 字节。为此，您必须根据 tmpFrom 的值和 int 类型的大小手动计算所需的字节数，或者声明 data 作为指向类型 int 的指针的指针。第二种是首选方法，但如果您真的希望您的函数支持任意数据类型，那么您必须退回到更难的第一种方法。

下面是 clang 生成的警告列表(通常使用诊断会好很多):

$ clang -Wall -pedantic -o test ./test.c
./test.c:109:18: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(a, &data[tmpFrom], szblob);
                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:36: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                   ^
./test.c:109:13: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(a, &data[tmpFrom], szblob);
                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:36: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                   ^
./test.c:109:18: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(a, &data[tmpFrom], szblob);
                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:33: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                                ^
./test.c:109:13: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(a, &data[tmpFrom], szblob);
                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:33: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                                ^
./test.c:111:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:54:21: note: expanded from macro 'memcpy'
  ((__darwin_obsz0 (dest) != (size_t) -1)                               \
                    ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:111:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:54:21: note: expanded from macro 'memcpy'
  ((__darwin_obsz0 (dest) != (size_t) -1)                               \
                    ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:111:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:30: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                             ^
./test.c:111:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:30: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                             ^
./test.c:111:31: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:36: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                   ^
./test.c:111:26: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:36: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                   ^
./test.c:111:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:62: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                                             ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:111:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:62: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                                             ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:111:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:27: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                          ^
./test.c:111:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:27: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                          ^
./test.c:111:31: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:33: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                                ^
./test.c:111:26: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpFrom], &data[tmpTo], szblob);
                ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:33: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                                ^
./test.c:113:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:54:21: note: expanded from macro 'memcpy'
  ((__darwin_obsz0 (dest) != (size_t) -1)                               \
                    ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:113:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:54:21: note: expanded from macro 'memcpy'
  ((__darwin_obsz0 (dest) != (size_t) -1)                               \
                    ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:113:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:30: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                             ^
./test.c:113:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:30: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                             ^
./test.c:113:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:62: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                                             ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:113:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:55:62: note: expanded from macro 'memcpy'
   ? __builtin___memcpy_chk (dest, src, len, __darwin_obsz0 (dest))     \
                                                             ^
/usr/include/secure/_common.h:38:55: note: expanded from macro '__darwin_obsz0'
#define __darwin_obsz0(object) __builtin_object_size (object, 0)
                                                      ^~~~~~
./test.c:113:15: warning: subscript of a pointer to void is a GNU extension [-pedantic,-Wpointer-arith]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:27: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                          ^
./test.c:113:10: warning: ISO C forbids taking the address of an expression of type 'void' [-pedantic]
                memcpy(&data[tmpTo], a, szblob);
                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/secure/_string.h:56:27: note: expanded from macro 'memcpy'
   : __inline_memcpy_chk (dest, src, len))
                          ^
24 warnings generated.

一旦上述警告得到修复，它就应该起作用了。但是，还有两个问题……

第一个问题是预期结果不正确。它应该是 3, -1, 1, 2 而不是 3, -1, 2, 1。映射应该像这样排序:

0,3
1,0
2,1
3,2

排列应该分四步完成:

1) 2, 3, -1, 1
2) 3, 2, -1, 1
3) 3, -1, 2, 1
4) 3, -1, 1, 2

第二个问题是排序不正确。通过执行两种排序，首先对“从”值进行排序，然后对“到”值进行排序，您最终得到一个仅按“到”排序的映射(您调用的最后一种排序)。应该做的是使用比较每个元素的“from”和“to”的谓词进行单一排序。例如:

int map_comparator(const void *a, const void *b)
{
    const MapEntry *s1 = a;
    const MapEntry *s2 = b;
    if (*s2->indexFrom != *s1->indexFrom) {
        return *s1->indexFrom - *s2->indexFrom;
    } else {
        return *s1->indexTo - *s2->indexTo;
    }
}

一旦上述问题得到解决，一切都会正常进行。除此之外，只有少数对您的代码有帮助的建议:

1. 您使用了太多的动态分配。考虑重新考虑如何做。例如，我认为不需要动态分配 MapEntry 结构的 indexFrom 和 indexTo 字段。
2. 您对 void * 进行了不必要的转换。例如:void *a = (void *)malloc(szblob); 应该只是 void *a = malloc(szblob);。
3. 从 void * 到其他指针类型(如 int *)的不必要的转换。这在 C 中是不必要的，因为 void * 指针可以隐式转换为其他类型的指针。然而，对于 C++，情况并非如此。
4. 不要typedef 结构，除非目标是创建一个不透明的类型(这不是您的情况)。输入 struct 可能看起来像很多输入，但对于那些阅读您的代码的 C 开发人员来说，它可以很好地提示类型。例如，参见 Linux Kernel Coding Style 的第 5 章以获得很好的解释。

我鼓励您自己修复您的代码，但这里是您的代码，只需进行最少的必要更改即可使其正常工作，供您引用:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAP_SIZE 4

typedef struct MapEntry {
    int * indexFrom;
    int * indexTo;
} MapEntry;

typedef MapEntry * Map;

int permute(void *data, int nblobs, int szblob, const Map map);

void build_map(Map);
void build_data(int *);
int is_map_valid(Map);
void print_map(Map);
int is_valid(Map);

int map_comparator(const void * a, const void * b);

int main(int argc, char const *argv[])
{
    int nblobs, * data, i;
    size_t szblob;
    Map map = (Map)malloc(sizeof(Map));
    data = (int *) malloc(sizeof(int) * 4);

    build_map(map);

    data[0] = 1;
    data[1] = 3;
    data[2] = -1;
    data[3] = 2;

    nblobs = 4;
    szblob = sizeof(int);

    if (!permute(data, nblobs, szblob, map)) {
        printf("Invalid Map\n");
        return 0;
    }

    i = 0;
    for (i = 0; i < szblob; ++i) {
        printf("%d ", data[i]);
    }

    return 0;
}

void print_map(Map map){
    int i;
    for (i = 0; i < MAP_SIZE; ++i) {
        printf("[%d - %d]\n", *map[i].indexFrom, *map[i].indexTo);
    }
}

int map_comparator(const void *a, const void *b)
{
    const MapEntry *s1 = a;
    const MapEntry *s2 = b;
    if (*s2->indexFrom != *s1->indexFrom) {
        return *s1->indexFrom - *s2->indexFrom;
    } else {
        return *s1->indexTo - *s2->indexTo;
    }
}

int is_map_valid(Map map) {
    int i,j;
    for (i = 1; i < MAP_SIZE; ++i){
        j = i - 1;
        if (*map[j].indexFrom == *map[i].indexFrom)
            return 0;
        if (*map[j].indexTo == *map[i].indexTo)
            return 0;
    }
    return 1;
}

int is_valid(Map map) {
    qsort(map, MAP_SIZE, sizeof(MapEntry), map_comparator);
    if (!is_map_valid(map)) return 0;
    return 1;
}


int permute(void *data, int nblobs, int szblob, const Map map){
    int i, tmpFrom, tmpTo;
    void * a = (void *)malloc(szblob);
    char *p = data;

    /* check if map has duplicate keys */
    /* sort the list, then check whether or not the map is valid */
    if (!is_valid(map)) return 0;
    /* where issues occur */

    for (i = 0; i < nblobs; ++i){

        tmpFrom = *map[i].indexFrom;

        tmpTo = *map[i].indexTo;

        memcpy(a, &p[tmpFrom*szblob], szblob);

        memcpy(&p[tmpFrom*szblob], &p[tmpTo*szblob], szblob);

        memcpy(&p[tmpTo*szblob], a, szblob);

    }

    return 1;

}
/* build mapping */
void build_map(Map map){
    int i;
    for (i = 0; i < MAP_SIZE; ++i) {
        map[i].indexFrom = (int *)malloc(sizeof(int));
        map[i].indexTo = (int *)malloc(sizeof(int));
    }

    *map[0].indexFrom = 0;
    *map[0].indexTo = 3;

    *map[1].indexFrom = 3;
    *map[1].indexTo = 2;

    *map[2].indexFrom = 2;
    *map[2].indexTo = 1;

    *map[3].indexFrom = 1;
    *map[3].indexTo = 0;

}

希望对您有所帮助。保持温暖，祝你好运!