Chinaunix

标题: g-bios标准string库实现 [打印本页]

作者: syukayo 时间: 2009-11-30 14:25
标题: g-bios标准string库实现
针对g-bios标准库中的string库函数的实现，及其注意事项，心得体会进行讨论。

这里先来说一下我对strcpy(), strncpy()两个函数的体会。

char *strcpy(char *dest, const char *src)
{
char *pdst = dest;

#if 1 // 参考代码
while (*pdst = *src)
{
pdst++;
src++;
}

#else // 我的代码
while (*src)
{
*pdst++ = *src++;
}

*pdst = '\0';
#endif

return dest;
}
strcpy()是个库函数，实现字符串的拷贝。由于会被频繁调用，因此代码精简度要求高。函数内部实现不需要参数校验，由调用者保证参数的正确传递。这个函数调用者需确保目标空间大于或等于源空间。传入的两个参数中，src源设置为const只读，确保在函数内源数据不被修改。
接下来是代码精简。比较我写的代码与参考代码，我觉得while (*pdst = *src) 比我的while (*src)要好的多。前者既赋了值，又完成了条件判断，相当精简。

char *strncpy(char *dst, const char *src, size_t count)
{
char *pdst = dst;

#if 0　　　//　修改前代码
size_t n = 0;

while (n < count && *src != '\0')
{
*pdst++ = *src++;
n++;
}

while (n < count)
{
*pdst++ = '\0';
n++;
}
#else　　　　　　　　　　　//　修改后代码
while ((count > 0) && (*pdst = *src))
{
pdst++;
src++;
count--;
}

while (count > 0)
{
*pdst++ = '\0';
count--;
}
#endif

return dst;
}
strncpy()这个库函数跟strcpy()实现相同的功能--字符串拷贝，由于第３个参数的存在，需要多方面考虑。首先调用者需要确保目的空间大于等于源空间，count小于等于目的空间大小。其次指定的拷贝字符的个数count, 如果count小于源空间大小，则完成strcpy()一样的工作，如果count大于等于源空间大小，拷贝完字符串后，还需在目的空间补上(count-字符串)个'\0'。　这里代码精简如上，后者省去了字符串个数 n的定义，由count自减完成，效率明显提高。

其他的库函数大家一起来研究下...

作者: lasting007 时间: 2009-11-30 14:54
标题: 偶来聊聊
小弟自己写了个g-bios string库。
俺的一点心得：
（１）标准string库是不会检查传入的指针的，所以使用string库时程序员要注意检查
指针的正确性;
  （２）strncpy，当目标字串的容量大于n+目标字串长度时，会在余下的位置上补‘\０’ ;
  （３）memcmp,在比较时，返回的值是int而不是long;
  （４）strchr、strrchr　传递要查找的字符时，用的数据类型是int而不是char
（５）memmove 、memcpy都可以实现内存块的拷贝，不同点在于当(源地址+n)>目标地址时memmove会拷贝仍然可以正确完成拷贝，而memcpy，则会发生内存覆盖

扩展的string库还在努力中，o(∩_∩)o...哈哈

usr_string.tar

20 KB, 下载次数: 26

作者: syukayo 时间: 2009-11-30 17:00
memcpy() 与 memmove() 这两个函数与 strcpy(),strncpy()有点类似，但区别很大。memcopy(), memmove()分两种情况：

(1) 目标地址在源地址前面的情况
  dest                src
|------------------|-------------|
                     |------------------|
                                       count

(2) 目标地址在源地址后面的情况
  src          dest
|-------------|---------------------|
|-----------------|
               count

memcpy() 在(2)的状态下会覆盖部分内存，因此采用了memmove()来弥补这一缺陷。
void *memcpy(void *pdst, const void *psrc, size_t count)
{
BYTE *iter = pdst;

while (count > 0)
{
*iter++ = *psrc++;
count--;
}

return pdst;
}
这里的count 我理解为字节数，数据拷贝以字节为单位。
void *memmove(void *pdst, const void *psrc, size_t count)
{
BYTE *pd;
BYTE *ps;

if (pdst < psrc)
{
pd = pdst;
ps = psrc;

while (count > 0)
{
*pd++ = *ps++;
count--;
}
}
else
{
pd = pdst + count;
ps = psrc + count;

while (count > 0)
{
*--pd = *--ps;
count--;
}
}

return pdst;
}
例如 a[50], dest=&a[0], src=&a[5], count=10的情况(1)
         src=&a[0], dest=&a[5], count=10的情况(2)
