redisソース解析(一)動的文字列sds構造体
30414 ワード
1.概要
Redisは、ANSI C言語を使用してオープンソースで作成され、BSDプロトコルを遵守し、ネットワークをサポートし、メモリベースで持続可能なログ型、Key-Valueデータベースであり、複数の言語のAPIを提供しています.値(value)は、文字列(String)、ハッシュ(Map)、リスト(list)、セット(sets)、およびシーケンスセット(sorted sets)などのタイプであることができるため、通常、データ構造サーバと呼ばれる.
このライブラリコードは優美で、実現が巧みで、学習に値するため、本編から最新バージョン4.0.11 redisのソースコード実現を学習する.このすべては、最も基礎的なデータ構造sdsから始まります.
2.sds構造
動的文字列sdsの実現は主にsdsである.cとsds.hでは、ヘッダファイルは主に構造体といくつかの基本関数を実現し、ソースファイルには動的文字列に必要な関数が定義される.基本機能はC++STLのvector動的配列と類似している.
次にsds構造体を見てみましょう.sds自体はchar*の別名にすぎず、ソースコードでは以下のように定義されています.
typedef char *sds;
は、sds動的文字列の長さに応じて、異なるsdshdr構造体を定義し、sdsに対応する情報と最後のbuf(フレキシブル配列を使用して可変長)を格納する.
/*
* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings.
*/
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
ここで主な違いはlenとallocが採用しているタイプの長さが異なることであり、この2つの変数はそれぞれ現在のbufの長さと割り当てられたメモリサイズを表している.flagsは、現在どのタイプのsdshdrが使用されているかを表すために使用されます.
3.sds基本関数
次はsdsを見てみましょう.hで与えられた基本関数.まず、2つのマクロ定義を理解する必要があります.ソースコードは次のとおりです.
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
この2つのマクロ定義を見ていると、少し見覚えがあるのではないでしょうか.原理とcontainer_ofは同じですが、詳細はこちらを参考にしてください.コア思想は,構造体が仮想メモリに連続したアドレス空間(スタック)に格納され,オフセット量計算によりsdsに基づいてsdshdrのヘッダアドレスや他の構造体内変数のアドレスを取得し,それらの値を得ることができる.SDS_HDRはsdshdrのヘッダアドレスを返し、SDS_HDR_VARはsdshdrポインタshを確立し,shに値を付与した.
この2つのマクロ定義を理解すると、以下の関数は簡単です.例えば、sdslen()関数はSDS_です.HDRは、構造体ポインタを取得してlenの値を読み出す.
/* sdshdr , container_of */
static inline size_t sdslen(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}
sdsavial()関数はalloc-lenの値、すなわち現在の残りの空き領域を返します.
/*s sdshdr */
static inline size_t sdsavail(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5: {
return 0;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
return sh->alloc - sh->len;
}
}
return 0;
}
関数sdssetlen()sdshdrの新しい長さを設定する
/* */
static inline void sdssetlen(sds s, size_t newlen) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
{
unsigned char *fp = ((unsigned char*)s)-1;
*fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
}
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->len = newlen;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->len = newlen;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->len = newlen;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->len = newlen;
break;
}
}
ジルコニウム関数sdsinclen()は既存のlenに基づいてincを増加させる
/* Len */
static inline void sdsinclen(sds s, size_t inc) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
{
unsigned char *fp = ((unsigned char*)s)-1;
unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
*fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
}
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->len += inc;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->len += inc;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->len += inc;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->len += inc;
break;
}
}
関数sdsalloc()は、sdshdr割り当ての空間サイズ、すなわちalloc値を返します.
/* alloc +
* sdsalloc() = sdsavail() + sdslen()
*/
static inline size_t sdsalloc(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->alloc;
case SDS_TYPE_16:
return SDS_HDR(16,s)->alloc;
case SDS_TYPE_32:
return SDS_HDR(32,s)->alloc;
case SDS_TYPE_64:
return SDS_HDR(64,s)->alloc;
}
return 0;
}
関数sdssetalloc()sdshdrに新しいalloc値を設定する
/* alloc*/
static inline void sdssetalloc(sds s, size_t newlen) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
/* Nothing to do, this type has no total allocation info. */
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->alloc = newlen;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->alloc = newlen;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->alloc = newlen;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->alloc = newlen;
break;
}
}
4.まとめ
本文はsds動的文字列の構造体と最も基本的ないくつかの操作関数を紹介し,次の文章では「動的」を実現する機能関数をさらに分析する.