比尔云BierYun--阿里云最新优惠活动
阿里云优惠码丨阿里云代金券

通用双向链表的设计(参考Linux系统中的实现)

通用双向链表的设计(参考Linux系统中的实现)

通常我们设计设计链表都是将数据域放在里面,这样每次需要使用链表的时候都需要实现一个链表,然后重新实现它的相关操作,这里参考Linux系统中的设计实现了一个通用的双向链表,只需要在你的结构里面有一个这个链表的域,就可以使用链表的相关操作了。

注意:这个通用的双向链表是参考Linux系统中的实现,它使用了typeof这个功能,所以有些编译器可能不支持。我是再Windows系统中使用MinGW下使用GCC编译的。

////////////////////////////////////////////////////////////////////////////////////////

// list.h


#ifndef _list_h
#define _list_h

typedef struct _list_head {
    struct _list_head *prev,*next;
} list_head;

#define offsetof(TYPE,MEMBER) ( (size_t) &((TYPE*)0)->MEMBER )

#define container_of(ptr,type,member) ({\
    const typeof( ((type*)0)->member ) *__mptr = (ptr);\
    (type*)( (char*)__mptr - offsetof(type,member) );})

#define list_empty(head) ( head->next==0&&head->prev==0 )

/* get the member of list object
 * @ptr        pointer to list_head
 * @type    the type of container which contains list_head field
 * @memeber field name in the container
 * @return    return pointer to the container
 */
#define list_entry(ptr,type,member) container_of(ptr,type,member)

/* add a new node after `head`
 */
void list_add(list_head *head,list_head *node);

/* delete a node
 */
void list_del(list_head *node);

#endif

/////////////////////////////////////////////////////////

// list.c

#include "list.h"

/* add a new node after `head`
 */
void list_add(list_head *head,list_head *node) {
    if(list_empty(head)) {
        head->next = head;
        head->prev = head;
    }
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}
/* delete a node
 */
void list_del(list_head *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

///////////////////////////////////////////////////////////////////////////////

// test.c

#include <stdio.h>
#include <assert.h>
#include "list.h"

typedef struct _task {
    int id;
    list_head next;
} task;

#define task_next(t) ( container_of(t->next.next,task,next) )

void task_print(task *t) {
    printf("#%d -> ",t->id);
}

void task_foreach(task *head,void (*callback)(task *)) {
    task *p = head;
    do {
        callback(p);
        p = task_next(p);
    }
    while (p!=head);
}

// use task like a list
void test_list() {
    task t1={1,{0,0}},
        t2={2,{0,0}},
        t3={3,{0,0}},
        t4={4,{0,0}},
        t5={5,{0,0}};

    list_add(&t1.next,&t2.next);
    list_add(&t2.next,&t3.next);
    list_add(&t3.next,&t4.next);
    list_add(&t4.next,&t5.next);

    task_foreach(&t1,task_print);
}

int main(int argc, char *argv[]) {
    test_list();

    return 0;
}

编译运行

    gcc test.c list.h list.c -o test
    .\test.exe

 

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

强烈推荐

高性能SSD云服务器ECS抗攻击,高可用云数据库RDS