Journey
0%

C语言实现一个支持任意类型的动态数组

发表于 更新于 阅读次数： Valine：

C语言中的内存对齐原则

详解内存对齐

内存对齐规则

  1. 第一个成员在与结构体变量偏移量为0的地址处。
  2. 其他成员变量要对齐到某个数字（对齐数）的整数倍的地址处。
  3. 结构体总大小为最大对齐数（每个成员变量都有一个对齐数）的整数倍。
  4. 如果嵌套了结构体的情况，嵌套的结构体对齐到自己的最大对齐数的整数倍处，结构体的整体大小就是所有最大对齐数（含嵌套结构体的对齐数）的整数倍。

对齐数

  1. 看编译环境，确认默认对齐位数 32位编译器，默认最小对齐为4字节，64位编译器默认最小对齐为8字节，指针长度也是8字节； 注意：64位系统在编译器是32位时或者注释为32位时，默认对齐也为4字节。可用以下语句声明为4字节： 

    1
    #pragma pack(4)

  2. 再确定最终对齐位数 在确定默认对齐位数后，找出结构体中最长字节的数据类型，比较最长数据类型和默认对齐位数，谁小，谁是最终对齐位数。 注意：最长字节的数据类型计算取其原始类型，比如，char a[3],在算最长数据类型时，其值为1。

  3. 长度计算 再加入新的长度时，需要计算已有长度是否能够整除新添加长度，不能整除需要填充空间进行偏移，直到能够整除，放入新的长度。最后完整长度需要能够整除最终对齐数，不能整除则需要填充偏移。

darray.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/**
 * @copyright (C) Lightshaker
 * @date 2023/07/03
*/

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

/**
 * @brief 支持build-in数据类型或自定义类型数据的动态顺序表
 * @memberof data_ 数据内容
 * @memberof listsize_ 数组长度
 * @memberof unitsize_ 数组单元大小
*/
typedef struct
{
    void *data_;    // 数据内容
    int listsize_;  // 数组长度
    int unitsize_;  // 数组单元大小
}dynamic_arr, *dynamic_arr_ptr;

/**
 * @brief 创建动态数据并初始化数据单元大小
 * @param unitsize 数据单元大小
*/
dynamic_arr darr_initiate(int unitsize); 

/**
 * @brief 以数据单元的整数倍扩容列表空间
 * @param arr_p 动态数组指针
 * @param extra 扩容长度(实际扩容extra*unitsize)
*/
void darr_expand(dynamic_arr_ptr arr_p, int extra); 

/**
 * @brief 添加数据单元到列表末尾
 * @param arr_p 动态数组指针
 * @param value 待添加的数据单元
*/
void darr_push(dynamic_arr_ptr arr_p, const void* value); 

/**
 * @brief 插入数据单元到列表中间索引为i的位置
 * @param arr_p 动态数组指针
 * @param i 插入的位置索引
 * @param value 待插入的数据单元
 * @return 是否执行成功
*/
bool darr_insert(dynamic_arr_ptr arr_p, int i, const void* value); 

/**
 * @brief 删除列表中索引为i的数据单元
 * @param arr_p 动态数组指针
 * @param i 删除的位置索引
 * @param element 删除成功时返回被删除的数据单元
 * @return 是否执行成功
*/
bool darr_erase(dynamic_arr_ptr arr_p, int i, void* element); 

/**
 * @brief 获取列表中索引为i的数据单元
 * @param arr_p 动态数组指针
 * @param i 获取的位置索引
 * @param element 获取成功时返回被获取的数据单元
 * @return 是否执行成功
*/
bool darr_get(const dynamic_arr_ptr arr_p, int i, void* element);

/**
 * @brief 替换列表中索引为i的数据单元
 * @param arr_p 动态数组指针
 * @param i 替换的位置索引
 * @param value 替换的数据单元
 * @return 是否执行成功
*/
bool darr_modify(dynamic_arr_ptr arr_p, int i, const void* value); 

/**
 * @brief 判断列表是否为空
 * @param arr_p 动态数组指针
 * @return 是否为空
*/
bool darr_isempty(const dynamic_arr_ptr arr_p); 

/**
 * @brief 清空列表
 * @param arr_p 动态数组指针
*/
void darr_clear(dynamic_arr_ptr arr_p); 

/**
 * @brief 十六进制打印数组内容
 * @param arr_p 动态数组指针
 * @param printsize 是否打印数组长度
*/
void darr_print(dynamic_arr_ptr arr_p, bool printsize);

darray.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
/**
 * @copyright (C) Lightshaker
 * @date 2023/07/03
*/

#include "darray.h"

dynamic_arr darr_initiate(int unitsize)
{
    dynamic_arr arr;
    arr.unitsize_ = unitsize;
    arr.listsize_ = 0;
    arr.data_ = NULL;
    return arr;
}

void darr_expand(dynamic_arr_ptr arr_p, int extra)
{
    // 原list长度为0时
    if(arr_p->listsize_ == 0)
    {
        arr_p->data_ = (void *)malloc(extra * arr_p->unitsize_);
        arr_p->listsize_ += extra;
        return;
    }
    int cur_listsize = arr_p->listsize_;
    void* dst = (void *)malloc((cur_listsize + extra) * arr_p->unitsize_);
    for(uint8_t* p = (uint8_t*)arr_p->data_, *pdst = (uint8_t*)dst; p < (uint8_t*)arr_p->data_+cur_listsize*arr_p->unitsize_+1; p++, pdst++)
    {
        memcpy(pdst, p, 1);
    }
    arr_p->listsize_ += extra;
    free(arr_p->data_);
    arr_p->data_ = dst;
    dst = NULL;
}

