通用双向循环链表操作函数集:你能想到、不能想到的都在这里了
发布日期:2021-06-23 04:43:55 浏览次数:3 分类:技术文章

本文共 22693 字,大约阅读时间需要 75 分钟。

前言

双向链表操作由于涉及多个指针,很容易出错。而我们在工作中有不可避免的会使用到,为了一劳永逸的解决问题,特意将Linux源码中的list.h略作整理,并结合多个项目中的实现,最终整理了一份很全面的双向链表操作函数的头文件,以后再遇到双向链表的问题,应该不用再发愁了。我们只需要专注我们自己的功能实现即可,无需再花费很多时间来写双向链表操作函数。

头文件

在这里插入图片描述

/**************************************************************************** *******                                                              ******* *******                D O U B L E      L I S T                      ******* *******                                                              ******* **************************************************************************** Author  :  Date    : 21-June-2020 * *  (C) 1990 - 2000 Specialix International Ltd., Byfleet, Surrey, UK. * *      This program is free software; you can redistribute it and/or modify *      it under the terms of the GNU General Public License as published by *      the Free Software Foundation; either version 2 of the License, or *      (at your option) any later version. * *      This program is distributed in the hope that it will be useful, *      but WITHOUT ANY WARRANTY; without even the implied warranty of *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the *      GNU General Public License for more details. * *      You should have received a copy of the GNU General Public License *      along with this program; if not, write to the Free Software *      Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. Version : 0.01                            Mods ----------------------------------------------------------------------------  Date     		By                Description ---------------------------------------------------------------------------- 2020.6.21		Toney				整理接口  ***************************************************************************/#ifndef _list_h#define _list_h 1   /* * Simple doubly linked list implementation of User space. * * Some of the internal functions ("__xxx") are useful when * manipulating whole lists rather than single entries, as * sometimes we already know the next/prev entries and we can * generate better code by using them directly rather than * using the generic single-entry routines. */ #ifdef __cplusplusextern "C" {
#endif struct list_head {
struct list_head *next, *prev;};/********************************************************* 0. 重要的工具宏**********************************************************//* * Copied from include/linux/... */#undef offsetof#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)/** * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})/********************************************************* 1. 创建、初始化双向链表**********************************************************/#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)#define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \} while (0)/********************************************************* 2. 添加新节点:头插和尾插**********************************************************//* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */static inline void__list_add(struct list_head *entry, struct list_head *prev, struct list_head *next){
next->prev = entry; entry->next = next; entry->prev = prev; prev->next = entry;}/** * Insert a new element after the given list head. The new element does not * need to be initialised as empty list. * The list changes from: * head → some element → ... * to * head → new element → older element → ... * * Example: * struct foo *newfoo = malloc(...); * list_add(&newfoo->entry, &bar->list_of_foos); * * @param entry The new element to prepend to the list. * @param head The existing list. */static inline voidlist_add(struct list_head *entry, struct list_head *head){
__list_add(entry, head, head->next);}/** * Append a new element to the end of the list given with this list head. * * The list changes from: * head → some element → ... → lastelement * to * head → some element → ... → lastelement → new element * * Example: * struct foo *newfoo = malloc(...); * list_add_tail(&newfoo->entry, &bar->list_of_foos); * * @param entry The new element to prepend to the list. * @param head The existing list. */static inline voidlist_add_tail(struct list_head *entry, struct list_head *head){
__list_add(entry, head->prev, head);}/********************************************************* 3. 删除节点**********************************************************/static inline void__list_del(struct list_head *prev, struct list_head *next){
next->prev = prev; prev->next = next;}/** * Remove the element from the list it is in. Using this function will reset * the pointers to/from this element so it is removed from the list. It does * NOT free the element itself or manipulate it otherwise. * * Using list_del on a pure list head (like in the example at the top of * this file) will NOT remove the first element from * the list but rather reset the list as empty list. * * Example: * list_del(&foo->entry); * * @param entry The element to remove. */static inline voidlist_del(struct list_head *entry){
__list_del(entry->prev, entry->next);}/** * delete entry from double linklist, and initiate entry */static inline voidlist_del_init(struct list_head *entry){
__list_del(entry->prev, entry->next); INIT_LIST_HEAD(entry);}/** * delete entry from A double linklist, * and insert to B double linklist */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);}/********************************************************* 4. 检查链表是否为空**********************************************************//** * Check if the list is empty. * * Example: * list_empty(&bar->list_of_foos); * * @return True if the list contains one or more elements or False otherwise. */static inline intlist_empty(const struct list_head *head){
return head->next == head;}/** * list_empty_careful - tests whether a list is empty and not being modified * @head: the list to test * * Description: * tests whether a list is empty _and_ checks that no other CPU might be * in the process of modifying either member (next or prev) * * NOTE: using list_empty_careful() without synchronization * can only be safe if the only activity that can happen * to the list entry is list_del_init(). Eg. it cannot be used * if another CPU could re-list_add() it. */static inline int list_empty_careful(const struct list_head *head){
struct list_head *next = head->next; return (next == head) && (next == head->prev);}/********************************************************* 5. 当前节点是否为最后一个节点**********************************************************//** * list_is_last - tests whether @list is the last entry in list @head * @list: the entry to test * @head: the head of the list */static inline int list_is_last(const struct list_head *list, const struct list_head *head){
return list->next == head;}/********************************************************* 6. 将一个节点从头移到尾部**********************************************************//** * list_rotate_left - rotate the list to the left * @head: the head of the list */static inline void list_rotate_left(struct list_head *head){
struct list_head *first; if (!list_empty(head)) {
first = head->next; list_move_tail(first, head); }}/********************************************************* 7. 替换链表中的某个节点**********************************************************//** * list_replace - replace old entry by new one * @old : the element to be replaced * @new : the new element to insert * * If @old was empty, it will be overwritten. */static inline void list_replace(struct list_head *old, struct list_head *new){
new->next = old->next; new->next->prev = new; new->prev = old->prev; new->prev->next = new;}static inline void list_replace_init(struct list_head *old, struct list_head *new){
list_replace(old, new); INIT_LIST_HEAD(old);}/********************************************************* 8. 根据entry或者自定义结构体地址**********************************************************//** * list_entry - get the struct for this entry * @ptr: the &struct list_head pointer. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. */#define list_entry(ptr, type, member) \ container_of(ptr, type, member)/** * list_first_entry - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note, that list is expected to be not empty. */#define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member)/** * list_last_entry - get the last element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note, that list is expected to be not empty. */#define list_last_entry(ptr, type, member) \ list_entry((ptr)->prev, type, member) /** * list_first_entry_or_null - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_head within the struct. * * Note that if the list is empty, it returns NULL. */#define list_first_entry_or_null(ptr, type, member) ({ \ struct list_head *head__ = (ptr); \ struct list_head *pos__ = (head__->next); \ pos__ != head__ ? list_entry(pos__, type, member) : NULL; \}) /** * list_next_entry - get the next element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */#define list_next_entry(pos, member) \ list_entry((pos)->member.next, typeof(*(pos)), member)/** * list_prev_entry - get the prev element in list * @pos: the type * to cursor * @member: the name of the list_head within the struct. */#define list_prev_entry(pos, member) \ list_entry((pos)->member.prev, typeof(*(pos)), member) /********************************************************* 9. 遍历双向链表**********************************************************//** * list_for_each - iterate over elements in a list * @pos: the &struct list_head to use as a loop counter. * @head: the head for your list. */#define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)/** * list_for_each_prev - iterate over a list backwards * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */#define list_for_each_prev(pos, head) \ for (pos = (head)->prev; pos != (head); pos = pos->prev) /** * list_for_each_safe - iterate over elements in a list, but don't dereference * pos after the body is done (in case it is freed) * @pos: the &struct list_head to use as a loop counter. * @pnext: the &struct list_head to use as a pointer to the next item. * @head: the head for your list (not included in iteration). */#define list_for_each_safe(pos, pnext, head) \ for (pos = (head)->next, pnext = pos->next; pos != (head); \ pos = pnext, pnext = pos->next)/** * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry * @pos: the &struct list_head to use as a loop cursor. * @n: another &struct list_head to use as temporary storage * @head: the head for your list. */#define list_for_each_prev_safe(pos, n, head) \ for (pos = (head)->prev, n = pos->prev; \ pos != (head); \ pos = n, n = pos->prev)/** * list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */#define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ &pos->member != (head); \ pos = list_next_entry(pos, member))/** * list_for_each_entry_reverse - iterate backwards over list of given type. * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. */#define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member); \ &pos->member != (head); \ pos = list_prev_entry(pos, member))/** * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue() * @pos: the type * to use as a start point * @head: the head of the list * @member: the name of the list_head within the struct. * * Prepares a pos entry for use as a start point in list_for_each_entry_continue(). */#define list_prepare_entry(pos, head, member) \ ((pos) ? : list_entry(head, typeof(*pos), member))/** * list_for_each_entry_continue - continue iteration over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Continue to iterate over list of given type, continuing after * the current position. */#define list_for_each_entry_continue(pos, head, member) \ for (pos = list_next_entry(pos, member); \ &pos->member != (head); \ pos = list_next_entry(pos, member))/** * list_for_each_entry_continue_reverse - iterate backwards from the given point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Start to iterate over list of given type backwards, continuing after * the current position. */#define list_for_each_entry_continue_reverse(pos, head, member) \ for (pos = list_prev_entry(pos, member); \ &pos->member != (head); \ pos = list_prev_entry(pos, member))/** * list_for_each_entry_from - iterate over list of given type from the current point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type, continuing from current position. */#define list_for_each_entry_from(pos, head, member) \ for (; &pos->member != (head); \ pos = list_next_entry(pos, member))/** * list_for_each_entry_from_reverse - iterate backwards over list of given type * from the current point * @pos: the type * to use as a loop cursor. * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate backwards over list of given type, continuing from current position. */#define list_for_each_entry_from_reverse(pos, head, member) \ for (; &pos->member != (head); \ pos = list_prev_entry(pos, member))/** * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. */#define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member), \ n = list_next_entry(pos, member); \ &pos->member != (head); \ pos = n, n = list_next_entry(n, member))/** * list_for_each_entry_safe_continue - continue list iteration safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type, continuing after current point, * safe against removal of list entry. */#define list_for_each_entry_safe_continue(pos, n, head, member) \ for (pos = list_next_entry(pos, member), \ n = list_next_entry(pos, member); \ &pos->member != (head); \ pos = n, n = list_next_entry(n, member))/** * list_for_each_entry_safe_from - iterate over list from current point safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate over list of given type from current point, safe against * removal of list entry. */#define list_for_each_entry_safe_from(pos, n, head, member) \ for (n = list_next_entry(pos, member); \ &pos->member != (head); \ pos = n, n = list_next_entry(n, member))/** * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage * @head: the head for your list. * @member: the name of the list_head within the struct. * * Iterate backwards over list of given type, safe against removal * of list entry. */#define list_for_each_entry_safe_reverse(pos, n, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member), \ n = list_prev_entry(pos, member); \ &pos->member != (head); \ pos = n, n = list_prev_entry(n, member))/** * list_safe_reset_next - reset a stale list_for_each_entry_safe loop * @pos: the loop cursor used in the list_for_each_entry_safe loop * @n: temporary storage used in list_for_each_entry_safe * @member: the name of the list_head within the struct. * * list_safe_reset_next is not safe to use in general if the list may be * modified concurrently (eg. the lock is dropped in the loop body). An * exception to this is if the cursor element (pos) is pinned in the list, * and list_safe_reset_next is called after re-taking the lock and before * completing the current iteration of the loop body. */#define list_safe_reset_next(pos, n, member) \ n = list_next_entry(pos, member) /********************************************************* 10. 判断双向链表是否有且只有一个节点**********************************************************//** * list_is_singular - tests whether a list has just one entry. * @head: the list to test. */static inline int list_is_singular(const struct list_head *head){
return !list_empty(head) && (head->next == head->prev);}/********************************************************* 11. 将一个链表拆为两个链表**********************************************************//** * 将head开始的双向循环链表从entry处拆成两个循环链表 * * head指向entry后的链表 * list直线前一个部分链表 */static inline void __list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry){
struct list_head *new_first = entry->next; list->next = head->next; list->next->prev = list; list->prev = entry; entry->next = list; head->next = new_first; new_first->prev = head;}/** * list_cut_position - cut a list into two * @list: a new list to add all removed entries * @head: a list with entries * @entry: an entry within head, could be the head itself * and if so we won't cut the list * * This helper moves the initial part of @head, up to and * including @entry, from @head to @list. You should * pass on @entry an element you know is on @head. @list * should be an empty list or a list you do not care about * losing its data. * */static inline void list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry){
if (list_empty(head)) return; if (list_is_singular(head) && (head->next != entry && head != entry)) return; if (entry == head) INIT_LIST_HEAD(list); else __list_cut_position(list, head, entry);}/** * list_cut_before - cut a list into two, before given entry * @list: a new list to add all removed entries * @head: a list with entries * @entry: an entry within head, could be the head itself * * This helper moves the initial part of @head, up to but * excluding @entry, from @head to @list. You should pass * in @entry an element you know is on @head. @list should * be an empty list or a list you do not care about losing * its data. * If @entry == @head, all entries on @head are moved to * @list. */static inline void list_cut_before(struct list_head *list, struct list_head *head, struct list_head *entry){
if (head->next == entry) {
INIT_LIST_HEAD(list); return; } list->next = head->next; list->next->prev = list; list->prev = entry->prev; list->prev->next = list; head->next = entry; entry->prev = head;}/********************************************************* 12. 将两个链表拼接为一个**********************************************************//** * __list_splice - splice two list into one * @list: a new list * @prev: insert position * @next: insert position *包含头节点的链表,这里的list已经不属于新的链表了 */static inline void __list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next){
struct list_head *first = list->next; struct list_head *last = list->prev; first->prev = prev; prev->next = first; last->next = next; next->prev = last;}/** * list_splice - join two lists, this is designed for stacks * @list: the new list to add. * @head: the place to add it in the first list. */static inline void list_splice(const struct list_head *list, struct list_head *head){
if (!list_empty(list)) __list_splice(list, head, head->next);}/** * list_splice_tail - join two lists, each list being a queue * @list: the new list to add. * @head: the place to add it in the first list. */static inline void list_splice_tail(struct list_head *list, struct list_head *head){
if (!list_empty(list)) __list_splice(list, head->prev, head);}/** * list_splice_init - join two lists and reinitialise the emptied list. * @list: the new list to add. * @head: the place to add it in the first list. * * The list at @list is reinitialised */static inline void list_splice_init(struct list_head *list, struct list_head *head){
if (!list_empty(list)) {
__list_splice(list, head, head->next); INIT_LIST_HEAD(list);/*list是头节点,拼接完毕后没有了作用。可以释放或者初始化供后面使用*/ }}/** * list_splice_tail_init - join two lists and reinitialise the emptied list * @list: the new list to add. * @head: the place to add it in the first list. * * Each of the lists is a queue. * The list at @list is reinitialised */static inline void list_splice_tail_init(struct list_head *list, struct list_head *head){
if (!list_empty(list)) {
__list_splice(list, head->prev, head); INIT_LIST_HEAD(list); }}#ifdef __cplusplus}#endif #endif /* ifndef _list.h */

