circular-linked-lists

链表存在以下几种形式

• 单向
• 双向(doubly)
• 线性(linear)
• 循环(circular)
• 有头
• 无头(without header node)

Linux Kernel include/linux/list.h

a linear list

list --> [info | next] --> [info | next] --> [info | next] --> [info | NULL]

a circular list with header node

    Header Node       First Node                                            Last Node
--> [NULL | next] --> [info | next] --> [info | next] --> [info | next] --> [info | next]--+
|                                                                                          |
+------------------------------------------------------------------------------------------+

with or without header node

主要区别在于双向链表的结构体设计，是否需要存在一个不带有有效负载，只有链表控制信息的头节点，例如：

with header node

struct gxlist_head
{
    struct gxlist_head *next, *prev;
};

struct _hot_device {
    int                     id;
    int                     active;
    GxFsActionType          action;
    struct gxlist_head      head;
    int                     hot;
    GxHotplugError          error;
    void *priv;
};

#define GX_LIST_HEAD_INIT(name) { &(name), &(name) }

#define GX_LIST_HEAD(name) \
     struct gxlist_head name = GX_LIST_HEAD_INIT(name)

GX_LIST_HEAD(__device_list); //双向循环链表的头节点，整个链表通过这个节点进行管理

struct _hot_device *dev = NULL;

gxlist_add(&dev->head, &__device_list);

without header node

struct gxlist_head
{
    struct gxlist_head *next, *prev;
};

struct _hot_device {
    int                     id;
    int                     active;
    GxFsActionType          action;
    struct gxlist_head      head;
    int                     hot;
    GxHotplugError          error;
    void *priv;
};

#define GX_LIST_HEAD_INIT(name) { &(name), &(name) }

#define GX_LIST_HEAD(name) struct gxlist_head name = GX_LIST_HEAD_INIT(name)

有头双向循环链表

无头双向循环链表

source code

链表的设计，next 和 priv 可以指向数据节点也可以指向控制节点，以下代码设计即指向控制节点

struct gxlist_head
{
    struct gxlist_head *next, *prev;
};

//双向链表初始化，next和prev均指向链表header
#define GX_LIST_HEAD_INIT(name) { &(name), &(name) }

//声明双向链表Header Node
#define GX_LIST_HEAD(name) struct gxlist_head name = GX_LIST_HEAD_INIT(name)

#define GX_INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

void gxlist_add     (struct gxlist_head *newnode, struct gxlist_head *head);
void gxlist_add_tail(struct gxlist_head *newnode, struct gxlist_head *head);
void gxlist_del     (struct gxlist_head *entry);
void gxlist_del_init(struct gxlist_head *entry);
int  gxlist_empty   (struct gxlist_head *head );
void gxlist_splice  (struct gxlist_head *list, struct gxlist_head *head);

struct gxlist_head *gxlist_get(struct gxlist_head *head);

//根据控制成员（member）偏移量来获取数据节点地址
#define gxlist_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

//从双向链表中循环取出链表控制信息段（struct gxlist_head）
//从双向链表中循环取出pos，pos类型为 struct gxlist_head
#define gxlist_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); \
            pos = pos->next)

//从双向链表中根据member循环取出数据节点
//从双向链表中取出pos，pos类型为包含member成员的结构体
#define gxlist_for_each_entry(pos, head, member)                            \
    for (pos = gxlist_entry((head)->next, typeof(*pos), member);        \
            &pos->member != (head);                                     \
            pos = gxlist_entry(pos->member.next, typeof(*pos), member))

//反序
#define list_for_each_entry_reverse(pos, head, member)                            \
    for (pos = list_entry((head)->prev, typeof(*pos), member);        \
            &pos->member != (head);                                     \
            pos = list_entry(pos->member.prev, typeof(*pos), member))

//从数据节点中直接取出双向循环链表
#define list_from_node(pos, node, member, head)                            \
    for (pos = list_entry((node)->next, typeof(*pos), member);        \
            pos != (head);                                     \
            pos = list_entry(pos->member.next, typeof(*pos), member))