用memcpy()在(2)时就把dest开始部分的一段数据给覆盖了，而memmove()则完整地完成了拷贝。

[ 本帖最后由 syukayo 于 2009-11-30 20:35 编辑 ]

作者: 469412293 时间: 2009-11-30 17:50
我来说说strcmp和strncmp函数：

int strcmp(const char *s1, const char *s2)
如果s1于s2相等(包含'\0')时候返回0，否则返回*s1 - *s2.

int strncmp(const char *s1, const char *s2, int n)
如果s1,s2<=n,且s1,s2相等(包含'\0')时候返回0.
如果s1,s2前n个字符相等时候返回0.
否则返回*s1 - *s2.

作者: crosszhang 时间: 2009-11-30 19:18
memcpy() 不用顾及地址前后，怎么拷贝都不会覆盖原数据。

我认为memcpy拷贝会覆盖内存，并会把先拷贝的数据铺盖掉
  src                   dest
|------------------|---------------------|
|------------------------｜
               count
这种情况memcpy内存同样会发生错误，编译可以通过。
  1 这是我写的代码，为什么标准库中copy完了dest结尾不补零哪？
  2
  3 void *memcpy(void *dest, void *src, int count)
  4 {
  5    char *p;
  6    char *d;
  7
  8    p = src;
  9    d = dest;
10
11    while (count)
12    {
13       *d++ = *p++;
14       count--;
15    }
16
17    *d = '\0';
18
19    return dest;
20 }
~
对于memmove函数
      void *memmove(void *pdst, const void *psrc, size_t count)
{
      BYTE *pd;
      BYTE *ps;

      if (pdst < psrc)
      {
            pd = pdst;
            ps = psrc;

            while (count > 0)
            {
                     *pd++ = *ps++;                pdst                psrc
                                                      |------------------|-------------|
                                                                           |------------------------|
                                                                              count 这是（pdst < psrc）情况pdst会覆盖到psrc 但没关系memmove只是数据移动
                     count--;                         移动之后源数据破坏了也没关系
            }                                        |-----------------------|
      }
      else
      {
            pd = pdst + count;
            ps = psrc + count;　　　　　　　　　　　　 psrc          pdst
  　　　　　　　　　　　　　　　　　　　　　　　　　　　　 |-------------|---------------------|
　　　　　　　　　　　　　　　　　　　　　　　　　　　　 |-----------------|
               　　　　　　　　　　　　　　　　　　　　　　　　　  count
                                                                     |-------------------|
            while (count > 0)　　　　　　　　　　　　　　　　　　　　这种情况(pdst >= psrc)这样复制会覆盖掉一部分数据的。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 src          dest
  　　　　　　　　　　　　　　　　　　　　　　　　　　　　 |-------------|---------------------|
　　　　　　　　　　　　　　　　　　　　　　　　　　　　  　　　　　　　|------------------|
               　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 count　　　^
            {　　　　　　　　　　　　　　　　　　　　　｜-----------------｜　　　　< ---|
                     *--pd = *--ps;                                     ^
                     count--;                                     < -----|
                                                      #copy like this!  no problem!
            }
      }

      return pdst;
}

作者: forkpower 时间: 2009-11-30 21:25
关于g-bios标准库中的string库函数strrchr函数的实现，我有点疑问。
strrchr函数原型：char *strrchr(const char *psrc, size_t c);
其功能，我的理解是返回源字符串最后一个首字符与变量c匹配的字串。
我的思路是定义一个指针变量记录首字符匹配的位置，形参指针变量遍历整个源字符串，当源字符串遍历完了，定义的指针变量刚好记录了最后一个首字符匹配的地址，于是自己写了一个strrchr函数如下：
char *strrchr(const char *psrc, size_t c)
{
      const char *p = NULL;

      while (*psrc)
      {
            if(*psrc == c)
            {
                     p = psrc;
            }

            psrc++;
      }

      if(p == NULL)
      {
            return NULL;
      }
      else
      {
            return (char *)p;
      }
}
但是看了标准库strrchr函数的实现，发现strrchr函数是先遍历完源字符串，在倒着遍历找出最后那个匹配字串，我有个疑问就是如果源字符串第一个字符就是最后那个首字符与字符c，那不是来回遍历了两次，这样的话，效率上是不是有些问题。自己写的函数，遍历源字符串一次就可以了，但为什么标准库会采取这种方式实现呢，我想标准库这样实现一定是有它的道理的，经讨论，我觉得我的函数实现中当源字符串中与c匹配的字符很多的时候，我那个函数记录首字符位置的指针变量被反复赋值，导致效率上也会出现问题，也许是我的理解有误，希望高手能指点迷津！

