Redisソースプロファイル-チェーンリスト

Redisのもう一つの基礎となるデータ構造はチェーンテーブルであり,Cにはチェーンテーブル構造が内蔵されていないため,Redis自身がリストを実現した.
チェーンテーブルキーに加えて、パブリケーションとサブスクリプション、スロークエリー、モニタなどの機能もチェーンテーブルに使用され、Redisサーバ自体はチェーンテーブルを使用して複数のクライアントの状態情報を保存し、チェーンテーブルを使用してクライアント出力バッファを構築します.
List構造
両端チェーンテーブルのノードは次のように定義されます.

typedef struct listNode {
    struct listNode *prev; //        
    struct listNode *next;  //        
    void *value;   //    
} listNode;

チェーンテーブル反復器の定義は次のとおりです.

typedef struct listIter {  //      
    listNode *next;   //        
    int direction;    //       
} listIter;

反復器の方向タグについては、定義されたグローバル変数をタグに使用します.

/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1

両端のリストは次のように定義されます.

//       
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;

チェーンテーブル操作
チェーンテーブルの初期化

/* Create a new list. The created list can be freed with
 * AlFreeList(), but private value of every node need to be freed
 * by the user before to call AlFreeList().
 *
 * On error, NULL is returned. Otherwise the pointer to the new list. */
list *listCreate(void)
{
    struct list *list;  //       
    //     ，      ，  NULL
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    //        
    list->head = list->tail = NULL;
    //      
    list->len = 0;
    //     、    、        NULL
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

チェーンテーブルクリア

/* Remove all the elements from the list without destroying the list itself. */
void listEmpty(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    //         
    while(len--) {
        next = current->next;
        //            ，         
        if (list->free) list->free(current->value);
        zfree(current);
        current = next;
    }
    //            
    list->head = list->tail = NULL;
    list->len = 0;
}

チェーンテーブルヘッダ挿入ノード

list *listAddNodeHead(list *list, void *value)
{
    listNode *node;  //       

    if ((node = zmalloc(sizeof(*node))) == NULL)  //      ，      NULL
        return NULL;
    //  value     
    node->value = value;
    if (list->len == 0) {
        //         ，        ，          
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        //   ，          
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    //      1
    list->len++;
    return list;
}

任意の位置にノードを挿入

list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;  //     

    if ((node = zmalloc(sizeof(*node))) == NULL) //    ，    NULL
        return NULL;
    node->value = value;
    if (after) {
        //    after  ，      old_node  ；  old_node   ，  tail  
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        //   ，      old_node  ，   old_node   ，  head  
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) {
            list->head = node;
        }
    }
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    list->len++;
    return list;
}

チェーンテーブルの末尾にノードを挿入する関数も提供され、同様の操作である.
ノード解放関数

void listDelNode(list *list, listNode *node)
{
    if (node->prev)
        //          ，  head  ，       next  
        node->prev->next = node->next;
    else
        //   ， head  ，  head    
        list->head = node->next;
    if (node->next)
        //          ，  tail  ，       prev  
        node->next->prev = node->prev;
    else
        //   ， tail  ，  tail    
        list->tail = node->prev;
    //      free  ，     free    
    if (list->free) list->free(node->value);
    zfree(node);
    list->len--;
}

チェーンテーブルの反復を取得

listIter *listGetIterator(list *list, int direction)
{
    listIter *iter; //        

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;  //     ，    NULL
    if (direction == AL_START_HEAD)
        //       ，    next  head
        iter->next = list->head;
    else
        //   ，     ，    next  tail
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

反復器の次のノードを取得

listNode *listNext(listIter *iter)
{
    listNode *current = iter->next; //       next         

    if (current != NULL) {
        //         ，  next   
        if (iter->direction == AL_START_HEAD)
            iter->next = current->next;
        else
            iter->next = current->prev;
    }
    return current;
}

チェーンテーブルのコピー

list *listDup(list *orig)
{
    list *copy;  //        
    listIter iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)
        return NULL;
    //          
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    //          
    listRewind(orig, &iter);
    while((node = listNext(&iter)) != NULL) {
        void *value;
        //             ，       
        if (copy->dup) {
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);
                return NULL;
            }
        } else
            //   ，       
            value = node->value;
        //            
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            return NULL;
        }
    }
    return copy;
}

チェーンテーブル回転
実は尾の結び目を取って頭に置くのです

/* Rotate the list removing the tail node and inserting it to the head. */
void listRotate(list *list) {
    listNode *tail = list->tail;  //      

    if (listLength(list) <= 1) return; //         ，         

    /* Detach current tail */
    list->tail = tail->prev;  //    tail    tail       ，   next  
    list->tail->next = NULL;
    /* Move it as head */
    list->head->prev = tail;  //              ，    head        
    tail->prev = NULL;
    tail->next = list->head;
    list->head = tail;
}