实现内存复制函数

面试中面试官经常会让写程序,根据题目的难度会在算法和编程习惯上各有侧重。比如写一个memcpy函数,这个题算法简单明确,因此重点考察编程习惯、工程思想。
该题目的算法如下
0.1

  1. void  memcpy(void *dst, void *src, int count)
  2. {
  3.     while(count–)
  4.     {
  5.         *dst = *src;
  6.         dst++;
  7.         src++;
  8.     }
  9. }

问题是void*不能直接累加 *dst = *src也是不对的。
0.2

  1. void memcpy(void *dst, void *src, int count)
  2. {
  3.     unsigned char *pdst = (unsigned char *)dst;
  4.     unsigned char *psrc = (unsigned char *)src;
  5.     while(count–)
  6.     {
  7.         *pdst = *psrc;
  8.         pdst++;
  9.         psrc++;
  10.     }
  11. }

在32位系统中,可复制的最多内存是多少?类型会不会不够用?
内存复制不应该修改原始内存吧。
因此,函数声明修改如下
0.3

  1. void memcpy(void *dst, const void *src, size_t count)

这样就万事大吉了吗?
如果传入了空指针呢?
接着修改吧
0.4

  1. void memcpy(void *dst, const void *src, size_t count)
  2. {
  3.     assert(dst != NULL);
  4.     assert(src != NULL);
  5.     unsigned char *pdst = (unsigned char *)dst;
  6.     const unsigned char *psrc = (const unsigned char *)src;
  7.     while(count–)
  8.     {
  9.         *pdst = *psrc;
  10.         pdst++;
  11.         psrc++;
  12.     }
  13. }

如果有这样的数组
char ina[]={0,1,2,3,4,5,6,7,8,9,10,11};
进行如下调用
memcpy(&ina[1], &ina[0], 5);
会发生什么情况?
由于原始数据和目的数据在空间上存在重叠,这样导致复制过程中不可避免会对原始数据做修改。而这样的修改在函数的声明中是看不到的(const void *src)。如果降低要求,可以修改原始数据完成复制,那么这样的设计能实现么?因此
0.5

  1. void memcpy(void *dst, const void *src, size_t count)
  2. {
  3.     assert(dst != NULL);
  4.     assert(src != NULL);
  5.     unsigned char *pdst = (unsigned char *)dst;
  6.     const unsigned char *psrc = (const unsigned char *)src;
  7.     assert(!(psrc<=pdst && pdst<psrc+count));//判断是否有重叠
  8.     assert(!(pdst<=psrc && psrc<pdst+count));
  9.     while(count–)
  10.     {
  11.         *pdst = *psrc;
  12.         pdst++;
  13.         psrc++;
  14.     }
  15. }

到这里实现已经比较健壮了。有些人想要链式的调用函数,也就是复制完内存后,返回值直接当做其他函数的参数。

  1. void * memcpy(void *dst, const void *src, size_t count)

0.6因此最终版本为

  1. void* memcpy(void *dst, const void *src, size_t count)
  2. {
  3.     assert(dst != NULL);
  4.     assert(src != NULL);
  5.     unsigned char *pdst = (unsigned char *)dst;
  6.     const unsigned char *psrc = (const unsigned char *)src;
  7.     assert(!(psrc<=pdst && pdst<psrc+count));
  8.     assert(!(pdst<=psrc && psrc<pdst+count));
  9.     while(count–)
  10.     {
  11.         *pdst = *psrc;
  12.         pdst++;
  13.         psrc++;
  14.     }
  15.     return dst;
  16. }

最后,有网友做了性能测试,结论显示上面的实现达不到库函数的性能。个人认为库函数可能做了优化,例如使用mmx技术,使得一次复制一个字节到一次复制多个字节。

这个题目在面试出现的次数太频繁,能够比较正确的写出这个函数的能说明什么呢?
1.缺乏项目经验,对于面试因此复习的很到位。
2.有可能有丰富的项目经验,在项目中也这么做。
3.认为有较多项目经验,但是没有注意非功能性要求。等着杯具吧。

发表评论

电子邮件地址不会被公开。 必填项已用*标注