作者: crosszhang 时间: 2009-11-30 21:44
标题: 答关于g-bios标准库中的string库函数strrchr函数的实现，我有点疑问。
strrchr()的功能是reverse反序搜索第一个与c匹配的字符。

作者: syukayo 时间: 2009-11-30 22:26
strchr 与 strrchr 的问题：
个人认为，strchr是返回所找字符在该字符串中第一次出现时的地址， strrchr是返回所找字符在该字符串中最后出现时的地址。
我的strrchr的刚开始的思路跟forkpower一样，直接找过去，找到最后一个就返回那个地址就是了。不知道哪个更有效点。

另外，forkpower的代码中
const char *p = NULL; 这里既然定义了p

if (p == NULL)
return NULL;
else
return (char *)p;
就没必要那么烦了，直接返回p不就好了。

[ 本帖最后由 syukayo 于 2009-11-30 22:28 编辑 ]

作者: syukayo 时间: 2009-11-30 22:37
cross 的memcpy

3 void *memcpy(void *dest, void *src, int count)
  4 {
  5    char *p;
  6    char *d;
  7
  8    p = src;
  9    d = dest;
10
11    while (count)
12    {
13       *d++ = *p++;
14       count--;
15    }
16
17    *d = '\0'; 这里补零干吗？个人认为内存间数据拷贝，以字节为单位，可以是任意类型的数据，不只是char型;
18
19    return dest;
20 }

作者: HELLO_MAX 时间: 2009-11-30 23:04
神勇的syukayo ，火眼金睛一下子就看出了forkpower和cross这2个小妖的问题，崇拜中。。。。。。

偶来说说，我在写string的一点感受。说明如下
例1：

char *my_strrchr(const char *psrc, int sc)
{
   const char *temp = psrc;

   while (*temp)
      temp++;

   while (temp > psrc)
{
      temp--;                      //如果temp--，放在这里，那么排除了sc为'\0'的情况，系统的strrch命令支持 strrchr = '\0' 的情况。
                                    //如果要实现这个目的，可以将 temp--；放在下面
      if (*temp == sc)
         return (char *)temp;

//    temp--;
}
}

[ 本帖最后由 HELLO_MAX 于 2009-11-30 23:31 编辑 ]

作者: HELLO_MAX 时间: 2009-11-30 23:44
继续。。。。。。

不太明白mem之类的命令，比如用memset将一个int型数组全部设为10 。。。

菜鸟ing。

作者: swangwu 时间: 2009-12-01 01:58
标题: 回复 #1 syukayo 的帖子
I have to write in English. It took me much time to have iBus work. But Chinese input method still can not work.
Last time, I did not explain the GCC pre-processing option clearly. The option is -E.
e.x.
gcc -E string-test.c -o string-test.i
The file of string-test.i has clear information about included .h files and data definition.
The option of -E is helpful for locating the compiling errors.

作者: stevenwang87061 时间: 2009-12-01 09:52
我在写MEMMOVE这个库函数的时候，只看函数的声明，我只是简单的将它认为是和MEMCPY没什么区别，写完之后我看了看源代码，我发现我少考虑了一个问题，就是当目标BUFFER的首地址比源BUFFER的首地址要大，而且目标BUFFER的首地址与源BUFFER的首地址的差值小于COUNT时，如果你不加判断的话，会把源BUFFER的后面的字节内容给覆盖掉，移动后的BUFFER内容与源BUFFER内容不相同。
怎样处理这个问题呢，我们可以把用两个指针*P1,*P2分别指向目标BUFFER的首地址和源的首地址，然后把两个指针都加上COUNT，然后执行P1--和P2--；这时候P1和P2就分别指向目标BUFFER的最后一个字节的地址和源的最后一个字节的地址，然后开始循环赋值，这样就保证了源BUFFER的最后几个字节不会被覆盖。
我依照这个思想写了一下MEMMOVE，贴出来，大家多多指正。
void *memmove(void *p1, const viod *p2, int count)
{
char *ptr1;
const char *ptr2;

ptr1 = p1; //进行了强转
ptr2 = p2;

if (ptr1 < ptr2)
{
      while (count > 0) //这中情况与MEMCPY类似
      {
         *ptr1 = *ptr2;
         ptr1++;
         ptr2++;
      }
}
else/* 这里为了简单，把目标BUFFER的首地址大于源BUFFER的首地址，但是他们之间的距离大于COUNT的这种情况也当作距离小于  */COUNT来处理。
{
      ptr1 = ptr1 + count;
      ptr2 = ptr2 + count;

      while (count > 0)
      {
         ptr1--; //这里先自减减，再赋值
         ptr2--;
         *ptr1 = *ptr2;
      }
}

return p1;
}

