神刀安全网

Yedis源码解析之itoa实现

写在最前

Yedis 是一款高性能的nosql数据库,旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问 这里 ,Python客户端请点击 这里

提出问题

如何用C/C++实现正确的、可移植的、高效的、对所有整数都work的itoa函数?

原型如下

int itoa(char *buffer, int64_t value);

将value转为字符串后存在buffer中,返回字符串的长度。

分析问题

这还不容易么?很容易写出这样的代码:

int itoa(char *buffer, int64_t value) {   char *p = buffer;   int64_t tmp = value;   do {     *p = tmp % 10 + '0';     tmp /= 10;     ++p;   } while(tmp);   if (value < 0) {     *p++ = '-';   }   std::reverse(buffer, p);   return p - buffer; } 

这个实现,有什么问题?

问题出在第6、7行。

举个例子,请问,-9/4结果是多少?

因为 -9 = (-2) * 4 + (-1) 因此结果为-2,同时 -9 % 4 = -1

但是!

因为 -9 =(-3)* 4 + 3 因此结果为-3,同时 -9 % 4 = 3

哪个结果是对的?

C++98和C++03标准并没有对被除数和除数不都为正数时的情形进行明确的说明,语言只保证:

如果 a = br + q

那么 a / b = ra % b = q

因此,当a和b都是正数时,语言保证结果是正的;否则,结果是实现相关的。

因此第6、7行的结果是未定义的,是很不可移植的。

有些人说,这还不容易吗?把负数都搞成正数,用它的绝对值来计算,不就行了吗?于是很容易写出这样的代码:

int itoa(char *buffer, int64_t value) {   char *p = buffer;   int64_t tmp = value < 0 ? -value : value;   do {     *p = tmp % 10 + '0';     tmp /= 10;     ++p;   } while(tmp);   if (value < 0) {     *p++ = '-';   }   std::reverse(buffer, p);   return p - buffer; } 

还是有问题,注意第4行。我们知道,对于有符号整数,它的最大值和最小值是不对称的,绝对值差1。其中,64位有符号整数的范围为[-9223372036854775808, 9223372036854775807]

因此,在第4行,如果value是INT64_MIN,对它求绝对值-value的结果其实已经超出了64位有符号整数可以表示的范围,这里已经溢出了!!!

哦哦,这好办,对INT64_MIN单独处理行不行?

行,但是代码会非常不优雅了。

解决问题

Yedis中实现了itoa,代码在 src/server/yedis_order.cpp

YEDIS_MUST_INLINE int64_t int2char(char *buffer, int64_t value) {   static const char offset[19] = {'9','8','7','6','5','4','3','2','1','0','1','2','3','4','5','6','7','8','9'};   static const char *digit = offset + 9;   char *p = buffer;   int64_t tmp = value;   do {     *p = *(digit + tmp % 10);     tmp /= 10;     ++p;   } while(tmp);   if (value < 0) {     *p++ = '-';   }   std::reverse(buffer, p);   return p - buffer; } 

通过offset数组,很巧妙、很完美的解决了这个问题。它对于[INT64_MIN, INT64_MAX]中的任何一个数都是正确的。

这个实现,想法来源于Matthew Wilson大神的Efficient Integer to String Conversions文章。

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Yedis源码解析之itoa实现

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