转载地址:https://blog.csdn.net/s2603898260/article/details/106888397 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:epoll代码框架
下一篇:平静的心-初八,杭州

发表评论

最新留言

不错!
[***.144.177.141]2024年03月16日 09时42分59秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php taglib.php,thinkphp5 taglib自定义标签教程 2019-04-21
java常用包类 array,Java中的StringBuffer和数组Arrays以及常用类型的包装类 2019-04-21
ctf常见php,CTF中常见的PHP伪协议 2019-04-21
php语言冒泡法,PHP 冒泡排序法 2019-04-21
php如何数组去重复,PHP如何去除数组重复元素? 2019-04-21
java转换ab的值,查看新闻/公告--[整理]Java将AB1234形式的16进制字符串转换为10进制数值,考虑字节序的影响.... 2019-04-21
ui php h5,画出自己的UI组件的详情 2019-04-21
linux服务文件编写,linux编写systemd下服务脚本 2019-04-21
hdfs linux 目录是否存在,Linux中判断hdfs文件是否存在 2019-04-21
linux学习需要什么基础,学linux需要什么基础? 2019-04-21
linux vim编辑kconfig 无法wq,Linux-4.9.2内核在mini2440上的移植(三)——编译环境测试... 2019-04-21
linux 强制结束任务管理器,结束拒绝访问的进程 cmd下结束进程 强行结束进程 2019-04-21
高斯勒让德在c语言中的程序,c语言:用递归方法编写程序,求n阶勒让德多项式的值... 2019-04-21
c语言单片机电子时钟,新人求个51单片机的电子时钟汇编语言(C语言的还没学到)... 2019-04-21
c++语言文件流,C++文件流 2019-04-21
android 动态毛玻璃,Android毛玻璃背景效果简单实现代码 2019-04-21
android 按钮提示,的Android按钮工具提示 2019-04-21
iphone通讯录 android,3个方法,教你如何快速而又有效的将联系人从iPhone转移到安卓... 2019-04-21
android horizontalscrollview 滑动事件,ScrollView的滑动监听(以HorizontalScrollView为例) 2019-04-21
win7自定义html为桌面,Win7系统自定义桌面主题的方法 2019-04-21