Given an array of any type (integers in this case) and a Map that tells what indexes are supposed to be swapped in an array. I am attempting to make a clean swap, but running into issues with the way I am using memcpy.
Here is what I have so far:
Goal: given a data array of [1,3,-1,2] and a mapping of [[0,3],[3,2],[2,1],[1,0]], a clean permutation would be [3,-1,2,1].
My current implementation : 0 3 -1 2... I think I have an off-by-one error somewhere.
#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;
}
You are a victim of the non-standard GCC extension that is enabled by default and allows pointer arithmetics on pointers to void and pointers to function by treating the size of a void or of a function as 1. This extension can be disabled by specifying a C standard as, say, C99, using -std option — for example, -std=c99 (see gcc manual page for details). Alternatively, you may ask gcc to issue a warning for such cases by specifying -Wpointer-arith option.
Back to the problem, consider what happens when you write &data[tmpFrom]. An address pointed by data is taken, then tmpFrom bytes are added to that address. What you want instead is to add tmpFrom * sizeof(int) bytes. To achieve that, you have to either manually calculate required number of bytes based on the value of tmpFrom and the size of int type, or declare data pointer as a pointer to type int. The second is a preferred way to go, but if you really want your functions to support arbitrary data types, then you have to fall back to a harder, first approach.
Below is a list of warnings generated by clang (it is generally a lot better with diagnostics):
$ 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.
Once the above warnings are fixed, it should have worked. However, there are two more problems...
The first problem is incorrect expected result. It should be 3, -1, 1, 2 and not 3, -1, 2, 1. The mapping should be sorted like this:
0,3
1,0
2,1
3,2
And the permutation should be done in four steps:
1) 2, 3, -1, 1
2) 3, 2, -1, 1
3) 3, -1, 2, 1
4) 3, -1, 1, 2
The second problem is incorrect sorting. By performing two sorts, first on "from" values and second on "to" values, you end up with a mapping sorted only by "to" (the last sort you invoke). What should be done instead is a single sort using a predicate that compares both "from" and "to" of each element. For example:
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;
}
}
Once the above is fixed, everything will work. Other than that, there are only few more suggestions to your code that might be helpful:
indexFrom and indexTo fields of MapEntry structure dynamically allocated.void *. For example: void * a = (void *)malloc(szblob); should be just void *a = malloc(szblob);.void * to other pointer types like int *. This is not necessary in C where void * pointer is implicitly convertible to pointers of other types. This is not true for C++, however.typedef structures unless the goal is to create an opaque type (which is not in your case). Typing struct may seem like a lot of typing, but it serves as a great hints about the type to those C developers who read your code. For example, see Chapter 5 of the Linux Kernel Coding Style for a great explanation.I encourage you to fix your code yourself, but here is your code with minimal necessary changes to make it work, for your reference:
#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;
}
Hope it helps. Stay warm and Good Luck!