【10】Strongswan collections —— array

//array 代码解释与测试

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdarg.h>#define INIT(this, ...) ({ (this) = malloc(sizeof(*(this))); \*(this) = (typeof(*(this))){ __VA_ARGS__ }; (this); })#define TRUE true
#define FALSE false#define METHOD(iface, name, ret, this, ...) \static ret name(union {iface *_public; this;} \__attribute__((transparent_union)), ##__VA_ARGS__); \static typeof(name) *_##name = (typeof(name)*)name; \static ret name(this, ##__VA_ARGS__)/** 清理前未使用的头部/尾部元素的最大数量 */
#define ARRAY_MAX_UNUSED 32/*** 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.*/
#define VA_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.*/
#define VA_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*/
#define VA_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*/
#define VA_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));typedef struct array_t array_t;/*** Special array index values for insert/remove.*/
enum array_idx_t {ARRAY_HEAD = 0,ARRAY_TAIL = -1,
};/*** 数据是一个已分配的数据块，可能有未使用的头部和尾部：**   "esize" each (or sizeof(void*) if esize = 0)*  /-\ /-\ /-\ /-\ /-\ /-\** +---------------+-------------------------------+---------------+* | h | e | a | d | e | l | e | m | e | n | t | s | t | a | i | l |* +---------------+-------------------------------+---------------+** \--------------/ \-----------------------------/ \-------------/*      unused                    used                   unused*      "head"                   "count"                 "tail"**/
struct array_t {/** 数组中当前元素的个数（不包括头尾元素） */uint32_t count;/** 每个元素的大小，指针式数组元素大小为 0 */uint16_t esize;/** 数组前部已分配但未使用的元素个数 */uint8_t head;/** 数组末尾已分配但未使用的元素个数 */uint8_t tail;/** 数值元素 */void *data;
};/*** 获取数组若干元素的实际大小*/
static size_t get_size(array_t *array, uint32_t num)
{if (array->esize){return (size_t)array->esize * num;}return sizeof(void*) * num;
}/*** 增加tail个空间到room个数字节的空间*/
static void make_tail_room(array_t *array, uint8_t room)
{if (array->tail < room){array->data = realloc(array->data,get_size(array, array->count + array->head + room));array->tail = room;}
}/*** 增加head个空间到room个数的字节数*/
static void make_head_room(array_t *array, uint8_t room)
{if (array->head < room){uint8_t increase = room - array->head;array->data = realloc(array->data,get_size(array, array->count + array->tail + room));memmove(array->data + get_size(array, increase), array->data,get_size(array, array->count + array->tail + array->head));array->head = room;}
}/*** 向count区插入一个数据，插入位置之后数据向后move，占用tail区一个空间*/
static void insert_tail(array_t *array, int idx)
{make_tail_room(array, 1);memmove(array->data + get_size(array, array->head + idx + 1),array->data + get_size(array, array->head + idx),get_size(array, array->count - idx));array->tail--;array->count++;
}/*** head区减少1个空间当作count区空间，count区数据整体向head区移动一个空间*/
static void insert_head(array_t *array, int idx)
{make_head_room(array, 1);/* move down all elements before idx by one */memmove(array->data + get_size(array, array->head - 1),array->data + get_size(array, array->head),get_size(array, idx));array->head--;array->count++;
}/*** count区移走一个，移走区之后数据前移一个*/
static void remove_tail(array_t *array, int idx)
{/* move all items after idx one down */memmove(array->data + get_size(array, idx + array->head),array->data + get_size(array, idx + array->head + 1),get_size(array, array->count - 1 - idx));array->count--;array->tail++;
}/*** head区多1，count区少1*/
static void remove_head(array_t *array, int idx)
{/* move all items before idx one up */memmove(array->data + get_size(array, array->head + 1),array->data + get_size(array, array->head), get_size(array, idx));array->count--;array->head++;
}array_t *array_create(u_int esize, uint8_t reserve)
{array_t *array;INIT(array,.esize = esize,.tail = reserve,);if (array->tail){//初始分配tail个空间array->data = malloc(get_size(array, array->tail));}return array;
}int array_count(array_t *array)
{if (array){return array->count;}return 0;
}void array_compress(array_t *array)
{if (array){uint32_t tail;tail = array->tail;//去头if (array->head){memmove(array->data, array->data + get_size(array, array->head),get_size(array, array->count + array->tail));tail += array->head;array->head = 0;}//丢弃tail数据，保留count数据if (tail){size_t size = get_size(array, array->count);if (size){array->data = realloc(array->data, size);}else{free(array->data);array->data = NULL;}array->tail = 0;}}
}typedef struct enumerator_t enumerator_t;/*** Enumerator interface, allows enumeration over collections.*/
struct enumerator_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;
}METHOD(enumerator_t, enumerate_empty, bool,enumerator_t *enumerator, va_list args)
{return FALSE;
}typedef struct {/** public enumerator interface */enumerator_t public;/** enumerated array */array_t *array;/** current index +1, initialized at 0 */int idx;
} array_enumerator_t;METHOD(enumerator_t, enumerate, bool,array_enumerator_t *this, va_list args)
{void *pos, **out;VA_ARGS_VGET(args, out);//idx在count范围内移动，下标从0开始if (this->idx >= this->array->count){return FALSE;}//偏移   + this->array->head到count区，this->idx +到偏移位置pos = this->array->data +get_size(this->array, this->idx + this->array->head);if (this->array->esize){//返回位置指针*out = pos;}else{//指针数组则，返回数组中保存的指针*out = *(void**)pos;}//为枚举下一个做准备this->idx++;return TRUE;
}enumerator_t* enumerator_create_empty()
{enumerator_t *this;INIT(this,.enumerate = enumerator_enumerate_default,.venumerate = _enumerate_empty,.destroy = (void*)free,);return this;
}enumerator_t* array_create_enumerator(array_t *array)
{array_enumerator_t *enumerator;if (!array){return enumerator_create_empty();}INIT(enumerator,.public = {.enumerate = enumerator_enumerate_default,.venumerate = _enumerate,.destroy = (void*)free,},.array = array,);return &enumerator->public;
}void array_insert(array_t *array, int idx, void *data)
{if (idx < 0 || idx <= array_count(array)){void *pos;if (idx < 0){idx = array_count(array);}if (array->head && !array->tail){insert_head(array, idx);}else if (array->tail && !array->head){insert_tail(array, idx);}else if (idx > array_count(array) / 2){insert_tail(array, idx);}else{insert_head(array, idx);}pos = array->data + get_size(array, array->head + idx);if (array->esize){memcpy(pos, data, get_size(array, 1));}else{/* pointer based array, copy pointer value */*(void**)pos = data;}}
}bool array_get(array_t *array, int idx, void *data)
{if (!array){return FALSE;}if (idx >= 0 && idx >= array_count(array)){return FALSE;}if (idx < 0){if (array_count(array) == 0){return FALSE;}idx = array_count(array) - 1;}if (data){memcpy(data, array->data + get_size(array, array->head + idx),get_size(array, 1));}return TRUE;
}bool array_remove(array_t *array, int idx, void *data)
{if (!array_get(array, idx, data)){return FALSE;}if (idx < 0){idx = array_count(array) - 1;}if (idx > array_count(array) / 2){remove_tail(array, idx);}else{remove_head(array, idx);}if (array->head + array->tail > ARRAY_MAX_UNUSED){array_compress(array);}return TRUE;
}void array_remove_at(array_t *array, enumerator_t *public)
{array_enumerator_t *enumerator = (array_enumerator_t*)public;if (enumerator->idx){array_remove(array, --enumerator->idx, NULL);}
}void array_insert_create(array_t **array, int idx, void *ptr)
{if (*array == NULL){*array = array_create(0, 0);}array_insert(*array, idx, ptr);
}void array_insert_create_value(array_t **array, u_int esize,int idx, void *val)
{if (*array == NULL){*array = array_create(esize, 0);}array_insert(*array, idx, val);
}void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
{void *ptr;while (enumerator->enumerate(enumerator, &ptr)){array_insert(array, idx, ptr);}enumerator->destroy(enumerator);
}int main()
{int *data = malloc(sizeof (int));*data = 1;int *iter;array_t *at;at = array_create(0, 0);array_insert(at, ARRAY_TAIL, data);array_insert(at, ARRAY_TAIL, data);enumerator_t *enumerator;enumerator = array_create_enumerator(at);while (enumerator->enumerate(enumerator, &iter)){printf("iter: %d\n", *iter);}return 0;
}