作者: paocaka 时间: 2009-12-01 10:35
在实现字符串连接函数strncat的时候，我参考了一下g-bios源码下面的库中的strncat，然后比较了一下，发现了一些细节问题。
我的代码是这样的：
char *my_strncat(char *dest, const char *src, usigned int count)
{
char *p = dest;

while (*p)
{
      p++;
}

while (*src && count)
{
      *p++ = *src++;
      count--;
｝

*p = '\0';

return desr;
}

g-bios 的库文件代码如下：
char *strncat(char *pdst, const char *psrc, unsigned int count)
{
char *iter;
unsigned int n = 0;

for (iter = pdst; *iter; iter++);

while (n < count && (*iter = *psrc))
{
   iter++;
   psrc++;
   n++;
}

while (n < count)
{
   *iter = '\0';
   iter++;
   n++;
}

return pdst;
}

现在分析几种情况，来对比一下我对strncat的实现以及g-bios中的实现和标准库中的strncat的实现：
首先，当要连接的字符串长度比count要长,也就是src要比count长时，函数会拷贝count个字符连接到dest后面,在自动加上且只加上一个
'\0'，这种情况，三个函数是一致的。

其次，当拷贝长度刚好等于源串长度，结果也和第一种一样。

最后，当要源串的长度小于拷贝长度时，标准库中的的只在连接完源串后补一个'\0',但是g-bios中的会在连接完源串后一直补'\0'直到到达长度count为止。我首先也和g-bios中的一样，这是受了strncpy的影响，因为strncpy是这么做的，不过后来我测试了标准库中的strncat发现无论在哪种情况下，它都只补一个'\0'.

在效率方面，我认为g-bios源码中的那个n有点多余，直接让count自减也可以完成同样的功能并且少了个变量和一条判断语句。

[ 本帖最后由 paocaka 于 2009-12-1 11:13 编辑 ]

作者: CFA8888 时间: 2009-12-01 11:25
g-bios中的strcmp与系统自带的不一样，用系统自带的函数比较两个字符串时，大于返回1，小于返回-1，而不是不相等字符之差。
以下是我的代码，请高手指点。

int my_strcmp(const char *str1, const char *str2)
{
while (*str1 == *str2)
{
      if(*str1 == '\0')
      {
         return 0;
      }

      str1++;
      str2++;
}

return *str1 - *str2 > 0 ? 1 : -1;
}

memcmp也有类似的情况，不过当count = 1，时返回的却是不相等字符之差，不知道这样做有何好处？

作者: CFA8888 时间: 2009-12-01 11:46
14楼的代码有些问题，当src的长度大于count时可能会使的dest越界，此时不能补零
while (*src && count)
{
*p++ = *src++;
count--;
｝

*p = '\0';

我认为应该改为：
while (count && (*p = *src))
{
p++;
src++;
count--;
｝
上述代码中while的两个条件（count 和 *p = *src）不能颠倒次序

作者: taoxie17 时间: 2009-12-01 13:57
对于memcpy 这个函数。它的作用是拷备内存单元，所以，仅作于原样拷备。不补任何内容。

作者: taoxie17 时间: 2009-12-01 14:04

原帖由 CFA8888 于 2009-12-1 11:46 发表
14楼的代码有些问题，当src的长度大于count时可能会使的dest越界，此时不能补零
while (*src && count)
{
*p++ = *src++;
count--;
｝

*p = '\0';

我认为应该改为：
w ...

这个问题 14楼的做法没有错。他做的工作，任然是先检查 count,然后再复拷备的。这于至于同一个while中的先后无异！

作者: 469412293 时间: 2009-12-01 15:16
14L可能有错...
首先，当要连接的字符串长度比count要长,也就是src要比count长时，函数会拷贝count个字符连接到dest后面,在自动加上且只加上一个'\0'.

g-bios中 char *strncat(char *pdst, const char *psrc, unsigned int count)函数

当要连接的字符串长度比count要长,也就是src要比count长时，函数会拷贝count个字符连接到dest后面,不会自动加上一个'\0'.

作者: sh19871122 时间: 2009-12-04 13:23
路过的不知道楼主要验证什么

作者: sniper 时间: 2009-12-06 17:35
都EFI了，还要BIOS干啥。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)