• linux 内核链表详解

    目录

    1. 老生常谈的两个宏（Linux）

    offset

    测试demo

    container_of

    ({})

    Typeof

    推算结构体起始地址

     测试demo

    2. Linux内核链表剖析

    移植linux内核链表，使其适用于非GNU编译器

    Linux内核链表的位置和依赖

    移植时的注意事项

    移植好的LinuxList.h

    分析linux内核中链表的基本实现

    linux内核链表的实现

    linux内核链表的结点定义 

    测试demo

    C/C++Linux服务器开发/后台架构师【零声教育】-学习视频教程-腾讯课堂

    1. 老生常谈的两个宏（Linux）

    offset

    1. //offsetof用于计算TYPE结构体中MEMBER成员的偏移位置
    2.  
    3. #ifndef offsetof
    4.  
    5. #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE*)0)->MEMBER)
    6.  
    7. #endif

    测试demo

    1. #include <stdio.h>
    2.  
    3. #ifndef offsetof
    4.  
    5. #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE*)0)->MEMBER)
    6.  
    7. #endif
    8.  
    9. struct ST
    10.  
    11. {
    12.  
    13.     int i;     // 0
    14.  
    15.     int j;     // 4
    16.  
    17.     char c;    // 8
    18.  
    19. };
    20.  
    21. void func(struct ST* pst)
    22.  
    23. {
    24.  
    25.     int* pi = &(pst->i);    //  0
    26.  
    27.     int* pj = &(pst->j);    //  4
    28.  
    29.     char* pc = &(pst->c);   //  8
    30.  
    31.     printf("pst = %p\n", pst);
    32.  
    33.     printf("pi = %p\n", pi);
    34.  
    35.     printf("pj = %p\n", pj);
    36.  
    37.     printf("pc = %p\n", pc);
    38.  
    39. }
    40.  
    41. int main()
    42.  
    43. {
    44.  
    45.     struct ST s = {0};
    46.  
    47.     func(&s);
    48.  
    49.     func(NULL);
    50.  
    51.     printf("offset i: %d\n", offsetof(struct ST, i));
    52.  
    53.     printf("offset j: %d\n", offsetof(struct ST, j));
    54.  
    55.     printf("offset c: %d\n", offsetof(struct ST, c));
    56.  
    57.     return 0;
    58.  
    59. }

     

    container_of

    ({})

    Typeof

    推算结构体起始地址

    1.typeof(((type*)0)->member)*得到成员数据类型的指针，ptr为指向结构体成员的指针。这样写可进行类型检查。

    2.((char*)__mptr - offsetof(type, member));结构体成员的地址-成员的偏移量来算出结构体的起始地址。

    1. //推算结构体起始地址
    2.  
    3. #ifndef container_of
    4.  
    5. #define container_of(ptr, type, member) ({          \
    6.  
    7.         const typeof(((type*)0)->member)* __mptr = (ptr);   \
    8.  
    9.         (type*)((char*)__mptr - offsetof(type, member)); })
    10.  
    11. #endif

     测试demo

    1. #include <stdio.h>
    2. //offsetof用于计算TYPE结构体中MEMBER成员的偏移位置
    3. #ifndef offsetof
    4. #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE*)0)->MEMBER)
    5. #endif
    6. //推算结构体起始地址
    7. #ifndef container_of
    8. #define container_of(ptr, type, member) ({		         \
    9.         const typeof(((type*)0)->member)* __mptr = (ptr);   \
    10.         (type*)((char*)__mptr - offsetof(type, member)); })
    11. #endif
    12. //修改后的container_of
    13. #ifndef container_of_new
    14. #define container_of_new(ptr, type, member) ((type*)((char*)(ptr) - offsetof(type, member)))
    15. #endif
    16. struct ST
    17. {
    18.     int i;     // 0
    19.     int j;     // 4
    20.     char c;    // 8
    21. };
    22. int main()
    23. {
    24.     struct ST s = {0};
    25.     char* pc = &s.c;
    26.     struct ST* pst = container_of(pc, struct ST, c);
    27.     printf("&s = %p\n", &s);
    28.     printf("pst = %p\n", pst);
    29.     return 0;
    30. }

     

     

    2. Linux内核链表剖析

    移植linux内核链表，使其适用于非GNU编译器

    Linux内核链表的位置和依赖

    移植时的注意事项

     

    移植好的LinuxList.h

    1. #ifndef _LINUX_LIST_H
    2. #define _LINUX_LIST_H
    3.  
    4. // #include <linux/types.h>
    5. // #include <linux/stddef.h>
    6. // #include <linux/poison.h>
    7. // #include <linux/prefetch.h>
    8.  
    9. #ifndef offsetof
    10. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    11. #endif
    12.  
    13. #ifndef container_of
    14. #define container_of(ptr, type, member) ((type *)((char *)ptr - offsetof(type,member)))
    15. #endif
    16.  
    17. #define prefetch(x) ((void)x)
    18.  
    19. #define LIST_POISON1  (NULL)
    20. #define LIST_POISON2  (NULL)
    21.  
    22. struct list_head {
    23.     struct list_head *next, *prev;
    24. };
    25.  
    26. struct hlist_head {
    27.     struct hlist_node *first;
    28. };
    29.  
    30. struct hlist_node {
    31.     struct hlist_node *next, **pprev;
    32. };
    33.  
    34. /*
    35.  * Simple doubly linked list implementation.
    36.  *
    37.  * Some of the internal functions ("__xxx") are useful when
    38.  * manipulating whole lists rather than single entries, as
    39.  * sometimes we already know the next/prev entries and we can
    40.  * generate better code by using them directly rather than
    41.  * using the generic single-entry routines.
    42.  */
    44. #define LIST_HEAD_INIT(name) { &(name), &(name) }
    45.  
    46. #define LIST_HEAD(name) \
    47.     struct list_head name = LIST_HEAD_INIT(name)
    48.  
    49. static void INIT_LIST_HEAD(struct list_head *list)
    50. {
    51.     list->next = list;
    52.     list->prev = list;
    53. }
    54.  
    55. /*
    56.  * Insert a new entry between two known consecutive entries.
    57.  *
    58.  * This is only for internal list manipulation where we know
    59.  * the prev/next entries already!
    60.  */
    61. #ifndef CONFIG_DEBUG_LIST
    62. static void __list_add(struct list_head *new,
    63.                   struct list_head *prev,
    64.                   struct list_head *next)
    65. {
    66.     next->prev = new;
    67.     new->next = next;
    68.     new->prev = prev;
    69.     prev->next = new;
    70. }
    71. #else
    72. extern void __list_add(struct list_head *new,
    73.                   struct list_head *prev,
    74.                   struct list_head *next);
    75. #endif
    76.  
    77. /**
    78.  * list_add - add a new entry
    79.  * @new: new entry to be added
    80.  * @head: list head to add it after
    81.  *
    82.  * Insert a new entry after the specified head.
    83.  * This is good for implementing stacks.
    84.  */
    85. static void list_add(struct list_head *new, struct list_head *head)
    86. {
    87.     __list_add(new, head, head->next);
    88. }
    89.  
    90.  
    91. /**
    92.  * list_add_tail - add a new entry
    93.  * @new: new entry to be added
    94.  * @head: list head to add it before
    95.  *
    96.  * Insert a new entry before the specified head.
    97.  * This is useful for implementing queues.
    98.  */
    99. static void list_add_tail(struct list_head *new, struct list_head *head)
    100. {
    101.     __list_add(new, head->prev, head);
    102. }
    103.  
    104. /*
    105.  * Delete a list entry by making the prev/next entries
    106.  * point to each other.
    107.  *
    108.  * This is only for internal list manipulation where we know
    109.  * the prev/next entries already!
    110.  */
    111. static void __list_del(struct list_head * prev, struct list_head * next)
    112. {
    113.     next->prev = prev;
    114.     prev->next = next;
    115. }
    116.  
    117. /**
    118.  * list_del - deletes entry from list.
    119.  * @entry: the element to delete from the list.
    120.  * Note: list_empty() on entry does not return true after this, the entry is
    121.  * in an undefined state.
    122.  */
    123. #ifndef CONFIG_DEBUG_LIST
    124. static void __list_del_entry(struct list_head *entry)
    125. {
    126.     __list_del(entry->prev, entry->next);
    127. }
    128.  
    129. static void list_del(struct list_head *entry)
    130. {
    131.     __list_del(entry->prev, entry->next);
    132.     entry->next = LIST_POISON1;
    133.     entry->prev = LIST_POISON2;
    134. }
    135. #else
    136. extern void __list_del_entry(struct list_head *entry);
    137. extern void list_del(struct list_head *entry);
    138. #endif
    139.  
    140. /**
    141.  * list_replace - replace old entry by new one
    142.  * @old : the element to be replaced
    143.  * @new : the new element to insert
    144.  *
    145.  * If @old was empty, it will be overwritten.
    146.  */
    147. static void list_replace(struct list_head *old,
    148.                 struct list_head *new)
    149. {
    150.     new->next = old->next;
    151.     new->next->prev = new;
    152.     new->prev = old->prev;
    153.     new->prev->next = new;
    154. }
    155.  
    156. static void list_replace_init(struct list_head *old,
    157.                     struct list_head *new)
    158. {
    159.     list_replace(old, new);
    160.     INIT_LIST_HEAD(old);
    161. }
    162.  
    163. /**
    164.  * list_del_init - deletes entry from list and reinitialize it.
    165.  * @entry: the element to delete from the list.
    166.  */
    167. static void list_del_init(struct list_head *entry)
    168. {
    169.     __list_del_entry(entry);
    170.     INIT_LIST_HEAD(entry);
    171. }
    172.  
    173. /**
    174.  * list_move - delete from one list and add as another's head
    175.  * @list: the entry to move
    176.  * @head: the head that will precede our entry
    177.  */
    178. static void list_move(struct list_head *list, struct list_head *head)
    179. {
    180.     __list_del_entry(list);
    181.     list_add(list, head);
    182. }
    183.  
    184. /**
    185.  * list_move_tail - delete from one list and add as another's tail
    186.  * @list: the entry to move
    187.  * @head: the head that will follow our entry
    188.  */
    189. static void list_move_tail(struct list_head *list,
    190.                   struct list_head *head)
    191. {
    192.     __list_del_entry(list);
    193.     list_add_tail(list, head);
    194. }
    195.  
    196. /**
    197.  * list_is_last - tests whether @list is the last entry in list @head
    198.  * @list: the entry to test
    199.  * @head: the head of the list
    200.  */
    201. static int list_is_last(const struct list_head *list,
    202.                 const struct list_head *head)
    203. {
    204.     return list->next == head;
    205. }
    206.  
    207. /**
    208.  * list_empty - tests whether a list is empty
    209.  * @head: the list to test.
    210.  */
    211. static int list_empty(const struct list_head *head)
    212. {
    213.     return head->next == head;
    214. }
    215.  
    216. /**
    217.  * list_empty_careful - tests whether a list is empty and not being modified
    218.  * @head: the list to test
    219.  *
    220.  * Description:
    221.  * tests whether a list is empty _and_ checks that no other CPU might be
    222.  * in the process of modifying either member (next or prev)
    223.  *
    224.  * NOTE: using list_empty_careful() without synchronization
    225.  * can only be safe if the only activity that can happen
    226.  * to the list entry is list_del_init(). Eg. it cannot be used
    227.  * if another CPU could re-list_add() it.
    228.  */
    229. static int list_empty_careful(const struct list_head *head)
    230. {
    231.     struct list_head *next = head->next;
    232.     return (next == head) && (next == head->prev);
    233. }
    234.  
    235. /**
    236.  * list_rotate_left - rotate the list to the left
    237.  * @head: the head of the list
    238.  */
    239. static void list_rotate_left(struct list_head *head)
    240. {
    241.     struct list_head *first;
    242.  
    243.     if (!list_empty(head)) {
    244.         first = head->next;
    245.         list_move_tail(first, head);
    246.     }
    247. }
    248.  
    249. /**
    250.  * list_is_singular - tests whether a list has just one entry.
    251.  * @head: the list to test.
    252.  */
    253. static int list_is_singular(const struct list_head *head)
    254. {
    255.     return !list_empty(head) && (head->next == head->prev);
    256. }
    257.  
    258. static void __list_cut_position(struct list_head *list,
    259.         struct list_head *head, struct list_head *entry)
    260. {
    261.     struct list_head *new_first = entry->next;
    262.     list->next = head->next;
    263.     list->next->prev = list;
    264.     list->prev = entry;
    265.     entry->next = list;
    266.     head->next = new_first;
    267.     new_first->prev = head;
    268. }
    269.  
    270. /**
    271.  * list_cut_position - cut a list into two
    272.  * @list: a new list to add all removed entries
    273.  * @head: a list with entries
    274.  * @entry: an entry within head, could be the head itself
    275.  *	and if so we won't cut the list
    276.  *
    277.  * This helper moves the initial part of @head, up to and
    278.  * including @entry, from @head to @list. You should
    279.  * pass on @entry an element you know is on @head. @list
    280.  * should be an empty list or a list you do not care about
    281.  * losing its data.
    282.  *
    283.  */
    284. static void list_cut_position(struct list_head *list,
    285.         struct list_head *head, struct list_head *entry)
    286. {
    287.     if (list_empty(head))
    288.         return;
    289.     if (list_is_singular(head) &&
    290.         (head->next != entry && head != entry))
    291.         return;
    292.     if (entry == head)
    293.         INIT_LIST_HEAD(list);
    294.     else
    295.         __list_cut_position(list, head, entry);
    296. }
    297.  
    298. static void __list_splice(const struct list_head *list,
    299.                  struct list_head *prev,
    300.                  struct list_head *next)
    301. {
    302.     struct list_head *first = list->next;
    303.     struct list_head *last = list->prev;
    304.  
    305.     first->prev = prev;
    306.     prev->next = first;
    307.  
    308.     last->next = next;
    309.     next->prev = last;
    310. }
    311.  
    312. /**
    313.  * list_splice - join two lists, this is designed for stacks
    314.  * @list: the new list to add.
    315.  * @head: the place to add it in the first list.
    316.  */
    317. static void list_splice(const struct list_head *list,
    318.                 struct list_head *head)
    319. {
    320.     if (!list_empty(list))
    321.         __list_splice(list, head, head->next);
    322. }
    323.  
    324. /**
    325.  * list_splice_tail - join two lists, each list being a queue
    326.  * @list: the new list to add.
    327.  * @head: the place to add it in the first list.
    328.  */
    329. static void list_splice_tail(struct list_head *list,
    330.                 struct list_head *head)
    331. {
    332.     if (!list_empty(list))
    333.         __list_splice(list, head->prev, head);
    334. }
    335.  
    336. /**
    337.  * list_splice_init - join two lists and reinitialise the emptied list.
    338.  * @list: the new list to add.
    339.  * @head: the place to add it in the first list.
    340.  *
    341.  * The list at @list is reinitialised
    342.  */
    343. static void list_splice_init(struct list_head *list,
    344.                     struct list_head *head)
    345. {
    346.     if (!list_empty(list)) {
    347.         __list_splice(list, head, head->next);
    348.         INIT_LIST_HEAD(list);
    349.     }
    350. }
    351.  
    352. /**
    353.  * list_splice_tail_init - join two lists and reinitialise the emptied list
    354.  * @list: the new list to add.
    355.  * @head: the place to add it in the first list.
    356.  *
    357.  * Each of the lists is a queue.
    358.  * The list at @list is reinitialised
    359.  */
    360. static void list_splice_tail_init(struct list_head *list,
    361.                      struct list_head *head)
    362. {
    363.     if (!list_empty(list)) {
    364.         __list_splice(list, head->prev, head);
    365.         INIT_LIST_HEAD(list);
    366.     }
    367. }
    368.  
    369. /**
    370.  * list_entry - get the struct for this entry
    371.  * @ptr:	the &struct list_head pointer.
    372.  * @type:	the type of the struct this is embedded in.
    373.  * @member:	the name of the list_struct within the struct.
    374.  */
    375. #define list_entry(ptr, type, member) \
    376.     container_of(ptr, type, member)
    377.  
    378. /**
    379.  * list_first_entry - get the first element from a list
    380.  * @ptr:	the list head to take the element from.
    381.  * @type:	the type of the struct this is embedded in.
    382.  * @member:	the name of the list_struct within the struct.
    383.  *
    384.  * Note, that list is expected to be not empty.
    385.  */
    386. #define list_first_entry(ptr, type, member) \
    387.     list_entry((ptr)->next, type, member)
    388.  
    389. /**
    390.  * list_for_each	-	iterate over a list
    391.  * @pos:	the &struct list_head to use as a loop cursor.
    392.  * @head:	the head for your list.
    393.  */
    394. #define list_for_each(pos, head) \
    395.     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
    396.             pos = pos->next)
    397.  
    398. /**
    399.  * __list_for_each	-	iterate over a list
    400.  * @pos:	the &struct list_head to use as a loop cursor.
    401.  * @head:	the head for your list.
    402.  *
    403.  * This variant differs from list_for_each() in that it's the
    404.  * simplest possible list iteration code, no prefetching is done.
    405.  * Use this for code that knows the list to be very short (empty
    406.  * or 1 entry) most of the time.
    407.  */
    408. #define __list_for_each(pos, head) \
    409.     for (pos = (head)->next; pos != (head); pos = pos->next)
    410.  
    411. /**
    412.  * list_for_each_prev	-	iterate over a list backwards
    413.  * @pos:	the &struct list_head to use as a loop cursor.
    414.  * @head:	the head for your list.
    415.  */
    416. #define list_for_each_prev(pos, head) \
    417.     for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
    418.             pos = pos->prev)
    419.  
    420. /**
    421.  * list_for_each_safe - iterate over a list safe against removal of list entry
    422.  * @pos:	the &struct list_head to use as a loop cursor.
    423.  * @n:		another &struct list_head to use as temporary storage
    424.  * @head:	the head for your list.
    425.  */
    426. #define list_for_each_safe(pos, n, head) \
    427.     for (pos = (head)->next, n = pos->next; pos != (head); \
    428.         pos = n, n = pos->next)
    429.  
    430. /**
    431.  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
    432.  * @pos:	the &struct list_head to use as a loop cursor.
    433.  * @n:		another &struct list_head to use as temporary storage
    434.  * @head:	the head for your list.
    435.  */
    436. #define list_for_each_prev_safe(pos, n, head) \
    437.     for (pos = (head)->prev, n = pos->prev; \
    438.          prefetch(pos->prev), pos != (head); \
    439.          pos = n, n = pos->prev)
    440.  
    441. /**
    442.  * list_for_each_entry	-	iterate over list of given type
    443.  * @pos:	the type * to use as a loop cursor.
    444.  * @head:	the head for your list.
    445.  * @member:	the name of the list_struct within the struct.
    446.  */
    447. #define list_for_each_entry(pos, head, member)				\
    448.     for (pos = list_entry((head)->next, typeof(*pos), member);	\
    449.          prefetch(pos->member.next), &pos->member != (head); 	\
    450.          pos = list_entry(pos->member.next, typeof(*pos), member))
    451.  
    452. /**
    453.  * list_for_each_entry_reverse - iterate backwards over list of given type.
    454.  * @pos:	the type * to use as a loop cursor.
    455.  * @head:	the head for your list.
    456.  * @member:	the name of the list_struct within the struct.
    457.  */
    458. #define list_for_each_entry_reverse(pos, head, member)			\
    459.     for (pos = list_entry((head)->prev, typeof(*pos), member);	\
    460.          prefetch(pos->member.prev), &pos->member != (head); 	\
    461.          pos = list_entry(pos->member.prev, typeof(*pos), member))
    462.  
    463. /**
    464.  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
    465.  * @pos:	the type * to use as a start point
    466.  * @head:	the head of the list
    467.  * @member:	the name of the list_struct within the struct.
    468.  *
    469.  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
    470.  */
    471. #define list_prepare_entry(pos, head, member) \
    472.     ((pos) ? : list_entry(head, typeof(*pos), member))
    473.  
    474. /**
    475.  * list_for_each_entry_continue - continue iteration over list of given type
    476.  * @pos:	the type * to use as a loop cursor.
    477.  * @head:	the head for your list.
    478.  * @member:	the name of the list_struct within the struct.
    479.  *
    480.  * Continue to iterate over list of given type, continuing after
    481.  * the current position.
    482.  */
    483. #define list_for_each_entry_continue(pos, head, member) 		\
    484.     for (pos = list_entry(pos->member.next, typeof(*pos), member);	\
    485.          prefetch(pos->member.next), &pos->member != (head);	\
    486.          pos = list_entry(pos->member.next, typeof(*pos), member))
    487.  
    488. /**
    489.  * list_for_each_entry_continue_reverse - iterate backwards from the given point
    490.  * @pos:	the type * to use as a loop cursor.
    491.  * @head:	the head for your list.
    492.  * @member:	the name of the list_struct within the struct.
    493.  *
    494.  * Start to iterate over list of given type backwards, continuing after
    495.  * the current position.
    496.  */
    497. #define list_for_each_entry_continue_reverse(pos, head, member)		\
    498.     for (pos = list_entry(pos->member.prev, typeof(*pos), member);	\
    499.          prefetch(pos->member.prev), &pos->member != (head);	\
    500.          pos = list_entry(pos->member.prev, typeof(*pos), member))
    501.  
    502. /**
    503.  * list_for_each_entry_from - iterate over list of given type from the current point
    504.  * @pos:	the type * to use as a loop cursor.
    505.  * @head:	the head for your list.
    506.  * @member:	the name of the list_struct within the struct.
    507.  *
    508.  * Iterate over list of given type, continuing from current position.
    509.  */
    510. #define list_for_each_entry_from(pos, head, member) 			\
    511.     for (; prefetch(pos->member.next), &pos->member != (head);	\
    512.          pos = list_entry(pos->member.next, typeof(*pos), member))
    513.  
    514. /**
    515.  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
    516.  * @pos:	the type * to use as a loop cursor.
    517.  * @n:		another type * to use as temporary storage
    518.  * @head:	the head for your list.
    519.  * @member:	the name of the list_struct within the struct.
    520.  */
    521. #define list_for_each_entry_safe(pos, n, head, member)			\
    522.     for (pos = list_entry((head)->next, typeof(*pos), member),	\
    523.         n = list_entry(pos->member.next, typeof(*pos), member);	\
    524.          &pos->member != (head); 					\
    525.          pos = n, n = list_entry(n->member.next, typeof(*n), member))
    526.  
    527. /**
    528.  * list_for_each_entry_safe_continue - continue list iteration safe against removal
    529.  * @pos:	the type * to use as a loop cursor.
    530.  * @n:		another type * to use as temporary storage
    531.  * @head:	the head for your list.
    532.  * @member:	the name of the list_struct within the struct.
    533.  *
    534.  * Iterate over list of given type, continuing after current point,
    535.  * safe against removal of list entry.
    536.  */
    537. #define list_for_each_entry_safe_continue(pos, n, head, member) 		\
    538.     for (pos = list_entry(pos->member.next, typeof(*pos), member), 		\
    539.         n = list_entry(pos->member.next, typeof(*pos), member);		\
    540.          &pos->member != (head);						\
    541.          pos = n, n = list_entry(n->member.next, typeof(*n), member))
    542.  
    543. /**
    544.  * list_for_each_entry_safe_from - iterate over list from current point safe against removal
    545.  * @pos:	the type * to use as a loop cursor.
    546.  * @n:		another type * to use as temporary storage
    547.  * @head:	the head for your list.
    548.  * @member:	the name of the list_struct within the struct.
    549.  *
    550.  * Iterate over list of given type from current point, safe against
    551.  * removal of list entry.
    552.  */
    553. #define list_for_each_entry_safe_from(pos, n, head, member) 			\
    554.     for (n = list_entry(pos->member.next, typeof(*pos), member);		\
    555.          &pos->member != (head);						\
    556.          pos = n, n = list_entry(n->member.next, typeof(*n), member))
    557.  
    558. /**
    559.  * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
    560.  * @pos:	the type * to use as a loop cursor.
    561.  * @n:		another type * to use as temporary storage
    562.  * @head:	the head for your list.
    563.  * @member:	the name of the list_struct within the struct.
    564.  *
    565.  * Iterate backwards over list of given type, safe against removal
    566.  * of list entry.
    567.  */
    568. #define list_for_each_entry_safe_reverse(pos, n, head, member)		\
    569.     for (pos = list_entry((head)->prev, typeof(*pos), member),	\
    570.         n = list_entry(pos->member.prev, typeof(*pos), member);	\
    571.          &pos->member != (head); 					\
    572.          pos = n, n = list_entry(n->member.prev, typeof(*n), member))
    573.  
    574. /**
    575.  * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
    576.  * @pos:	the loop cursor used in the list_for_each_entry_safe loop
    577.  * @n:		temporary storage used in list_for_each_entry_safe
    578.  * @member:	the name of the list_struct within the struct.
    579.  *
    580.  * list_safe_reset_next is not safe to use in general if the list may be
    581.  * modified concurrently (eg. the lock is dropped in the loop body). An
    582.  * exception to this is if the cursor element (pos) is pinned in the list,
    583.  * and list_safe_reset_next is called after re-taking the lock and before
    584.  * completing the current iteration of the loop body.
    585.  */
    586. #define list_safe_reset_next(pos, n, member)				\
    587.     n = list_entry(pos->member.next, typeof(*pos), member)
    588.  
    589. /*
    590.  * Double linked lists with a single pointer list head.
    591.  * Mostly useful for hash tables where the two pointer list head is
    592.  * too wasteful.
    593.  * You lose the ability to access the tail in O(1).
    594.  */
    596. #define HLIST_HEAD_INIT { .first = NULL }
    597. #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
    598. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
    599. static void INIT_HLIST_NODE(struct hlist_node *h)
    600. {
    601.     h->next = NULL;
    602.     h->pprev = NULL;
    603. }
    604.  
    605. static int hlist_unhashed(const struct hlist_node *h)
    606. {
    607.     return !h->pprev;
    608. }
    609.  
    610. static int hlist_empty(const struct hlist_head *h)
    611. {
    612.     return !h->first;
    613. }
    614.  
    615. static void __hlist_del(struct hlist_node *n)
    616. {
    617.     struct hlist_node *next = n->next;
    618.     struct hlist_node **pprev = n->pprev;
    619.     *pprev = next;
    620.     if (next)
    621.         next->pprev = pprev;
    622. }
    623.  
    624. static void hlist_del(struct hlist_node *n)
    625. {
    626.     __hlist_del(n);
    627.     n->next = LIST_POISON1;
    628.     n->pprev = LIST_POISON2;
    629. }
    630.  
    631. static void hlist_del_init(struct hlist_node *n)
    632. {
    633.     if (!hlist_unhashed(n)) {
    634.         __hlist_del(n);
    635.         INIT_HLIST_NODE(n);
    636.     }
    637. }
    638.  
    639. static void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
    640. {
    641.     struct hlist_node *first = h->first;
    642.     n->next = first;
    643.     if (first)
    644.         first->pprev = &n->next;
    645.     h->first = n;
    646.     n->pprev = &h->first;
    647. }
    648.  
    649. /* next must be != NULL */
    650. static void hlist_add_before(struct hlist_node *n,
    651.                     struct hlist_node *next)
    652. {
    653.     n->pprev = next->pprev;
    654.     n->next = next;
    655.     next->pprev = &n->next;
    656.     *(n->pprev) = n;
    657. }
    658.  
    659. static void hlist_add_after(struct hlist_node *n,
    660.                     struct hlist_node *next)
    661. {
    662.     next->next = n->next;
    663.     n->next = next;
    664.     next->pprev = &n->next;
    665.  
    666.     if(next->next)
    667.         next->next->pprev  = &next->next;
    668. }
    669.  
    670. /* after that we'll appear to be on some hlist and hlist_del will work */
    671. static void hlist_add_fake(struct hlist_node *n)
    672. {
    673.     n->pprev = &n->next;
    674. }
    676. /*
    677.  * Move a list from one list head to another. Fixup the pprev
    678.  * reference of the first entry if it exists.
    679.  */
    680. static void hlist_move_list(struct hlist_head *old,
    681.                    struct hlist_head *new)
    682. {
    683.     new->first = old->first;
    684.     if (new->first)
    685.         new->first->pprev = &new->first;
    686.     old->first = NULL;
    687. }
    689. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
    691. #define hlist_for_each(pos, head) \
    692.     for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
    693.          pos = pos->next)
    695. #define hlist_for_each_safe(pos, n, head) \
    696.     for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
    697.          pos = n)
    699. /**
    700.  * hlist_for_each_entry	- iterate over list of given type
    701.  * @tpos:	the type * to use as a loop cursor.
    702.  * @pos:	the &struct hlist_node to use as a loop cursor.
    703.  * @head:	the head for your list.
    704.  * @member:	the name of the hlist_node within the struct.
    705.  */
    706. #define hlist_for_each_entry(tpos, pos, head, member)			 \
    707.     for (pos = (head)->first;					 \
    708.          pos && ({ prefetch(pos->next); 1;}) &&			 \
    709.         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    710.          pos = pos->next)
    712. /**
    713.  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
    714.  * @tpos:	the type * to use as a loop cursor.
    715.  * @pos:	the &struct hlist_node to use as a loop cursor.
    716.  * @member:	the name of the hlist_node within the struct.
    717.  */
    718. #define hlist_for_each_entry_continue(tpos, pos, member)		 \
    719.     for (pos = (pos)->next;						 \
    720.          pos && ({ prefetch(pos->next); 1;}) &&			 \
    721.         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    722.          pos = pos->next)
    724. /**
    725.  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
    726.  * @tpos:	the type * to use as a loop cursor.
    727.  * @pos:	the &struct hlist_node to use as a loop cursor.
    728.  * @member:	the name of the hlist_node within the struct.
    729.  */
    730. #define hlist_for_each_entry_from(tpos, pos, member)			 \
    731.     for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
    732.         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    733.          pos = pos->next)
    735. /**
    736.  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
    737.  * @tpos:	the type * to use as a loop cursor.
    738.  * @pos:	the &struct hlist_node to use as a loop cursor.
    739.  * @n:		another &struct hlist_node to use as temporary storage
    740.  * @head:	the head for your list.
    741.  * @member:	the name of the hlist_node within the struct.
    742.  */
    743. #define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
    744.     for (pos = (head)->first;					 \
    745.          pos && ({ n = pos->next; 1; }) && 				 \
    746.         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
    747.          pos = n)
    749. #endif

    分析linux内核中链表的基本实现

    linux内核链表的实现

    1. 带头结点的双向循环链表，且头结点为表中成员。
    2. 头结点的next指针指向首结点。
    3. 头结点的prev指针指向尾节点

    linux内核链表的结点定义 

    1. struct list_head {
    2.     struct list_head *next, *prev;
    3. };

    使用list_head自定义链表结点来存放数据

    1. struct Node
    2. {
    3.     struct list_head head;
    4.     int value;
    5. };

    测试demo

    Main.c

    1. #include <stdio.h>
    2. #include "LinuxList.h"
    3. void list_demo()
    4. {
    5.     struct Node
    6.     {
    7.         struct list_head head;
    8.         int value;
    9.     };
    10.     struct Node l = {0};
    11.     struct list_head* list = &l.head;
    12.     struct list_head* slider = NULL;
    13.     int i = 0;
    14.     INIT_LIST_HEAD(list);
    15.     printf("Insert begin ...\n");
    16.     for(i=0; i<5; i++)
    17.     {
    18.         struct Node* n = (struct Node*)malloc(sizeof(struct Node));
    19.         n->value = i;
    20.         list_add(&n->head, list);
    21.     }
    22.     list_for_each(slider, list)
    23.     {
    24.         //list_entry -> container_of
    25.         printf("%d\n", list_entry(slider, struct Node, head)->value);
    26.     }
    27.     printf("Insert end ...\n");
    28.     printf("Delete begin ...\n");
    29.     list_for_each(slider, list)
    30.     {
    31.         struct Node* n = list_entry(slider, struct Node, head);
    32.         if( n->value == 3 )
    33.         {
    34.             list_del(slider);
    35.             free(n);
    36.             break;
    37.         }
    38.     }
    39.     list_for_each(slider, list)
    40.     {
    41.         printf("%d\n", list_entry(slider, struct Node, head)->value);
    42.     }
    43.     printf("Delete end ...\n");
    44. }
    45. int main()
    46. {
    47.     list_demo();
    48.     return 0;
    49. }

  • 相关阅读:
    [HDLBits] Fsm2s
    C++ Mysql对接实现登录注册
    基于阿里云 Serverless 快速部署 function 的极致体验
    【C/C++】string类的使用&&探索string底层原理
    BigDecimal使用
    C语言 | 类型的基本归类
    JavaScript系列从入门到精通系列第七篇：JavaScrip当中的运算符，主要涉及JavaScript当中的六大数据类型的四则运算
    向量化操作简介和Pandas、Numpy示例
    linux设置ssh免密登录
    【vue】下载导出excel
  • 原文地址：https://blog.csdn.net/kakaka666/article/details/127834244