数据结构与算法9 — 二维动态字节数组

尊重作者劳动成果，转载请注明出处，谢谢！

1. byteArray.h

#ifndef bytesArray_H
#define bytesArray_H

#include "types.h"

//字节数组集合
typedef struct
{
    byte **dataSet;  //指针数组，存放着每个数组的首地址
    size_t *sizeSet; //每个数组的大小集合
    size_t capacity; //数组容量
    size_t size;     //数组长度
} BytesArray;

#define bytesArrayItem(array, index) 
    ((array)->dataSet[index])

#define bytesArrayItemSize(array, index) 
    ((array)->sizeSet[index])

#ifdef __cplusplus
extern "C"
{
#endif
    BytesArray *bytesArray_create(size_t capacity);
    boolean bytesArray_init(BytesArray *array, size_t capacity);
    void bytesArray_destory(BytesArray *array);
    void bytesArray_free(BytesArray *array);
    void bytesArray_clear(BytesArray *array);
    boolean bytesArray_expand(BytesArray *array, size_t increment);
    boolean bytesArray_shrink(BytesArray *array);
    size_t bytesArray_length(const BytesArray *array);
    boolean bytesArray_full(const BytesArray *array);
    size_t bytesArray_get(const BytesArray *array, size_t index, byte **data);
    void bytesArray_set(BytesArray *array, size_t index, const byte *data, size_t dataSize);
    void bytesArray_add(BytesArray *array, const byte *data, size_t dataSize);
    void bytesArray_insert(BytesArray *array, size_t index, const byte *data, size_t dataSize);
    void bytesArray_remove(BytesArray *array, size_t index);
#ifdef __cplusplus
}
#endif

#endif

2. byteArray.c

#include "bytesArray.h"
#include <string.h>
#include <stdlib.h>

static boolean byteArray_init(byte **array, const byte *data, size_t dataSize)
{
    if (array == NULL || dataSize <= 0)
        return False;

    *array = (byte *)malloc(dataSize * sizeof(byte));
    if (*array == NULL)
        return False;

    memcpy(*array, data, dataSize);
    return True;
}

//创建并初始化一个数组（推荐使用）
BytesArray *bytesArray_create(size_t capacity)
{
    BytesArray *array = (BytesArray *)malloc(sizeof(BytesArray));
    if (array == NULL)
        return NULL;

    if (!bytesArray_init(array, capacity))
    {
        free(array);
        return NULL;
    }

    return array;
}

//初始化
boolean bytesArray_init(BytesArray *array, size_t capacity)
{
    if (array == NULL || capacity <= 0)
        return False;

    array->dataSet = (byte **)malloc(capacity * sizeof(byte *));
    if (array->dataSet == NULL)
        return False;

    array->sizeSet = (size_t *)malloc(capacity * sizeof(size_t));
    if (array->sizeSet == NULL)
    {
        free(array->dataSet);
        return False;
    }

    memset(array->dataSet, 0, capacity * sizeof(byte *));
    memset(array->sizeSet, 0, capacity * sizeof(size_t));
    array->capacity = capacity;
    array->size = 0;
    return True;
}

//销毁（与create配对使用）
void bytesArray_destory(BytesArray *array)
{
    if (array == NULL)
        return;

    bytesArray_free(array);
    free(array);
}

//释放内存（与init配对使用）
void bytesArray_free(BytesArray *array)
{
    if (array == NULL)
        return;

    if (array->dataSet != NULL)
    {
        //释放每一个数组
        size_t i;
        for (i = 0; i < array->size; i++)
        {
            free(array->dataSet[i]);
        }

        free(array->dataSet);
        array->dataSet = NULL;
    }

    if (array->sizeSet != NULL)
    {
        free(array->sizeSet);
        array->sizeSet = NULL;
    }

    array->size = 0;
    array->capacity = 0;
}

//清空数组
void bytesArray_clear(BytesArray *array)
{
    if (array == NULL)
        return;

    if (array->dataSet != NULL)
    {
        //释放每一个数组
        size_t i;
        for (i = 0; i < array->size; i++)
        {
            free(array->dataSet[i]);
        }

        memset(array->dataSet, 0, array->capacity * sizeof(byte *));
        memset(array->sizeSet, 0, array->capacity * sizeof(size_t));
    }

    array->size = 0;
    bytesArray_shrink(array); //收缩数组
}

//扩充数组
boolean bytesArray_expand(BytesArray *array, size_t increment)
{
    if (array == NULL || increment <= 0)
        return False;

    byte **data = (byte **)realloc(array->dataSet, (array->capacity + increment) * sizeof(byte *));
    if (data == NULL)
        return False;

    size_t *size = (size_t *)realloc(array->sizeSet, (array->capacity + increment) * sizeof(size_t));
    if (size == NULL)
        return False;

    array->dataSet = data;
    array->sizeSet = size;
    array->capacity += increment;
    return True;
}

//收缩数组
boolean bytesArray_shrink(BytesArray *array)
{
    if (array == NULL)
        return False;

    if (bytesArray_full(array))
        return False;

    size_t capacity;
    if (array->size == 0)
        capacity = 1; //收缩为1
    else
        capacity = array->size; //收缩到当前大小

    byte **data = (byte **)realloc(array->dataSet, capacity * sizeof(byte *));
    if (data == NULL)
        return False;

    size_t *size = (size_t *)realloc(array->sizeSet, capacity * sizeof(size_t));
    if (size == NULL)
        return False;

    array->dataSet = data;
    array->sizeSet = size;
    array->capacity = capacity;
    return True;
}

