redis源碼分析 -- redis對象系統 -开发者知识库

redis源碼分析 -- redis對象系統 -开发者知识库,第1张

redis 中使用的主要數據結構有簡單動態字符串(sds)、雙向鏈表(linkedlist)、字典(dict)、壓縮列表(ziplist)、整數集合(set)等,但是 redis 並沒有直接使用這些結構,而是通過這些數據結構創建了一個對象系統,這個系統包含字符串對象、列表對象、哈希對象、集合對象和有序集合對象,而每種對象都使用了至少一種數據結構。

對象結構

/* A redis object, that is a type able to hold a string / list / set */

/* The actual Redis Object */
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount;
void *ptr;
} robj;

redis 使用對象來表示數據庫中的鍵和值,也就是說,每一個鍵值對,都至少有兩個對象,一個對象表示鍵,一個表示值。這個結構體大小 sizeof (robj) 為12,因為前三個元素是位域,共32位,4個字節可以表示。

redis 對象的結構如上所示,有五個成員:
type: 表示對象的類型,對應的是 redis 中的 TYPE 命令,在 redis 中,鍵總是一個字符串對象,而值可以是字符串對象、列表對象、哈希對象、集合對象或者有序集合對象中一種。

encoding: redis 的編碼,這個屬性,決定 ptr 指向對象的底層實現數據結構是什么數據結構。

lru: 可以理解為 last recently used,用於記錄 redis 對象最后一次被命令程序訪問的時間信息,可以用於計算數據庫鍵的空轉時長,即當前時間減去 lru 就是空轉時長, redis 可以將空轉時長大的鍵值對優先刪除。

refcount: 對象的引用計數,redis 舒勇引用計數器的方法對對象進行管理,如果該值為0,就釋放當前對象。

ptr: 對象指向的值,該值的數據結構由 encoding 編碼決定。

對象的類型 (TYPE)

對象的 TYPE 屬性記錄了對象的類型。在 redis 客戶端中,當使用 TYPE 命令查看某個鍵的類型時,服務器會根據對象的類型返回相應的值。
redis源碼分析 -- redis對象系統 -开发者知识库,type command,第2张
那代碼中, TYPE 命令有幾個值呢

/* Object types */
#define REDIS_STRING 0 /* 字符串對象,返回 "string" */
#define REDIS_LIST 1 /* 列表對象,返回 "list" */
#define REDIS_SET 2 /* 集合對象,返回 "set" */
#define REDIS_ZSET 3 /* 有序集合對象,返回 "zset" */
#define REDIS_HASH 4 /* 哈希對象,返回 "hash" */

上面列出了對象的所有類型

對象的編碼(encoding)

encoding 屬性決定了對象的 ptr 指向的底層數據結構的實現,也就是說這個對象使用了什么數據結構作為底層實現。 redis 中的宏常量為

/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object. */
#define REDIS_ENCODING_RAW 0 /* Raw representation */
#define REDIS_ENCODING_INT 1 /* Encoded as integer */
#define REDIS_ENCODING_HT 2 /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6 /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8 /* Embedded sds string encoding */

每種類型的對象都至少使用了兩種不同的編碼。其中,字符串編碼有 REDIS_ENCODING_RAWREDIS_ENCODING_EMBSTR 兩種,前者是普通的 sds 字符串對象,但是當字符串長度不超過39時, redis 為了節約內存,使用的是后面的字符串編碼方式。

在 redis 中,可以通過使用 OBJECT ENCODING 命令來查看鍵的編碼方式

/* results of "object encoding" command */
char *strEncoding(int encoding) {
switch(encoding) {
case REDIS_ENCODING_RAW: return "raw";
case REDIS_ENCODING_INT: return "int";
case REDIS_ENCODING_HT: return "hashtable";
case REDIS_ENCODING_LINKEDLIST: return "linkedlist";
case REDIS_ENCODING_ZIPLIST: return "ziplist";
case REDIS_ENCODING_INTSET: return "intset";
case REDIS_ENCODING_SKIPLIST: return "skiplist";
case REDIS_ENCODING_EMBSTR: return "embstr";
default: return "unknown";
}
}

