#include<stdio.h>#include<stdbool.h>#include<stdlib.h>#include<stdarg.h>#defineTRUEtrue#defineFALSEfalse/**
* Object allocation/initialization macro, using designated initializer.
*/#defineINIT(this,...)({(this)=malloc(sizeof(*(this)));\*(this)=(typeof(*(this))){ __VA_ARGS__ };(this);})/**
* Method declaration/definition macro, providing private and public interface.
*
* Defines a method name with this as first parameter and a return value ret,
* and an alias for this method with a _ prefix, having the this argument
* safely casted to the public interface iface.
* _name is provided a function pointer, but will get optimized out by GCC.
*/#defineMETHOD(iface, name, ret, this,...)\static ret name(union{iface *_public; this;}\__attribute__((transparent_union)),##__VA_ARGS__);\statictypeof(name)*_##name =(typeof(name)*)name;\static ret name(this,##__VA_ARGS__)/**
* args macro
*//**
* This macro allows counting the number of arguments passed to a macro.
* Combined with the VA_ARGS_DISPATCH() macro this can be used to implement
* macro overloading based on the number of arguments.
* 0 to 10 arguments are currently supported.
*/#defineVA_ARGS_NUM(...)_VA_ARGS_NUM(0,##__VA_ARGS__,10,9,8,7,6,5,4,3,2,1,0)#define_VA_ARGS_NUM(_0,_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NUM,...) NUM/**
* This macro can be used to dispatch a macro call based on the number of given
* arguments, for instance:
*
* @code
* #define MY_MACRO(...) VA_ARGS_DISPATCH(MY_MACRO, __VA_ARGS__)(__VA_ARGS__)
* #define MY_MACRO1(arg) one_arg(arg)
* #define MY_MACRO2(arg1,arg2) two_args(arg1,arg2)
* @endcode
*
* MY_MACRO() can now be called with either one or two arguments, which will
* resolve to one_arg(arg) or two_args(arg1,arg2), respectively.
*/#defineVA_ARGS_DISPATCH(func,...)_VA_ARGS_DISPATCH(func,VA_ARGS_NUM(__VA_ARGS__))#define_VA_ARGS_DISPATCH(func, num)__VA_ARGS_DISPATCH(func, num)#define__VA_ARGS_DISPATCH(func, num) func ##num/**
* Assign variadic arguments to the given variables.
*
* @note The order and types of the variables are significant and must match the
* variadic arguments passed to the function that calls this macro exactly.
*
* @param last the last argument before ... in the function that calls this
* @param ... variable names
*/#defineVA_ARGS_GET(last,...)({\va_list _va_args_get_ap;\va_start(_va_args_get_ap, last);\_VA_ARGS_GET_ASGN(__VA_ARGS__)\va_end(_va_args_get_ap);\})/**
* Assign variadic arguments from a va_list to the given variables.
*
* @note The order and types of the variables are significant and must match the
* variadic arguments passed to the function that calls this macro exactly.
*
* @param list the va_list variable in the function that calls this
* @param ... variable names
*/#defineVA_ARGS_VGET(list,...)({\va_list _va_args_get_ap;\va_copy(_va_args_get_ap, list);\_VA_ARGS_GET_ASGN(__VA_ARGS__)\va_end(_va_args_get_ap);\})#define_VA_ARGS_GET_ASGN(...)VA_ARGS_DISPATCH(_VA_ARGS_GET_ASGN, __VA_ARGS__)(__VA_ARGS__)#define_VA_ARGS_GET_ASGN1(v1)__VA_ARGS_GET_ASGN(v1)#define_VA_ARGS_GET_ASGN2(v1,v2)__VA_ARGS_GET_ASGN(v1)__VA_ARGS_GET_ASGN(v2)#define_VA_ARGS_GET_ASGN3(v1,v2,v3)__VA_ARGS_GET_ASGN(v1)__VA_ARGS_GET_ASGN(v2)\__VA_ARGS_GET_ASGN(v3)#define_VA_ARGS_GET_ASGN4(v1,v2,v3,v4)__VA_ARGS_GET_ASGN(v1)__VA_ARGS_GET_ASGN(v2)\__VA_ARGS_GET_ASGN(v3)__VA_ARGS_GET_ASGN(v4)#define_VA_ARGS_GET_ASGN5(v1,v2,v3,v4,v5)__VA_ARGS_GET_ASGN(v1)__VA_ARGS_GET_ASGN(v2)\__VA_ARGS_GET_ASGN(v3)__VA_ARGS_GET_ASGN(v4)__VA_ARGS_GET_ASGN(v5)#define__VA_ARGS_GET_ASGN(v) v =va_arg(_va_args_get_ap,typeof(v));typedefstructenumerator_tenumerator_t;structenumerator_t{bool(*enumerate)(enumerator_t*this,...);bool(*venumerate)(enumerator_t*this, va_list args);void(*destroy)(enumerator_t*this);};
bool enumerator_enumerate_default(enumerator_t*enumerator,...){
va_list args;
bool result;if(!enumerator->venumerate){return FALSE;}va_start(args, enumerator);
result = enumerator->venumerate(enumerator, args);va_end(args);return result;}typedefenumstatus_tstatus_t;/**
* Return values of function calls.
*/enumstatus_t{/** Call succeeded */
SUCCESS,/** Call failed */
FAILED,/** Out of resources */
OUT_OF_RES,/** The suggested operation is already done */
ALREADY_DONE,/** Not supported */
NOT_SUPPORTED,/** One of the arguments is invalid */
INVALID_ARG,/** Something could not be found */
NOT_FOUND,/** Error while parsing */
PARSE_ERROR,/** Error while verifying */
VERIFY_ERROR,/** Object in invalid state */
INVALID_STATE,/** Destroy object which called method belongs to */
DESTROY_ME,/** Another call to the method is required */
NEED_MORE,};/**
* 对链表中的元素进行匹配的功能
*
* @param item current list item
* @param args user supplied data
* @return TRUE, if the item matched, FALSE otherwise
*/typedefbool(*linked_list_match_t)(void*item, va_list args);/**
* 对链表中的元素上进行函数调用
*
* @param item current list item
* @param args user supplied data
*/typedefvoid(*linked_list_invoke_t)(void*item, va_list args);typedefstructlinked_list_tlinked_list_t;structlinked_list_t{/**
* 得到列表中项的计数。
*
* @return number of items in list
*/int(*get_count)(linked_list_t*this);/**
* 在列表上建立一个枚举器。
*
* @note 枚举者的位置在第一次调用枚举( )之前是无效的。
*
* @return enumerator over list items
*/enumerator_t*(*create_enumerator)(linked_list_t*this);/**
* 将枚举者的当前位置重置到列表的开头。
*
* @param enumerator enumerator to reset
*/void(*reset_enumerator)(linked_list_t*this,enumerator_t*enumerator);/**
* 在列表的开头插入一个新的项目。
*
* @param item item value to insert in list
*/void(*insert_first)(linked_list_t*this,void*item);/**
* 删除列表中的第一项，并返回其值。
*
* @param item returned value of first item, or NULL
* @return SUCCESS, or NOT_FOUND if list is empty
*/status_t(*remove_first)(linked_list_t*this,void**item);/**
* 在枚举器当前指向的项前插入一个新项。
*
* 如果该方法在所有项都被枚举后才被调用，则该项最后被插入。这对于在排序列表中插入项目是有帮助的。
*
* @note The position of the enumerator is not changed. So it is safe to
* call this before or after remove_at() to replace the item at the current
* position (the enumerator will continue with the next item in the list).
* And in particular, when inserting an item before calling enumerate(),
* the enumeration will continue (or start) at the item that was first in
* the list before any items were inserted (enumerate() will return FALSE
* if the list was empty before).
*
* @param enumerator enumerator with position
* @param item item value to insert in list
*/void(*insert_before)(linked_list_t*this,enumerator_t*enumerator,void*item);/**
* 从枚举器指向的列表中移除一个项。
*
* If this method is called before calling enumerate() of the enumerator,
* the first item in the list, if any, will be removed. No item is removed,
* if the method is called after enumerating all items.
*
* @param enumerator enumerator with position
*/void(*remove_at)(linked_list_t*this,enumerator_t*enumerator);/**
* 从与给定项目匹配的列表中删除项目。
*
* If a compare function is given, it is called for each item, with the
* first parameter being the current list item and the second parameter
* being the supplied item. Return TRUE from the compare function to remove
* the item, return FALSE to keep it in the list.
*
* If compare is NULL, comparison is done by pointers.
*
* @param item item to remove/pass to comparator
* @param compare compare function, or NULL
* @return number of removed items
*/int(*remove)(linked_list_t*this,void*item,bool(*compare)(void*,void*));/**
* 返回第一个列表项的值，不将其移除。
*
* @param item returned value of first item
* @return SUCCESS, NOT_FOUND if list is empty
*/status_t(*get_first)(linked_list_t*this,void**item);/**
* 在列表的末尾插入一个新的项目。
*
* @param item value to insert into list
*/void(*insert_last)(linked_list_t*this,void*item);/**
* 删除列表中的最后一项，并返回其值。
*
* @param item returned value of last item, or NULL
* @return SUCCESS, NOT_FOUND if list is empty
*/status_t(*remove_last)(linked_list_t*this,void**item);/**
* 返回最后一个列表项的值，不将其移除。
*
* @param item returned value of last item
* @return SUCCESS, NOT_FOUND if list is empty
*/status_t(*get_last)(linked_list_t*this,void**item);/**
* 找到列表中的第一个匹配元素。
*
* The first object passed to the match function is the current list item,
* followed by the user supplied data.
* If the supplied function returns TRUE so does this function, and the
* current object is returned in the third parameter (if given), otherwise,
* the next item is checked.
*
* If match is NULL, *item and the current object are compared.
*
* @param match comparison function to call on each object, or NULL
* @param item the list item, if found, or NULL
* @param ... user data to supply to match function
* @return TRUE if found, FALSE otherwise (or if neither match,
* nor item is supplied)
*/bool(*find_first)(linked_list_t*this,linked_list_match_t match,void**item,...);/**
* 在所有包含的对象上调用一个方法。
*
* If a linked list contains objects with function pointers,
* invoke() can call a method on each of the objects. The
* method is specified by an offset of the function pointer,
* which can be evaluated at compile time using the offsetof
* macro, e.g.: list->invoke(list, offsetof(object_t, method));
*
* @param offset offset of the method to invoke on objects
*/void(*invoke_offset)(linked_list_t*this,size_t offset);/**
* 在所有包含的对象上调用一个函数。
*
* @param function function to call for each object
* @param ... user data to supply to called function
*/void(*invoke_function)(linked_list_t*this,linked_list_invoke_t function,...);/**
* 利用对象的克隆方法，克隆一个链表及其对象。
*
* @param offset offset to the objects clone function
* @return cloned list
*/linked_list_t*(*clone_offset)(linked_list_t*this,size_t offset);/**
* 用给定比较的方法比较两个列表及其相等的对象。
*
* @param other list to compare
* @param offset offset of the objects equals method
* @return TRUE if lists and objects are equal, FALSE otherwise
*/bool(*equals_offset)(linked_list_t*this,linked_list_t*other,size_t offset);/**
* Compare two lists and their objects for equality using the given function.
*
* @param other list to compare
* @param function function to compare the objects
* @return TRUE if lists and objects are equal, FALSE otherwise
*/bool(*equals_function)(linked_list_t*this,linked_list_t*other,bool(*)(void*,void*));/**
* 销毁一个Linked _ List对象。
*/void(*destroy)(linked_list_t*this);/**
* 使用析构函数销毁列表及其对象。
*
* If a linked list and the contained objects should be destroyed, use
* destroy_offset. The supplied offset specifies the destructor to
* call on each object. The offset may be calculated using the offsetof
* macro, e.g.: list->destroy_offset(list, offsetof(object_t, destroy));
*
* @param offset offset of the objects destructor
*/void(*destroy_offset)(linked_list_t*this,size_t offset);/**
* 使用清理函数销毁列表及其内容。
*
* If a linked list and its contents should get destroyed using a specific
* cleanup function, use destroy_function. This is useful when the
* list contains malloc()-ed blocks which should get freed,
* e.g.: list->destroy_function(list, free);
*
* @param function function to call on each object
*/void(*destroy_function)(linked_list_t*this,void(*)(void*));};linked_list_t*linked_list_create(void);typedefstructelement_telement_t;/**
* This element holds a pointer to the value it represents.
*/structelement_t{/**
* 列表项的值。
*/void*value;/**
* 前一个列表元素。
*
* NULL if first element in list.
*/element_t*previous;/**
* 下一个.
*
* NULL if last element in list.
*/element_t*next;};typedefstructprivate_linked_list_tprivate_linked_list_t;/**
* Private data of a linked_list_t object.
*
*/structprivate_linked_list_t{/**
* Public part of linked list.
*/linked_list_t public;/**
* 列表中的项目数量。
*/int count;/**
* 列表中的第一个元素。如果列表中没有元素，则NULL。
*/element_t*first;/**
* 列表中的最后一个元素。如果列表中没有元素，则NULL。
*/element_t*last;};METHOD(linked_list_t, get_count,int,private_linked_list_t*this){return this->count;}typedefstructprivate_enumerator_tprivate_enumerator_t;/**
* linked lists enumerator implementation
*/structprivate_enumerator_t{/**
* implements enumerator interface
*/enumerator_t public;/**
* associated linked list
*/private_linked_list_t*list;/**
* current item
*/element_t*current;};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;}METHOD(enumerator_t, enumerate_next, bool,private_enumerator_t*this, va_list args){if(this->current){
this->current = this->current->next;}returndo_enumerate(this, args);}METHOD(enumerator_t, enumerate_current, bool,private_enumerator_t*this, va_list args){
this->public.venumerate = _enumerate_next;returndo_enumerate(this, args);}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;}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;}METHOD(linked_list_t, get_first,status_t,private_linked_list_t*this,void**item){if(this->count ==0){return NOT_FOUND;}*item = this->first->value;return SUCCESS;}METHOD(linked_list_t, get_last,status_t,private_linked_list_t*this,void**item){if(this->count ==0){return NOT_FOUND;}*item = this->last->value;return SUCCESS;}//返回首次匹配的itemMETHOD(linked_list_t, find_first, bool,private_linked_list_t*this,linked_list_match_t match,void**item,...){element_t*current = this->first;
va_list args;
bool matched = FALSE;if(!match &&!item){return FALSE;}while(current){if(match){va_start(args, item);
matched =match(current->value, args);va_end(args);}else{
matched = current->value ==*item;}if(matched){if(item !=NULL){*item = current->value;}return TRUE;}
current = current->next;}return FALSE;}staticelement_t*element_create(void*value){element_t*this;INIT(this,.value = value,);return this;}//创建一个item，赋值val，插入list最前面METHOD(linked_list_t, insert_first,void,private_linked_list_t*this,void*item){element_t*element;
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++;}METHOD(linked_list_t, insert_last,void,private_linked_list_t*this,void*item){element_t*element;
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++;}METHOD(linked_list_t, insert_before,void,private_linked_list_t*this,private_enumerator_t*enumerator,void*item){element_t*current,*element;//list为空，无所谓，调用insert_last插入即可，insert_last里面会创建item
current = enumerator->current;if(!current){insert_last(this, item);return;}//创建item，若current->previous非空，插入previous和current之间，否则插在current之前，此时相当于放在list第一个位置
element =element_create(item);if(current->previous){
current->previous->next = element;
element->previous = current->previous;
current->previous = element;
element->next = current;}else{
current->previous = element;
element->next = current;
this->first = element;}
this->count++;}/**
* 从列表中解开一个元素，返回下面的元素
*/staticelement_t*remove_element(private_linked_list_t*this,element_t*element){element_t*next,*previous;//释放当前element，后空，则修正this->last，前空则修正this->first，否则next和previous互连，若都空则同时修正last和first为NULL
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;}METHOD(linked_list_t, remove_first,status_t,private_linked_list_t*this,void**item){if(get_first(this, item)== SUCCESS){remove_element(this, this->first);return SUCCESS;}return NOT_FOUND;}METHOD(linked_list_t, remove_last,status_t,private_linked_list_t*this,void**item){if(get_last(this, item)== SUCCESS){remove_element(this, this->last);return SUCCESS;}return NOT_FOUND;}METHOD(linked_list_t, remove_,int,private_linked_list_t*this,void*item,bool(*compare)(void*,void*)){element_t*current = this->first;int removed =0;while(current){//用函数比较或直接比较指针值if((compare &&compare(current->value, item))||(!compare && current->value == item)){
removed++;
current =remove_element(this, current);}else{//没有找到则继续遍历
current = current->next;}}//返回总计移除的数量return removed;}METHOD(linked_list_t, remove_at,void,private_linked_list_t*this,private_enumerator_t*enumerator){element_t*current;if(enumerator->current){
current = enumerator->current;
enumerator->current = current->next;/* the enumerator already points to the next item */
enumerator->public.venumerate = _enumerate_current;remove_element(this, current);}}METHOD(linked_list_t, invoke_offset,void,private_linked_list_t*this,size_t offset){element_t*current = this->first;void(**method)(void*);while(current){//如果一个链表包含带函数指针的对象,invoke ( )可以在每个对象上调用一个方法。其中//方法是通过函数指针的一个偏移量来指定的。可以在编译时使用offsetof进行评估
method = current->value + offset;(*method)(current->value);
current = current->next;}}METHOD(linked_list_t, invoke_function,void,private_linked_list_t*this,linked_list_invoke_t fn,...){element_t*current = this->first;
va_list args;//在所有包含的对象上调用fn,参数为链表上的对象和传入的argswhile(current){va_start(args, fn);fn(current->value, args);va_end(args);
current = current->next;}}METHOD(linked_list_t, clone_offset,linked_list_t*,private_linked_list_t*this,size_t offset){element_t*current = this->first;linked_list_t*clone;//新建链表，将原链表中的每个元素各自都执行其offset指定的函数，将函数返回值保存在链表中
clone =linked_list_create();while(current){void*(**method)(void*)= current->value + offset;
clone->insert_last(clone,(*method)(current->value));
current = current->next;}return clone;}METHOD(linked_list_t, equals_offset, bool,private_linked_list_t*this,linked_list_t*other_pub,size_t offset){private_linked_list_t*other =(private_linked_list_t*)other_pub;element_t*cur_t,*cur_o;//链表元素个数不同返回错误if(this->count != other->count){return FALSE;}//遍历，取各元素经offset获取的方法，比较二者，若不相同则返回错误，直至最后能够返回正确cur_t= this->first;
cur_o = other->first;while(cur_t&& cur_o){bool(**method)(void*,void*)=cur_t->value + offset;if(!(*method)(cur_t->value, cur_o->value)){return FALSE;}cur_t=cur_t->next;
cur_o = cur_o->next;}return TRUE;}//和equals_offset区别在于使用的比较函数为入参fnMETHOD(linked_list_t, equals_function, bool,private_linked_list_t*this,linked_list_t*other_pub,bool(*fn)(void*,void*)){private_linked_list_t*other =(private_linked_list_t*)other_pub;element_t*cur_t,*cur_o;if(this->count != other->count){return FALSE;}cur_t= this->first;
cur_o = other->first;while(cur_t&& cur_o){if(!fn(cur_t->value, cur_o->value)){return FALSE;}cur_t=cur_t->next;
cur_o = cur_o->next;}return TRUE;}METHOD(linked_list_t, destroy,void,private_linked_list_t*this){void*value;/* Remove all list items before destroying list */while(remove_first(this,&value)== SUCCESS){/* values are not destroyed so memory leaks are possible
* if list is not empty when deleting */}free(this);}METHOD(linked_list_t, destroy_offset,void,private_linked_list_t*this,size_t offset){element_t*current = this->first,*next;while(current){void(**method)(void*)= current->value + offset;(*method)(current->value);
next = current->next;free(current);
current = next;}free(this);}METHOD(linked_list_t, destroy_function,void,private_linked_list_t*this,void(*fn)(void*)){element_t*current = this->first,*next;while(current){fn(current->value);
next = current->next;free(current);
current = next;}free(this);}linked_list_t*linked_list_create(void){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,.remove_first = _remove_first,.remove_last = _remove_last,.remove = _remove_,.remove_at =(void*)_remove_at,.invoke_offset = _invoke_offset,.invoke_function = _invoke_function,.clone_offset = _clone_offset,.equals_offset = _equals_offset,.equals_function = _equals_function,.destroy = _destroy,.destroy_offset = _destroy_offset,.destroy_function = _destroy_function,},);return&this->public;}#include<stdint.h>#include<string.h>intmain(){typedefstructcache_entry_tcache_entry_t;/**
* Cache line in the interface name cache.
*/structcache_entry_t{/** reqid of the CHILD_SA */uint32_t reqid;/** cached interface name */char*iface;};uint32_t unique_id =0;cache_entry_t*val;linked_list_t*candidates;
candidates =linked_list_create();cache_entry_t*entry_0;INIT(entry_0,.reqid = unique_id++,.iface =strdup("eth0"),);
candidates->insert_first(candidates, entry_0);printf("count: %d\n", candidates->get_count(candidates));
candidates->get_first(candidates,(void*)&val);printf("first: reqid:%d-iface:%s\n", val->reqid, val->iface);cache_entry_t*entry_1;INIT(entry_1,.reqid = unique_id++,.iface =strdup("eth1"),);
candidates->insert_first(candidates, entry_1);printf("count: %d\n", candidates->get_count(candidates));
candidates->get_first(candidates,(void*)&val);printf("first: reqid:%d-iface:%s\n", val->reqid, val->iface);cache_entry_t*entry_2;INIT(entry_2,.reqid = unique_id++,.iface =strdup("eth2"),);
candidates->insert_last(candidates, entry_2);printf("count: %d\n", candidates->get_count(candidates));
candidates->get_first(candidates,(void*)&val);printf("first: reqid:%d-iface:%s\n", val->reqid, val->iface);
candidates->get_last(candidates,(void*)&val);printf("last: reqid:%d-iface:%s\n", val->reqid, val->iface);if(candidates->find_first(candidates,NULL,(void*)&val,(void*)&entry_2)){printf("find_first:reqid:%d-iface:%s\n", val->reqid, val->iface);}else{printf("not find first\n");}
candidates->destroy(candidates);return0;}
