侵入式单链表的简单实现(cont)-白红宇

侵入式单链表的简单实现(cont)

阅读量：4542 次

发布时间：2019-06-08

本文共 8231 字，大约阅读时间需要 27 分钟。

前一节介绍的侵入式链表实现在封装性方面做得不好，因为会让消费者foo.c直接使用宏container_of()。这一节对list的定义做了一点改进，如下所示：

typedef struct list_s {        struct list_s *next;        size_t offset;} list_t;

既然链表结点已经保存了offset, 那么就不再需要宏container_of()了。(注：Solaris的侵入式双向循环链表就是这么玩的，跟Linux玩法不一样。)

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 member10  * @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 typedef struct list_s {16         struct list_s *next;17         size_t offset;18 } list_t;19 20 extern list_t *list_d2l(void *object, size_t offset);21 extern   void *list_l2d(list_t *list);22 23 #ifdef  __cplusplus24 }25 #endif26 27 #endif /* _LIST_H */

list_d2l(): 根据数据(data)结点的内存首地址得到侵入式链表(list)结点的内存首地址。

list_l2d(): 根据侵入式链表(list)结点的内存首地址得到数据(data)结点的内存首地址。

2. list.c

1 /* 2  * Generic single linked list implementation 3  */ 4 #include 
     
       5 #include "list.h" 6  7 list_t * 8 list_d2l(void *object, size_t offset) 9 {10         if (object == NULL)11                 return NULL;12 13         list_t *p = (list_t *)((char *)object + offset);14         p->offset = offset;15         p->next = NULL;16 17         return p;18 }19 20 void *21 list_l2d(list_t *list)22 {23         if (list == NULL)24                 return NULL;25 26         return (void *)((char *)list - list->offset);27 }

list_d2l(): 侵入式链表结点的内存首地址 = 数据结点的内存首地址 + offset

list_l2d(): 数据结点的内存首地址 = 侵入式链表结点的内存首地址 - offset

3. foo.c

1 #include 
     
       2 #include 
      
        3 #include "list.h" 4  5 typedef struct foo_s { 6         int     data; 7         list_t  link; 8 } foo_t; 9 10 static void11 foo_init(list_t **head, void *object, size_t offset)12 {13         if (object == NULL)14                 return;15 16         printf("init (node) %p\n", object);17         list_t *node = list_d2l(object, offset);18 19         if (*head == NULL) {20                 *head = node;21                 return;22         }23 24         list_t *tail = NULL;25         for (list_t *p = *head; p != NULL; p = p->next)26                 tail = p;27         tail->next = node;28 }29 30 static void31 foo_fini(list_t *head)32 {33         list_t *p = head;34         while (p != NULL) {35                 list_t *q = p;36                 p = p->next;37 38                 void *obj = list_l2d(q);39                 printf("free (node) %p next (list) %p\n", obj, p);40                 free(obj);41         }42 }43 44 static void45 foo_show(list_t *head)46 {47         for (list_t *p = head; p != NULL; p = p->next) {48                 foo_t *obj = list_l2d(p);49 50                 printf("show (list) %p next (list) %p \t: "51                     "show (node) %p = {0x%x, {%p, %d}}\n",52                     &obj->link, obj->link.next,53                     obj, obj->data, obj->link.next, obj->link.offset);54         }55 }56 57 int58 main(int argc, char *argv[])59 {60         if (argc != 2) {61                 fprintf(stderr, "Usage: %s 
       
        \n", argv[0]);62                 return -1;63         }64 65         list_t *head = NULL;66         for (int i = 0; i < atoi(argv[1]); i++) {67                 foo_t *p = (foo_t *)malloc(sizeof (foo_t));68                 if (p == NULL) /* error */69                         return -1;70                 p->data = 0x1001 + i;71 72                 foo_init(&head, (void *)p, offsetof(foo_t, link));73         }74 75         foo_show(head);76         foo_fini(head);77 78         return 0;79 }

注意： list_l2d()与container_of()是等效的。例如：

48                 foo_t *obj = list_l2d(p);

等效于

foo_t *obj = container_of(p, foo_t, link);

4. Makefile

1 CC      = gcc 2 CFLAGS  = -g -Wall -m32 -std=gnu99 3  4 all: foo 5  6 foo: foo.o list.o 7         ${CC} ${CFLAGS} -o $@ $^ 8  9 foo.o: foo.c10         ${CC} ${CFLAGS} -c $<11 12 list.o: list.c list.h13         ${CC} ${CFLAGS} -c $<14 15 clean:16         rm -f *.o17 18 clobber: clean19         rm -f foo20 cl: clobber

5. 编译并运行

