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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
static void vec_append(char **data, int *length, int *capacity, int memsz) {
if (*length + 1 > *capacity) {
*capacity = (int)(*capacity * VEC_EXPAND_FACTOR + 1);
*data = (char *)realloc(*data, *capacity * memsz);
}
}
动态数组的完整实现
```c
#ifndef __VEC_H__
#define __VEC_H__
#include <stdlib.h>
#include <string.h>
// 扩容因子
#define VEC_EXPAND_FACTOR 1.5
#define VEC_EXTEND_FACTOR 1.25
/**
* @brief 声明一个动态数组
* @param T 数组中每个元素的数据类型
*/
#define Vec(T) \
struct { \
T *data; \
int len; \
int cap; \
}
/**
* @brief 数组解包
* @param v 数组指针
*/
#define vec_unpack(v) \
(char **)&(v)->data, &(v)->len, &(v)->cap, sizeof(*(v)->data)
/**
* @brief 动态数组扩容
* @param data 数组指针
* @param length 数组长度
* @param capacity 数组容量
* @param memsz 数组中每个元素的大小
*/
static void vec_append(char **data, int *length, int *capacity, int memsz) {
if (*length + 1 > *capacity) {
*capacity = (int)(*capacity * VEC_EXPAND_FACTOR + 1);
*data = (char *)realloc(*data, *capacity * memsz);
}
}
static void vec_extend(char **data, int *length, int *capacity, int memsz,
char **values, int count) {
if (*length + count > *capacity) {
*capacity = (int)((*length + count) * VEC_EXTEND_FACTOR + 1);
*data = (char *)realloc(*data, *capacity * memsz);
}
memcpy(*data + *length * memsz, *values, count * memsz);
*length += count;
}
/**
* @brief 删除元素
* @param data 数组指针
* @param length 数组长度
* @param capacity 数组容量
* @param memsz 数组中每个元素的大小
* @param start 删除的起始位置
* @param count 删除的元素个数
*/
static inline void vec_remove(char **data, int *length, int *capacity,
int memsz, int start, int count) {
(void)capacity;
memmove(*data + start * memsz, *data + (start + count) * memsz,
(*length - start - count) * memsz);
*length -= count;
}
/**
* @brief 获取切片
* @param data 数组指针
* @param length 数组长度
* @param capacity 数组容量
* @param memsz 数组中每个元素的大小
* @param start 切片的起始位置
* @param count 切片的元素个数
*/
static inline void *vec_splice(char **data, int *length, int *capacity,
int memsz, int start, int count) {
(void)capacity;
void *ptr = malloc(count * memsz);
memcpy(ptr, *data + start * memsz, count * memsz);
return ptr;
}
/**
* @brief 初始化动态数组
* @param v 数组指针
* @param __len 初始数组长度
* @param __cap 初始数组容量
*/
#define vec_init(v, __len, __cap) \
do { \
(v)->data = malloc((__cap) * sizeof(typeof(*(v)->data))); \
(v)->len = (__len); \
(v)->cap = (__cap); \
} while (0)
/**
* @brief 释放动态数组
*/
#define vec_free(v) free((v)->data)
#define vec_clear(v) ((v)->len = 0)
#define vec_append(v, val) \
(vec_append(vec_unpack(v)), (v)->data[(v)->len++] = (val))
/**
* @brief 返回数组切片
* @param dest 目标数组指针
* @param src 源数组指针
* @param start 切片的起始位置， 包含, 负数表示从后往前数
* @param end 切片的中止位置，不包含， 负数表示从后往前数
*/
#define vec_splice(dest, src, start, end) \
do { \
int l = start, r = end; \
if (start < 0) { \
l = (src)->len + start; \
} \
if (end < 0) { \
r = (src)->len + end; \
} \
(dest)->len = (r) - (l); \
(dest)->cap = (dest)->len; \
(dest)->data = vec_splice(vec_unpack(src), l, r - l); \
} while (0)
/**
* @brief 删除数组元素
* @param v 数组指针
* @param start 删除的起始位置
* @param count 删除的元素个数
*/
#define vec_remove(v, start, count) vec_remove(vec_unpack(v), start, count)
/**
* @brief 扩展数组
*/
#define vec_extend(v, buf, length) vec_extend(vec_unpack(v), buf, length)
#define vec_pop(v) \
do { \
if ((v)->len > 0) { \
(v)->len--; \
} \
} while (0)
#endif
|
