Implementing a generical 'map' function over arrays in C

Question

Hi!

I'm having difficulties implementing a generic 'map' function over arrays. I started with the following draft:

void MapArray(void * src, void * dest, void * (f)(void *), size_t n, size_t elem)
{
   unsigned int i = 0, j = 0;
   void * temp = malloc(elem);

   for(i = 0; i<n, i++)
   {
      temp = (f)((char *) src) + i));
      for(j = 0; j < elem; j++)
      {
         *(((char *) dest) + i) = *(((char *) temp) + i);
      }
   }
   free(temp);
}

I understand why it's not correct - i'm casting to (char *) before giving it to 'f' - but i'm now demotivated and can't come up with a solution. (I'm doing this in the process of learning C)

My rationale was to obtain the result of 'f' and, byte by byte, copy it to dest[i].

Can you give me any hint?

Answer 1

• Check that the function f is not returning a pointer to a local variable
• I am not sure what the loop over j is supposed to be doing

Answer 2

Your first problem is that you're doing WAY too much in a few expressions. You need to break it down.

void MapArray(void * src, void * dest, void * (f)(void *), size_t n, size_t elem)
{
   unsigned int i = 0, j = 0;
   void * temp = malloc(elem);

   char* csrc = (char*)src;
   char* cdest = (char*)dest;
   char* ctemp = (char*)temp;
   for(i = 0; i<n; i++)
   {
       csrc++;
       cdest++;
       ctemp++;
       temp = f(csrc);
       for(j = 0; j < elem; j++)
       {
           cdest[i] = ctemp[i];
       }
   }
   free(temp);
}

Now your second problem. You malloc a buffer, then you .. assign to that pointer? Repeatedly? Then free only the last f call's result? This is totally unnecessary.

void MapArray(void * src, void * dest, void * (f)(void *), size_t n, size_t elem)
{
   unsigned int i = 0, j = 0;

   char* csrc = (char*)src;
   char* cdest = (char*)dest;
   for(i = 0; i<n; i++)
   {
       csrc++;
       cdest++;
       char* ctemp = (char*)f(csrc);
       for(j = 0; j < elem; j++)
       {
           cdest[i] = ctemp[i];
       }
   }
}

Now your third problem. You pass a pointer in - but only to char. You don't pass in a void*. This means that your function can't be generic - f can't be applied to anything. We need an array of void*s, so that the function can take any type as argument. We also need to take the size of the type as an argument so we know how far to move along dest.

void MapArray(void ** src, void * dest, void * (f)(void *), size_t n, size_t sizeofT)
{
    for(unsigned int i = 0; i < n; i++) {
        void* temp = f(src[n]);
        memcpy(dest, temp, sizeofT);
        dest = (char*)dest + sizeofT;
    }
}

We still have another problem - the memory of temp. We don't free it. Nor do we pass a user data argument into f, which would allow it to return heap-allocated memory that we don't need to free. The only way in which f can work is if it returned a static buffer.

void MapArray(void ** src, void * dest, void * (f)(void *, void*), void* userdata, size_t n, size_t sizeofT)
{
    for(unsigned int i = 0; i < n; i++) {
        void* temp = f(src[n], userdata);
        memcpy(dest, temp, sizeofT);
        dest = (char*)dest + sizeofT;
    }
}

Now f can operate on pretty much whatever it likes and hold whatever state it needs. But we still don't free the buffer. Now, f returns a simple struct that tells us if we need to free the buffer. This also allows us to free or not free the buffer on different calls of f.

typedef struct {
    void* data;
    int free;
} freturn;

void MapArray(void ** src, void * dest, freturn (f)(void *, void*), void* userdata, size_t n, size_t sizeofT)
{
    for(unsigned int i = 0; i < n; i++) {
        freturn thisreturn = f(src[n], userdata);
        void* temp = thisreturn.data;
        memcpy(dest, temp, sizeofT);
        dest = (char*)dest + sizeofT;
        if (thisreturn.free)
            free(temp);
    }
}

However, I still don't understand the purpose of this function. All of this to replace a simple for loop? The code that you're trying to replace is simpler than the code to call your function, and probably more efficient, and definitely more powerful (they can use continue/break, for example).

More than that, C really sucks for this kind of work. C++ is far better. It's pretty trivial there to apply a function to each member of an array, for example.

Answer 3

There's a reason nothing much like this is in the C standard library -- it's next to impossible to do it well in C. You can't copy the result, "byte by byte" to dest[i] -- since you've cast dest to a char *, it only points to one char (byte).

Presumably, elem is intended to be the size of whatever type f returns, and n is the number of elements in src and dest. In that case, your code isn't too far off, but (as you've apparently surmised) the way you're manipulating the pointers (especially the cast to char *) isn't going to cut it.

Even if you fix that, however, you'll have one other problem: assigning the return type from f without knowing the type is going to be really (really) difficult. In fact, about the only way I can think of is to wrap this code up into a macro instead:

#define MapArray(s, d, f, n) \
do {                         \
   unsigned i;               \
   for (i = 0; i<n; i++)     \
      d[i] = f(s[i]);        \
} while (0)

You'd use this something like this:

int f(int a) { return a + 100; }

#define elements(array) (sizeof(array)/sizeof(array[0]))

int main() { 
    unsigned i;
    int x[] = { 0, 1, 2, 3};
    int y[elements(x)];

    MapArray(x, y, f, elements(x));

    for (i=0; i<elements(x); i++)
        printf("%d\n", y[i]);
    return 0;
}

Take note: I'm not recommending this. This is a way to do what you're asked for, but as I said to start with, this is next to impossible to do well in C. This code works to some degree, but IMO it does not qualify as doing the job well.