strEncoding 函數返回了 OBJECT ENCODING 命令時的結果。

通過 encoding 屬性來設定對象所使用的編碼,而不是為特定類型的對象關聯一種固定的編碼,極大的提升了 redis 的靈活性和效率。 redis 可以根據不同的使用場景來為對象設置不同的編碼,從而可以優化對象在某一場景下的效率。因為列表的編碼之間是可以轉換的(不是任意轉換)。比如:
當哈希對象所保存的元素比較少時,redis 使用壓縮列表作為哈希對象的底層實現:

  • 壓縮列表比字典哈希更節約內存(字典通過拉鏈表解決沖突,一部分是通過單鏈表實現的),且在內存中是以連續塊的方式保存的,可以更快的加載到緩存中;
  • 隨着哈希對象元素的不斷增加,使用壓縮列表的方式保存元素的優勢逐逐漸消失時,對象就將底層實現從壓縮列表轉向功能更強、更合適的字典哈希上。

其他類型的對象也會使用多種不同的編碼來進行類似的優化。

redis中不同的對象

redis 中根據不同數據類型創建不同的對象,設置對象的類型,編碼和ptr 指針,同時,將引用計數器 refcount 的值設置為1

字符串對象

字符串對象的類型 TYPEREDIS_STRING,而編碼可以為 int (REDIS_ENCODING_INT)、 raw (REDIS_ENCODING_RAW)和 embstr (REDIS_ENCODING_EMBSTR)。

robj *createObject(int type, void *ptr) {
robj *o = zmalloc(sizeof(*o)); // sizeof (robj) is 12 bytes
o->type = type;
o->encoding = REDIS_ENCODING_RAW;
o->ptr = ptr;
o->refcount = 1;

/* Set the LRU to the current lruclock (minutes resolution). */
o->lru = LRU_CLOCK();
return o;
}

createObject 函數就是創建一個字符串對象。如果對象保存的是一個字符串的值,同時這個字符串的長度大於39,那么對象將通過一個簡單動態字符串(SDS)來保存這個值,並將編碼設置為 raw。

/* Create a string object with encoding REDIS_ENCODING_RAW, that is a plain
* string object where o->ptr points to a proper sds string. */
robj *createRawStringObject(char *ptr, size_t len) {
return createObject(REDIS_STRING,sdsnewlen(ptr,len));
}

其結構如下所示:
redis源碼分析 -- redis對象系統 -开发者知识库,sds object,第3张
當對象保存的值是整數時,將字符串的編碼設置為REDIS_ENCODING_INT,同時將整數值保存在字符串對象結構的 ptr 里面

robj *createStringObjectFromLongLong(long long value) {
robj *o;
if (value >= 0 && value < REDIS_SHARED_INTEGERS) {
incrRefCount(shared.integers[value]); // 引用計數器,如果整數在 0 - 10000范圍內,不需要再創建對象,只需要將對應的引用計數器加1,后面在詳細討論
o = shared.integers[value];
} else {
if (value >= LONG_MIN && value <= LONG_MAX)
o = createObject(REDIS_STRING, NULL);
o->encoding = REDIS_ENCODING_INT;
o->ptr = (void*)((long)value); //轉成 void*
} else { // 超出范圍,將數字轉成字符串存儲
o = createObject(REDIS_STRING,sdsfromlonglong(value)); //convert long long to string
}
}
return o;
}

如果對象保存的是字符串,且字符串的長度小於39時, redis 為了節約內存,使用另一種字符串的存儲方式 embstr,創建字符串對象。

embstr 編碼是專門用於保存短字符串的一種優化編碼結構,這種編碼與 raw 一樣,都是用 redisObject 結構和 sdshdr 結構來表示字符串對象,但是 raw 編碼在通過調用 createRawStringObject 函數時,需要調用兩次內存分配,先通過 sdsnew 創建 sds ,然后在通過 createObject 創建字符串對象 redisObject,而 embstr 編碼只需要一次內存分配。

