[关闭]
@LIUHUAN 2019-03-11T14:32:49.000000Z 字数 8068 阅读 1138

redis链表源码解析

redis

数据结构

  1. // 链表节点
  2. typedef struct listNode {
  3.     struct listNode *prev; // 前驱
  4.     struct listNode *next; // 后继
  5.     void *value;  // 值
  6. } listNode;
  8. // 链表迭代器
  9. typedef struct listIter {
  10.     listNode *next; // 下一个节点
  11.     int direction; // 迭代方向
  12. } listIter;
  14. // 迭代方向
  15. #define AL_START_HEAD 0
  16. #define AL_START_TAIL 1
  19. // 链表定义
  20. typedef struct list {
  21.     listNode *head; // 链表头指针
  22.     listNode *tail; // 链表尾指针
  23.     void *(*dup)(void *ptr); // 节点值的复制函数
  24.     void (*free)(void *ptr); // 节点值的释放函数
  25.     int (*match)(void *ptr, void *key); // 节点值的匹配函数 
  26.     unsigned long len; // 链表长度
  27. } list;

相关宏定义

  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) // 获取某个节点的值
  9. #define listSetDupMethod(l,m) ((l)->dup = (m))  // 设置节点复制函数
  10. #define listSetFreeMethod(l,m) ((l)->free = (m)) // 设置节点释放函数
  11. #define listSetMatchMethod(l,m) ((l)->match = (m))// 设置节点匹配函数
  13. #define listGetDupMethod(l) ((l)->dup) // 获取节点复制函数
  14. #define listGetFree(l) ((l)->free) // 获取节点释放函数
  15. #define listGetMatchMethod(l) ((l)->match) // 获取节点匹配函数

功能函数实现

  1. /* Prototypes */
  2. list *listCreate(void);
  3. void listRelease(list *list);
  4. list *listAddNodeHead(list *list, void *value);
  5. list *listAddNodeTail(list *list, void *value);
  6. list *listInsertNode(list *list, listNode *old_node, void *value, int after);
  7. void listDelNode(list *list, listNode *node);
  8. listIter *listGetIterator(list *list, int direction);
  9. listNode *listNext(listIter *iter);
  10. void listReleaseIterator(listIter *iter);
  11. list *listDup(list *orig);
  12. listNode *listSearchKey(list *list, void *key);
  13. listNode *listIndex(list *list, long index);
  14. void listRewind(list *list, listIter *li);
  15. void listRewindTail(list *list, listIter *li);
  16. void listRotate(list *list);

