Chinaunix首页 | 论坛 | 博客
  • 博客访问: 293018
  • 博文数量: 63
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 763
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(63)

文章存档

2019年(15)

2018年(47)

2017年(1)

我的朋友

分类: NOSQL

2019-01-14 23:24:34

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. /* Directions for iterators */
  6. #define AL_START_HEAD 0
  7. #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. #define listSetDupMethod(l,m) ((l)->dup = (m))
  9. #define listSetFreeMethod(l,m) ((l)->free = (m))
  10. #define listSetMatchMethod(l,m) ((l)->match = (m))

  11. #define listGetDupMethod(l) ((l)->dup)
  12. #define listGetFree(l) ((l)->free)
  13. #define listGetMatchMethod(l) ((l)->match)


之后的话,就是list当中的一些“常规操作了”

创建,清空,释放函数如下:

点击(此处)折叠或打开

  1. list *listCreate(void)
  2. {
  3.     struct list *list;

  4.     if ((list = zmalloc(sizeof(*list))) == NULL)
  5.         return NULL;
  6.     list->head = list->tail = NULL;
  7.     list->len = 0;
  8.     list->dup = NULL;
  9.     list->free = NULL;
  10.     list->match = NULL;
  11.     return list;
  12. }

  13. /* Remove all the elements from the list without destroying the list itself. */
  14. void listEmpty(list *list)
  15. {
  16.     unsigned long len;
  17.     listNode *current, *next;

  18.     current = list->head;
  19.     len = list->len;
  20.     while(len--) {
  21.         next = current->next;
  22.         if (list->free) list->free(current->value);
  23.         zfree(current);
  24.         current = next;
  25.     }
  26.     list->head = list->tail = NULL;
  27.     list->len = 0;
  28. }

  29. /* Free the whole list.
  30.  *
  31.  * This function can't fail. */
  32. void listRelease(list *list)
  33. {
  34.     listEmpty(list);
  35.     zfree(list);
  36. }
分别从头尾两端插入节点

点击(此处)折叠或打开

  1. list *listAddNodeHead(list *list, void *value)
  2. {
  3.     listNode *node;

  4.     if ((node = zmalloc(sizeof(*node))) == NULL)
  5.         return NULL;
  6.     node->value = value;
  7.     if (list->len == 0) {
  8.         list->head = list->tail = node;
  9.         node->prev = node->next = NULL;
  10.     } else {
  11.         node->prev = NULL;
  12.         node->next = list->head;
  13.         list->head->prev = node;
  14.         list->head = node;
  15.     }
  16.     list->len++;
  17.     return list;
  18. }
  19. list *listAddNodeTail(list *list, void *value)
  20. {
  21.     listNode *node;

  22.     if ((node = zmalloc(sizeof(*node))) == NULL)
  23.         return NULL;
  24.     node->value = value;
  25.     if (list->len == 0) {
  26.         list->head = list->tail = node;
  27.         node->prev = node->next = NULL;
  28.     } else {
  29.         node->prev = list->tail;
  30.         node->next = NULL;
  31.         list->tail->next = node;
  32.         list->tail = node;
  33.     }
  34.     list->len++;
  35.     return list;
  36. }
根据参数选择插入节点的相对位置

点击(此处)折叠或打开

  1. list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
  2.     listNode *node;

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

点击(此处)折叠或打开

  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.     if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
  5.     if (direction == AL_START_HEAD)
  6.         iter->next = list->head;
  7.     else
  8.         iter->next = list->tail;
  9.     iter->direction = direction;
  10.     return iter;
  11. }

  12. /* Release the iterator memory */
  13. void listReleaseIterator(listIter *iter) {
  14.     zfree(iter);
  15. }

  16. /* Create an iterator in the list private iterator structure */
  17. void listRewind(list *list, listIter *li) {
  18.     li->next = list->head;
  19.     li->direction = AL_START_HEAD;
  20. }

  21. void listRewindTail(list *list, listIter *li) {
  22.     li->next = list->tail;
  23.     li->direction = AL_START_TAIL;
  24. }
  25. listNode *listNext(listIter *iter)
  26. {
  27.     listNode *current = iter->next;

  28.     if (current != NULL) {
  29.         if (iter->direction == AL_START_HEAD)
  30.             iter->next = current->next;
  31.         else
  32.             iter->next = current->prev;
  33.     }
  34.     return current;
  35. }
list的复制查找

点击(此处)折叠或打开

  1. list *listDup(list *orig)
  2. {
  3.     list *copy;
  4.     listIter iter;
  5.     listNode *node;

  6.     if ((copy = listCreate()) == NULL)
  7.         return NULL;
  8.     copy->dup = orig->dup;
  9.     copy->free = orig->free;
  10.     copy->match = orig->match;
  11.     listRewind(orig, &iter);
  12.     while((node = listNext(&iter)) != NULL) {
  13.         void *value;

  14.         if (copy->dup) {
  15.             value = copy->dup(node->value);
  16.             if (value == NULL) {
  17.                 listRelease(copy);
  18.                 return NULL;
  19.             }
  20.         } else
  21.             value = node->value;
  22.         if (listAddNodeTail(copy, value) == NULL) {
  23.             listRelease(copy);
  24.             return NULL;
  25.         }
  26.     }
  27.     return copy;
  28. }
  29. listNode *listSearchKey(list *list, void *key)
  30. {
  31.     listIter iter;
  32.     listNode *node;

  33.     listRewind(list, &iter);
  34.     while((node = listNext(&iter)) != NULL) {
  35.         if (list->match) {
  36.             if (list->match(node->value, key)) {
  37.                 return node;
  38.             }
  39.         } else {
  40.             if (key == node->value) {
  41.                 return node;
  42.             }
  43.         }
  44.     }
  45.     return NULL;
  46. }
  47. listNode *listIndex(list *list, long index) {
  48.     listNode *n;

  49.     if (index < 0) {
  50.         index = (-index)-1;
  51.         n = list->tail;
  52.         while(index-- && n) n = n->prev;
  53.     } else {
  54.         n = list->head;
  55.         while(index-- && n) n = n->next;
  56.     }
  57.     return n;
  58. }
将最后一个元素插入到列表头

点击(此处)折叠或打开

  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.     if (listLength(list) <= 1) return;

  5.     /* Detach current tail */
  6.     list->tail = tail->prev;
  7.     list->tail->next = NULL;
  8.     /* Move it as head */
  9.     list->head->prev = tail;
  10.     tail->prev = NULL;
  11.     tail->next = list->head;
  12.     list->head = tail;
  13. }
合并两个列表

点击(此处)折叠或打开

  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.     if (l->tail)
  7.         l->tail->next = o->head;
  8.     else
  9.         l->head = o->head;

  10.     if (o->tail) l->tail = o->tail;
  11.     l->len += o->len;

  12.     /* Setup other as an empty list. */
  13.     o->head = o->tail = NULL;
  14.     o->len = 0;
  15. }
总体来开,redis当中的adlist还是跟我们平素里用到的list差不多的,虽然作者有点造轮子之嫌,但是于读者而言,多读一读源代码还是好处多多的,毕竟“源码之前,了无秘密”,与诸位共勉~~~


阅读(1893) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册