/* Create a string object with encoding REDIS_ENCODING_EMBSTR, that is
* an object where the sds string is actually an unmodifiable string
* allocated in the same chunk as the object itself. */
robj *createEmbeddedStringObject(char *ptr, size_t len) {
robj *o = zmalloc(sizeof(robj) sizeof(struct sdshdr) len 1);
struct sdshdr *sh = (void*)(o 1); //申請的是連續空間,sh指向了sdshdr,跳過了robj

o->type = REDIS_STRING;
o->encoding = REDIS_ENCODING_EMBSTR;
o->ptr = sh 1; // sdshdr 中 buf 是可變長數組,sizeof (sdshdr) is 8 bytes,此時,ptr 剛好指向的就是 buf,申請的連續內存,后面對buf賦值
o->refcount = 1;
o->lru = LRU_CLOCK();

sh->len = len;
sh->free = 0;
if (ptr) {
memcpy(sh->buf,ptr,len);
sh->buf[len] = '\0';
} else {
memset(sh->buf,0,len 1);
}
return o;
}

embstr 編碼通過一次內存分配申請一塊連續的內存空間,包括 redisObject 和 sdshdr

robj *o = zmalloc(sizeof(robj) sizeof(struct sdshdr) len 1);

然后獲取 sdshdr 在這個連續空間出的位置

struct sdshdr *sh = (void*)(o 1);

TYPE 設置為 REDIS_STRINGencoding 設置為 REDIS_ENCODING_EMBSTR,因為是連續的內存塊,通過 sdshdr 結構體的說明可知, sizeof (sdshdr) 的大小為8,成員 buf 是可變長數組,是不能通過sizeof 計算長度的,所以獲取 sdshdr 的地址 sh 后,往后便宜 sizeof (sdshdr) 的大小就是 buf 字符串的值。

o->ptr = sh 1;

其結構如下所示
redis源碼分析 -- redis對象系統 -开发者知识库,embstr object,第4张

使用 embstr 編碼保存字符串的優點:

  • embstr 創建字符串對象時比 raw 編碼創建對象少分進行一次內存分配
  • 釋放時,同樣,embstr 只需釋放一次,raw 需要釋放兩次
  • embstr 編碼將字符串對象保存在一塊連續的內存空間中,它比 raw 編碼的字符串能夠更快的加載到緩存,能夠更好的利用緩存帶來的優勢。

long double 類型的浮點數,在 redis 中也是作為字符串的值來保存的。

/* Create a string object from a long double. If humanfriendly is non-zero
* it does not use exponential format and trims trailing zeroes at the end,
* however this results in loss of precision. Otherwise exp format is used
* and the output of snprintf() is not modified.
*
* The 'humanfriendly' option is used for INCRBYFLOAT and HINCRBYFLOAT. */
robj *createStringObjectFromLongDouble(long double value, int humanfriendly) {
char buf[256];
int len;

if (isinf(value)) {
/* Libc in odd systems (Hi Solaris!) will format infinite in a
* different way, so better to handle it in an explicit way. */
if (value > 0) {
memcpy(buf,"inf",3);
len = 3;
} else {
memcpy(buf,"-inf",4);
len = 4;
}
} else if (humanfriendly) {
/* We use 17 digits precision since with 128 bit floats that precision
* after rounding is able to represent most small decimal numbers in a
* way that is "non surprising" for the user (that is, most small
* decimal numbers will be represented in a way that when converted
* back into a string are exactly the same as what the user typed.) */
len = snprintf(buf,sizeof(buf),"%.17Lf", value);
/* Now remove trailing zeroes after the '.' */
if (strchr(buf,'.') != NULL) {
char *p = buf len-1;
while(*p == '0') {
p--;
len--;
}
if (*p == '.') len--;
}
} else {
len = snprintf(buf,sizeof(buf),"%.17Lg", value); //將浮點數轉變成字符串,保留17位小數
}
return createStringObject(buf,len);
}

將浮點數通過 snprintf 的方法轉成字符串,保留17為小數,如果需要可讀性好,將小數點后的最后一個非0數字后的0全部去掉,但是這樣會降低精度。