- 具体实现

  1. /* Create a new list. The created list can be freed with
  2.  * AlFreeList(), but private value of every node need to be freed
  3.  * by the user before to call AlFreeList().
  4.  *
  5.  * On error, NULL is returned. Otherwise the pointer to the new list. */
  7. // 创建链表
  8. list *listCreate(void)
  9. {
  10.     struct list *list;
  11.     // 分配内存
  12.     if ((list = zmalloc(sizeof(*list))) == NULL)
  13.         return NULL;
  14.     // 初始化
  15.     list->head = list->tail = NULL;
  16.     list->len = 0;
  17.     list->dup = NULL;
  18.     list->free = NULL;
  19.     list->match = NULL;
  20.     return list;
  21. }
  23. /* Free the whole list.
  24.  *
  25.  * This function can't fail. */
  26. // 释放链表
  27. void listRelease(list *list)
  28. {
  29.     unsigned long len;
  30.     listNode *current, *next;
  32.     current = list->head;
  33.     len = list->len; // 链表长度
  34.     while(len--) {
  35.         next = current->next;
  36.         if (list->free) list->free(current->value); // 如果有值的释放函数调用
  37.         zfree(current); // 释放内存
  38.         current = next;
  39.     }
  40.     zfree(list); // 释放整个链表管理节点
  41. }
  43. /* Add a new node to the list, to head, containing the specified 'value'
  44.  * pointer as value.
  45.  *
  46.  * On error, NULL is returned and no operation is performed (i.e. the
  47.  * list remains unaltered).
  48.  * On success the 'list' pointer you pass to the function is returned. */
  49. // 头部增加节点
  50. list *listAddNodeHead(list *list, void *value)
  51. {
  52.     listNode *node;
  53.     // 为节点分配内存
  54.     if ((node = zmalloc(sizeof(*node))) == NULL)
  55.         return NULL;
  56.     node->value = value;
  57.     if (list->len == 0) { // 添加前链表为空
  58.         list->head = list->tail = node;
  59.         node->prev = node->next = NULL;
  60.     } else {// 已经存在头节点
  61.         node->prev = NULL;
  62.         node->next = list->head;
  63.         list->head->prev = node;
  64.         list->head = node;
  65.     }
  66.     list->len++; // 增加长度
  67.     return list;
  68. }
  70. /* Add a new node to the list, to tail, containing the specified 'value'
  71.  * pointer as value.
  72.  *
  73.  * On error, NULL is returned and no operation is performed (i.e. the
  74.  * list remains unaltered).
  75.  * On success the 'list' pointer you pass to the function is returned. */
  76. // 在链表尾部添加节点
  77. list *listAddNodeTail(list *list, void *value)
  78. {
  79.     listNode *node;
  81.     if ((node = zmalloc(sizeof(*node))) == NULL)
  82.         return NULL;
  83.     node->value = value;
  84.     if (list->len == 0) { // 链表为空
  85.         list->head = list->tail = node;
  86.         node->prev = node->next = NULL;
  87.     } else { // 链表非空
  88.         node->prev = list->tail;
  89.         node->next = NULL;
  90.         list->tail->next = node;
  91.         list->tail = node;
  92.     }
  93.     list->len++; // 增加长度
  94.     return list;
  95. }
  97. // 在某个节点前（后）插入节点
  98. list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
  99.     listNode *node;
  100.     // 创建插入节点
  101.     if ((node = zmalloc(sizeof(*node))) == NULL)
  102.         return NULL;
  103.     node->value = value;
  104.     if (after) {// 节点之后插入
  105.         node->prev = old_node;
  106.         node->next = old_node->next;
  107.         if (list->tail == old_node) { // 在尾部节点之后插入节点
  108.             list->tail = node;
  109.         }
  110.     } else {// 节点之前插入
  111.         node->next = old_node;
  112.         node->prev = old_node->prev;
  113.         if (list->head == old_node) {// 在头部部节点之前插入节点
  114.             list->head = node;
  115.         }
  116.     }
  117.     if (node->prev != NULL) { // 插入节点后，非头节点
  118.         node->prev->next = node;
  119.     }
  120.     if (node->next != NULL) { // 插入节点后，非尾部节点
  121.         node->next->prev = node;
  122.     }
  123.     list->len++;
  124.     return list;
  125. }
  127. /* Remove the specified node from the specified list.
  128.  * It's up to the caller to free the private value of the node.
  129.  *
  130.  * This function can't fail. */
  132. // 删除某个节点
  133. void listDelNode(list *list, listNode *node)
  134. {
  135.     if (node->prev) // 待删除节点有前驱节点
  136.         node->prev->next = node->next;
  137.     else // 删除头节点
  138.         list->head = node->next;
  139.     if (node->next)// 待删除节点有后继节点
  140.         node->next->prev = node->prev;
  141.     else // 删除尾节点
  142.         list->tail = node->prev;
  143.     if (list->free) list->free(node->value); // 释放值函数
  144.     zfree(node); 
  145.     list->len--; // 链表长度减1
  146. }
  148. /* Returns a list iterator 'iter'. After the initialization every
  149.  * call to listNext() will return the next element of the list.
  150.  *
  151.  * This function can't fail. */
  152. // 获取链表某个方向上的迭代器
  153. listIter *listGetIterator(list *list, int direction)
  154. {
  155.     listIter *iter;
  157.     if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
  158.     if (direction == AL_START_HEAD)// 头部开始的迭代器
  159.         iter->next = list->head;
  160.     else// 尾部开始的迭代器
  161.         iter->next = list->tail;
  162.     iter->direction = direction; // 迭代器方向
  163.     return iter;
  164. }
  166. /* Release the iterator memory */
  167. // 释放迭代器内存
  168. void listReleaseIterator(listIter *iter) {
  169.     zfree(iter);
  170. }
  172. /* Create an iterator in the list private iterator structure */
  173. // 关联迭代器和链表，从头部开始迭代
  174. void listRewind(list *list, listIter *li) {
  175.     li->next = list->head;
  176.     li->direction = AL_START_HEAD;
  177. }
  179. // 关联迭代器和链表，从尾部开始迭代
  180. void listRewindTail(list *list, listIter *li) {
  181.     li->next = list->tail;
  182.     li->direction = AL_START_TAIL;
  183. }
  185. /* Return the next element of an iterator.
  186.  * It's valid to remove the currently returned element using
  187.  * listDelNode(), but not to remove other elements.
  188.  *
  189.  * The function returns a pointer to the next element of the list,
  190.  * or NULL if there are no more elements, so the classical usage patter
  191.  * is:
  192.  *
  193.  * iter = listGetIterator(list,<direction>);
  194.  * while ((node = listNext(iter)) != NULL) {
  195.  *     doSomethingWith(listNodeValue(node));
  196.  * }
  197.  *
  198.  * */
  199. // 获取迭代器的下一个元素
  200. listNode *listNext(listIter *iter)
  201. {
  202.     listNode *current = iter->next;
  204.     if (current != NULL) {
  205.         if (iter->direction == AL_START_HEAD) // 后向
  206.             iter->next = current->next;
  207.         else// 前向
  208.             iter->next = current->prev;
  209.     }
  210.     return current;
  211. }
  213. /* Duplicate the whole list. On out of memory NULL is returned.
  214.  * On success a copy of the original list is returned.
  215.  *
  216.  * The 'Dup' method set with listSetDupMethod() function is used
  217.  * to copy the node value. Otherwise the same pointer value of
  218.  * the original node is used as value of the copied node.
  219.  *
  220.  * The original list both on success or error is never modified. */
  221. // 复制链表
  222. list *listDup(list *orig)
  223. {
  224.     list *copy;
  225.     listIter *iter;
  226.     listNode *node;
  228.     if ((copy = listCreate()) == NULL)
  229.         return NULL;
  230.     // 函数复制
  231.     copy->dup = orig->dup;
  232.     copy->free = orig->free;
  233.     copy->match = orig->match;
  234.     iter = listGetIterator(orig, AL_START_HEAD);
  235.     while((node = listNext(iter)) != NULL) {
  236.         void *value;
  238.         if (copy->dup) {
  239.             value = copy->dup(node->value);
  240.             if (value == NULL) { // 复制节点值失败
  241.                 listRelease(copy);
  242.                 listReleaseIterator(iter);
  243.                 return NULL;
  244.             }
  245.         } else // 没有复制函数，那么复制后的链表指向复制前的链表
  246.             value = node->value;
  247.         if (listAddNodeTail(copy, value) == NULL) { // 添加节点到尾部
  248.             listRelease(copy);
  249.             listReleaseIterator(iter);
  250.             return NULL;
  251.         }
  252.     }
  253.     listReleaseIterator(iter);
  254.     return copy;
  255. }
  257. /* Search the list for a node matching a given key.
  258.  * The match is performed using the 'match' method
  259.  * set with listSetMatchMethod(). If no 'match' method
  260.  * is set, the 'value' pointer of every node is directly
  261.  * compared with the 'key' pointer.
  262.  *
  263.  * On success the first matching node pointer is returned
  264.  * (search starts from head). If no matching node exists
  265.  * NULL is returned. */
  266. // 查找链表
  267. listNode *listSearchKey(list *list, void *key)
  268. {
  269.     listIter *iter;
  270.     listNode *node;
  272.     iter = listGetIterator(list, AL_START_HEAD);
  273.     while((node = listNext(iter)) != NULL) {
  274.         if (list->match) {// 值匹配函数
  275.             if (list->match(node->value, key)) {
  276.                 listReleaseIterator(iter);
  277.                 return node;
  278.             }
  279.         } else { // 直接使用==
  280.             if (key == node->value) {
  281.                 listReleaseIterator(iter);
  282.                 return node;
  283.             }
  284.         }
  285.     }
  286.     listReleaseIterator(iter);
  287.     return NULL;
  288. }
  290. /* Return the element at the specified zero-based index
  291.  * where 0 is the head, 1 is the element next to head
  292.  * and so on. Negative integers are used in order to count
  293.  * from the tail, -1 is the last element, -2 the penultimate
  294.  * and so on. If the index is out of range NULL is returned. */
  295. // 获取索引上的链表节点
  296. listNode *listIndex(list *list, long index) {
  297.     listNode *n;
  299.     if (index < 0) { // 索引为负数，从尾部开始查找
  300.         index = (-index)-1;
  301.         n = list->tail;
  302.         while(index-- && n) n = n->prev;
  303.     } else { // 索引非负，从头部开始查找
  304.         n = list->head;
  305.         while(index-- && n) n = n->next;
  306.     }
  307.     return n;
  308. }
  310. /* Rotate the list removing the tail node and inserting it to the head. */
  311. // 旋转链表，把尾部节点删除，插入到头部
  312. void listRotate(list *list) {
  313.     listNode *tail = list->tail;
  315.     if (listLength(list) <= 1) return;
  317.     /* Detach current tail */
  318.     list->tail = tail->prev;
  319.     list->tail->next = NULL;
  320.     /* Move it as head */
  321.     list->head->prev = tail;
  322.     tail->prev = NULL;
  323.     tail->next = list->head;
  324.     list->head = tail;
  325. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注