- //
- // Created by jbj on 15-10-27.
- //
- /*
- *一个通用链表的实现,结构体struct list_head可放置与其他自定义结构体内部进行包装链接
- *使用者可以进行进一步封装
- *
- *接口:1,list_for_each(pos,head)遍历链表,pos是一个struct list_head类型的指针,可视为C++的迭代器
- * 2,list_add_tail(new,head)
- * 3,list_add(new,head)
- * 4,list_del(del)del是一个struct list_head指针
- * 5,list_is_last(head)
- * 6,list_empty()
- * 7,list_entry()是一个非常有用的工具函数,它可以返回外层数据域的地址,从而进行遍历
- *
- *
- *
- *
- * */
- #ifndef DATASTRUCTE_LIST_H
- #define DATASTRUCTE_LIST_H
- #endif //DATASTRUCTE_LIST_H
- #include <stdio.h>
- //定义指针结构体
- struct list_head{
- struct list_head *next,*prev;
- };
- #define POISON_POINTER_DELTA 0
- #define LIST_POISON1 ((void*)0x00100100+ POISON_POINTER_DELTA)
- #define LIST_POISON2 ((void*)0x00200200+ POISON_POINTER_DELTA)
- #define LIST_HEAD_INIT(name) { &(name), &(name) }
- #define LIST_HEAD(name) \\
- struct list_head name = LIST_HEAD_INIT(name)
- //计算member元素在type中的位置
- #define offsetof(type,member) (size_t)(&((type*)0)->member) //数0被看做一个type类型有效地址的开始
- //根据member的地址获得type的起始地址
- #define container_of(ptr, type, member) ({ \\
- const typeof( ((type *)0)->member ) *__mptr = (ptr); \\
- (type *)( (char *)__mptr - offsetof(type,member) );}) //考虑一下const typeof(ptr)是否可行=.=#
- static inline void init_list_head(struct list_head *list)
- {
- list->prev = list;
- list->next = list;
- }
- static inline void _list_add(struct list_head *new, struct list_head *prev,struct list_head *next)
- {
- next->prev=new;
- new->next=next;
- new->prev=prev;
- prev->next=new;
- }
- //插入到第一个元素
- static inline void list_add(struct list_head* new, struct list_head* head)
- {
- _list_add(new,head,head->next);
- }
- //插入到做后一个元素
- static inline void list_add_tail(struct list_head* new, struct list_head*head)
- {
- _list_add(new,head->prev,head);
- }
- //删除一个节点
- /***********************************************************************/
- static inline void _list_del(struct list_head* prev,struct list_head* next)
- {
- next->prev=prev;
- prev->next=next;
- }
- //摧毁一个指针,并使删除节点指向安全位置
- static inline void list_del(struct list_head* entry)
- {
- _list_del(entry->prev,entry->next);
- entry->next=LIST_POISON1;
- entry->prev=LIST_POISON2;
- }
- /***********************************************************************/
- static inline void list_move(struct list_head*list, struct list_head*head)
- {
- _list_del(list->prev,list->next);
- list_add(list,head);
- }
- static inline void list_move_tail(struct list_head* list,struct list_head*head)
- {
- _list_del(list->prev,list->next);
- list_add_tail(list,head);
- }
- /***************************************************************************/
- //链表判断
- static inline int list_is_last(const struct list_head* list, const struct list_head*head)
- {
- return list->next==head;
- }
- //是否为空
- static inline int list_empty(const struct list_head*head)
- {
- return (head->next==head);
- }
- /******************************************************************************/
- //遍历链表
- #define list_entry(ptr,type,member) container_of(ptr,type,member)
- #define list_first_entry(ptr, type, member) \\
- list_entry((ptr)->next, type, member)
- #define list_for_each(pos, head) \\
- for (pos = (head)->next;pos != (head); \\
- pos = pos->next)
- //该片段来自于http://www.codesnippet.cn/detail/1311201513976.html
来源: http://www.codesnippet.cn/detail/1311201513976.html