如果需要對保存到 redis 中的浮點數進行操作,比如加上或者減去某個值, redis 會先將字符串轉成浮點數,計算后再轉成字符串保存在 redis 中

int getLongDoubleFromObject(robj *o, long double *target) {
long double value;
char *eptr;

if (o == NULL) {
value = 0;
} else {
redisAssertWithInfo(NULL,o,o->type == REDIS_STRING);
if (sdsEncodedObject(o)) {
errno = 0;
value = strtold(o->ptr, &eptr); // convert string to long double
if (isspace(((char*)o->ptr)[0]) || eptr[0] != '\0' ||
errno == ERANGE || isnan(value))
return REDIS_ERR;
} else if (o->encoding == REDIS_ENCODING_INT) {
value = (long)o->ptr;
} else {
redisPanic("Unknown string encoding");
}
}
*target = value;
return REDIS_OK;
}

編碼的轉換

字符串對象中,int 編碼和 embstr 編碼在一定條件下可以轉換成 raw 編碼。

對於 int 編碼對象,如果在 redis 中,對該對象進行操作,比如 append 一個字符串,是的該對象的值不在保存的是整數值,而是字符串時,該對象的編碼將變成的 raw (REDIS_ENCODING_RAW)

對與 embstr 編碼對象,因為 redis 沒有為 embstr 編碼的字符串編寫任何相應的修改程序(只有 int 編碼和 raw 編碼的字符串對象才有),所以 embstr 編碼的字符串對象實際上是只讀的。當需要修改 embstr 編碼的對象時, redis 首先將該對象的編碼從 embstr 轉換成 raw,然后再進行修改。所以,embstr 編碼的字符串對象,在修改之后,總是編程 raw 編碼的字符串對象。

其他對象

下面分別是創建雙向鏈表對象、壓縮列表對象、集合對象、整數集合對象、有序集合對象、哈希對象和有序集合壓縮列表對象。后續在深入分析這些代碼時,在分別對這些對象的結構、編碼轉換等做詳細的分析。

robj *createListObject(void) {
list *l = listCreate();
robj *o = createObject(REDIS_LIST,l);
listSetFreeMethod(l,decrRefCountVoid);
o->encoding = REDIS_ENCODING_LINKEDLIST;
return o;
}

robj *createZiplistObject(void) {
unsigned char *zl = ziplistNew();
robj *o = createObject(REDIS_LIST,zl);
o->encoding = REDIS_ENCODING_ZIPLIST;
return o;
}

robj *createSetObject(void) {
dict *d = dictCreate(&setDictType,NULL);
robj *o = createObject(REDIS_SET,d);
o->encoding = REDIS_ENCODING_HT;
return o;
}

robj *createIntsetObject(void) {
intset *is = intsetNew();
robj *o = createObject(REDIS_SET,is);
o->encoding = REDIS_ENCODING_INTSET;
return o;
}

robj *createHashObject(void) {
unsigned char *zl = ziplistNew();
robj *o = createObject(REDIS_HASH, zl);
o->encoding = REDIS_ENCODING_ZIPLIST;
return o;
}

robj *createZsetObject(void) {
zset *zs = zmalloc(sizeof(*zs));
robj *o;

zs->dict = dictCreate(&zsetDictType,NULL);
zs->zsl = zslCreate();
o = createObject(REDIS_ZSET,zs);
o->encoding = REDIS_ENCODING_SKIPLIST;
return o;
}

robj *createZsetZiplistObject(void) {
unsigned char *zl = ziplistNew();
robj *o = createObject(REDIS_ZSET,zl);
o->encoding = REDIS_ENCODING_ZIPLIST;
return o;
}

類型檢查

redis 中用於操作鍵的命令可分為兩種,一種可以對任何類型的鍵進行操作,比如 DEL、EXPIRE、RENAME、TYPE、OBJECT 等,另一種只能對特定類型的鍵執行,比如 SET、GET、APPEND、STRLEN 只能對字符串鍵執行,而 RPUSH、HSET、HGET、HLEN 只能對列表鍵執行,如果用 SET 對列表鍵執行,redis 將返回一個錯誤。

