redis下位データ構造のadlist

最近、redisのソースコードでredisを学びたいです.普段の仕事ではあまり使われていませんが、redisに興味があります.結局、性能はいいです.redisはオープンソースのプロジェクトで、ソースコードを通じてredisを理解することができます.私は后で自分の学习を通じて、redisのソースコードについての招待状を书きます.投稿の主な内容は、ソースコードを詳細に説明することなく、コード設計を分析することです.間違ったところがあれば、指摘してください.ソースコードはreids 3.0.3バージョンです.
adlist
一、adlist、二重チェーンリスト
データ構造の定義は次のとおりです.

//  
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
//   
typedef struct listIter {
    listNode *next;
    int direction;//     
} listIter;
//  
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);//    
    void (*free)(void *ptr);//    
    int (*match)(void *ptr, void *key);//    
    unsigned long len;
} list;

一般的な双方向チェーンテーブルとはあまり違いません.redisの双方向チェーンテーブルは比較的汎用的なチェーンテーブルに設計されているため、valueはポインタであり、valueの実際のタイプに限らず、チェーンテーブルに複製、破棄、マッチングのための関数を提供し、チェーンテーブルのvalueが異なるメモリ管理方法をサポートしたり、コールバックを行ったりすることができる.
また、チェーンテーブルの反復器は通常ランダム反復器ではなく、1つの要素だけが1つの要素でジャンプする反復器も提供されています.これは双方向チェーンテーブルであるため,反復器は前方にジャンプしたり後方にジャンプしたりすることができるが,redisは後方にジャンプする関数のみを提供する.反復器は、directionフィールドで方向を指定する必要がある順方向、逆方向もサポートします.Directionと組み合わせて反復器の前方ジャンプも実現できるので、adlistは前方ジャンプの関数を提供していないのではないでしょうか.
二、adlistの関連操作関数
主に2種類あります.1種類はマクロで、1種類は関数で、コードを見るのは簡単です.ここではコードを詳しく説明しません.関数を簡単に列挙するだけです.

/* Prototypes */
list *listCreate(void);//    
void listRelease(list *list);//    
list *listAddNodeHead(list *list, void *value);//       
list *listAddNodeTail(list *list, void *value);//       
list *listInsertNode(list *list, listNode *old_node, void *value, int after); //       
void listDelNode(list *list, listNode *node);//    
listIter *listGetIterator(list *list, int direction);//   
listNode *listNext(listIter *iter);//      ，   
void listReleaseIterator(listIter *iter);//     
list *listDup(list *orig);//    
listNode *listSearchKey(list *list, void *key);//  
listNode *listIndex(list *list, long index);//         
void listRewind(list *list, listIter *li);//       ，     
void listRewindTail(list *list, listIter *li);//      ，     
void listRotate(list *list);//    ，         

三、adlist提供オブジェクトのメモリ管理
ここでadlistがdup,freeを介してメモリ管理を行う方法について説明します.
注意すべき点は3つあります.
a.要素を挿入すると、nodeのvalueは直接パラメータのvalueに割り当てられ、dup関数は呼び出されません.
b.listDupでdup関数が存在する場合、dup関数を呼び出してvalueをコピーします.
c.listDelNodeおよびlistReleaseでは、free関数が存在する場合、freeメソッドによってvalueを破棄します.
上記の3つの点から、主に対象メモリの申請と破棄に関する管理を行う簡単なメモリ管理方法を実現することができます.簡単な使い方をご紹介します.
1)adlistは申請と破棄の責任を負わない
次のコード(コードがコンパイルテストに合格しなかった場合、エラーが発生する可能性があります)

char s[] = “hello world”;
list *lst = listCreate();
//list free，dup    
listAddNodeTail(lst, &s[0]);
listAddNodeTail(lst, &s[1]);
listAddNodeTail(lst, &s[2]);
listAddNodeTail(lst, &s[3]);

//do some thing with lst
list *lst2 = listDup(lst);
//do some thing with lst2

listRelease(lst);
listRelease(lst2);

上記の例では、adlistはvalueメモリ領域の申請と破棄を担当せず、呼び出し元によって完全に管理されています.この場合、valueで指定した要素の生存サイクルはadlistよりも長いことが要求されます.そうしないと、adlistのvalue指定は失効する可能性があります.
2)adlistは動的申請と破棄を担当する
次のコードのように、(コードがコンパイルテストに合格しなかった場合、エラーが発生する可能性があります):

void addStringToListHead(list *lst, char *s)
{
    char *snew = (char*)malloc(strlen(s)+1);
    assert(snew);
    strcpy(snew,s);
    listAddNodeHead(list,snew);
}
void *stringDup(void *s)
{
    char *sorg = (char*)s;
    char *snew = (char*)malloc(strlen(sorg)+1);
    assert(snew);
    strcpy(snew,sorg);
    return snew;    
}
void *stringFree(void *s)
{
    if (s) free(s);
}
int stringMatch(void *s1, void *s2)
{
    if (s1 && s2) return strcmp((char*)s1,(char*)s2) == 0 ? 1 : 0;
    if (!s1 && !s2) return 1;
    return 0;
}

list *lst = listCreate();
listSetDupMethod(lst, stringDup);
listSetFreeMethod(lst, stringFree);
listSetMatchMethod(lst, stringMatch);
addStringToListHead(lst,”hello”);
addStringToListHead(lst,”world”);

// do something
list *lst2 = listDup(lst);
// do something

listRelease(lst);
listRelease(lst2);

上記の例で動的に生成された空間をadlistに挿入すると、完全にadlistが管理を担当し、呼び出し元が動的空間のポインタを長期にわたって保持したり削除したりしてはならない.そうしないと、管理が混乱する.adlistのdup関数は、レプリケーション時に深くレプリケーションする必要があります.そうしないと、1つの動的申請の空間が2つのポインタで長期にわたって保存され、1つのポインタがfreeされると、もう1つのポインタが失効し、再アクセスまたはfree失効ポインタがエラーになります.
3)reference countingを友好的にサポートできなかった
reference countingをうまくサポートできなかったのは、要素を挿入するときに参照カウントを増やすために関連関数が呼び出されなかったためです.リストのコピー時にdupにより参照カウントプラス1を実現し,ノードの削除時にfreeにより参照カウントマイナス1を行う.しかし、要素を挿入する際にdupを呼び出さなかったり、他の関数を行って参照カウントを1加算したりしたため、valueはポインタを持っており、adlistはreference countingを友好的にサポートできません.ただし、これは、挿入前に参照カウンタに1を加算し、挿入に失敗した場合は参照カウントを1減算するなど、他の方法でサポートできます.
四、メモリの破片が発生しやすい.
valueはともかく、nodeだけ見ます.要素を挿入したりチェーンテーブルをコピーしたりするときにadlistがノード空間を申請する必要があり、ノードを削除するときに空間を解放する必要があることがわかります.挿入と削除を繰り返す場合、すべてのzmalloc、zfree関数がメモリ管理ポリシーをうまく行わなければ、コンテンツの断片化が容易になります.
五、まとめ
メモリ管理に呼び出し元をカスタマイズする方法が提供されているほか、adlistは一般的な双方向チェーンテーブルとあまり変わらないが、前述したように特徴的で、ここでは説明しない.