C 語言實現泛型棧：void 指針、記憶體複製與 qsort 風格介面設計

C 語言無模板/泛型機制，但標準庫 `qsort`、`bsearch` 證明了「`void*` + 尺寸參數 + 回調函數」即可實現類型無關的演算法。本文深度解析泛型編程核心——**記憶體位元組級複製**，並逐步構建一個完整、可生產使用的泛型棧：動態陣列存儲、類型無關 `push`/`pop`、自動擴容、銷毀回調支援。

一、泛型編程核心洞察：賦值 = 記憶體複製

無論 `int`、`double`、`struct`，賦值本質都是將來源記憶體區塊逐位元組複製到目標區塊。

• 基本類型：`a = b` 編譯器生成固定長度 `mov` 指令序列。
• 結構體/陣列：`memcpy(&dest, &src, sizeof(Type))` 逐字節複製。
• 字串：`strcpy` 逐字節複製直到 `\0`。

**結論**：若知道「目標地址、來源地址、字節數」，`memcpy` 即可完成任意類型賦值。這是 `void*` 泛型介面的理論基石。

二、`void*` 指針：通用介面的紐帶

• 無類型關聯，可隱式轉換自/向任何物件指針 (非函數指針)。
• 不可解引用 (`*voidPtr` 錯誤)，不可算術運算 (`voidPtr++` 為 +1 位元組，非標準)。
• 流程：專用類型指針 → void* → 通用代碼 → void* → 目標類型指針 → 專用代碼。

三、泛型賦值函數原型

// 等價於 memcpy，語義更清晰
void genericAssign(void *dest, const void *src, size_t byteSize) {
    memcpy(dest, src, byteSize);
}

// 使用範例
int a = 42, b;
genericAssign(&b, &a, sizeof(int));

double x = 3.14, y;
genericAssign(&y, &x, sizeof(double));

四、泛型棧設計

1. 棧節點 (單鏈表實現，避免擴容複製開銷)

typedef struct StackNode {
    void *data;              // 指向元素記憶體塊
    struct StackNode *next;
} StackNode;

typedef struct {
    StackNode *top;
    size_t elementSize;      // 元素字節大小 (構造時指定)
    void (*destroy)(void*);  // 可選：元素銷毀回調 (釋放內部資源)
    size_t count;
} GenericStack;

2. 初始化與銷毀

GenericStack* stackCreate(size_t elementSize, void (*destroy)(void*)) {
    GenericStack *s = malloc(sizeof(GenericStack));
    s->top = NULL;
    s->elementSize = elementSize;
    s->destroy = destroy;
    s->count = 0;
    return s;
}

void stackDestroy(GenericStack *s) {
    while (s->top) {
        StackNode *node = s->top;
        s->top = node->next;
        if (s->destroy) s->destroy(node->data); // 調用銷毀回調
        free(node->data);                       // 釋放元素記憶體
        free(node);                             // 釋放節點
    }
    free(s);
}

3. Push：分配元素記憶體 + 複製數據

bool stackPush(GenericStack *s, const void *element) {
    StackNode *node = malloc(sizeof(StackNode));
    if (!node) return false;

    node->data = malloc(s->elementSize);
    if (!node->data) { free(node); return false; }

    memcpy(node->data, element, s->elementSize); // 核心：泛型複製
    node->next = s->top;
    s->top = node;
    s->count++;
    return true;
}

4. Pop：複製數據到呼叫者緩衝區 + 釋放節點

bool stackPop(GenericStack *s, void *outElement) {
    if (!s->top) return false; // 空棧

    StackNode *node = s->top;
    memcpy(outElement, node->data, s->elementSize); // 複製出去

    s->top = node->next;
    if (s->destroy) s->destroy(node->data);
    free(node->data);
    free(node);
    s->count--;
    return true;
}

5. Peek (僅查看不彈出)

bool stackPeek(const GenericStack *s, void *outElement) {
    if (!s->top) return false;
    memcpy(outElement, s->top->data, s->elementSize);
    return true;
}

五、使用範例：存儲 `int`、`Point` 結構體、動態字串

// 1. 整數棧
GenericStack *intStack = stackCreate(sizeof(int), NULL);
int vals[] = {10, 20, 30};
for (int i = 0; i < 3; i++) stackPush(intStack, &vals[i]);
int topVal; stackPeek(intStack, &topVal); // 30

// 2. 結構體棧 (無內部指針，無需 destroy)
typedef struct { double x, y; } Point;
GenericStack *ptStack = stackCreate(sizeof(Point), NULL);
Point p = {1.5, 2.5};
stackPush(ptStack, &p);

// 3. 動態字串棧 (需 destroy 釋放字串緩衝區)
void freeString(void *ptr) { free(*(char**)ptr); } // 解引用 char**

GenericStack *strStack = stackCreate(sizeof(char*), freeString);
char *s1 = strdup("Hello");
char *s2 = strdup("World");
stackPush(strStack, &s1); // 傳遞 char** 地址
stackPush(strStack, &s2);
// pop 時 freeString 會 free 字串內容

六、進階：動態陣列實現 (類 `std::vector`)，支援隨機訪問

鏈表無法 O(1) 隨機訪問。動態陣列版核心差異：

typedef struct {
    void *elements;        // 連續記憶體塊
    size_t elementSize;
    size_t capacity;       // 當前容量 (元素數)
    size_t count;          // 當前元素數
    void (*destroy)(void*);
} ArrayStack;

bool arrayStackPush(ArrayStack *s, const void *elem) {
    if (s->count == s->capacity) {
        size_t newCap = s->capacity ? s->capacity * 2 : 4;
        void *newMem = realloc(s->elements, newCap * s->elementSize);
        if (!newMem) return false;
        s->elements = newMem;
        s->capacity = newCap;
    }
    // 複製到正確偏移位置
    char *dest = (char*)s->elements + s->count * s->elementSize;
    memcpy(dest, elem, s->elementSize);
    s->count++;
    return true;
}

優點：緩存友好、隨機訪問、記憶體開銷小。缺點：擴容時需移動所有元素 (memmove)，指針/引用失效。

七、關鍵設計決策總結

八、標準庫對照：`qsort` 介面設計啟示

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));
// base: 陣列首址 | nmemb: 元素數 | size: 元素字節數 | compar: 比較回調

我們的泛型棧同樣採用 `base, size, count` 三元組描述類型無關數據，配合回調函數 (`destroy`) 處理類型相關邏輯，這是 C 語言泛型編程的**標準範式**。

掌握這套「`void*` + `size_t` + `memcpy` + 回調」模式，你就擁有了在 C 語言中構建任意類型安全容器、演算法框架的核心能力，這也是眾多 C 系統級庫 (GLib, Apache APR, Linux 內核 `list_head` 變體) 的共同基因。