為了確保指定的鍵能夠執行某些特定的命令,redis 在執行命令前會先檢查輸入鍵的類型是否正確,然后再決定是否執行給定的命令。

int checkType(redisClient *c, robj *o, int type) {
if (o->type != type) {
addReply(c,shared.wrongtypeerr); //wrong_type_err
return 1;
}
return 0;
}

通過 redisObject 的 TYPE 屬性來判斷類型是否正確:

  • 在執行一個特定的命令之前,服務器會先檢查輸入數據庫鍵的值對象是否為執行命令所需的類型,如果是,才會執行指定的命令
  • 否則,服務器將拒絕執行命令,並返回一個錯誤

多態命令的實現

redis 除了根據對象的 TYPE 屬性判斷鍵能否執行指定的命令之外,還需要根據編碼屬性 encoding 來選擇正確的命令實現代碼執行命令(因為通常一種對象因為優化的原因可以有不同的編碼方式)。

比如列表對象,可以有 linkedlist(REDIS_ENCODING_LINEDLIST) 和 ziplist(REDIS_ENCODING_ZIPLIST) 兩個編碼方式,但是,在執行 LLEN 命令時,redis 除了需要判斷 TYPE 是否是 REDIS_LIST 外,還需要根據編碼判斷是 linkedlist 還是 ziplist,然后才能使用雙向鏈表的 API 還是 ziplist 的 API 執行相應的函數獲取長度。

void llenCommand(redisClient *c) {
robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.czero);
if (o == NULL || checkType(c,o,REDIS_LIST)) return;
addReplyLongLong(c,listTypeLength(o));
}

unsigned long listTypeLength(robj *subject) {
if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
return ziplistLen(subject->ptr);
} else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
return listLength((list*)subject->ptr);
} else {
redisPanic("Unknown list encoding");
}
}

上面兩個函數展示了 LLEN 的求取過程。

借用面向對象的術語,我們可以認為 LLEN 命令是多態的,只要執行 LLEN,不管對象的編碼方式是 linkedlist 還是 ziplist ,都可以得到列表對象的長度。
(就像 the pragmatic programmer 中所說,思想的“異花授粉”(cross-pollination),當你熟悉面向對象時,可以使用不同的方式編寫純c,加入面向對象的思想)。

而相對於特征類型的特定命令,DEL、EXPIRE、TYPE、OBJECT等這些命令可以同時處理多種不同類型的鍵,前者是基於編碼的多態,后者是基於類型的多態。

內存技術器 refcount

C語言沒有內存回收功能,所以 redis 在自己的對象系統中,構建了一個內存計數器 (reference counting) 技術實現內存回收功能。通過這一機制,程序可以通過跟蹤對象的引用計數信息,當 refcount 為 0 時釋放對象回收內存。

在 redisObject 對象中有一個 refcount 屬性,該屬性記錄的就是對象的引用計數信息。對象的引用計數信息會隨着對象的狀態變化而不斷變化。

  • 創建新對象時,引用計數器設置為1
  • 當對象被新程序使用時,引用計數值加1 (incrRefCount)
  • 當對象不再被新程序使用時,引用計數減1 (decrRefCount)
  • 當對象的引用計數為0時,釋放對象

void decrRefCount(robj *o) {
if (o->refcount <= 0) redisPanic("decrRefCount against refcount <= 0");
if (o->refcount == 1) {
switch(o->type) {
case REDIS_STRING: freeStringObject(o); break;
case REDIS_LIST: freeListObject(o); break;
case REDIS_SET: freeSetObject(o); break;
case REDIS_ZSET: freeZsetObject(o); break;
case REDIS_HASH: freeHashObject(o); break;
default: redisPanic("Unknown object type"); break;
}
zfree(o);
} else {
o->refcount--;
}
}

對象共享

不知道大家還記不記得,上面的字符串對象中,當編碼方式為int (REDIS_ENCODING_INT)時,對象的創建函數 createStringObjectFromLongLong,當整數值在 0 - 10000的范圍內時,不會新創建一個字符串對象,而是將 shared 這個共享對象中的 intergers 這個 redisObject 對象數組中對應的元素添加一個指向該元素的引用,同時將該元素的引用計數加1。

