链表结构定义如下，public成员为公共的方法，count，first和last为私有成员，count表示链表中元素的数量，first和last分别指向链表的头和尾。public（linked_list_t结构）定义了一系列操作链表的方法，其必须为第一个结构成员，方便在公共方法和私有结构间转换。

struct private_linked_list_t {
    linked_list_t public;
    int count;
    element_t *first;
    element_t *last;
};

链表元素结构element_t如下，包括值value，和指向前一个(previous)和后一个元素(next)的两个指针：

struct element_t {
    void *value;
    element_t *previous;
    element_t *next;
};

如下函数创建通用的链表元素结构。

static element_t *element_create(void *value)
{
    element_t *this;
    INIT(this,
        .value = value,
    );
    return this;
}

创建新链表

创建新的链表，实例化链表结构，这里主要初始化了链表的公共方法，没有初始化私有成员。

linked_list_t *linked_list_create()
{
    private_linked_list_t *this;
    INIT(this,
        .public = {
            .get_count = _get_count,
            .create_enumerator = _create_enumerator,
            .reset_enumerator = (void*)_reset_enumerator,
            .get_first = _get_first,
            .get_last = _get_last,
            .find_first = _find_first,
            .insert_first = _insert_first,
            .insert_last = _insert_last,
            .insert_before = (void*)_insert_before,
            ...
        },
    );
    return &this->public;

链表元素操作

向链表尾部插入元素时，对于链表为空的情况，链表成员first和last都指向此元素。对于链表非空的情况，链表中原有最后一个元素last的next指向新元素，新元素的previous指向原有最后一个元素。新元素保存为最后一个元素last。

METHOD(linked_list_t, insert_last, void, private_linked_list_t *this, void *item)
{
    element_t *element = element_create(item);
    if (this->count == 0) {    /* first entry in list */
        this->first = element;
        this->last = element;
    } else {
        element->previous = this->last;
        this->last->next = element;
        this->last = element;
    }
    this->count++;

链表起初只有一个元素（1st_elem），在尾部增加第二个元素之后如下图所示：

this->first                     this->first  |---<-------------<-------------------|
        |                                |   |                                     |   
this->last                               |   |               this->last            |   
        |                                |   |                      |              |   
   |-----------|                     |-----------|            |-----------|        |   
   |           |--pre=NULL           |           |--pre=NULL  |           |--pre---|   
   |  1st_elem |                     |  1st_elem |            |  2nd_elem |            
   |           |--next=NULL          |           |--next----->|           |--next=NULL 
   |-----------|                     |-----------|            |-----------|            

方法insert_first在链表首部插入一个元素，递增链表元素计数。

METHOD(linked_list_t, insert_first, void, private_linked_list_t *this, void *item)
{
    element_t *element = element_create(item);
    if (this->count == 0) {
        /* first entry in list */
        this->first = element;
        this->last = element;
    } else {
        element->next = this->first;
        this->first->previous = element;
        this->first = element;
    }
    this->count++;

链表起初只有一个元素（1st_elem），在首部增加第二个元素之后如下图所示：

this->first                     this->first   |---------<------<-----------------------------|                             
        |                               |     |                                              |
this->last                              |     |                     this->last               |   
        |                               |     |                             |                |   
   |-----------|                   |--------------|                 |---------------|        |     
   |           |--pre=NULL         |              |--pre=NULL       |               |--pre---|   
   |  1st_elem |                   | new_1st_elem |                 |  old_1st_elem |             
   |           |--next=NULL        |              |--next---------->|               |--next=NULL  
   |-----------|                   |--------------|                 |---------------|             

释放元素时，先行保存元素在链表中的下一个next和前一个元素previous。如果下一个元素有值，拿起previous应当指向上上个元素；否则，删除的为链表最后一个元素，previous变成最后一个元素。

如果前一个元素有值，其last应当指向下下个元素；否则，删除的为链表第一个元素，next变成第一个元素。

链表中的元素个数递减一，如果递减之后等于0，将链表的first和last指针置空。函数返回链表中被删除元素的下一个元素。

static element_t* remove_element(private_linked_list_t *this, element_t *element)
{
    element_t *next, *previous;

    next = element->next;
    previous = element->previous;
    free(element);
    if (next)
        next->previous = previous;
    else
        this->last = previous;
    if (previous)
        previous->next = next;
    else
        this->first = next;
    if (--this->count == 0){
        this->first = NULL;
        this->last = NULL;
    }
    return next;

链表枚举器

链表的枚举器结构定义如下，public成员为公共的方法，list和current为私有成员。public必须为第一个结构成员，方便在公共方法和私有结构间切换。

struct private_enumerator_t {
    enumerator_t public;
    private_linked_list_t *list;
    element_t *current;
};

枚举器结构的公共方法有以下三个。

struct enumerator_t {
    bool (*enumerate)(enumerator_t *this, ...);
    bool (*venumerate)(enumerator_t *this, va_list args);
    void (*destroy)(enumerator_t *this);
};

create_enumerator函数创建枚举器，初始化private_enumerator_t结构，链表结构实现了venumerate函数，enumerate函数使用枚举器默认的。私有成员list初始化为链表结构this，current成员指向链表首个元素。

METHOD(linked_list_t, create_enumerator, enumerator_t*, private_linked_list_t *this)
{   
    private_enumerator_t *enumerator;
    
    INIT(enumerator,
        .public = {
            .enumerate = enumerator_enumerate_default,
            .venumerate = _enumerate_current,
            .destroy = (void*)free,
        },
        .list = this,
        .current = this->first,
    );
    return &enumerator->public;

枚举器要求必须实现venumerate方法，其默认函数（enumerator_enumerate_default）是对venumerate的封装。此函数接受可变数量的参数，之后将这些参数传入venumerate方法。

bool enumerator_enumerate_default(enumerator_t *enumerator, ...)
{
    va_list args;
    bool result;

    if (!enumerator->venumerate) {
        DBG1(DBG_LIB, "!!! ENUMERATE DEFAULT: venumerate() missing !!!");
        return FALSE;
    }
    va_start(args, enumerator);
    result = enumerator->venumerate(enumerator, args);
    va_end(args);
    return result;

枚举器初始化的venumerate函数如下，在首次调用之后，其公共方法venumerate更换为_enumerate_next，用于获取枚举器的下一个元素。

METHOD(enumerator_t, enumerate_current, bool,
    private_enumerator_t *this, va_list args)
{
    this->public.venumerate = _enumerate_next;
    return do_enumerate(this, args);
}

初始化时，枚举器的current指向了链表结构的首个元素，如果current和传入参数都有效，将current元素的值赋予参数中。对于链表结构，可变参数的数量为1。

如果current为空，返回FALSE，表示整个枚举过程结束，链表结构的元素遍历完成。

static bool do_enumerate(private_enumerator_t *this, va_list args)
{   
    void **item;
    
    VA_ARGS_VGET(args, item);
    
    if (!this->current) 
        return FALSE;
    if (item)
        *item = this->current->value;
    return TRUE;

通常在遍历第二个元素时，枚举器的venumerate函数换成了enumerate_next，枚举器的私有成员current指向链表下一个元素。do_enumerate执行以上的取值操作，取出下一个链表元素。

METHOD(enumerator_t, enumerate_next, bool, private_enumerator_t *this, va_list args)
{
    if (this->current)
        this->current = this->current->next;
    return do_enumerate(this, args);
}

枚举器使用完之后，需要由reset_enumerator复位，枚举器的current再次指向链表结构的首个元素，枚举器的公共方法venumerate恢复为指向enumerate_current函数。

METHOD(linked_list_t, reset_enumerator, void,
    private_linked_list_t *this, private_enumerator_t *enumerator)
{
    enumerator->current = this->first;
    enumerator->public.venumerate = _enumerate_current;
}

strongswan-5.9.14