redis源码阅读之adlist

redis当中的list的话是一个双向链表，其结构如下所示

点击(此处)折叠或打开

1. typedef struct listNode {
   
2.     struct listNode *prev;
   
3.     struct listNode *next;
   
4.     void *value;
   
5. } listNode;
   
6. typedef struct list {
   
7.     listNode *head;
   
8.     listNode *tail;
   
9.     void *(*dup)(void *ptr);
   
10.     void (*free)(void *ptr);
    
11.     int (*match)(void *ptr, void *key);
    
12.     unsigned long len;
    
13. } list;

除了以上两个结构，还定义了一个类似stl当中的迭代器，用于遍历当前链表，并定义了迭代器的方向

点击(此处)折叠或打开

1. typedef struct listIter {
   
2.     listNode *next;
   
3.     int direction;
   
4. } listIter;
   
5. 
   
6. /* Directions for iterators */
   
7. #define AL_START_HEAD 0
   
8. #define AL_START_TAIL 1

然后它定义了一堆当做函数来用的宏定义。。。

点击(此处)折叠或打开

1. /* Functions implemented as macros */
   
2. #define listLength(l) ((l)->len)
   
3. #define listFirst(l) ((l)->head)
   
4. #define listLast(l) ((l)->tail)
   
5. #define listPrevNode(n) ((n)->prev)
   
6. #define listNextNode(n) ((n)->next)
   
7. #define listNodeValue(n) ((n)->value)
   
8. 
   
9. #define listSetDupMethod(l,m) ((l)->dup = (m))
   
10. #define listSetFreeMethod(l,m) ((l)->free = (m))
    
11. #define listSetMatchMethod(l,m) ((l)->match = (m))
    
12. 
    
13. #define listGetDupMethod(l) ((l)->dup)
    
14. #define listGetFree(l) ((l)->free)
    
15. #define listGetMatchMethod(l) ((l)->match)

之后的话，就是list当中的一些“常规操作了”
创建，清空，释放函数如下：

点击(此处)折叠或打开

1. list *listCreate(void)
   
2. {
   
3.     struct list *list;
   
4. 
   
5.     if ((list = zmalloc(sizeof(*list))) == NULL)
   
6.         return NULL;
   
7.     list->head = list->tail = NULL;
   
8.     list->len = 0;
   
9.     list->dup = NULL;
   
10.     list->free = NULL;
    
11.     list->match = NULL;
    
12.     return list;
    
13. }
    
14. 
    
15. /* Remove all the elements from the list without destroying the list itself. */
    
16. void listEmpty(list *list)
    
17. {
    
18.     unsigned long len;
    
19.     listNode *current, *next;
    
20. 
    
21.     current = list->head;
    
22.     len = list->len;
    
23.     while(len--) {
    
24.         next = current->next;
    
25.         if (list->free) list->free(current->value);
    
26.         zfree(current);
    
27.         current = next;
    
28.     }
    
29.     list->head = list->tail = NULL;
    
30.     list->len = 0;
    
31. }
    
32. 
    
33. /* Free the whole list.
    
34.  *
    
35.  * This function can't fail. */
    
36. void listRelease(list *list)
    
37. {
    
38.     listEmpty(list);
    
39.     zfree(list);
    
40. }

分别从头尾两端插入节点

点击(此处)折叠或打开

1. list *listAddNodeHead(list *list, void *value)
   
2. {
   
3.     listNode *node;
   
4. 
   
5.     if ((node = zmalloc(sizeof(*node))) == NULL)
   
6.         return NULL;
   
7.     node->value = value;
   
8.     if (list->len == 0) {
   
9.         list->head = list->tail = node;
   
10.         node->prev = node->next = NULL;
    
11.     } else {
    
12.         node->prev = NULL;
    
13.         node->next = list->head;
    
14.         list->head->prev = node;
    
15.         list->head = node;
    
16.     }
    
17.     list->len++;
    
18.     return list;
    
19. }
    
20. list *listAddNodeTail(list *list, void *value)
    
21. {
    
22.     listNode *node;
    
23. 
    
24.     if ((node = zmalloc(sizeof(*node))) == NULL)
    
25.         return NULL;
    
26.     node->value = value;
    
27.     if (list->len == 0) {
    
28.         list->head = list->tail = node;
    
29.         node->prev = node->next = NULL;
    
30.     } else {
    
31.         node->prev = list->tail;
    
32.         node->next = NULL;
    
33.         list->tail->next = node;
    
34.         list->tail = node;
    
35.     }
    
36.     list->len++;
    
37.     return list;
    
38. }

根据参数选择插入节点的相对位置

点击(此处)折叠或打开

1. list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
   
2.     listNode *node;
   
3. 
   
4.     if ((node = zmalloc(sizeof(*node))) == NULL)
   
5.         return NULL;
   
6.     node->value = value;
   
7.     if (after) {
   
8.         node->prev = old_node;
   
9.         node->next = old_node->next;
   
10.         if (list->tail == old_node) {
    
11.             list->tail = node;
    
12.         }
    
13.     } else {
    
14.         node->next = old_node;
    
15.         node->prev = old_node->prev;
    
16.         if (list->head == old_node) {
    
17.             list->head = node;
    
18.         }
    
19.     }
    
20.     if (node->prev != NULL) {
    
21.         node->prev->next = node;
    
22.     }
    
23.     if (node->next != NULL) {
    
24.         node->next->prev = node;
    
25.     }
    
26.     list->len++;
    
27.     return list;
    
