redis基础数据结构-list简介

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;

typedef struct listIter {
listNode *next;
int direction;
} listIter;

typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned int len;
} list;

特点

  • 可以转载任何类型的数据
  • 可以定制dup,free,match方法,自由度大
  • 可以从头、尾分别插入链表
  • 提供迭代器,方便遍历整个链表

重要接口实现

  • 构建/释放list

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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;
    }

    void listRelease(list *list)
    {
    unsigned int len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
    next = current->next;
    if (list->free) list->free(current->value);
    zfree(current);
    current = next;
    }
    zfree(list);
    }
  • 遍历和复制list

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    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;
    }

    list *listDup(list *orig)
    {
    list *copy;
    listIter *iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)
    return NULL;
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    iter = listGetIterator(orig, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
    void *value;

    if (copy->dup) {
    value = copy->dup(node->value);
    if (value == NULL) {
    listRelease(copy);
    listReleaseIterator(iter);
    return NULL;
    }
    } else
    value = node->value;
    if (listAddNodeTail(copy, value) == NULL) {
    listRelease(copy);
    listReleaseIterator(iter);
    return NULL;
    }
    }
    listReleaseIterator(iter);
    return copy;
    }
-------------本文结束 感谢阅读-------------