void darr_push(dynamic_arr_ptr arr_p, const void* value)
{
    darr_expand(arr_p, 1);
    memcpy((uint8_t*)arr_p->data_+(arr_p->listsize_-1)*arr_p->unitsize_, (uint8_t*)value, arr_p->unitsize_);
}

bool darr_insert(dynamic_arr_ptr arr_p, int i, const void* value)
{
    if(i < 0 || i > arr_p->listsize_)
        return false;
    if(i == arr_p->listsize_)
    {
        darr_push(arr_p, value);
        return true;
    }
    else 
    {
        darr_expand(arr_p, 1);
        for(int j = arr_p->listsize_-1; j >= i; j--)
            memcpy((uint8_t*)arr_p->data_ + j*arr_p->unitsize_, (uint8_t*)arr_p->data_ + (j-1)*arr_p->unitsize_, arr_p->unitsize_);
        memcpy((uint8_t*)arr_p->data_ + i*arr_p->unitsize_, (uint8_t*)value, arr_p->unitsize_);
        return true;
    }
}

bool darr_erase(dynamic_arr_ptr arr_p, int i, void* element)
{
    if(i < 0)
        return false;
    else 
    {
        if(element != NULL)
            memcpy(element, arr_p->data_ + i, arr_p->unitsize_);
        if(i < arr_p->listsize_ - 1)
            for(int j = i; j < arr_p->listsize_; j++)
                memcpy(arr_p->data_+j*arr_p->unitsize_, arr_p->data_+(j+1)*arr_p->unitsize_, arr_p->unitsize_);
        arr_p->listsize_ --;
        return true;
    }
}

bool darr_get(const dynamic_arr_ptr arr_p, int i, void* element)
{
    if(i < 0 || i > arr_p->listsize_ - 1)
        return false;
    else
    {
        memcpy(element, (uint8_t*)arr_p->data_+i*arr_p->unitsize_, arr_p->unitsize_);
        return true;
    }
}

bool darr_modify(dynamic_arr_ptr arr_p, int i, const void* value)
{
    if(i < 0 || i > arr_p->listsize_ - 1)
        return false;
    else
    {
        memcpy(arr_p->data_+i*arr_p->unitsize_, value, arr_p->unitsize_);
        return true;
    }  
}

bool darr_isempty(const dynamic_arr_ptr arr_p)
{
    return arr_p->listsize_ == 0;
}

void darr_clear(dynamic_arr_ptr arr_p)
{
    free(arr_p->data_);
    arr_p->data_ = NULL;
    arr_p->listsize_ = 0;
    arr_p->unitsize_=0;
}

void darr_print(dynamic_arr_ptr arr_p, bool printsize)
{
    if(printsize)
    {
        printf("(darr_print) Length of input arr is ------ %d units\n", arr_p->listsize_);
        printf("(darr_print) Unitsize of input arr is ---- %d bytes = %d bits\n", arr_p->unitsize_, arr_p->unitsize_*8);
        printf("(darr_print) Total size of input arr is -- %d bytes = %d bits\n", arr_p->listsize_*arr_p->unitsize_, (arr_p->listsize_*arr_p->unitsize_)*8);
    }

    printf("(darr_print) Data of input arr is: ");
    // for(uint8_t* p = (uint8_t*)arr_p->data_; p < (uint8_t*)arr_p->data_+arr_p->listsize_*arr_p->unitsize_; p++)
    for(uint8_t* p = (uint8_t*)arr_p->data_+arr_p->listsize_*arr_p->unitsize_-1; p > (uint8_t*)arr_p->data_-1; p--)
    {
        // printf("%x", *p);
        printf("%s%x", *p<16?"0":"", *p);
        if((p-(uint8_t*)arr_p->data_) % arr_p->unitsize_ == 0)
            printf(" ");
    }
    printf("\n");
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @copyright (C) Lightshaker
 * @date 2023/07/03
*/

#include "darray.h"

#pragma pack(1) // 指定编译器对齐数为1字节

typedef struct{
    char a;
    short b;
    const char* c;
}test_struct, *test_struct_ptr;

int main()
{
    printf("sizeof(test_struct) = %ld\n", sizeof(test_struct));
    dynamic_arr arr = darr_initiate(sizeof(test_struct));
  
    test_struct t1 = {'a', 1, "hello"};
    test_struct t2 = {'b', 255, "world"};
    test_struct t3 = {'c', 65535, "!"};
    darr_push(&arr, &t1);
    darr_push(&arr, &t2);
    darr_push(&arr, &t3);
  
    darr_print(&arr, true);

    test_struct t4;
    darr_get(&arr, 1, &t4);
    printf("t4.a = %c, t4.b = %d, t4.c = %s\n", t4.a, t4.b, t4.c);

    darr_erase(&arr, 1, NULL);
    darr_get(&arr, 1, &t4);
    printf("t4.a = %c, t4.b = %d, t4.c = %s\n", t4.a, t4.b, t4.c);
}