C 語言實現通用動態數組：從數據結構到完整庫設計

編輯：關於C語言

引言：動態數組設計切入點

高級語言中動態數組常見為 list 或 vector。本文在 C 語言中實現類 vector 容器，參考優秀開源項目 twemproxy（源碼）的設計風格，追求清晰、高效、美感。

核心數據結構

設計思路集中於結構體定義：

struct array {
    void *as;        // 數據區首地址
    unsigned len;    // 當前元素個數
    unsigned size;   // 當前容量（元素總數）
    size_t alloc;    // 單個元素字節大小
};

as：指向堆內存起始地址。
len：已使用元素數。
size：已分配容量，滿時擴容（通常翻倍）。
alloc：元素大型，支持任意類型存儲。

C11 內聯函數最佳實踐

為兼容 MSVC (VS2015) 與 GCC (5.3+)，採用分離聲明/定義模式：

/* 頭文件聲明 */
extern void heoo(void);

/* 源文件定義 */
inline void heoo(void) { ... }

避免 inline 解析差異導致的警告。參考：外部資料。

接口設計（array.h）

array.h 圖示

#ifndef _H_SIMPLEC_ARRAY
#define _H_SIMPLEC_ARRAY

#include <stdlib.h>
#define sm_free free

typedef enum {
    RT_SuccessBase = 0,
    RT_ErrorBase = -1,
    RT_ErrorParam = -2,
    RT_ErrorMalloc = -3,
    RT_ErrorFopen = -4,
    RT_ErrorClose = -5
} flag_e;

typedef int (*icmp_f)(const void *, const void *);  // 比較函數類型
typedef flag_e (*each_f)(void *node, void *arg);    // 遍歷回調類型

struct array {
    void *as;
    unsigned len;
    unsigned size;
    size_t alloc;
};
typedef struct array *array_t;

/* 棧上對象宏：自動調用 array_newinit 初始化 */
#define ARRAY_NEW(var, size, alloc) \
    struct array $__##var = { NULL, 0, 0, alloc }, *var = &$__##var; \
    array_newinit(var, size)
#define ARRAY_DELETE(var) sm_free(var->as)

/* 堆上對象生命週期 */
extern array_t array_new(unsigned size, size_t alloc);
extern void array_delete(array_t a);
extern void array_newinit(array_t a, unsigned size);

/* 元素操作 */
extern unsigned array_idx(array_t a, void *elem);
extern void *array_push(array_t a);
extern void *array_pop(array_t a);
extern void *array_get(array_t a, unsigned idx);
extern void *array_top(array_t a);

/* 容器操作 */
extern void array_swap(array_t a, array_t b);
extern void array_sort(array_t a, icmp_f compare);
extern flag_e array_each(array_t a, each_f func, void *arg);

#endif

實現細節（array.c）

array.c 圖示

1. 內存管理封裝

static void *sm_malloc(size_t sz) {
    void *ptr = malloc(sz);
    if (!ptr) { fprintf(stderr, "malloc %zu fail\n", sz); exit(EXIT_FAILURE); }
    memset(ptr, 0, sz);
    return ptr;
}
static void *sm_realloc(void *ptr, size_t sz) {
    void *nptr = realloc(ptr, sz);
    if (!nptr) { free(ptr); fprintf(stderr, "realloc fail\n"); exit(EXIT_FAILURE); }
    if (ptr) memset(nptr, 0, sz);
    return nptr;
}

2. 生命週期核心函數

array_t array_new(unsigned size, size_t alloc) {
    struct array *a = sm_malloc(sizeof(struct array));
    if (size * alloc > 0) a->as = sm_malloc(size * alloc);
    a->size = size; a->alloc = alloc; return a;
}
inline void array_delete(array_t a) { sm_free(a->as); sm_free(a); }
inline void array_newinit(array_t a, unsigned size) {
    assert(a);
    a->as = sm_realloc(a->as, size * a->alloc);
    if (a->len > size) a->len = size;
    a->size = size;
}

