//list.h #pragma once struct list_head { struct list_head *next; struct list_head *prev; }; #define LIST_HEAD(head) struct list_head (head) = { &(head), &(head)} /* inline: 内联，主要修饰函数，内联函数不占用内存空间 当编译器编译时，当发现有内联函数被调用，将拷贝该函数的函数体到调用的位置，省去了函数寻址，传参返回的过程，提高程序执行的效率 弊端： 程序的体积有所增大 特点： 1. inline仅仅是个建议，inline能否成立还需要遵循一些规则 2. 规则： a) 函数功能比较简洁,10行一下的代码量 b) 不允许出现循环、递归、多分支语句，（if支持） c) 不允许使用函数指针指向该函数 d) 一般与static配合使用，防止作用域中名称冲突 */ static inline void INIT_LIST_HEAD(struct list_head *node) { node->next = node; node->prev = node; } static inline void __list_add(struct list_head *node, struct list_head *Prev, struct list_head *Next) { node->next = Next; node->prev = Prev; Prev->next = node; Next->prev = node; } static inline void list_add(struct list_head *node, struct list_head *head) { __list_add(node, head, head->next); } static inline void list_add_tail(struct list_head *node, struct list_head *head) { __list_add(node, head->prev, head); } static inline void list_del(struct list_head *node) { node->prev->next = node->next; node->next->prev = node->prev; } static inline void list_del_init(struct list_head *node) { list_del(node); INIT_LIST_HEAD(node); } static inline int list_is_empty(struct list_head *head) { return head->next == head && head->prev == head; } #define list_for_each(cur, head) for (cur = (head)->next; cur != (head); cur = (cur)->next) #define list_for_each_reverse(cur, head) for (cur = (head)->prev; cur != (head); cur = (cur)->prev) #define list_for_each_safe(cur, Next, head) for (cur = (head)->next; cur != (head) && (Next) = (cur)->next; cur = (Next)) /*小指针转大指针*/ #define offset_of(type, member) ((size_t)&(((type *)0)->member)) #define container_of(ptr, type, member) ((type *)((char *)ptr - offset_of(type, member))) #define list_entry(ptr, type, member) container_of(ptr, type, member) #define list_for_each_from(cur, head)
//sort_list.c #include <stdio.h> #include "list.h" struct data_info { char *name; int age; struct list_head list; }; #define NMEMB(array) ((sizeof array) / sizeof(array[0])) /*比较*/ int cmp_age(const struct list_head *a, const struct list_head *b) { struct data_info *pa = list_entry(a, struct data_info, list); struct data_info *pb = list_entry(b, struct data_info, list); return pa->age - pb->age; } /*交换*/ void swap(struct list_head *a, struct list_head *b) { struct list_head tmp = {NULL, NULL}; __list_add(&tmp, b->prev, b); list_del_init(b); __list_add(b, a->prev, a); list_del_init(a); __list_add(a, tmp.prev, &tmp); list_del_init(&tmp); } void sort_bubble(struct list_head *head, int (*cmp)(const struct list_head *a, const struct list_head *b)) { struct list_head *last, *begin; for (last = head->prev; last != head; last = last->prev) { for (begin = head->next; begin != last; begin = begin->next) { if (cmp(begin, begin->next) > 0) { swap(begin, begin->next); /*重新置位：以从正确位置开始*/ begin = begin->prev; if (begin == last) { last = last->next; } } } } } void sort_select(struct list_head *head, int (*cmp)(const struct list_head *a, const struct list_head *b)) { struct list_head *i, *j, *min; for (i = head->next; i != head->prev; i = i->next) { min = i; for (j = i->next; j != head; j = j->next) { if (cmp(j, min) < 0) { min = j; } } if (min != i) { swap(i, min); /*重新置位*/ i = min; } } } void sort_insert(struct list_head *head, int (*cmp)(const struct list_head *a, const struct list_head *b)) { struct list_head *i, *j; for (i = head->next->next; i != head; i = i->next) { j = i->prev; if (cmp(i , j) > 0) { continue; } list_del_init(i); for (; j != head; j = j->prev) { if (cmp(j, i) <= 0) { break; } } __list_add(i, j, j->next); } } int main() { struct data_info s[] = { {"tom", 18}, {"niko", 22}, {"frank", 17}, {"kevin", 28}, {"richard", 22}, {"mark", 20} , {"tube", 21}, {"jack", 23} }; LIST_HEAD(head); int i; for (i = 0; i < NMEMB(s); ++i) { list_add_tail(&s[i].list, &head); } //swap(&s[0].list, &s[1].list); struct data_info *pdata = NULL; list_for_each_entry(pdata, &head, list) { printf("%s:%d ", pdata->name, pdata->age); } printf(".......sorting.... "); //sort_bubble(&head, cmp_age); sort_select(&head, cmp_age); //sort_insert(&head, cmp_age); list_for_each_entry(pdata, &head, list) { printf("%s:%d ", pdata->name, pdata->age); } return 0; }
for (; cur != (head); cur = (cur)->next) #define list_for_each_continue(cur, head) for (cur = (cur)->next; cur != (head); cur = (cur)->next) #define list_for_each_from_safe(cur, Next, head) for (; (cur != (head)) && (Next = (cur)->next); cur = Next) #define list_for_each_continue_safe(cur, Next, head) for (cur = (cur)->next; (cur != (head)) && (Next = (cur)->next); cur = Next) #define list_for_each_entry(Pos, head, member) for (Pos = list_entry((head)->next, typeof(*Pos), member); &((Pos)->member) != (head); Pos = list_entry((Pos)->member.next, typeof(*Pos),member))