Redis源码阅读(二) 链表

1. 定义

• 链表结点

  通过prev指针与上一个结点相连，通过next指针与下一个结点相连，这样组成双端链表方便操作。

typedef struct listNode {
    // 前驱结点
    struct listNode *prev;
    // 后继节点
    struct listNode *next;
    // 结点内容指针
    void *value;
} listNode;

• 链表结构

  list结构为链表提供了头指针、尾指针、链表长度用于方面的对链表进行操作，还有dup、free和match用于不同类型值的操作函数。

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;

• 链表迭代器

typedef struct listIter {
    // 当前迭代器指向的结点
    listNode *next;
    
    // 迭代器方向
    int direction;
} listIter;

2. 源码剖析

• 创建链表

/**                                                                                                    
 * 创建一个空链表                                                                                      
 */                                                                                                    
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;                                                                                       
}

• 结点插入

/**                                                                                                 
 * 添加一个新结点到头部                                                                             
 */                                                                                                 
list *listAddNodeHead(list *list, void *value)                                                      
{                                                                                                   
    listNode *node;                                                                                 
                                                                                                    
    // 给新结点分配内存空间                                                                         
    if ((node = zmalloc(sizeof(*node))) == NULL)                                                    
        return NULL;                                                                                
                                                                                                    
    // 赋值                                                                                         
    node->value = value;                                                                            
                                                                                                    
    // 如果是第一个元素，则head，tail都指向该结点                                                   
    if (list->len == 0) {                                                                           
        list->head = list->tail = node;                                                             
        node->prev = node->next = NULL;                                                             
    } else {                                                                                        
        // 新结点成为头结点，prev为空，next为之前的头结点                                                                                                                                        
        node->prev = NULL;                                                                          
        node->next = list->head;                                                                    
        list->head->prev = node;                                                                    
        list->head = node;                                                                          
    }                                                                                               
    list->len++;                                                                                    
    return list;                                                                                    
}

/**                                                                                                 
 * 添加一个新结点到尾部                                                                             
 */                                                                                                 
list *listAddNodeTail(list *list, void *value)                                                      
{                                                                                                   
    listNode *node;                                                                                 
                                                                                                    
    // 分配结点内存                                                                                 
    if ((node = zmalloc(sizeof(*node))) == NULL)                                                    
        return NULL;                                                                                
    // 赋值                                                                                         
    node->value = value;                                                                            
                                                                                                    
    // 如果是第一个结点，则head，tail都指向该结点                                                   
    if (list->len == 0) {                                                                           
        list->head = list->tail = node;                                                             
        node->prev = node->next = NULL;                                                             
    } else {                                                                                        
        // 新结点成为尾结点，prev为之前尾结点，next为NULL                                           
        node->prev = list->tail;                                                                    
        node->next = NULL;                                                                          
        list->tail->next = node;                                                                    
        list->tail = node;                                                                                                                                                                                
    }                                                                                               
    list->len++;                                                                                    
    return list;                                                                                    
} 

/**                                                                                                 
 * 在链表指定结点位置添加一个新结点                                                                 
 */                                                                                                 
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {                      
    listNode *node;                                                                                 
                                                                                                    
    // 新结点分配内存空间                                                                           
    if ((node = zmalloc(sizeof(*node))) == NULL)                                                    
        return NULL;                                                                                
    // 赋值                                                                                         
    node->value = value;                                                                            
                                                                                                    
    // after表示插入在该结点之后                                                                    
    if (after) {                                                                                    
        // 新结点prev指向插入结点                                                                   
        node->prev = old_node;                                                                      
        // 新结点next指向插入结点的next                                                             
        node->next = old_node->next;                                                                
                                                                                                    
        // 如果插入位置是tail，则tail指向新结点                                                     
        if (list->tail == old_node) {                                                               
            list->tail = node;                                                                      
        }                                                                                           
    } else { // 添加在指定结点之前                                                                  
                                                                                                    
        // 新结点的next指向插入结点                                                                 
        node->next = old_node;                                                                      
        // 新结点的prev指向插入结点的prev                                                           
        node->prev = old_node->prev;                                                                
        // 如果插入位置是head，则head指向新结点                                                     
        if (list->head == old_node) {                                                               
            list->head = node;                                                                      
        }                                                                                           
    }                                                                                               
    // 新结点前驱结点的next指向新结点                                                               
    if (node->prev != NULL) {                                                                       
        node->prev->next = node;                                                                    
    }                                                                                               
    // 新结点的后继结点prev指向新结点                                                               
    if (node->next != NULL) {                                                                       
        node->next->prev = node;                                                                    
    }                                                                                               
    list->len++;                                                                                    
    return list;                                                                                    
}

• 结点删除

/**                                                                                                 
 * 删除链表中的结点, 并释放内存空间                                                                 
 */                                                                                                 
void listDelNode(list *list, listNode *node)                                                        
{                                                                                                   
    if (node->prev) // 删除的不是头结点                                                             
        // 删除结点的前驱next直接指向删除结点的后继                                                 
        node->prev->next = node->next;                                                              
    else // 删除的是头结点                                                                          
        // 更换头结点为删除结点的后继                                                               
        list->head = node->next;                                                                    
                                                                                                    
    if (node->next) // 删除的不是尾结点                                                             
        // 删除结点的后继prev直接指向删除结点的前驱                                                 
        node->next->prev = node->prev;                                                              
    else // 删除的是尾结点                                                                          
        // 更换尾结点为删除结点的前驱                                                               
        list->tail = node->prev;                                                                    
                                                                                                    
    // 释放删除结点的value                                                                          
    if (list->free) list->free(node->value);                                                        
    // 释放删除结点本身                                                                             
    zfree(node);                                                                                    
                                                                                                    
    // 链表长度-1                                                                                   
    list->len--;                                                                                                                                                                                          
}

• 迭代器

/**                                                                                                 
 * 获取链表迭代器，调用listNext()可以获取下一个元素                                                 
 */                                                                                                 
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;                                                                                    
}

/**                                                                                                 
 * 获取迭代器指向的结点                                                                             
 */                                                                                                 
listNode *listNext(listIter *iter)                                                                  
{                                                                                                   
    listNode *current = iter->next;                                                                 
                                                                                                    
    if (current != NULL) {                                                                          
        if (iter->direction == AL_START_HEAD)                                                       
            iter->next = current->next;                                                             
        else                                                                                        
            iter->next = current->prev;                                                             
    }                                                                                               
    return current;                                                                                 
} 

/**                                                                                                 
 * 查找链表中指定key的结点                                                                          
 */                                                                                                 
listNode *listSearchKey(list *list, void *key)                                                      
{                                                                                                   
    listIter iter;                                                                                  
    listNode *node;                                                                                 
                                                                                                    
    // 从头部开始遍历，寻找key的结点                                                                
    listRewind(list, &iter);                                                                        
    while((node = listNext(&iter)) != NULL) {                                                       
        if (list->match) {                                                                          
            if (list->match(node->value, key)) {                                                    
                return node;                                                                        
            }                                                                                       
        } else {                                                                                    
            if (key == node->value) {                                                               
                return node;                                                                        
            }                                                                                       
        }                                                                                           
    }                                                                                               
    return NULL;                                                                                    
}