3. 關鍵操作：array_push

void *array_push(array_t a) {
    assert(a);
    if (a->len == a->size) {
        a->size <<= 1;  // 容量翻倍
        a->as = sm_realloc(a->as, a->size * a->alloc);
    }
    return (unsigned char *)a->as + a->alloc * a->len++;  // 返回新元素地址，調用者自行初始化
}

4. 其他操作（均為 O(1) 或委托標準庫）

inline void *array_pop(array_t a) { --a->len; return (unsigned char *)a->as + a->alloc * a->len; }
inline void *array_get(array_t a, unsigned idx) { return (unsigned char *)a->as + a->alloc * idx; }
inline void *array_top(array_t a) { return (unsigned char *)a->as + a->alloc * (a->len - 1); }
inline void array_swap(array_t a, array_t b) { struct array t = *a; *a = *b; *b = t; }
inline void array_sort(array_t a, icmp_f cmp) { qsort(a->as, a->len, a->alloc, cmp); }
flag_e array_each(array_t a, each_f func, void *arg) {
    unsigned char *s = a->as, *e = s + a->alloc * a->len;
    while (s < e) { flag_e rt = func(s, arg); if (rt != RT_SuccessBase) return rt; s += a->alloc; }
    return RT_SuccessBase;
}

測試驗證

Makefile

CC = gcc
DEBUG = -ggdb3 -Wall
RUN = $(CC) $(DEBUG) -o $@ $^
RUNO = $(CC) -c -o $@ $<
RUNMAIN = $(RUN) -nostartfiles -e $(*F)

all: test_array.out test_array_stack.out

%.o: %.c
    $(RUNO)

test_array.out: test_array.o array.o
    $(RUNMAIN)

test_array_stack.out: test_array.o array.o
    $(RUNMAIN)

.PHONY: clean
clean: rm -rf *.i *.s *.o *.out *~ ; ls

測試代碼（test_array.c）

test_array.c 圖示

#include "array.h"
#include <stdio.h>, <string.h>

#define LEN(arr) (sizeof(arr)/sizeof(*(arr)))

struct dict { char *key; char *value; };

static flag_e _dict_echo(struct dict *node, void *arg) {
    printf("[%s] => [%s]\n", node->key, node->value);
    return RT_SuccessBase;
}
static int _dict_cmp(struct dict *ln, struct dict *rn) {
    return strcmp(ln->key, rn->key);
}

void test_array(void) {  // 堆上對象測試
    struct dict dicts[] = { {"zero","零"}, {"one","一"}, {"two","二"}, {"three","三"}, {"four","四"},
                            {"five","五"}, {"six","六"}, {"seven","七"}, {"eight","八"}, {"nine","九"}, {"ten","十"} };
    int len = LEN(dicts);
    array_t a = array_new(len, sizeof(struct dict));
    for (int i = 0; i < len; i++) { *array_push(a) = dicts[i]; }
    puts("--- 初始數據 ---"); array_each(a, (each_f)_dict_echo, NULL);
    array_sort(a, (icmp_f)_dict_cmp);
    puts("--- 排序後 ---"); array_each(a, (each_f)_dict_echo, NULL);
    array_delete(a); exit(EXIT_SUCCESS);
}

void test_array_stack(void) {  // 棧上對象測試
    struct dict dicts[] = { ... };  // 同上
    int len = LEN(dicts);
    ARRAY_NEW(a, len, sizeof(struct dict));
    for (int i = 0; i < len; i++) { *array_push(a) = dicts[i]; }
    puts("--- 初始數據 ---"); array_each(a, (each_f)_dict_echo, NULL);
    array_sort(a, (icmp_f)_dict_cmp);
    puts("--- 排序後 ---"); for (int i=0;i<len;++i) _dict_echo(array_get(a,i),NULL);
    ARRAY_DELETE(a); exit(EXIT_SUCCESS);
}