//获取数组长度
size_t bytesArray_length(const BytesArray *array)
{
    if (array == NULL || array->dataSet == NULL)
        return 0;

    return array->size;
}

//判断数据是否已满
boolean bytesArray_full(const BytesArray *array)
{
    if (array == NULL)
        return False;

    return array->size == array->capacity ? True : False;
}

//获取指定索引的元素，类似数组的下标访问
size_t bytesArray_get(const BytesArray *array, size_t index, byte **data)
{
    if (array == NULL || index >= array->size)
        return 0;

    if (data != NULL)
        *data = array->dataSet[index];

    return array->sizeSet[index];
}

//修改指定索引位置的元素
void bytesArray_set(BytesArray *array, size_t index, const byte *data, size_t dataSize)
{
    if (array == NULL || index >= array->size)
        return;

    if (dataSize <= array->sizeSet[index])
    {
        memcpy(array->dataSet[index], data, dataSize);
    }
    else
    {
        free(array->dataSet[index]);
        byteArray_init(&array->dataSet[index], data, dataSize);
    }

    array->sizeSet[index] = dataSize;
}

//在数组末尾添加元素
void bytesArray_add(BytesArray *array, const byte *data, size_t dataSize)
{
    if (array == NULL)
        return;

    if (bytesArray_full(array) && !bytesArray_expand(array, array->capacity))
        return;

    byteArray_init(&array->dataSet[array->size], data, dataSize);
    array->sizeSet[array->size] = dataSize;
    array->size++;
}

//在指定索引的位置上插入元素
void bytesArray_insert(BytesArray *array, size_t index, const byte *data, size_t dataSize)
{
    if (array == NULL || index > array->size)
        return;

    if (bytesArray_full(array) && !bytesArray_expand(array, array->capacity))
        return;

    if (index == array->size) //add
    {
        byteArray_init(&array->dataSet[array->size], data, dataSize);
    }
    else //insert
    {
        byte **src = array->dataSet + index;
        byte **dest = src + 1;
        memmove(dest, src, (array->size - index) * sizeof(byte *));
        byteArray_init(&array->dataSet[index], data, dataSize);

        size_t *src_s = array->sizeSet + index;
        size_t *dest_s = src_s + 1;
        memmove(dest_s, src_s, (array->size - index) * sizeof(size_t));
    }

    array->sizeSet[index] = dataSize;
    array->size++;
}

//删除指定索引位置的元素
void bytesArray_remove(BytesArray *array, size_t index)
{
    if (array == NULL)
        return;

    if (index >= array->size)
        return;

    free(array->dataSet[index]);

    if (index != array->size - 1)
    {
        byte **src = array->dataSet + index + 1;
        byte **dest = array->dataSet + index;
        memmove(dest, src, (array->size - 1 - 1) * sizeof(byte *));

        size_t *src_s = array->sizeSet + index + 1;
        size_t *dest_s = array->sizeSet + index;
        memmove(dest_s, src_s, (array->size - 1 - 1) * sizeof(size_t));
    }

    array->size -= 1;
}

 3. main.c

#include "bytesArray.h"
#include "byteConverter.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void test_bytesArray()
{
    printf("
########## bytesArray ##########
");

    BytesArray *array = bytesArray_create(3);

    byte buf1[] = {0, 1, 2, 3};
    bytesArray_add(array, buf1, sizeof(buf1));

    byte buf2[] = {5, 6, 7, 8, 9};
    bytesArray_insert(array, 0, buf2, sizeof(buf2));

    byte buf3[] = {0x11, 0x12, 0x13, 0x14, 0x15, 0x16};
    bytesArray_add(array, buf3, sizeof(buf3));

    byte *buf4 = (byte *)malloc(6);
    buf4[0] = 0x20;
    buf4[1] = 0x21;
    buf4[2] = 0x22;
    buf4[3] = 0x23;
    buf4[4] = 0x24;
    buf4[5] = 0x25;
    bytesArray_insert(array, 3, buf4, 6);
    free(buf4);

    printf("bytesArray: size = %d
", array->size);
    size_t i;
    for (i = 0; i < array->size; i++)
    {
        byte *buf;
        size_t len = bytesArray_get(array, i, &buf);
        if (len > 0)
        {
            printBytes(buf, len, False);
            printf("
");
        }
    }
    printf("
");

    bytesArray_remove(array, 2);
    bytesArray_clear(array);
    bytesArray_add(array, buf1, sizeof(buf1));
    bytesArray_add(array, buf2, sizeof(buf2));

    printf("bytesArray: size = %d
", array->size);
    for (i = 0; i < array->size; i++)
    {
        byte *buf = bytesArrayItem(array, i);
        size_t len = bytesArrayItemSize(array, i);
        if (len > 0)
        {
            printBytes(buf, len, False);
            printf("
");
        }
    }

    bytesArray_destory(array);
}

int main(int argc, char **argv)
{
    test_bytesArray();
    return 0;
}