【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;
}