252 lines
7.2 KiB
C
252 lines
7.2 KiB
C
typedef struct { size_t len; size_t cap; } array_header_t;
|
|
#define array_header(x) ((x) ? (((array_header_t *)(x)) - 1) : 0)
|
|
#define arrlen(x) ((x) ? array_header(x)->len : 0)
|
|
#define arrleni(x) ((int)arrlen(x))
|
|
#define arrcap(x) ((x) ? array_header(x)->cap : 0)
|
|
#define arrpush(x, i) (array_grow((void **)&(x), sizeof((x)[0]), 1), (x)[array_header(x)->len++] = (i))
|
|
#define arrpop(x) (assert(arrlen(x) > 0), (x)[--array_header(x)->len])
|
|
#define arrlast(x) (assert(x), ((x) + arrlen(x) - 1))
|
|
#define arrend(x) ((x) + arrlen(x))
|
|
#define arrdelswap(x, i) (assert((i) < arrlen(x)), (x)[(i)] = (x)[--array_header(x)->len])
|
|
#define arrdeln(x, i, n) (assert(arrlen(x) > 0), assert((n) > 0), assert((i) < arrlen(x)), assert((i) + (n) <= arrlen(x)), memmove((x) + (i), (x) + (i) + (n), (arrlen(x) - (i) - (n)) * sizeof((x)[0])), array_header(x)->len -= (n))
|
|
#define arrdel(x, i) arrdeln((x), (i), 1)
|
|
#define arrfree(x) (free(array_header(x)), (x) = NULL)
|
|
#define arrsetcap(x,v) array_set_cap((void **)&(x), sizeof((x)[0]), (v))
|
|
#define arrsetlen(x,v) array_set_len((void **)&(x), sizeof((x)[0]), (v))
|
|
#define arrgrow(x,len) array_grow((void **)&(x), sizeof((x)[0]), (len))
|
|
#define arrforex(T, arr, it) for (T *it = (arr); it != arrend(arr); it += 1)
|
|
#define arrfor(T, arr) arrforex(T, arr, it)
|
|
#define arrins(x,i,v) (array_make_space_insert((void **)&(x), sizeof((x)[0]), (i)), (x)[(i)] = (v), array_header(x)->len+=1)
|
|
|
|
static void array_set_cap(void **p, size_t sizeof_elem, size_t cap) {
|
|
assert(cap < INT_MAX);
|
|
assert(sizeof_elem < INT_MAX);
|
|
if (arrcap(*p) != cap) {
|
|
array_header_t *new_head = realloc(array_header(*p), sizeof(array_header_t) + sizeof_elem * cap);
|
|
new_head->cap = cap;
|
|
if (new_head->len > new_head->cap) {
|
|
new_head->len = new_head->cap;
|
|
}
|
|
*p = new_head + 1;
|
|
}
|
|
}
|
|
|
|
static void array_set_len(void **p, size_t sizeof_elem, size_t len) {
|
|
assert(len < INT_MAX);
|
|
assert(sizeof_elem < INT_MAX);
|
|
if (len > arrcap(*p)) {
|
|
array_set_cap(p, sizeof_elem, len);
|
|
}
|
|
array_header(*p)->len = len;
|
|
}
|
|
|
|
static void array_grow(void **p, size_t sizeof_element, size_t add_len) {
|
|
size_t cap = arrcap(*p);
|
|
if (arrlen(*p) + add_len > cap) {
|
|
size_t cap_check0 = (cap ? cap : 8);
|
|
size_t new_cap = (cap_check0 + add_len - 1) * 2;
|
|
assert(new_cap >= cap);
|
|
array_header_t *new_head = realloc(array_header(*p), sizeof_element * new_cap + sizeof(array_header_t));
|
|
assert(new_head);
|
|
new_head->cap = new_cap;
|
|
if (cap == 0) {
|
|
new_head->len = 0;
|
|
}
|
|
*p = new_head + 1;
|
|
}
|
|
}
|
|
|
|
void print_int_array(int *arr) {
|
|
printf("len: %zu cap: %zu data: [", arrlen(arr), arrcap(arr));
|
|
for (size_t i = 0; i < arrlen(arr); i += 1) {
|
|
printf("%d ", arr[i]);
|
|
}
|
|
printf("]\n");
|
|
}
|
|
|
|
static void array_make_space_insert(void **p, size_t sizeof_elem, size_t i) {
|
|
assert(i < arrlen(*p)+1);
|
|
array_grow(p, sizeof_elem, 1);
|
|
void *source = *p + (i * sizeof_elem);
|
|
void *dest = *p + ((i + 1) * sizeof_elem);
|
|
size_t move_size = (arrlen(*p) - i) * sizeof_elem;
|
|
memmove(dest, source, move_size);
|
|
}
|
|
|
|
static void test_array(void) {
|
|
// basic push/pop
|
|
{
|
|
int *arr = NULL;
|
|
for (int i = 0; i < 65; i += 1) {
|
|
arrpush(arr, i);
|
|
}
|
|
{
|
|
int i = 0;
|
|
for (int *it = arr; it != arrend(arr); it += 1, i += 1) {
|
|
assert(*it == i);
|
|
}
|
|
i = 0;
|
|
arrfor(int, arr) {
|
|
assert(*it == i);
|
|
i += 1;
|
|
}
|
|
assert(i == 65);
|
|
}
|
|
for (int i = 64; i >= 0; i -= 1) {
|
|
int val = arrpop(arr);
|
|
assert(val == i);
|
|
}
|
|
assert(arrlen(arr) == 0);
|
|
assert(arrcap(arr) == 128);
|
|
arrfree(arr);
|
|
}
|
|
|
|
{
|
|
int *arr = NULL;
|
|
arrfor(int, arr) {
|
|
assert(0);
|
|
}
|
|
}
|
|
|
|
// delswap
|
|
{
|
|
int *arr = NULL;
|
|
arrpush(arr, 0);
|
|
arrpush(arr, 1);
|
|
arrpush(arr, 2);
|
|
arrpush(arr, 3);
|
|
arrdelswap(arr, 1);
|
|
assert(arrlen(arr) == 3);
|
|
assert(arr[0] == 0);
|
|
assert(arr[1] == 3);
|
|
assert(arr[2] == 2);
|
|
arrfree(arr);
|
|
}
|
|
|
|
// setlen
|
|
{
|
|
int *arr = NULL;
|
|
arrsetlen(arr, 5);
|
|
assert(arrlen(arr) == 5);
|
|
assert(arrcap(arr) == 5);
|
|
arr[0] = 10;
|
|
arr[1] = 11;
|
|
arr[2] = 12;
|
|
arr[3] = 13;
|
|
arr[4] = 14;
|
|
arrsetlen(arr, 2);
|
|
assert(arrlen(arr) == 2);
|
|
assert(arr[0] == 10);
|
|
assert(arr[1] == 11);
|
|
arrsetlen(arr, 8);
|
|
assert(arrlen(arr) == 8);
|
|
assert(arrcap(arr) == 8);
|
|
arr[7] = 99;
|
|
assert(arr[7] == 99);
|
|
arrfree(arr);
|
|
}
|
|
|
|
// setcap
|
|
{
|
|
int *arr = NULL;
|
|
arrsetcap(arr, 16);
|
|
assert(arrcap(arr) == 16);
|
|
assert(arrlen(arr) == 0);
|
|
for (int i = 0; i < 8; i += 1) {
|
|
arrpush(arr, i);
|
|
}
|
|
assert(arrlen(arr) == 8);
|
|
assert(arrcap(arr) == 16);
|
|
arrsetcap(arr, 64);
|
|
assert(arrcap(arr) == 64);
|
|
assert(arrlen(arr) == 8);
|
|
assert(arr[0] == 0);
|
|
assert(arr[7] == 7);
|
|
arrsetcap(arr, 4);
|
|
assert(arrlen(arr) == 4);
|
|
assert(arrcap(arr) == 4);
|
|
arrfor(int, arr) *it = 1;
|
|
arrfree(arr);
|
|
}
|
|
|
|
// arrins
|
|
{
|
|
int *arr = NULL;
|
|
arrins(arr,0,0);
|
|
arrins(arr,0,1);
|
|
arrins(arr,0,2);
|
|
assert(arrlen(arr) == 3);
|
|
assert(arrcap(arr) == 16);
|
|
assert(arr[0] == 2);
|
|
assert(arr[1] == 1);
|
|
assert(arr[2] == 0);
|
|
arrins(arr,1,5);
|
|
assert(arr[1] == 5);
|
|
assert(arr[2] == 1);
|
|
// print_int_array(arr);
|
|
}
|
|
|
|
// arrdeln
|
|
{
|
|
int *arr = NULL;
|
|
arrpush(arr, 1);
|
|
arrpush(arr, 2);
|
|
arrpush(arr, 3);
|
|
arrpush(arr, 4);
|
|
arrdeln(arr, 0, 2);
|
|
assert(arrlen(arr) == 2);
|
|
assert(arr[0] == 3);
|
|
assert(arr[1] == 4);
|
|
arrdeln(arr, 0, 2);
|
|
assert(arrlen(arr) == 0);
|
|
arrfree(arr);
|
|
}
|
|
|
|
// arrdeln
|
|
{
|
|
int *arr = NULL;
|
|
arrpush(arr, 0);
|
|
arrpush(arr, 1);
|
|
arrpush(arr, 2);
|
|
arrpush(arr, 3);
|
|
arrdeln(arr, 2, 1);
|
|
arrdeln(arr, 0, 1);
|
|
assert(arrlen(arr) == 2);
|
|
assert(arr[0] == 1);
|
|
assert(arr[1] == 3);
|
|
arrfree(arr);
|
|
}
|
|
|
|
// arrins + arrdeln/arrdel overlap
|
|
{
|
|
// 1, 2, 3, 4, 5, 6
|
|
int *arr = NULL;
|
|
for (int i = 0; i < 6; i += 1) {
|
|
arrins(arr, i, i + 1);
|
|
}
|
|
for (int i = 0; i < 6; i += 1) {
|
|
assert(arr[i] == i + 1);
|
|
}
|
|
|
|
// len=9 cap=16
|
|
// $8 = {100, 1, 101, 2, 102, 3, 4, 5, 6}
|
|
for (int i = 0; i < 3; i += 1) {
|
|
int idx = (i * 2) % (arrlen(arr) + 1);
|
|
arrins(arr, idx, 100 + i);
|
|
}
|
|
assert(arrlen(arr) == 9);
|
|
arrdeln(arr, 2, 2);
|
|
assert(arrlen(arr) == 7);
|
|
arrdel(arr, arrlen(arr) - 1);
|
|
assert(arrlen(arr) == 6);
|
|
|
|
for (int i = 0; i < arrleni(arr); i += 1) {
|
|
if (i > 0) {
|
|
assert(arr[i] != arr[i - 1]);
|
|
}
|
|
assert(arr[i] > 0);
|
|
}
|
|
arrfree(arr);
|
|
}
|
|
}
|