Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implementing a generical 'map' function over arrays in C

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?

like image 912
Lasirc Avatar asked Oct 28 '10 21:10

Lasirc


1 Answers

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.

like image 63
Puppy Avatar answered Sep 30 '22 22:09

Puppy