shared 是一個全局變量,用於共享

* Our shared "common" objects */

struct sharedObjectsStruct shared;

createSharedObject 函數中創建和初始化,其中,對 intergers 數組初始化如下

for (j = 0; j < REDIS_SHARED_INTEGERS; j  ) {
shared.integers[j] = createObject(REDIS_STRING,(void*)(long)j);
shared.integers[j]->encoding = REDIS_ENCODING_INT;
}

其中,REDIS_SHARED_INTEGERS 這個常量為 10000,可以通過修改這個值,來改變共享整數對象的范圍。

redis 的引用計數機制,實現的共享對象的方法,能夠極大的節約內存,所引用的對象,出了引用計數進行了加1之外,其他屬性都沒有發生改變。數據庫中保存的相同值對象越多,就越能節約內存。

在 redis 中,不僅只有字符串對象能夠使用這些共享對象,在數據結構中嵌套了字符串對象的其他對象,都可以使用這些共享對象(redis 中目前只能嵌套字符串對象)。

在 redis 中,考慮到時間復雜度和CPU時間的限制,只共享保存整數值的字符串對象,這是因為,在決定共享對象能夠被其他對象直接使用時,redis 需要保證共享對象與目標對象時完全相同的,只有保存整數值的字符串對象才是最簡單的,復雜度最低,而保存的值越復雜,驗證共享對象和目標對象是否相同所需的復雜度就越高,消耗CPU的時間就越多。

對象的空轉時長

redisObject 中 lru 屬性,記錄的就是對象的訪問時間信息,根據該信息就能夠計算出對象的空轉時長。

OBJECT IDLETIME 命令可以打印兌現的空轉時長,這是通過將當前時間減去鍵的值對象的 lru 的時間計算得出的。

