Redisソースのプロファイリング-adlistの実装

adlist adlistはRedis基本データ構造の1つであり、双方向チェーンテーブルであり、チェーンテーブル長を記録し、adlistの反復器で反復ノードと方向を記録し、個人的にはSTLより優れたlistを実現すると考えられる
いくつかの重要な構造
adlist実装は比較的簡素で、基本的にチェーンテーブル関連のコードを書くとすぐにすべての実装関数を書くことができます.

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

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

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

基本関数の概要
関数＃カンスウ＃
機能
複雑さ
listCreate
チェーンテーブルの作成
O(1)
listRelease
リリース
O(N)
listInsertNode
ノードの挿入
O(1)
listDelNode
ノードの削除
O(1)
listSearchKey
ノードの検索
O(N)
listGetIterator
反復の取得
O(1)
…
…
…
他のマクロ/関数の実装は簡単です.紹介しない
listCreate

//            
list *listCreate(void) {
    struct list *list;

    //     
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;

    //      
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;

    return list;
}

listRelease

//          List
void listRelease(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;
    }

    //       
    zfree(list);
}

listInsertNode

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

    //      
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;

    //    
    node->value = value;

    //              
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        //           
        if (list->tail == old_node) {
            list->tail = node;
        }
    //              
    } else {
        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;
}

listDelNode

//     
void listDelNode(list *list, listNode *node) {
    //          
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;

    //          
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;

    //    
    if (list->free) list->free(node->value);

    //     
    zfree(node);

    //      
    list->len--;
}

listSearchKey

//     Key     ，        
listNode *listSearchKey(list *list, void *key) {
    listIter *iter;
    listNode *node;

    //       
    iter = listGetIterator(list, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {

        //   
        if (list->match) {
            if (list->match(node->value, key)) {
                listReleaseIterator(iter);
                //   
                return node;
            }
        } else {
            if (key == node->value) {
                listReleaseIterator(iter);
                //   
                return node;
            }
        }
    }

    listReleaseIterator(iter);

    //    
    return NULL;
}

listGetIterator

//          
listIter *listGetIterator(list *list, int direction) {
    //         
    listIter *iter;
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;

    //       ，          
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;

    //       
    iter->direction = direction;

    return iter;
}

小結adlistの実装は比較的簡単で、STLのlistに比べて複雑性はかなり小さいが、基本的な機能はすべてある.STLは統合ソートなどの機能を提供し、adlistはチェーンテーブルの長さを記録し、O(1)で長さを得ることができる.