多种双链表设计_学以致用--Apple的学习笔记
2021-04-27 本文已影响0人
applecai
一，前言
上一篇C工程框架_学以致用--Apple的学习笔记是设计了框架，然后子模块中添加了单链表进行练手，今天是双链表的练手，重点是结构体的创建及添加,删除和遍历。里面搜索算法，排序算法先不使用。双链表使用很广泛，我今天自己建立了双链表结构test3.c，又模拟了linux内核驱动的双链表设计test4.c。
二，实战篇
我建立的双链表如下，首尾都是NULL，使用起来和单链表差不多，这里面尾插我就要从头循环访问到尾，确实效率低。linux内核建立的围成了圈，头插和尾插效率一样。而且关于头插和尾插分层设计的很好，另外它需要配合containof来使用，通过成员体指针变量来访问到主对象结构体变量。
我的代码test3.c
/*******************************************************************************
| Project : Double linked list
| Description : create;insert;remove;search;traversal functions
| CPU and Compiler : win10 CodeBlocks MinGw32
| R E V I S I O N H I S T O R Y
|-------------------------------------------------------------------------------
| Date Version Author Description
| ---------- -------- ------ ---------------------------------------------
| 2020-04-25 01.00.00 AppleCai First version
*******************************************************************************/
/*********************
* INCLUDES
*********************/
#include <stdio.h>
#include <stdlib.h>
#include "../typedef.h"
/**********************
* MACROS
**********************/
/* the status of borrow of book */
#define BOOKED 1
#define RETURNED 0
/**********************
* TYPEDEFS
**********************/
typedef struct _dl
{
struct _dl *pre;
struct _dl *next;
} dl_t;
typedef struct
{
uint8 bookID;
uint16 personID;
boolean bookStatus;
} systemDL_t;
typedef struct _booksystemDL_t
{
dl_t dl; /* shall be put in the top of struct */
systemDL_t obj;
void (*initbook)(struct _booksystemDL_t *);
void (*borrowbooks)(struct _booksystemDL_t *,struct _booksystemDL_t *);
void (*returnbooks)(struct _booksystemDL_t * ,uint8 );
void (*printborrowbooklist)(struct _booksystemDL_t *);
void (*searchbooks)(struct _booksystemDL_t * ,uint8 );
} booksystemDL_t;
/**********************
* GLOBAL VAR
**********************/
/**********************
* CONST VAR
**********************/
/**********************
* Functions Implement
**********************/
static void init_dlist(booksystemDL_t * head)
{
head->dl.next = NULL;
head->dl.pre = NULL;
}
static void insertDList_head(booksystemDL_t *head,booksystemDL_t *node)
{
node->dl.next = head->dl.next;
if(head->dl.next)
{
head->dl.next->pre = node;
}
node->dl.pre = head;
head->dl.next = node;
LOG_TRACE("head insert for double linked list done!");
}
static void insertdList_tail(booksystemDL_t *head,booksystemDL_t *node)
{
booksystemDL_t *p = head;
/* find the last node when p->next is null */
while(p->dl.next)
{
p = p->dl.next;
}
/* change null to new node */
p->dl.next = node;
node->dl.pre = p;
node->dl.next = NULL;
LOG_TRACE("tail insert for single list done!");
}
static void print_dlist(booksystemDL_t * head)
{
booksystemDL_t *p = (booksystemDL_t *)head->dl.next;
while(p)
{
printf("Book ID %d borrowed for person ID 0x%X\n",p->obj.bookID,p->obj.personID);
p = p->dl.next;
}
LOG_TRACE("Traversal double linked list done!");
}
static void print_dlist_backward(booksystemDL_t * head)
{
booksystemDL_t *p = (booksystemDL_t *)head; /* point to the last item */
while(p->dl.next)
{
p = p->dl.next;
}
while(p->dl.pre!=NULL)
{
printf("Book ID %d borrowed for person ID 0x%X\n",p->obj.bookID,p->obj.personID);
p = p->dl.pre;
}
LOG_TRACE("Traversal double linked list done!");
}
static void search_dlist(booksystemDL_t *head,uint8 bookid)
{
booksystemDL_t *p = (booksystemDL_t *)head->dl.next;
boolean found = 0;
while(p)
{
if(p->obj.bookID == bookid)
{
found = 1;
printf("Book ID %d is borrowed for person ID 0x%X\n",p->obj.bookID,p->obj.personID);
break;
}
p = p->dl.next;
}
if(found == 0)
{
printf("Nobody borrow book ID %d\n",bookid);
}
LOG_TRACE("Search double linked list done!");
}
#define REMOVE_FROM_DLIST(st,head,elem,item) \
st *p = head; \
st *n = (st *)p->dl.next; \
uint8 found = 0; \
while(n) \
{ \
if(n->obj.elem == item) \
{ \
found = 1; \
p->dl.next = n->dl.next; \
if(n->dl.next) \
n->dl.next->pre = p; \
free(n); \
break; \
} \
p = n; \
n = (st *)n->dl.next; \
} \
if(found == 0) \
{ \
LOG_TRACE("Can't find Book ID!"); \
}
static void removefromdlist(booksystemDL_t * head,uint8 item)
{
REMOVE_FROM_DLIST(booksystemDL_t,head,bookID,item);
}
/**
* free list from head
* @param head: head of single list
*/
static void DeInitAll_DL(booksystemDL_t * head)
{
booksystemDL_t *p = head;
booksystemDL_t *q;
while(p)
{
q = p->dl.next; /* save next */
free(p); /* free current point */
p = q; /* point to the next obj */
}
}
void dlist1(void)
{
printf("you select double linked list test example 1!\n");
/*********** Init *****************************/
booksystemDL_t *appleBooks; /* head */
appleBooks = (booksystemDL_t *)malloc(sizeof(booksystemDL_t));
appleBooks->obj.bookID = 0;
appleBooks->obj.bookStatus = RETURNED;
appleBooks->obj.personID = 0x0;
appleBooks->initbook = init_dlist;
appleBooks->borrowbooks = insertDList_head;
appleBooks->printborrowbooklist = print_dlist;
appleBooks->searchbooks = search_dlist;
appleBooks->returnbooks = removefromdlist;
/* initlize head */
printf("\n1) Initlize Apple Book System!\n");
if(appleBooks->initbook)
{
appleBooks->initbook(appleBooks);
}
/* insert node */
printf("\n2) Three person borrow books!\n");
if(appleBooks->borrowbooks)
{
uint8 i = 0;
for (i = 0;i<3;i++)
{
booksystemDL_t *customer = (booksystemDL_t *)malloc(sizeof(booksystemDL_t));
customer->obj.bookID = i+1;
customer->obj.bookStatus = BOOKED;
customer->obj.personID = 0x1001+i;
customer->initbook = init_dlist;
customer->initbook(customer);
appleBooks->borrowbooks(appleBooks,customer);
printf("Book ID %d is borrowed for person ID 0x%X\n",customer->obj.bookID,customer->obj.personID);
}
}
/* traversal */
printf("\n3) Print borrow-list of booksystem foreward!\n");
if(appleBooks->printborrowbooklist)
{
appleBooks->printborrowbooklist(appleBooks);
}
printf("\n4) Print borrow-list of booksystem backward!\n");
appleBooks->printborrowbooklist = print_dlist_backward;
if(appleBooks->printborrowbooklist)
{
appleBooks->printborrowbooklist(appleBooks);
}
/* search */
printf("\n5) Check the status of book ID 2!\n");
if(appleBooks->searchbooks)
{
appleBooks->searchbooks(appleBooks,2);
}
/* remove */
printf("\n6) Return book ID 2!\n");
if(appleBooks->returnbooks)
{
appleBooks->returnbooks(appleBooks,2);
}
printf("\n7) Print borrow-list of booksystem again!\n");
if(appleBooks->printborrowbooklist)
{
appleBooks->printborrowbooklist(appleBooks);
}
printf("\n8) Next person borrow a book!\n");
appleBooks->borrowbooks = insertdList_tail;
if(appleBooks->borrowbooks)
{
booksystemDL_t *customer = (booksystemDL_t *)malloc(sizeof(booksystemDL_t));
customer->obj.bookID = 4;
customer->obj.bookStatus = BOOKED;
customer->obj.personID = 0x1004;
customer->initbook = init_dlist;
customer->initbook(customer);
appleBooks->borrowbooks(appleBooks,customer);
}
printf("\n9) Print borrow-list of booksystem backward!\n");
if(appleBooks->printborrowbooklist)
{
appleBooks->printborrowbooklist(appleBooks);
}
DeInitAll_DL(appleBooks);
/*********** End ******************************/
printf("\nPlease select next test item[1-9],print q to exit!Please:");
}
test4.c，参考了linux的双链表风格，并且配合containof使用，所以传入参数都是直接为对象中的双链表了，这样才是链表和对象体分离，对比后才发现我之前做的并不算链表和对象数据分离，哈哈~
/*******************************************************************************
| Project : Double linked list follow Linux
| Description : create;insert;remove;search;traversal functions
| CPU and Compiler : win10 CodeBlocks MinGw32
| R E V I S I O N H I S T O R Y
|-------------------------------------------------------------------------------
| Date Version Author Description
| ---------- -------- ------ ---------------------------------------------
| 2020-04-25 01.00.00 AppleCai First version
*******************************************************************************/
/*********************
* INCLUDES
*********************/
#include <stdio.h>
#include <stdlib.h>
#include "../typedef.h"
/**********************
* MACROS
**********************/
/* the status of borrow of book */
#define BOOKED 1
#define RETURNED 0
/* get the offset of element with the struct head */
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
/* get the head address of struct */
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
/**********************
* TYPEDEFS
**********************/
typedef struct _list_head
{
struct _list_head *next, *prev;
} list_head;
typedef struct
{
uint8 bookID;
uint16 personID;
boolean bookStatus;
} systemDL_t;
typedef struct _booksystemDL_t
{
list_head dl; /* shall be put in the top of struct */
systemDL_t obj;
void (*initbook)(list_head *);
void (*borrowbooks)(list_head *node,list_head *head);
void (*returnbooks)(list_head *,uint8 );
void (*printborrowbooklist)(list_head *);
//void (*printborrowbooklist)(struct _booksystemDL_t *);
void (*searchbooks)(struct _booksystemDL_t *,uint8 );
} booksystemDL_t;
/**********************
* GLOBAL VAR
**********************/
/**********************
* CONST VAR
**********************/
/**********************
* Functions Implement
**********************/
static void INIT_LIST_HEAD(list_head *list)
{
list->next = list;
list->prev = list;
}
/**
* put new between prev and next
* @param new: new node
* @param prev: prev of head
* @param next: next of head
*/
static inline void _list_add(list_head *new,list_head *prev,list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
/**
* add new node after head
* @param new: new node
* @param head: head of double linked list
*/
static inline void list_add(list_head *new, list_head *head)
{
_list_add(new,head,head->next);
LOG_TRACE("Insert in the head!");
}
/**
* add new node before head, means put the new node at the end of list
* @param new: new node
* @param head: head of double linked list
*/
static inline void list_add_tail(list_head *new, list_head *head)
{
_list_add(new,head->prev,head);
LOG_TRACE("Insert at tail!");
}
/* traversal */
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
static inline void __list_del(list_head * prev, list_head * next)
{
next->prev = prev;
prev->next = next;
}
static inline void __list_del_entry(list_head *entry)
{
__list_del(entry->prev, entry->next);
}
/**
* delete entry between prev.
*/
static inline void list_del_init(list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
LOG_TRACE("remove from double linked list done!");
}
static void print_dlist(list_head * head)
{
list_head *p;
booksystemDL_t *objhead;
/* search all the double linked list */
list_for_each(p,head)
{
/* get the head of struct */
objhead = container_of(p, booksystemDL_t, dl);
printf("Book ID %d borrowed for person ID 0x%X\n",objhead->obj.bookID,objhead->obj.personID);
}
LOG_TRACE("Traversal double linked list done!");
}
static void print_dlist1(booksystemDL_t * head)
{
booksystemDL_t *p =head;
while(p->dl.next != head)
{
printf("Book ID %d borrowed for person ID 0x%X\n",p->obj.bookID,p->obj.personID);
p = p->dl.next;
}
LOG_TRACE("Traversal double linked list done!");
}
static removefromdlist(list_head *head,uint8 bookid)
{
list_head *p;
booksystemDL_t *objhead;
list_for_each(p, head)
{
objhead = container_of(p, booksystemDL_t, dl);
if(objhead->obj.bookID == bookid)
{
list_del_init(p);
free(objhead);
break; /* if don't use break, we shall use list_for_each_safe */
}
}
}
static DeInitAll_DL(list_head *head)
{
list_head *p,*next;
booksystemDL_t *objhead;
list_for_each_safe(p, next, head) /* due to we shall release p, so use safe */
{
objhead = container_of(p, booksystemDL_t, dl);
list_del_init(p);
free(objhead);
}
}
void dlist2(void)
{
printf("you select double linked list test example 2!\n");
/*********** Init *****************************/
booksystemDL_t *appleBooks; /* head */
appleBooks = (booksystemDL_t *)malloc(sizeof(booksystemDL_t));
appleBooks->obj.bookID = 0;
appleBooks->obj.bookStatus = RETURNED;
appleBooks->obj.personID = 0x0;
appleBooks->initbook = INIT_LIST_HEAD;
appleBooks->borrowbooks = list_add_tail;
appleBooks->printborrowbooklist = print_dlist;
appleBooks->returnbooks = removefromdlist;
/* initlize head */
printf("\n1) Initlize Apple Book System!\n");
if(appleBooks->initbook)
{
appleBooks->initbook(&(appleBooks->dl));
}
/* insert node */
printf("\n2) Three person borrow books!\n");
if(appleBooks->borrowbooks)
{
uint8 i = 0;
for (i = 0; i<3; i++)
{
booksystemDL_t *customer = (booksystemDL_t *)malloc(sizeof(booksystemDL_t));
customer->obj.bookID = i+1;
customer->obj.bookStatus = BOOKED;
customer->obj.personID = 0x1001+i;
appleBooks->borrowbooks(&(customer->dl),&(appleBooks->dl));
printf("Book ID %d is borrowed for person ID 0x%X\n",customer->obj.bookID,customer->obj.personID);
}
}
/* traversal */
printf("\n3) Print borrow-list of booksystem foreward!\n");
if(appleBooks->printborrowbooklist)
{
appleBooks->printborrowbooklist(&(appleBooks->dl));
}
/* remove */
printf("\n4) Return book ID 2!\n");
if(appleBooks->returnbooks)
{
appleBooks->returnbooks(&(appleBooks->dl),6);
}
printf("\n5) Print borrow-list of booksystem again!\n");
if(appleBooks->printborrowbooklist)
{
appleBooks->printborrowbooklist(&(appleBooks->dl));
}
/* insert after head */
printf("\n6) Next person borrow a book!\n");
appleBooks->borrowbooks = list_add;
if(appleBooks->borrowbooks)
{
uint8 i = 0;
booksystemDL_t *customer = (booksystemDL_t *)malloc(sizeof(booksystemDL_t));
customer->obj.bookID = 4;
customer->obj.bookStatus = BOOKED;
customer->obj.personID = 0x1004;
appleBooks->borrowbooks(&(customer->dl),&(appleBooks->dl));
printf("Book ID %d is borrowed for person ID 0x%X\n",customer->obj.bookID,customer->obj.personID);
}
printf("\n7) Print borrow-list of booksystem again!\n");
if(appleBooks->printborrowbooklist)
{
appleBooks->printborrowbooklist(&(appleBooks->dl));
}
printf("\n8) free memory!\n");
DeInitAll_DL(&(appleBooks->dl));
/*********** End ******************************/
printf("\nPlease select next test item[1-9],print q to exit!Please:");
}
三，学习篇
3.1. qemu中的双链表设计
又看了qemu虚化代码中双链表的设计，它设计的比较特别。head没有next只有last。之后的node就是标准的pre和next。
#define Q_TAILQ_HEAD(name, type, qual) \
struct name { \
qual type *tqh_first; /* first element */ \
qual type *qual *tqh_last; /* addr of last next element */ \
}
#define Q_TAILQ_ENTRY(type, qual) \
struct { \
qual type *tqe_next; /* next element */ \
qual type *qual *tqe_prev; /* address of previous next element */\
}
它这样的设计，last直接指向尾巴(head)->tqh_last = &(elm)->field.tqe_next;,且一开始尾巴NULL的值就被设置为了待插入节点*(head)->tqh_last = (elm);，所以尾插效率比我自己做的要高，另外，它不用containof来找主对象，所以采用了elm和field的参数方式，这样的方式我在单链表中也用过这类用法。
#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
(elm)->field.tqe_next = NULL; \
(elm)->field.tqe_prev = (head)->tqh_last; \
*(head)->tqh_last = (elm); \
(head)->tqh_last = &(elm)->field.tqe_next; \
} while (/*CONSTCOND*/0)
我的代码再演进下应该就是qemu这样的设计，然后最好的设计当然是linux内核这样的设计。
3.2 littlevgl的双链表设计
它的设计和我类似，又说到尾插的优化问题，他是添加了n_size，然后要找位置就直接#define LL_PREV_P_OFFSET(ll_p) (ll_p->n_size),但是一个头插_lv_ll_ins_head函数就要调用3个小函数，感觉设计的好复杂，不喜欢。而且他的头插就是直接把new节点插入在head的前面node_set_prev(ll_p, ll_p->head, n_new);然后重置head的地址，直接指向newll_p->head = n_new;这个和之前理解的头插不改变head的地址是不同的。所以看不惯，哈哈~
/** Description of a linked list*/
typedef struct {
uint32_t n_size;
lv_ll_node_t * head;
lv_ll_node_t * tail;
} lv_ll_t;
/**
* Return with the pointer of the previous node after 'n_act'
* @param ll_p pointer to linked list
* @param n_act pointer a node
* @return pointer to the previous node
*/
void * _lv_ll_get_prev(const lv_ll_t * ll_p, const void * n_act)
{
/*Pointer to the prev. node is stored in the end of this node.
*Go there and return the address found there*/
const lv_ll_node_t * n_act_d = n_act;
n_act_d += LL_PREV_P_OFFSET(ll_p);
return *((lv_ll_node_t **)n_act_d);
}
/**
* Set the previous node pointer of a node
* @param ll_p pointer to linked list
* @param act pointer to a node which prev. node pointer should be set
* @param prev pointer to a node which should be the previous node before 'act'
*/
static void node_set_prev(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * prev)
{
if(act == NULL) return; /*Can't set the prev node of `NULL`*/
uint8_t * act8 = (uint8_t *)act;
act8 += LL_PREV_P_OFFSET(ll_p);
lv_ll_node_t ** act_node_p = (lv_ll_node_t **) act8;
lv_ll_node_t ** prev_node_p = (lv_ll_node_t **) &prev;
*act_node_p = *prev_node_p;
}
/**
* Set the 'next node pointer' of a node
* @param ll_p pointer to linked list
* @param act pointer to a node which next node pointer should be set
* @param next pointer to a node which should be the next node before 'act'
*/
static void node_set_next(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * next)
{
if(act == NULL) return; /*Can't set the next node of `NULL`*/
uint8_t * act8 = (uint8_t *)act;
act8 += LL_NEXT_P_OFFSET(ll_p);
lv_ll_node_t ** act_node_p = (lv_ll_node_t **) act8;
lv_ll_node_t ** next_node_p = (lv_ll_node_t **) &next;
*act_node_p = *next_node_p;
}
/**
* Add a new head to a linked list
* @param ll_p pointer to linked list
* @return pointer to the new head
*/
void * _lv_ll_ins_head(lv_ll_t * ll_p)
{
lv_ll_node_t * n_new;
n_new = lv_mem_alloc(ll_p->n_size + LL_NODE_META_SIZE);
if(n_new != NULL) {
node_set_prev(ll_p, n_new, NULL); /*No prev. before the new head*/
node_set_next(ll_p, n_new, ll_p->head); /*After new comes the old head*/
if(ll_p->head != NULL) { /*If there is old head then before it goes the new*/
node_set_prev(ll_p, ll_p->head, n_new);
}
ll_p->head = n_new; /*Set the new head in the dsc.*/
if(ll_p->tail == NULL) { /*If there is no tail (1. node) set the tail too*/
ll_p->tail = n_new;
}
}
return n_new;
}
3.3 nuttx OS的双链表设计
nuttx OS中双链表的数据结构设计和qemu类似，head和node不同，node就是普通的pre（上一个）和next（下一个），而head是head（头）和tail（尾巴）queue->tail = node;。这样的代码还是比较清爽的，比qemu看起来舒服
struct dq_entry_s
{
FAR struct dq_entry_s *flink;
FAR struct dq_entry_s *blink;
};
typedef struct dq_entry_s dq_entry_t;
struct sq_queue_s
{
FAR sq_entry_t *head;
FAR sq_entry_t *tail;
};
typedef struct sq_queue_s sq_queue_t;
/****************************************************************************
* Name: dq_addlast
*
* Description:
* dq_addlast adds 'node' to the end of 'queue'
*
****************************************************************************/
void dq_addlast(FAR dq_entry_t *node, dq_queue_t *queue)
{
node->flink = NULL;
node->blink = queue->tail;
if (!queue->head)
{
queue->head = node;
queue->tail = node;
}
else
{
queue->tail->flink = node;
queue->tail = node;
}
}
/****************************************************************************
* Name: dq_addfirst
*
* Description:
* dq_addfirst affs 'node' at the beginning of 'queue'
*
****************************************************************************/
void dq_addfirst(FAR dq_entry_t *node, dq_queue_t *queue)
{
node->blink = NULL;
node->flink = queue->head;
if (!queue->head)
{
queue->head = node;
queue->tail = node;
}
else
{
queue->head->blink = node;
queue->head = node;
}
}
四，总结
最近看了多个开源代码，开源代码的双链表的结构体设计大多不同，只有nuttxOS和qemu设计的类似，但也不是完全一样。估计也就这样几种思路了。总之结构体成员设计的不同，它使用起来方法也不同。总体来看我最喜欢的是linux内核中的双链表设计方式，结构简单，代码分层理解起来也容易。在我的认知中，越容易理解的代码越优秀。高手写的代码看起来都很舒服，并且通俗易懂。
