侵入式单链表的简单实现

```typedef struct foo_s {
int             data;
struct foo_s    *next;
} foo_t;```

```typedef struct list_s {
struct list_s *next;
} list_t;

typedef struct foo_s {
int     data;
} foo_t;```

• 普通的单链表的结点链接域存的是下一个结点的内存首地址
• 侵入式单链表的结点链接域存的是下一个结点的链接域成员变量的内存首地址

1. list.h

``` 1 #ifndef _LIST_H
2 #define _LIST_H
3
4 #ifdef  __cplusplus
5 extern "C" {
6 #endif
7
8 /**
9  * offsetof - offset of a structure member
10  * @TYPE:       the type of the struct.
11  * @MEMBER:     the name of the member within the struct.
12  */
13 #define offsetof(TYPE, MEMBER) ((size_t)(&(((TYPE *)0)->MEMBER)))
14
15 /**
16  * container_of - cast a member of a structure out to the containing structure
17  * @ptr:        the pointer to the member.
18  * @type:       the type of the container struct this is embedded in.
19  * @member:     the name of the member within the struct.
20  *
21  */
22 #define container_of(ptr, type, member) ({                      \
23         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
24         (type *)( (char *)__mptr - offsetof(type, member) );})
25
26 typedef struct list_s {
27         struct list_s *next;
28 } list_t;
29
30 typedef void (*list_handler_t)(void *arg);
31
32 extern void list_init(list_t **head, list_t *node);
33 extern void list_fini(list_t *head, list_handler_t fini);
34 extern void list_show(list_t *head, list_handler_t show);
35
36 #ifdef  __cplusplus
37 }
38 #endif
39
40 #endif /* _LIST_H */```

2. list.c

``` 1 /*
2  * Generic single linked list implementation
3  */
4 #include <stdio.h>
5 #include "list.h"
6
7 void
9 {
10         static list_t *tail = NULL;
11
12         if (*head == NULL) {
13                 *head = tail = node;
14                 return;
15         }
16
17         tail->next = node;
18         tail = node;
19         node->next = NULL;
20 }
21
22 void
24 {
25         for (list_t *p = head; p != NULL; p = p->next)
26                 show(p);
27 }
28
29 void
31 {
33         while (p != NULL) {
34                 list_t *q = p;
35                 p = p->next;
36                 fini(q);
37         }
38 }```

3. foo.c

``` 1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "list.h"
4
5 typedef struct foo_s {
6         int     data;
8 } foo_t;
9
10 static void
11 foo_show(void *arg)
12 {
13         list_t *q = (list_t *)arg;
14         foo_t  *p = container_of(q, foo_t, link);
15
16         printf("show (list) %p next (list) %p \t: "
17             "show (node) %p = {0x%x, %p}\n",
19 }
20
21 static void
22 foo_fini(void *arg)
23 {
24         list_t *q = (list_t *)arg;
25         foo_t  *p = container_of(q, foo_t, link);
26
27         foo_t *next_nodep = NULL;
30
31         printf("free (node) %p next (node) %p\n", p, next_nodep);
33         free(p);
34 }
35
36 int
37 main(int argc, char *argv[])
38 {
39         if (argc != 2) {
40                 fprintf(stderr, "Usage: %s <num>\n", argv[0]);
41                 return -1;
42         }
43
45         for (int i = 0; i < atoi(argv[1]); i++) {
46                 foo_t *p = (foo_t *)malloc(sizeof (foo_t));
47                 if (p == NULL) /* error */
48                         return -1;
49                 p->data = 0x1001 + i;
50
51                 printf("init (node) %p\n", p);
53         }
54
56
58
59         return 0;
60 }```

4. Makefile

```CC    = gcc
CFLAGS    = -g -Wall -m32 -std=gnu99

all: foo

foo: foo.o list.o
\${CC} \${CFLAGS} -o \$@ \$^

foo.o: foo.c
\${CC} \${CFLAGS} -c \$<

list.o: list.c list.h
\${CC} \${CFLAGS} -c \$<

clean:
rm -f *.o

clobber: clean
rm -f foo
cl: clobber```

5. 编译并运行

```\$ make
gcc -g -Wall -m32 -std=gnu99 -c foo.c
gcc -g -Wall -m32 -std=gnu99 -c list.c
gcc -g -Wall -m32 -std=gnu99 -o foo foo.o list.o

\$ ./foo 3
init (node) 0x88a1008
init (node) 0x88a1018
init (node) 0x88a1028
show (list) 0x88a100c next (list) 0x88a101c     : show (node) 0x88a1008 = {0x1001, 0x88a101c}
show (list) 0x88a101c next (list) 0x88a102c     : show (node) 0x88a1018 = {0x1002, 0x88a102c}
show (list) 0x88a102c next (list) (nil)         : show (node) 0x88a1028 = {0x1003, (nil)}
free (node) 0x88a1008 next (node) 0x88a1018
free (node) 0x88a1018 next (node) 0x88a1028
free (node) 0x88a1028 next (node) (nil)```

原文作者：veli
原文地址: https://www.cnblogs.com/idorax/p/6808112.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。