//反序从数据节点中直接取出双向循环链表
#define list_from_node_reverse(pos, node, member, head)                            \
    for (pos = list_entry((node)->prev, typeof(*pos), member);        \
            pos != (head);                                     \
            pos = list_entry(pos->member.prev, typeof(*pos), member))


//safe系列接口，n与pos相同的数据类型，n为链表中pos的下一个
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
            pos = n, n = pos->next)

#define list_for_each_entry_safe(pos, n, head, member)                           \
    for (pos = list_entry((head)->next, typeof(*pos), member),               \
            n = list_entry(pos->member.next, typeof(*pos), member);  \
            &pos->member != (head);                                    \
            pos = n, n = list_entry(n->member.next, typeof(*n), member))

#define list_for_each_entry_safe_reverse(pos, n, head, member)        \
    for (pos = list_entry((head)->prev, typeof(*pos), member),    \
        n = list_entry(pos->member.prev, typeof(*pos), member);    \
         &pos->member != (head);                     \
         pos = n, n = list_entry(n->member.prev, typeof(*n), member))


#endif

/*
 * 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 void __list_add(struct gxlist_head *new_node, struct gxlist_head *head, struct gxlist_head *head_next)
{
    head_next->prev = new_node;
    new_node->next = head_next;
    new_node->prev = head;
    head->next = new_node;
}

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
void gxlist_add(struct gxlist_head *new_node, struct gxlist_head *head)
{
    __list_add(new_node, head, head->next);
}

/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
void gxlist_add_tail(struct gxlist_head *new_node, struct gxlist_head *head)
{
    __list_add(new_node, head->prev, head);
}

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static void __list_del(struct gxlist_head *prev_head, struct gxlist_head *next_head)
{
    next_head->prev = prev_head;
    prev_head->next = next_head;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
 */
void gxlist_del(struct gxlist_head *entry)
{
    __list_del(entry->prev, entry->next);
}

/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
void gxlist_del_init(struct gxlist_head *entry)
{
    __list_del(entry->prev, entry->next);
    GX_INIT_LIST_HEAD(entry);
}

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
int gxlist_empty(struct gxlist_head *head)
{
    return head->next == head;
}

struct gxlist_head *gxlist_get(struct gxlist_head *head)
{
    struct gxlist_head *first = head->next;

    if (first != head)  {
        __list_del(first->prev, first->next);
        return first;
    }

    return 0;
}

/**
 * list_splice - join two lists
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */
void gxlist_splice(struct gxlist_head *list, struct gxlist_head *head)
{
    //去除header node
    struct gxlist_head *first = list->next;

    if (first != list) {
        struct gxlist_head *last = list->prev;
        struct gxlist_head *at = head->next;

        first->prev = head;
        head->next = first;

        last->next = at;
        at->prev = last;
    }
}

GX_LIST_HEAD(__usbwifi_device_list);

cyg_mutex_t usbwifi_list_lock;

#define DEV_LOCK()   cyg_mutex_lock(&usbwifi_list_lock)
#define DEV_UNLOCK() cyg_mutex_unlock(&usbwifi_list_lock)
#define DEV_TRYLOCK()   cyg_mutex_trylock(&usbwifi_list_lock)

