C 侵入式数据结构

之前在网上了解到 Linux 内核开发时用的是侵入式（intrusive）数据结构，就想了解下。然后读了这篇介绍 Linux 内核中用到的双向链表实现的文章 。

看完那篇博客后，就想自己写个小例子感受下。

• 实现一个简单的单向链表。

• 然后模拟一个游戏的背包实现。添加道具到背包，然后遍历背包中的道具，最后销毁道具。

• 我在 mingw 上测试的，若是在 Linux 上编译不过去，可以试试 -std 选项。

  /**

  • 采用侵入式数据结构，实现一个简单的单向链表。
  • gcc -o test test.c */ #include <stdio.h> #include <stdlib.h>

  ////////////////////////////////////////////////////////////// // 链表的实现 struct list_head { struct list_head *next; };

  #define LIST_HEAD_INIT(name) { &(name) } #define LIST_HEAD(name)
  struct list_head name = LIST_HEAD_INIT(name)

  static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; }

  static inline void list_add(struct list_head *new, struct list_head *head) { new->next = head->next; head->next = new; }

  // 对外接口 // #define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );}) // 采用 typeof 编译不过 #define list_entry(ptr, type, member) container_of(ptr, type, member) #define list_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next) // 内部接口 #define container_of(ptr, type, member) ({
  const __auto_type __mptr = (ptr);
  (type *)( (char *)__mptr - offsetof(type,member) );}) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) //////////////////////////////////////////////////////////////

  // 游戏中背包的道具。 struct item_info { struct list_head list; int id; };

  static LIST_HEAD(items);

  // 向背包中添加一个道具。 void additem(int id) { struct item_info item = (struct item_info)malloc(sizeof(struct item_info)); INIT_LIST_HEAD(&item->list);

  1item->id = id;
  2list_add(&item->list, &items);
  

  }

  int main(int argc, char *argv[]) { int count = 0;

  1additem(200);
  2additem(300);
  3additem(0);
  4
  5struct item_info *nouse_item = NULL;
  6struct list_head *pos = NULL, *nouse = NULL;
  7list_for_each(pos, &items) {
  8	if (nouse) { // 要在本循环销毁上一个循环获取的道具
  9		nouse_item = list_entry(nouse, struct item_info, list);
  10		printf("\nfree one item:%d\n", nouse_item->id);
  11		free(nouse_item);
  12	}
  13
  14	count++;
  15	struct item_info *info = list_entry(pos, struct item_info, list);
  16	printf("id:%d ", info->id);
  17
  18	nouse = pos;
  19}
  20if (nouse) {
  21	nouse_item = list_entry(nouse, struct item_info, list);
  22	printf("\nfree the last item:%d\n", nouse_item->id);
  23	free(nouse_item);
  24}
  25printf("total count:%d\n", count);
  26
  27return 0;
  

  }

思考

• 侵入式链表中的节点并未包含具体的数据，又是如何获取到数据的呢？
• offsetof 宏获取的偏移值，是不是在编译时就计算出来的呢，还是允许时动态算出来的。

参考

• gcc typeof 与 __auto_type