【在主畫面加入捷徑】
       
【選擇語系】
繁中 简中

[C 語言] 程式設計教學:使用 void 指標撰寫泛型程式

Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
【贊助商連結】

    泛型程式是一種無型別的程式,主要的好處在於可將同一套核心邏輯套用在不同型別的程式上。C 語言內建語法不支援泛型,通常是用以下三種方法之一來模擬:

    • 指向 void 的指標 (void *)
    • 巨集 (macro)
    • _Generic 敘述 (限 c11)

    三種方法各有優缺點,我們在這裡有討論過,本文不重覆這些內容。本文的重點在展示一個用指向 void 的指標所做的擬泛型程式。完整的程式碼略長,我們將其放在這裡,本文僅展示部分內容。

    C 語言

    我們先藉由外部程式來看如何使用這個泛型佇列:

    #include <assert.h>
    #include "integer.h"  // Home-made `int`-wrapping box class.
    #include "queue.h"
    
    int main()
    {
        // Queue: NULL
        Queue *queue = queue_new(int_copy, int_free);
        Int *temp;
    
        // Queue: 9 -> NULL
        queue_push_front(queue, int_new(9));
    
        temp = (Int *) queue_peek_front(queue);
        assert(int_value(temp) == 9);
        temp = (Int *) queue_peek_rear(queue);
        assert(int_value(temp) == 9);
        
        // Queue: 4 -> 9 -> NULL
        queue_push_front(queue, int_new(4));
        
        temp = (Int *) queue_peek_front(queue);
        assert(int_value(temp) == 4);
        temp = (Int *) queue_peek_rear(queue);
        assert(int_value(temp) == 9);
        
        // Queue: 4 -> 9 -> 5 -> NULL
        queue_push_rear(queue, int_new(5));
        
        temp = (Int *) queue_peek_front(queue);
        assert(int_value(temp) == 4);
        temp = (Int *) queue_peek_rear(queue);
        assert(int_value(temp) == 5);
        
        // Queue: 9 -> 5 -> NULL
        temp = (Int *) queue_pop_front(queue);
        assert(int_value(temp) == 4);
        int_free(temp);
    
        temp = (Int *) queue_peek_front(queue);
        assert(int_value(temp) == 9);
        temp = (Int *) queue_peek_rear(queue);
        assert(int_value(temp) == 5);
    
        // Queue: 9 -> NULL
        temp = (Int *) queue_pop_rear(queue);
        assert(int_value(temp) == 5);
        int_free(temp);
      
        temp = (Int *) queue_peek_front(queue);
        assert(int_value(temp) == 9);
        temp = (Int *) queue_peek_rear(queue);
        assert(int_value(temp) == 9);
    
        // Queue: NULL
        temp = (Int *) queue_pop_rear(queue);
        assert(int_value(temp) == 9);
        int_free(temp);
    
        queue_free(queue);
    
        return 0;
    }
    

    如果觀察這段程式碼,可能無法立即發現有泛型程式,不過,我們的佇列的確可以接收不同的指標型別。由於指向 void 的指標無法承接整數或其他的基礎型別,我們在這個使用一個簡易的 box class 來包裝整數;由於 C 語言沒有自動回收記憶體的機制,拋出整數物件後要記得手動釋放記憶體。

    觀察一下本例的泛型佇列的宣告:

    #ifndef GENERIC_LIST_H
    #define GENERIC_LIST_H
    
    #include <stdbool.h>
    
    typedef void * item_t;
    typedef void (*copyFn) (void **, void *);
    typedef void (*freeFn) (void *);
    
    typedef struct queue Queue;
    
    Queue* queue_new(copyFn, freeFn);
    bool queue_is_empty(Queue *self);
    item_t queue_peek_front(Queue *self);
    item_t queue_peek_rear(Queue *self);
    void queue_push_front(Queue *self, item_t data);
    item_t queue_pop_front(Queue *self);
    void queue_push_rear(Queue *self, item_t data);
    item_t queue_pop_rear(Queue *self);
    void queue_free(void *self);
    
    #endif // GENERIC_LIST_H
    

    由此宣告可知我們的確沒有把型別寫死在參數中,而是可承接不同的型別。

    此佇列的「類別」宣告如下:

    typedef struct node {
        item_t data;
        struct node *prev;
        struct node *next;
    } Node;
    
    struct queue {
        copyFn item_copy;
        freeFn item_free;
        Node *head;
        Node *tail;
    };
    

    除了在資料結構中常見的 node 型別外,我們額外宣告 copyFnfreeFn 兩個函式型別,因為我們無法預先知道如何釋放該型別的記憶體,要用函式庫使用者提供。

    以下是將資料推入佇列前端的程式碼:

    void queue_push_front(Queue *self, item_t data)
    {
        Node *node = node_new(data);
        
        if (self->head == NULL) {
            self->head = node;
            self->tail = node;
            return;
        }
        
        node->next = self->head;
        self->head->prev = node;
        self->head = node;
    }
    

    其實和一般的佇列程式差不多。

    再看一下將資料移出佇列前端的程式碼:

    item_t queue_pop_front(Queue *self)
    {
        assert(!queue_is_empty(self));
    
        if (self->head == self->tail) {
            item_t popped;
            self->item_copy(&popped, self->head->data);
    
            self->item_free(self->head->data);
            free(self->head);
            self->head = NULL;
            self->tail = NULL;
    
            return popped;
        }
        
        Node *curr = self->head;
        item_t popped;
        self->item_copy(&popped, curr->data);
        
        self->head = self->head->next;
        self->item_free(curr->data);
        free(curr);
        
        return popped;
    }
    

    可以發現我們在此處用到額外的函式,一個用來拷貝物件,一個用來釋放重覆的物件。對於基礎型別來說,這些動作都可以省下來;但對指標型別來說,就要考慮如何處理指標指向的物件。此處我們參考 Rust 的做法,將物件複製一份後傳出。

    最後來看釋放佇列的程式碼:

    void queue_free(void *self)
    {
        if (self == NULL) {
            return;
        }
    
        freeFn fn = ((Queue *) self)->item_free;
        Node *curr = ((Queue *) self)->head;
        Node *temp = NULL;
        
        while (curr != NULL) {
            temp = curr;
            curr = curr->next;
            
            (*fn)(temp->data);
            free(temp);
        }
    
        free(self);
    }
    

    同樣地,在釋放節點內的物件時,會用到額外的 item_free 函式,這函式無法預先得知,需由函式庫使用者提供。

    由本例可知,在 C 語言中,的確可以做到擬泛型程式,但會比一般的高階語言來得麻煩一些,像是要額外宣告一些函式;此外,這樣的程式不具有型別安全,因為所有傳入的物件的型別都是指向 void 的指標。雖然我們可以達到一些泛型的特性,但要不要這樣做就留給讀者自行思考。

    【贊助商連結】
    標籤: C 語言
    【贊助商連結】
    【分類瀏覽】