$ makegcc -g -Wall -m32 -std=gnu99 -c foo.cgcc -g -Wall -m32 -std=gnu99 -c list.cgcc -g -Wall -m32 -std=gnu99 -o foo foo.o list.o$ ./foo 3init (node) 0x81a8008init (node) 0x81a8018init (node) 0x81a8028show (list) 0x81a800c next (list) 0x81a801c     : show (node) 0x81a8008 = {
   0x1001, {
   0x81a801c, 4}}show (list) 0x81a801c next (list) 0x81a802c     : show (node) 0x81a8018 = {
   0x1002, {
   0x81a802c, 4}}show (list) 0x81a802c next (list) (nil)         : show (node) 0x81a8028 = {
   0x1003, {(nil), 4}}free (node) 0x81a8008 next (list) 0x81a801cfree (node) 0x81a8018 next (list) 0x81a802cfree (node) 0x81a8028 next (list) (nil)

6. 用gdb查看链表

(gdb) b foo_showBreakpoint 1 at 0x80485d4: file foo.c, line 47.(gdb) r 3Starting program: /tmp/list/foo 3init (node) 0x804b008init (node) 0x804b018init (node) 0x804b028Breakpoint 1, foo_show (head=0x804b00c) at foo.c:4747      for (foo_t *p = list_head(head); p != NULL; p = list_next(&p->link)) {(gdb) #(gdb) x /2x head0x804b00c:      0x0804b01c      0x00000004(gdb) x /2x head->next0x804b01c:      0x0804b02c      0x00000004(gdb) x /2x head->next->next0x804b02c:      0x00000000      0x00000004(gdb) #(gdb) p head$1 = (list_t *) 0x804b00c(gdb) #(gdb) x /3x 0x804b00c-0x40x804b008:      0x00001001      0x0804b01c      0x00000004(gdb) x /3x 0x804b01c-0x40x804b018:      0x00001002      0x0804b02c      0x00000004(gdb) x /3x 0x804b02c-0x40x804b028:      0x00001003      0x00000000      0x00000004(gdb) #

小结：

在这一版本的侵入式链表实现中，实现细节已经被充分屏蔽，核心函数就两个，list_d2l()和list_l2d()，也很容易理解。当然，对于消费者程序来说，无需知晓数据（data）结点的内存首地址与链表(list)结点的内存首地址之间是如何相互转换的。

后记：

在上面的代码实现中，list_d2l()总是会将((list_t *)p)->next设置成NULL。这么做存在着一个问题，那就是一旦链表构造完成后，如果想从某一个数据结点通过list_d2l()找到对应的链表结点，就会将链表截断。于是，我对list_d2l()做了一点修改，并增加了三个基本的链表操作函数list_insert_tail(), list_insert_head()和list_delete()。

1. list_d2l()和list_l2d()

1 /* 2  * Cast ptr of DATA object node to ptr of LIST node 3  */ 4 list_t * 5 list_d2l(void *object, size_t offset) 6 { 7         if (object == NULL) 8                 return NULL; 9 10         return (list_t *)((char *)object + offset);11 }12 13 /*14  * Cast ptr of LIST node to ptr of DATA object node15  */16 void *17 list_l2d(list_t *list)18 {19         if (list == NULL)20                 return NULL;21 22         return (void *)((char *)list - list->offset);23 }

2. LIST_INIT_NODE()

1 #define LIST_INIT_NODE(list, offset) do {       \2                 (list)->next = NULL;            \3                 (list)->offset = (offset);      \4         } while (0)

3. 将数据结点插入到侵入式链表中

list_insert_tail() // 尾插法

list_insert_head() // 头插法

1 /* 2  * Insert an object after the tail of list 3  */ 4 void 5 list_insert_tail(list_t **head, void *object, size_t offset) 6 { 7         if (object == NULL) 8                 return; 9 10         list_t *node = list_d2l(object, offset);11         LIST_INIT_NODE(node, offset);12 13         if (*head == NULL) {14                 *head = node;15                 return;16         }17 18         list_t *tail = NULL;19         for (list_t *p = *head; p != NULL; p = p->next)20                 tail = p;21         tail->next = node;22 }23 24 /*25  * Insert an object before the head of list26  */27 void28 list_insert_head(list_t **head, void *object, size_t offset)29 {30         if (object == NULL)31                 return;32 33         list_t *node = list_d2l(object, offset);34         LIST_INIT_NODE(node, offset);35 36         if (*head == NULL) {37                 *head = node;38                 return;39         }40 41         node->next = *head;42         *head = node;43 }

4. 从侵入式连表中删除一个结点

1 /* 2  * Delete a node from list 3  */ 4 void 5 list_delete(list_t **head, list_t *node) 6 { 7         if (head == NULL || *head == NULL || node == NULL) 8                 return; 9 10         if (*head == node) {11                 *head = node->next;12                 return;13         }14 15         list_t *q = *head;16         for (list_t *p = *head; p != NULL; p = p->next) {17                 if (p == node)18                         break;19                 q = p;20         }21         q->next = node->next;22 }

如对完整的代码实现感兴趣，请戳。

转载于:https://www.cnblogs.com/idorax/p/6812484.html

你可能感兴趣的文章