28. }

删除节点

点击(此处)折叠或打开

1. void listDelNode(list *list, listNode *node)
   
2. {
   
3.     if (node->prev)
   
4.         node->prev->next = node->next;
   
5.     else
   
6.         list->head = node->next;
   
7.     if (node->next)
   
8.         node->next->prev = node->prev;
   
9.     else
   
10.         list->tail = node->prev;
    
11.     if (list->free) list->free(node->value);
    
12.     zfree(node);
    
13.     list->len--;
    
14. }

关于迭代器的一些基础操作

点击(此处)折叠或打开

1. listIter *listGetIterator(list *list, int direction)
   
2. {
   
3.     listIter *iter;
   
4. 
   
5.     if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
   
6.     if (direction == AL_START_HEAD)
   
7.         iter->next = list->head;
   
8.     else
   
9.         iter->next = list->tail;
   
10.     iter->direction = direction;
    
11.     return iter;
    
12. }
    
13. 
    
14. /* Release the iterator memory */
    
15. void listReleaseIterator(listIter *iter) {
    
16.     zfree(iter);
    
17. }
    
18. 
    
19. /* Create an iterator in the list private iterator structure */
    
20. void listRewind(list *list, listIter *li) {
    
21.     li->next = list->head;
    
22.     li->direction = AL_START_HEAD;
    
23. }
    
24. 
    
25. void listRewindTail(list *list, listIter *li) {
    
26.     li->next = list->tail;
    
27.     li->direction = AL_START_TAIL;
    
28. }
    
29. listNode *listNext(listIter *iter)
    
30. {
    
31.     listNode *current = iter->next;
    
32. 
    
33.     if (current != NULL) {
    
34.         if (iter->direction == AL_START_HEAD)
    
35.             iter->next = current->next;
    
36.         else
    
37.             iter->next = current->prev;
    
38.     }
    
39.     return current;
    
40. }

list的复制查找

点击(此处)折叠或打开

1. list *listDup(list *orig)
   
2. {
   
3.     list *copy;
   
4.     listIter iter;
   
5.     listNode *node;
   
6. 
   
7.     if ((copy = listCreate()) == NULL)
   
8.         return NULL;
   
9.     copy->dup = orig->dup;
   
10.     copy->free = orig->free;
    
11.     copy->match = orig->match;
    
12.     listRewind(orig, &iter);
    
13.     while((node = listNext(&iter)) != NULL) {
    
14.         void *value;
    
15. 
    
16.         if (copy->dup) {
    
17.             value = copy->dup(node->value);
    
18.             if (value == NULL) {
    
19.                 listRelease(copy);
    
20.                 return NULL;
    
21.             }
    
22.         } else
    
23.             value = node->value;
    
24.         if (listAddNodeTail(copy, value) == NULL) {
    
25.             listRelease(copy);
    
26.             return NULL;
    
27.         }
    
28.     }
    
29.     return copy;
    
30. }
    
31. listNode *listSearchKey(list *list, void *key)
    
32. {
    
33.     listIter iter;
    
34.     listNode *node;
    
35. 
    
36.     listRewind(list, &iter);
    
37.     while((node = listNext(&iter)) != NULL) {
    
38.         if (list->match) {
    
39.             if (list->match(node->value, key)) {
    
40.                 return node;
    
41.             }
    
42.         } else {
    
43.             if (key == node->value) {
    
44.                 return node;
    
45.             }
    
46.         }
    
47.     }
    
48.     return NULL;
    
49. }
    
50. listNode *listIndex(list *list, long index) {
    
51.     listNode *n;
    
52. 
    
53.     if (index < 0) {
    
54.         index = (-index)-1;
    
55.         n = list->tail;
    
56.         while(index-- && n) n = n->prev;
    
57.     } else {
    
58.         n = list->head;
    
59.         while(index-- && n) n = n->next;
    
60.     }
    
61.     return n;
    
62. }

将最后一个元素插入到列表头

点击(此处)折叠或打开

1. /* Rotate the list removing the tail node and inserting it to the head. */
   
2. void listRotate(list *list) {
   
3.     listNode *tail = list->tail;
   
4. 
   
5.     if (listLength(list) <= 1) return;
   
6. 
   
7.     /* Detach current tail */
   
8.     list->tail = tail->prev;
   
9.     list->tail->next = NULL;
   
10.     /* Move it as head */
    
11.     list->head->prev = tail;
    
12.     tail->prev = NULL;
    
13.     tail->next = list->head;
    
14.     list->head = tail;
    
15. }

合并两个列表

点击(此处)折叠或打开

1. /* Add all the elements of the list 'o' at the end of the
   
2.  * list 'l'. The list 'other' remains empty but otherwise valid. */
   
3. void listJoin(list *l, list *o) {
   
4.     if (o->head)
   
5.         o->head->prev = l->tail;
   
6. 
   
7.     if (l->tail)
   
8.         l->tail->next = o->head;
   
9.     else
   
10.         l->head = o->head;
    
11. 
    
12.     if (o->tail) l->tail = o->tail;
    
13.     l->len += o->len;
    
14. 
    
15.     /* Setup other as an empty list. */
    
16.     o->head = o->tail = NULL;
    
17.     o->len = 0;
    
18. }

总体来开，redis当中的adlist还是跟我们平素里用到的list差不多的，虽然作者有点造轮子之嫌，但是于读者而言，多读一读源代码还是好处多多的，毕竟“源码之前，了无秘密”，与诸位共勉~~~