void (*proc_wifi_init)(void);
void (*proc_wifi_exit)(void);
static void usbwifi_proc(void *p)
{
    usbwifi_dev_info disk_info;
    struct gx_usbwifi_hot_device *dev = NULL;

    while(1) {
        if (0 != usbwifi_detect(&disk_info)) {
            LOG("disk_detect return error \n");
            continue;
        }

        if (disk_info.dev_status == CYG_IO_SET_CONFIG_DISK_IN) {

            dev = GxCore_Malloc(sizeof(struct gx_usbwifi_hot_device));

            if (NULL == dev) {
                printf(" %s cann't fetch memory, try again \n", __func__);
                continue;
            }
            memset(dev, 0, sizeof(struct gx_usbwifi_hot_device));

            dev->id     = disk_info.index;
            dev->hot    = 0;
            dev->active = 1;
            dev->action = PLUG_IN;
            dev->error = PLUG_SUCCESS;

            DEV_LOCK();
            gxlist_add(&dev->head, &__usbwifi_device_list);
            DEV_UNLOCK();

            cyg_semaphore_post(&device_detect_sem);

            if (proc_wifi_init)
                (*proc_wifi_init)();
        }
        else if (disk_info.dev_status == CYG_IO_SET_CONFIG_DISK_OUT) {
            int found = 0;

            DEV_LOCK();

            gxlist_for_each_entry(dev, &__usbwifi_device_list, head) {
                if (dev->id == disk_info.index) {
                    found = 1;
                    break;
                }
            }

            if (found == 0) {
                DEV_UNLOCK();
                continue;
            }

            dev->action = PLUG_OUT;

            DEV_UNLOCK();

            cyg_semaphore_post(&device_detect_sem);

            if (proc_wifi_exit)
                (*proc_wifi_exit)();
        }

        GxCore_ThreadDelay(20);
    }
}

void GxCore_UsbwifiHotplugInit()
{
    handle_t thread_id_do;

    cyg_semaphore_init(&device_detect_sem, 0);
    cyg_mutex_init(&usbwifi_list_lock);

    LOG("device_detect_sem.count = 0x%x , line = %d \n", device_detect_sem.count, __LINE__);

    GxCore_ThreadCreate(
            "usbwifi_proc",
            &thread_id_do,
            usbwifi_proc,
            NULL,
            8 * 1024,
            GXOS_DEFAULT_PRIORITY);
}

struct gx_usbwifi_hot_device *GxCore_UsbwifiHotplugGetFirst(void)
{
    if (gxlist_empty(&__usbwifi_device_list) )
        return NULL;

    return gxlist_entry(__usbwifi_device_list.next, struct gx_usbwifi_hot_device, head);
}

struct gx_usbwifi_hot_device *GxCore_UsbwifiHotplugGetNext(struct gx_usbwifi_hot_device *dev)
{
    if (dev == NULL)
        return NULL;

    if (dev->head.next == &__usbwifi_device_list)
        return NULL;

    return gxlist_entry(dev->head.next, struct gx_usbwifi_hot_device, head);
}

struct gx_usbwifi_hot_device *GxCore_UsbwifiHotplugWait(void)
{
    cyg_semaphore_wait(&device_detect_sem);

    DEV_LOCK();
    if (gxlist_empty(&__usbwifi_device_list) ) {
        return NULL;
    }

    return gxlist_entry(__usbwifi_device_list.next, struct gx_usbwifi_hot_device, head);
}

int GxCore_UsbwifiHotplugClean(void)
{
    struct gx_usbwifi_hot_device *dev, *n;

    gxlist_for_each_entry_safe(dev, n, &__usbwifi_device_list, head) {
        if (dev->action == PLUG_OUT) {
            gxlist_del(&dev->head);
            GxCore_Free(dev);
        }
    }
    DEV_UNLOCK();
    return GXCORE_SUCCESS;
}

typedef enum {
    PLUG_IN    = 1,
    PLUG_OUT   = 2,
    PLUG_CLEAN = 3,
}GxFsActionType;

typedef enum {
    PLUG_SUCCESS             = 0,
    PLUG_ERROR_FS_NO_SUPPORT = 1,
    PLUG_ERROR_NO_PARTITION  = 2,
} GxHotplugError;

struct gx_usbwifi_hot_device {
    int                     id;
    int                     active;
    GxFsActionType          action;          // PLUG-IN PLUG-OUT
    struct gxlist_head      head;
    int                     hot;
    GxHotplugError          error;
    void *priv;
};

Ref

1. 链表（四）——实现双向循环链表创建、插入、删除、释放内存等简单操作
2. 单链表/双向链表的建立/遍历/插入/删除