ddddfang's Blog.

list

链表
字数统计: 1.9k阅读时长: 11 min
2019/01/30 Share

list.h

这个list.h其实是linux内核中链表实现的精简版(只需要一个头文件)，linux提供的这套接口更像是构造list的零部件。用户可以选择直接用它定制化自己的 list型数据结构，甚至可以实现一个更为 高层次的、通用的 list接口（如下面的clist）

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#ifndef _LIST_H_
#define _LIST_H_
#ifdef __cplusplus
extern "C"
{
#endif

struct list_node
{
    struct list_node *next;
    struct list_node *prev;
};

/**
* ListNodeToItem - get the struct for this entry
* @node:    the &struct list_node pointer.
* @container:    the type of the struct this is embedded in.
* @member:    the name of the list_struct within the struct.
*/
#define ListNodeToItem(node, container, member) \
    (container *) (((char*) (node)) - ((unsigned long) &((container *)0)->member))

#define ListDeclare(name) \
    struct list_node name = { \
        .next = &name, \
        .prev = &name, \
    }

/**
* ListForEach    -    iterate over a list
* @node:    the &struct list_node to use as a loop cursor.
* @list:    the head for your list.
*/
#define ListForEach(node, list) \
    for (node = (list)->next; node != (list); node = node->next)

/**
* ListForEachReverse    -    iterate over a list backwards
* @node:    the &struct list_node to use as a loop cursor.
* @list:    the head for your list.
*/
#define ListForEachReverse(node, list) \
    for (node = (list)->prev; node != (list); node = node->prev)

/**
* ListForEachSafe - iterate over a list safe against removal of list entry
* @node:    the &struct list_node to use as a loop cursor.
* @n:        another &struct list_node to use as temporary storage
* @list:    the head for your list.
*/
#define ListForEachSafe(node, n, list) \
    for (node = (list)->next, n = node->next; \
         node != (list); \
         node = n, n = node->next)

static inline void ListInit(struct list_node *node)
{
    node->next = node;
    node->prev = node;
}

/**
* ListAddTail - add a new entry
* @head: list head to add it before
* @item: new entry to be added
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void ListAddTail(struct list_node *head, struct list_node *item)
{
    item->next = head;
    item->prev = head->prev;
    head->prev->next = item;
    head->prev = item;
}

/**
* ListAddHead - add a new entry
* @head: list head to add it after
* @item: new entry to be added
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void ListAddHead(struct list_node *head, struct list_node *item)
{
    item->next = head->next;
    item->prev = head;
    head->next->prev = item;
    head->next = item;
}

/**
* ListAppend - let list2(head2) append to the tail of list1(head1)
*/
static inline void ListAppend(struct list_node *head1, struct list_node *head2)
{
    head2->prev->next = head1;
    head2->next->prev = head1->prev;
    head1->prev->next = head2->next;
    head1->prev = head2->prev;

    head2->prev = head2;
    head2->next = head2;
}

static inline void ListReverse(struct list_node *head)
{
    struct list_node *pNode = head;
    struct list_node *pTmp = NULL;
    while(pNode->next != head)
    {
        //store the next node
        pTmp = pNode->next;
        //swap
        //pTmp = pNode->next;
        pNode->next = pNode->prev;
        pNode->prev = pTmp;

        pNode = pTmp;
    }
    //last swap
    pTmp = pNode->next;
    pNode->next = pNode->prev;
    pNode->prev = pTmp;
}

/*
* ZX_ListRemove - delete a list entry
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void ListRemove(struct list_node *item)
{
    item->next->prev = item->prev;
    item->prev->next = item->next;
}

#define ListIsEmpty(list) ((list) == (list)->next)
#define ListHead(list) ((list)->next)
#define ListTail(list) ((list)->prev)

#ifdef __cplusplus
}
#endif
#endif //LIST_H_
直接使用 list.h

在头文件中,定义一个node,一个manager

1
2
3
4
5
6
7
8
9
10
11
//自己实现的一个stack(queue也是可以实现的)
typedef struct {
    pthread_mutex_t lock;           //这里应该有一个mutex lock的,但是写的时候忘记加了
    unsigned int u32StackSize;
    struct zxlist_node listNode;
}FRAME_UI_STACK_MGR;                 //stack manager结构体

typedef struct {
    UI_FRAME_S *pUIFrame;
    struct zxlist_node listNode;
}FRAME_UI_STACK_NODE;

在.c文件中,

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
static FRAME_UI_STACK_MGR gstFrameUIStack = {
    .lock = PTHREAD_MUTEX_INITIALIZER,
};

static int frameUIStackInit() {
    gstFrameUIStack.u32StackSize = 0;
    ZX_ListInit(&gstFrameUIStack.listNode);
    return 0;
}

static int frameUIStackDeinit() {//descroy the stack
    zxlist_node *pListNode = NULL;
    FRAME_UI_STACK_NODE *pStackNode = NULL;
    while(!ZX_ListEmpty(&gstFrameUIStack.listNode)) {
        pListNode = ZX_ListTail(&gstFrameUIStack.listNode);
        pStackNode = ZX_ListNodeToItem(pListNode, FRAME_UI_STACK_NODE, listNode);
        ZX_ListRemove(pListNode);
        free(pStackNode);
    }
    gstFrameUIStack.u32StackSize = 0;
    return 0;
}

static int frameUIStackPush(UI_FRAME_S *pUIFrame) {
    if(pUIFrame == NULL) {
        printf("frameUIStackPush error: invalid param\n");
        return -1;
    }
    FRAME_UI_STACK_NODE *pUINode = (FRAME_UI_STACK_NODE *)malloc(sizeof(FRAME_UI_STACK_NODE));
    if(pUINode == NULL) {
        printf("frameUIStackPush add node error: no more availiable mem\n");
        return -1;
    }
    pUINode->pUIFrame = pUIFrame;
    ZX_ListAddTail(&gstFrameUIStack.listNode,&(pUINode->listNode));    //add to tail
    gstFrameUIStack.u32StackSize++;
    return 0;
}

static int frameUIStackTop(UI_FRAME_S **ppUIFrame) {
    if(ppUIFrame == NULL) {
        printf("frameUIStackTop error: invalid param\n");
        return -1;
    }
    if(gstFrameUIStack.u32StackSize == 0) {
        if(ZX_ListEmpty(&gstFrameUIStack.listNode)) {//confirm
            printf("frameUIStackTop stack is empty!\n");
            *ppUIFrame = NULL;
            return 0;
        } else {
            printf("frameUIStackTop error!\n");
            *ppUIFrame = NULL;
            return -1;
        }
    }
    zxlist_node *pListNode = ZX_ListTail(&gstFrameUIStack.listNode);        //just get the tail
    FRAME_UI_STACK_NODE *pStackNode = ZX_ListNodeToItem(pListNode, FRAME_UI_STACK_NODE, listNode);
    *ppUIFrame = pStackNode->pUIFrame;
    return 0;
}

static int frameUIStackPop(UI_FRAME_S **ppUIFrame) {
    if(gstFrameUIStack.u32StackSize == 0) {
        if(ZX_ListEmpty(&gstFrameUIStack.listNode)){
            printf("frameUIStackPop stack is empty!\n");
            *ppUIFrame = NULL;
            return 0;
        } else {
            printf("frameUIStackPop error!\n");
            *ppUIFrame = NULL;
            return -1;
        }
    }
    zxlist_node *pListNode = ZX_ListTail(&gstFrameUIStack.listNode);    //get the tail
    FRAME_UI_STACK_NODE *pStackNode = ZX_ListNodeToItem(pListNode, FRAME_UI_STACK_NODE, listNode);
    if(ppUIFrame != NULL) {//if param is null, just discard top element
        *ppUIFrame = pStackNode->pUIFrame;
    }
    ZX_ListRemove(pListNode);                                                                       //remove the tail
    free(pStackNode);
    gstFrameUIStack.u32StackSize--;
    return 0;
}

数组实现的stack和queue比链表效率更高一点

  • 数组实现的stack应该很简单
  • 数组实现的queue分为两种：
    • 使用环形队列，效率高，但需要考虑wrap的情况 (RingBuf)
    • 不用环形队列，使用memmove，效率有折损但简单（bufQueue）
      list、stack、fifo(即queue)都属于线性结构，stack和fifo可以看作阉割版的list
cList.c，这是在学习了《c 接口与实现》第7章 后弄的一个类 lisp 链表 的实现
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include <stdarg.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "cList.h"

//将一个数据push到list的head
clist List_push(clist list, void *x)
{
    unsigned int flag=0;
    clist listTmp = NULL;
    clistNode *pNodeTmp = NULL;
    if(!list)
    {    //new malloc a list manager node and init
        listTmp = (clist)malloc(sizeof(struct clistManager));
        if(!listTmp)
            goto FAIL_1;
        ListInit(&listTmp->listNode);
        listTmp->u32ListSize = 0;
        flag = 1;
    }
    else
        listTmp = list;

    //new list node and init
    pNodeTmp = (clistNode *)malloc(sizeof(clistNode));
    if(!pNodeTmp)
        goto FAIL_2;
    ListInit(&pNodeTmp->listNode);
    pNodeTmp->data = x;

    //add list node to clist manager(header)
    ListAddHead(&listTmp->listNode, &pNodeTmp->listNode);
    listTmp->u32ListSize++;
    return listTmp;

FAIL_2:
    if(flag)
        free(listTmp);
FAIL_1:
    return NULL;
}

//构造一个list,应该以NULL或者其他为false的值结尾
clist List_list(void *x, ...)
{
    va_list ap;
    va_start(ap, x);

    clist listTmp = NULL;
    clistNode *pNodeTmp = NULL;
    struct list_node *plistNode = NULL;

    //new malloc a list manager node and init
    listTmp = (clist)malloc(sizeof(struct clistManager));
    if(!listTmp)
        goto FAIL_1;
    ListInit(&listTmp->listNode);
    listTmp->u32ListSize = 0;

    for ( ; x; x = va_arg(ap, void *))
    {
        //new list node and init
        pNodeTmp = (clistNode *)malloc(sizeof(clistNode));
        if(!pNodeTmp)    // TODO: this may cause memleak
            goto FAIL_2;
        ListInit(&pNodeTmp->listNode);
        pNodeTmp->data = x;

        ListAddTail(&listTmp->listNode, &pNodeTmp->listNode);
        listTmp->u32ListSize++;
    }
    va_end(ap);
    return listTmp;

FAIL_2:
    List_free(&listTmp);
FAIL_1:
    return NULL;
}

clist List_append(clist list, clist tail)
{
    if(!list)
        return tail;

    if(tail)
    {
        ListAppend(&list->listNode, &tail->listNode);
        list->u32ListSize += tail->u32ListSize;
        tail->u32ListSize = 0;
    }
    return list;
}

clist List_copy(clist list)
{
    clist listTmp = NULL;
    clistNode *pNodeTmpSrc = NULL;
    clistNode *pNodeTmpDst = NULL;

    if(list)
    {
        //new malloc a list manager node and init
        listTmp = (clist)malloc(sizeof(struct clistManager));
        if(!listTmp)
            goto FAIL_1;
        ListInit(&listTmp->listNode);
        listTmp->u32ListSize = 0;

        struct list_node *plistNode = NULL;
        ListForEach(plistNode,&list->listNode)
        {
            pNodeTmpSrc = ListNodeToItem(plistNode, clistNode, listNode);
            //new list node and init
            pNodeTmpDst = (clistNode *)malloc(sizeof(clistNode));
            if(!pNodeTmpDst)
                goto FAIL_2;
            ListInit(&pNodeTmpDst->listNode);
            pNodeTmpDst->data = pNodeTmpSrc->data;
            //insert
            ListAddTail(&listTmp->listNode, &pNodeTmpDst->listNode);
            listTmp->u32ListSize++;
        }
    }
    return listTmp;

FAIL_2:
    List_free(&listTmp);
FAIL_1:
    return NULL;
}

clist List_pop(clist list, void **x)
{
    struct list_node *plistNode = NULL;
    clistNode *pNodeTmp = NULL;
    if (list && !ListIsEmpty(&list->listNode))
    {
        plistNode = ListHead(&list->listNode);
        pNodeTmp = ListNodeToItem(plistNode, clistNode, listNode);
        if (x)
            *x = pNodeTmp->data;
        ListRemove(plistNode);
        free(pNodeTmp);
        list->u32ListSize--;
    }
    return list;
}

//NOTE :param list and returned list both reversed!
clist List_reverse(clist list)
{
    if(list)
        ListReverse(&list->listNode);
    return list;
}

int List_length(clist list)
{
    int n=0;
    if(list)
        n = list->u32ListSize;
    return n;
}

void List_free(clist *plist)
{
    struct list_node *plistNode = NULL;
    clistNode *pNodeTmp = NULL;
    clist list = NULL;
    if (plist)
    {
        list = *plist;
        if(list)
        {
            while(!ListIsEmpty(&list->listNode))
            {
                plistNode = ListHead(&list->listNode);
                pNodeTmp = ListNodeToItem(plistNode, clistNode, listNode);
                ListRemove(plistNode);
                free(pNodeTmp);
                list->u32ListSize--;
            }
            free(list);
        }
        *plist = NULL;
    }
}

void List_map(clist list, void apply(void **x,int index, void *cl), void *cl)
{
    struct list_node *plistNode = NULL;
    clistNode *pNodeTmp = NULL;
    int i=0;
    if(apply && list)
    {
        ListForEach(plistNode,&list->listNode)
        {
            //apply 使用的是指向 first 的指针,因此可能改变 first 指针的指向
            pNodeTmp = ListNodeToItem(plistNode, clistNode, listNode);
            apply(&pNodeTmp->data,i++,cl);    //
        }
    }
}

void **List_toArray(clist list, void *end)
{
    int i=0, n;
    struct list_node *plistNode = NULL;
    clistNode *pNodeTmp = NULL;
    void **array = NULL;
    if(list)
    {
        n = list->u32ListSize;
        array = (void **)malloc((n + 1)*sizeof (void *));
        if(!array)
            return NULL;
        ListForEach(plistNode,&list->listNode)
        {
            pNodeTmp = ListNodeToItem(plistNode, clistNode, listNode);
            array[i++] = pNodeTmp->data;
        }
        array[i] = end;    
    }
    return array;
}
cList.h
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
//cList.h
#ifndef _COMMON_LIST_H
#define _COMMON_LIST_H

#include "list.h"

typedef struct clistManager{
    struct list_node listNode;
    unsigned int u32ListSize;
} *clist;

typedef struct {
    struct list_node listNode;
    void *data;
} clistNode;

clist List_push(clist list, void *x);
clist List_list(void *x, ...);
clist List_append(clist list, clist tail);
clist List_copy(clist list);
clist List_pop(clist list, void **x);
clist List_reverse(clist list);
int List_length(clist list);
void List_free(clist *plist);
void List_map(clist list, void apply(void **x,int index, void *cl), void *cl);
void **List_toArray(clist list, void *end);


#endif

原文作者：ddddfang

原文链接：https://ddddfang.github.io/2019/01/30/list/

发表日期：January 30th 2019, 4:21:13 pm

更新日期：January 30th 2019, 4:44:35 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. list.h
    1. 1.0.0.1. 直接使用 list.h
    2. 1.0.0.2. cList.c，这是在学习了《c 接口与实现》第7章 后弄的一个类 lisp 链表 的实现
    3. 1.0.0.3. cList.h
Total : 42
2019
binary-search bitmap caffe c++ 单例模式 common misc makefile 宏 顺序容器 智能指针 排序 shell linux command docker blog ffmpeg gdb gitbook p4 printf 可变参数 static and dynamic library 第k小的数 ubuntu setup 并查集 git draw.io markdown vscode office2016 密钥 键值对集合 链表 最大堆(大顶堆) swig python c vim 红黑树 skip-list hash-table
algorithm-and-data-struct caffe common-misc cpp linux-daily ffmpeg