Redis的Adlist实现了数据结构中的双端链表，整个结构例如以下：

链表节点定义：

typedef struct listNode {

    struct listNode *prev;

    struct listNode *next;

    void *value;

} listNode;

链表定义：

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;

当中的三个函数指针先不用管，后面遇到了再看详细是干什么的，另外还实现了一个迭代器，有点c++的味道在里面

typedef struct listIter {

    listNode *next;

    int direction;

} listIter;

链表三要素。创建，插入，和删除

list *listCreate(void)

{

    struct list *list;

    if ((list = malloc(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 = malloc(sizeof(*node))) == NULL)

        return NULL;

    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;

    }

    list->len++;

    return 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);

        free(current);

        current = next;

    }

    free(list);

}

迭代器的创建，以后能够效仿这样的做法，迭代器分方向：

/* Returns a list iterator 'iter'. After the initialization every

 * call to listNext() will return the next element of the list.

 *

 * This function can't fail. */

listIter *listGetIterator(list *list, int direction)

{

    listIter *iter;

    if ((iter = malloc(sizeof(*iter))) == NULL) return NULL;

    if (direction == AL_START_HEAD)

        iter->next = list->head;

    else

        iter->next = list->tail;

    iter->direction = direction;

    return iter;

}

版权声明：本文博客原创文章。博客，未经同意，不得转载。