面試中經(jīng)常考察memcpy和memmov的實現(xiàn)，百度一搜早歇，有很多篇文章莉恼，但遺憾的是，很多都是有問題的报强，并且互相抄來抄去瞒御，一起出錯钾腺。
面試官通過考察memcpy的實現(xiàn)泥耀，可以考察應聘者對以下知識點的掌握：
- 內(nèi)存對齊的理解
- 內(nèi)存存取粒度與效率的關(guān)系
- 內(nèi)存重疊的問題(memory overlap)
基本實現(xiàn)
#include <stdio.h>
void *memcpy(void *dst, void const *src, size_t size)
{
assert((dst != NULL) && (src != NULL));
unsigned char *pdst = (char*)dst;
unsigned char const *psrc = src;
while(size--)
{
*pdst++ = *psrc++;
}
return dst;
}
基本實現(xiàn)很簡單饺汹，assert斷言的添加可以告訴面試官，我們是有邊界條件的控制意識的痰催。盡管許多官方的實現(xiàn)要求程序員自己去注意NULL指針的情況兜辞。但我們是在面試，不是嘛夸溶！
進一步完善
進一步完善弦疮，考慮內(nèi)存重疊的情況。
首先來一個錯誤示范蜘醋，網(wǎng)上很多都是這樣實現(xiàn)的。
#include <stdio.h>
void *memcpy(void *dst, const void *src, size_t size)
{
assert((dst != NULL) && (src != NULL));
unsigned char *pdst = dst;
const unsigned char *psrc = src;
if(psrc < pdst)
{
psrc = psrc + size - 1;
pdst = pdst + size - 1;
while(size--) //自后向前
{
*pdst-- = *psrc--;
}
}
else
{
while(size--) //自前向后
{
*pdst++ = *psrc++;
}
}
return dst;
}
通過這段代碼可以看到咏尝，應聘者是意識到內(nèi)存重疊的情況压语，并試圖解決的。但實際上编检，這段代碼有一個不算致命的錯誤：psrc < pdst
錯誤就在于這兩個指針的比較胎食，C語言 the Standard, 6.5.9 規(guī)定：如果兩個指針都指向同一個數(shù)組中的元素，那么它們之間可以執(zhí)行<允懂、<=厕怜、>和>=等關(guān)系運算。兩個不相關(guān)的指針執(zhí)行關(guān)系運算蕾总，其結(jié)果是未定義的粥航。
然而，這段代碼又是可以正常工作的生百，因為無論psrc < pdst結(jié)果是什么递雀，都達到了不破壞內(nèi)存的目的。
因此蚀浆，作為一個無需太嚴謹?shù)某绦騿T缀程，可以去這樣實現(xiàn)。但如果去參與開發(fā)libc庫的實現(xiàn)市俊，就不能這么寫了杨凑，這也許就是官方庫實現(xiàn)中沒有去檢查內(nèi)存重疊的原因。
就算允許內(nèi)存重疊情況存在的memmove函數(shù)摆昧，也沒有去判斷是否有內(nèi)存重疊撩满，而是把源操作數(shù)復制到一個臨時位置，這個臨時位置不會與源或目標操作數(shù)重疊，再把它從這個臨時位置復制到目標操作數(shù)鹦牛。
其可能的實現(xiàn)大致是這樣的：
void *memmove(void *dst, const void *src, size_t size)
{
unsigned char temp[size];
memcpy(temp, src, size);
memcpy(dst, temp, size);
return dst;
}
再進一步完善：存取效率與內(nèi)存對齊
面試官可能進一步考察內(nèi)存存取方面的知識搞糕。比如這位在Stack Overflow上的提問：Implementing own memcpy (size in bytes?)
我看了glibc-2.28中memcpy的實現(xiàn)，比較復雜曼追。但可以看出考慮內(nèi)存存取的優(yōu)化：
void *
memcpy (void *dstpp, const void *srcpp, size_t len)
{
unsigned long int dstp = (long int) dstpp;
unsigned long int srcp = (long int) srcpp;
/* Copy from the beginning to the end. */
/* If there not too few bytes to copy, use word copy. */
if (len >= OP_T_THRES)
{
/* Copy just a few bytes to make DSTP aligned. */
len -= (-dstp) % OPSIZ;
BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
/* Copy whole pages from SRCP to DSTP by virtual address manipulation,
as much as possible. */
PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
/* Copy from SRCP to DSTP taking advantage of the known alignment of
DSTP. Number of bytes remaining is put in the third argument,
i.e. in LEN. This number may vary from machine to machine. */
WORD_COPY_FWD (dstp, srcp, len, len);
/* Fall out and copy the tail. */
}
/* There are just a few bytes to copy. Use byte memory operations. */
BYTE_COPY_FWD (dstp, srcp, len);
return dstpp;
}
下面看另一個庫實現(xiàn)版本窍仰，這個比較容易理解。但是是網(wǎng)友提供的礼殊，不知道來源于哪個庫：
00018 void *memcpy(void *dst, const void *src, size_t len)
00019 {
00020 size_t i;
00021
00022 /*
00023 * memcpy does not support overlapping buffers, so always do it
00024 * forwards. (Don't change this without adjusting memmove.)
00025 *
00026 * For speedy copying, optimize the common case where both pointers
00027 * and the length are word-aligned, and copy word-at-a-time instead
00028 * of byte-at-a-time. Otherwise, copy by bytes.
00029 *
00030 * The alignment logic below should be portable. We rely on
00031 * the compiler to be reasonably intelligent about optimizing
00032 * the divides and modulos out. Fortunately, it is.
00033 */
00034
00035 if ((uintptr_t)dst % sizeof(long) == 0 &&
00036 (uintptr_t)src % sizeof(long) == 0 &&
00037 len % sizeof(long) == 0) {
00038
00039 long *d = dst;
00040 const long *s = src;
00041
00042 for (i=0; i<len/sizeof(long); i++) {
00043 d[i] = s[i];
00044 }
00045 }
00046 else {
00047 char *d = dst;
00048 const char *s = src;
00049
00050 for (i=0; i<len; i++) {
00051 d[i] = s[i];
00052 }
00053 }
00054
00055 return dst;
00056 }
35~36行驹吮，判斷dst與src是否以內(nèi)存對齊方式存儲的，對齊值為sizeof(long)晶伦。
37行碟狞，判斷需要讀取的字節(jié)數(shù)是否是sizeof(long)的整數(shù)倍。
如果以上兩個條件都滿足婚陪，以sizeof(long)字節(jié)為單位進行內(nèi)存存取族沃。這樣效率比單字節(jié)存取效率高的多。
46~53行泌参，是上述條件不滿足的情況下脆淹，執(zhí)行單字節(jié)存取。
內(nèi)存對齊沽一、內(nèi)存存取粒度與效率的關(guān)系盖溺，可見我的博文：內(nèi)存對齊相關(guān)問題的簡要總結(jié)
根據(jù)上面的代碼再進一步優(yōu)化，比如當前是四字節(jié)對齊铣缠，那么將需要復制的字節(jié)數(shù)n拆為兩部分烘嘱，一部分是四字節(jié)的整數(shù)倍(n/4)，一部分不足四字節(jié)(n%4)蝗蛙。
當dst與src都按照四字節(jié)對齊時蝇庭，前者按照四字節(jié)存取，后者按照單字節(jié)存取歼郭。否則遗契，都按照單字節(jié)存取。代碼如下：
#include <stdio.h>
//假設內(nèi)存存取粒度是align = sizeof(unsigned int)字節(jié)
void *mymemcpy(void *dst, void const *src, size_t n)
{
size_t div = n / sizeof(unsigned int); //有多少個align字節(jié)
size_t rem = n % sizeof(unsigned int); //不足align字節(jié)的部分
unsigned char *pdst = dst;
unsigned char const *psrc = src;
if((unsigned int)dst % sizeof(unsigned int) == 0 && // 是否align字節(jié)對齊
(unsigned int)src % sizeof(unsigned int) == 0 )
{
for(size_t i = 0; i < div; ++i)
{
*((unsigned int *)pdst) = *((unsigned int*)psrc);//align字節(jié)存取
pdst += sizeof(unsigned int); //按align字節(jié)移動單字節(jié)指針病曾。
psrc += sizeof(unsigned int);
}
for(size_t i = 0; i < rem; ++i) //單字節(jié)存取
*pdst++ = *psrc++;
}
else
{
for(size_t i = 0; i < n; ++i) //單字節(jié)存取
{
*pdst++ = *psrc++;
}
}
return dst;
}
以上總結(jié)牍蜂，如有錯誤或不足，歡迎指正泰涂。