/* Given an object returns the min number of milliseconds the object was never
* requested, using an approximated LRU algorithm. */
unsigned long long estimateObjectIdleTime(robj *o) {
unsigned long long lruclock = LRU_CLOCK();
if (lruclock >= o->lru) {
return (lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
} else {
return (lruclock (REDIS_LRU_CLOCK_MAX - o->lru)) *
REDIS_LRU_CLOCK_RESOLUTION;
}
}

OBJECT IDLTTIME 這個命令不會改變對象的 lru 屬性,像 GET、SET等命令都會改變對象的 lru 屬性

鍵的空轉時長還有另外一個作用,就是如果服務器打開了 maxmemory 選項,並且服務器的回收內存算法為 volatile-lru 或者 allkeys-lru,那么當服務器的內存數超過 maxmemory 時,空轉時長較高的那部分鍵會被服務器優先釋放,回收內存。


其他

OBJECT的命令實現

OBJECT 的三種命令

/* Object command allows to inspect the internals of an Redis Object.
* Usage: OBJECT <refcount|encoding|idletime> <key> */
void objectCommand(redisClient *c) {
robj *o;

if (!strcasecmp(c->argv[1]->ptr,"refcount") && c->argc == 3) {
if ((o = objectCommandLookupOrReply(c,c->argv[2],shared.nullbulk))
== NULL) return;
addReplyLongLong(c,o->refcount);
} else if (!strcasecmp(c->argv[1]->ptr,"encoding") && c->argc == 3) {
if ((o = objectCommandLookupOrReply(c,c->argv[2],shared.nullbulk))
== NULL) return;
addReplyBulkCString(c,strEncoding(o->encoding));
} else if (!strcasecmp(c->argv[1]->ptr,"idletime") && c->argc == 3) {
if ((o = objectCommandLookupOrReply(c,c->argv[2],shared.nullbulk))
== NULL) return;
addReplyLongLong(c,estimateObjectIdleTime(o)/1000);
} else {
addReplyError(c,"Syntax error. Try OBJECT (refcount|encoding|idletime)");
}
}

redis中將字符串轉與long long的巧妙轉換

/* Convert a long long into a string. Returns the number of
* characters needed to represent the number.
* If the buffer is not big enough to store the string, 0 is returned.
*
* Based on the following article (that apparently does not provide a
* novel approach but only publicizes an already used technique):
*
* https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920
*
* Modified in order to handle signed integers since the original code was
* designed for unsigned integers. */
int ll2string(char* dst, size_t dstlen, long long svalue) {
static const char digits[201] =
"0001020304050607080910111213141516171819"
"2021222324252627282930313233343536373839"
"4041424344454647484950515253545556575859"
"6061626364656667686970717273747576777879"
"8081828384858687888990919293949596979899";
/* digits 數組保存的是0-99這100個數字的字符串數組,每一個數字由兩個字符組成 */
int negative;
unsigned long long value;

/* The main loop works with 64bit unsigned integers for simplicity, so
* we convert the number here and remember if it is negative. */
if (svalue < 0) {
if (svalue != LLONG_MIN) {
value = -svalue;
} else {
value = ((unsigned long long) LLONG_MAX) 1;
}
negative = 1;
} else {
value = svalue;
negative = 0;
}

/* Check length. */
uint32_t const length = digits10(value) negative;
if (length >= dstlen) return 0;

/* Null term. */
uint32_t next = length;
dst[next] = '\0';
next--;

/* 每次取100的模數,相當於取最后兩位數字,在 digits 數組中查找,因為數組中記錄的就是0-99的數字,對應的下標是數字*2 */
while (value >= 100) {
int const i = (value % 100) * 2;
value /= 100;
dst[next] = digits[i 1];
dst[next - 1] = digits[i];
next -= 2;
}

/* Handle last 1-2 digits. */
if (value < 10) {
dst[next] = '0' (uint32_t) value;
} else {
int i = (uint32_t) value * 2;
dst[next] = digits[i 1];
dst[next - 1] = digits[i];
}

/* Add sign. */
if (negative) dst[0] = '-';
return length;
}

在上述算法中,通過使用一個字符串數組,數組中保存的是0-99數字的字符串,每一個數字由兩個字符組成,一共200個字符,包括結尾的 NULL TERM字符,一共是201的長度。求某個數字的字符串形式,每次對數字對100取模,得到的是最后兩位數字,0-99的范圍內,根據數字在數組中查找,直接獲取這個0-99范圍內的模數的字符串形式,保存到對應的結果中,循環,就能得到 long long 數字的字符串形式了。

/* Convert a string into a long long. Returns 1 if the string could be parsed
* into a (non-overflowing) long long, 0 otherwise. The value will be set to
* the parsed value when appropriate. */
int string2ll(const char *s, size_t slen, long long *value) {
const char *p = s;
size_t plen = 0;
int negative = 0;
unsigned long long v;

if (plen == slen)
return 0;

/* Special case: first and only digit is 0. */
if (slen == 1 && p[0] == '0') {
if (value != NULL) *value = 0;
return 1;
}

if (p[0] == '-') {
negative = 1;
p ; plen ;

/* Abort on only a negative sign. */
if (plen == slen)
return 0;
}

/* First digit should be 1-9, otherwise the string should just be 0. */
if (p[0] >= '1' && p[0] <= '9') {
v = p[0]-'0';
p ; plen ;
} else if (p[0] == '0' && slen == 1) {
*value = 0;
return 1;
} else {
return 0;
}

while (plen < slen && p[0] >= '0' && p[0] <= '9') {
if (v > (ULLONG_MAX / 10)) /* Overflow. */
return 0;
v *= 10;

if (v > (ULLONG_MAX - (p[0]-'0'))) /* Overflow. */
return 0;
v = p[0]-'0';

p ; plen ;
}

/* Return if not all bytes were used. */
/* non digit exist */
if (plen < slen)
return 0;

if (negative) {
if (v > ((unsigned long long)(-(LLONG_MIN 1)) 1)) /* Overflow. */
return 0;
if (value != NULL) *value = -v;
} else {
if (v > LLONG_MAX) /* Overflow. */
return 0;
if (value != NULL) *value = v;
}
return 1;
}

參考文獻:
Redis 設計與實現,黃健宏著。

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复