Fog Creek Software
Discussion Board




memmove() implementation.

This is also one of the questions that most interviewers ask. How is memmove() implemented (copy from Src to Dst when the memory of Src and Dst overlap).

I have come up with this.

-----------------------------------------------------------------------
void mymove(char **from, char **to, int size)
{
  int i,diff;

  if(*from==*to)
  {
    printf("\n\nNothing to copy!\n");
  }
  else if(*from>*to)
  {
    diff=*from-*to;
    for(i=diff;i<=size+diff-1;i++)
    {
      (*to)[i-diff] = (*from)[(i-diff)];
    }
  }
  else
  {
    diff=*to-*from;
    for(i=size+diff-1;i>=diff;i--)
    {
      (*to)[(i-diff)] = (*from)[(i-diff)];
    }
  }
}

-----------------------------------------------------------------------

The "diff" thing is actually added to see if the memories dont overlap in the first place. Thats checked by if(diff>size) in an enhanced version of this function (code not mentioned above).

Now, does this implementation depends on whether the machine is Little Endian or Big Endian? Any more optimizations that can be done? Any loop holes?

Srirang Bhushan
Monday, February 14, 2005

All "**" thing is wrong. Your prototype should be mymove(void *from, void *to, size_t count);

It doesn't matter if it's little of big endian.

OnlyOne
Monday, February 14, 2005

Ah! sorry. Yes, "**" should be "*". Copy-Paste error.

Srirang Bhushan
Monday, February 14, 2005

I believe it's pretty good C question if you put it like this: "I'm implementing memmove() and here is a code I come up with. Could you look at it and say if it's ok and if there is some room for improvement".

Interviewers also like to ask candidates to rate themselves from 1 to 10 (not that they always have specific criteria for each level). I don't rate myself high in C (have not done it in years), so here is my err... guess:

A good candidate with say 3-4 in C can fix original code to have OnlyOne's signature - something like
--------------------------------------
void mymemmove(void *from, void *to, size_t size)
{
  size_t i;

  if(from == to)
  {
    // Nothing to copy!
  }
  else if(from > to)
  {
    for(i = 0; i < size; i++) to[i] = from[i];
  }
  else
  {
    for(i = size-1; i >= 0; i--) to[i] = from[i];
  }
}
--------------------------------------
To make sure candidate is ok you can ask him/her why original signature was wrong, why we should not use printf from this function etc.

Candidate around 5-6 would probably further get rid of indexes and will be able to explain what is performance difference. From 7-9 you can expect a discussion of why and how this function can have processor-specific implementations, why we may want to copy memory in blocks etc.

something like this.

DK
Tuesday, February 15, 2005

It looks to me like either of those examples will break if the two memory areas overlap, and size is large enough to include some of the overlap.

Can someone tell me what I'm missing here?

Brendon
Tuesday, February 22, 2005

@DK

Yes we may move those in blocks from dest to src. I was thinking we cud typecast char* to int* and move them. But do you see any memory alignment problem here? Any Endian issues?

Thanks

Anonymous and I dont know why
Wednesday, March 16, 2005

Brendon,
this code is moving bytes one at a time and the whole point of the "if"s and "else"s is to prevent writing on bytes we will read later.

Anonymous,
Depending on the processor and/or memory management chip, casting to int's could pose problems (and not only because of alignment). This is where it is important to know the underlying hardware when you want to optimize. Plus the code gets more complicated as you start to add code that will move the first and last bytes of the zones to handle alignment. And when you start this way, it may be a good idea to check that your processor and/or system doesn't provide some kind of BITBLT function (and/or) DMA move.

BTW, "endianity" is rarely a problem when moving blocks because you tend to always write in the same order than you read :)

Tom Bouton
Friday, March 25, 2005

there is a verison of memMove that i implemented.

void memMove(char *dest, char *src, size_t n)
{
    assert(n => 0);
    assert((dest != NULL) && (src != NULL));

    /* No need to do that thing. */
    if (dest == src)
        return;

    /* Check for destructive overlap.  */
    if (src < dest && dest < src + n) {
        /* Destructive overlap ... have to copy backwards.  */
        src += n;
        dest += n;
        while (n-- > 0)
            *--dest = *--src;
    } else {
        /* Do an ascending copy.  */
        while (n-- > 0)
            *dest++ = *src++;
    }
}

matthew chen
Tuesday, March 29, 2005

i dont understand why are we incrementing the src with n times with destination, when the dest is inbetween src and src + n;

I think we will loose the src completely...

hafeez
Wednesday, May 04, 2005

*  Recent Topics

*  Fog Creek Home