Bài 55.128 phút đọc

Thiết kế giao diện container tổng quát

Sau bài này bạn sẽ làm được

Thiết kế bộ con trỏ hàm cho so sánh, hủy, duyệt và băm
Đặt void *ctx vào mọi hàm gọi lại
Áp dụng tám nguyên tắc thiết kế thư viện tốt
Viết header tự đủ và có tiền tố tên

Trước khi viết một dòng cài đặt nào, phải quyết định giao diện. Với thư viện container thì giao diện quyết định gần như mọi thứ, và sáu kiểu con trỏ hàm ở đầu bài này là phần quan trọng nhất.

#Sáu kiểu con trỏ hàm

cds.h, phần đầu

#ifndef CDS_H
#define CDS_H

#include <stddef.h>

/* So sanh hai phan tu. Tra ve am, khong, duong nhu strcmp. */
typedef int    (*CmpFn) (const void *a, const void *b, void *ctx);

/* Giai phong tai nguyen ben trong mot phan tu.
   KHONG giai phong chinh phan tu: container lam viec do. */
typedef void   (*FreeFn)(void *pt, void *ctx);

/* Ap dung len tung phan tu khi duyet. */
typedef void   (*ApplyFn)(void *pt, void *ctx);

/* Vi tu: tra ve khac 0 neu phan tu thoa man. */
typedef int    (*PredFn)(const void *pt, void *ctx);

/* Bam mot khoa thanh mot so. */
typedef size_t (*HashFn)(const void *khoa, void *ctx);

/* So sanh bang nhau, cho bang bam. Tra ve khac 0 neu bang. */
typedef int    (*EqFn)  (const void *a, const void *b, void *ctx);

Kiểu	Dùng ở đâu	Trả về gì
CmpFn	vec_sort, tree_insert, heap_push	Âm, không, dương
FreeFn	vec_free, list_free, hm_free	Không có
ApplyFn	vec_foreach, tree_inorder, hm_foreach	Không có
PredFn	vec_find, vec_remove_if	Khác 0 nếu thỏa mãn
HashFn	hm_new	Một số bất kỳ
EqFn	hm_new	Khác 0 nếu bằng

CmpFn khác qsort ở một điểm quyết định

/* Chu ky cua qsort chuan: */
int (*)(const void *, const void *)          /* KHONG co ngu canh */

/* Chu ky cua chung ta: */
int (*)(const void *, const void *, void *)  /* CO ngu canh */

/* Bai 29.3 va Bai 30.4 da noi ve han che nay cua qsort:
   khong co cho truyen ngu canh, nen phai dung bien toan cuc,
   va bien toan cuc thi khong an toan da luong va khong long nhau duoc.

   Nen thu vien cua chung ta tu cai dat sap xep, hoac bao qsort_r.
   Nhung qsort_r co HAI bien the khong tuong thich:

     GNU:  qsort_r(base, n, sz, cmp, ctx)   ctx la tham so CUOI cua cmp
     BSD:  qsort_r(base, n, sz, ctx, cmp)   ctx la tham so DAU cua cmp

   Nen cach kha chuyen nhat la tu cai dat mot thuat toan sap xep.
   Bai 55.2 se lam. */

FreeFn không giải phóng chính phần tử, và đó là quyết định quan trọng

typedef struct {
    char  *ten;        /* con tro do phan tu SO HUU */
    int    ma;
} SinhVien;

/* Vector luu SinhVien theo GIA TRI, tuc sao chep 16 byte vao mang.
   Khi huy vector:
     - vector giai phong MANG cua no
     - nhung "ten" ben trong tung phan tu thi ai giai phong? */

static void huy_sv(void *pt, void *ctx) {
    (void)ctx;
    SinhVien *sv = pt;
    free(sv->ten);          /* giai phong TAI NGUYEN BEN TRONG */
    /* KHONG free(sv): sv tro vao giua mang cua vector */
}

vec_free(v, huy_sv, NULL);

/* Neu FreeFn co nhiem vu free chinh phan tu thi:
     - no phai biet phan tu duoc cap phat rieng hay nam trong mang
     - va container mat quyen kiem soat bo nho cua chinh no

   Nen quy uoc: container so huu KHOI, nguoi dung so huu
   NHUNG GI BEN TRONG moi phan tu. Ghi ro dieu do vao tai lieu. */

#Vì sao mọi hàm gọi lại cần void *ctx

Không có ngữ cảnh

/* Khong co ngu canh: phai dung bien toan cuc */

static const double *g_khoa;          /* bien toan cuc */

static int ss_theo_khoa(const void *a, const void *b) {
    double x = g_khoa[*(const int *)a];
    double y = g_khoa[*(const int *)b];
    return (x > y) - (x < y);
}

g_khoa = khoa;
qsort(idx, n, sizeof idx[0], ss_theo_khoa);

/* Ba van de:
     1. khong an toan da luong
     2. hai lan sap xep long nhau la hong
     3. ham khong tai su dung duoc o cho khac */

Có ngữ cảnh

/* Co ngu canh: moi thu di kem loi goi */

static int ss_theo_khoa(const void *a, const void *b, void *ctx) {
    const double *khoa = ctx;
    double x = khoa[*(const int *)a];
    double y = khoa[*(const int *)b];
    return (x > y) - (x < y);
}

vec_sort(v, ss_theo_khoa, khoa);

/* An toan da luong, long nhau duoc, va ham thuan tuy. */

Bốn thứ ngữ cảnh hay mang theo

/* 1. Du lieu phu de so sanh */
vec_sort(v, ss_theo_khoa, mang_khoa);

/* 2. Bo dem hoac ket qua tich luy */
typedef struct { double tong; size_t dem; } ThongKe;
ThongKe tk = { 0 };
vec_foreach(v, cong_don, &tk);

/* 3. Tham so cua vi tu */
static int lon_hon(const void *pt, void *ctx) {
    return *(const int *)pt > *(const int *)ctx;
}
int nguong = 100;
long i = vec_find(v, lon_hon, &nguong);

/* 4. Bo cap phat hoac tai nguyen he thong */
typedef struct { Be *be; FILE *log; } NguCanh;
vec_foreach(v, xu_ly, &nc);

/* Va mot quy uoc: neu ham goi lai KHONG can ngu canh thi
   truyen NULL, va trong ham viet "(void)ctx;" de tat canh bao
   tham so khong dung. */

Ngữ cảnh phải sống đủ lâu

void f(Vector *v) {
    int nguong = 100;
    vec_find(v, lon_hon, &nguong);      /* AN TOAN: vec_find chay NGAY,
                                           va tra ve truoc khi f ket thuc */
}

void g(Vector *v) {
    int nguong = 100;
    vec_dang_ky_bo_loc(v, lon_hon, &nguong);   /* NGUY HIEM neu vector
                                                  GIU con tro do */
}                                              /* nguong chet o day */

/* Quy tac: neu ham LUU con tro ngu canh lai thi phai ghi ro
   trong tai lieu, va nguoi dung phai bao dam no song du lau.

   Trong thu vien cds nay, MOI ham goi lai deu duoc goi NGAY
   va khong luu lai. Ghi dieu do vao dau header. Bai 52.1. */

#Header cds.h

cds.h, phần giao diện

/* ===== VECTOR ===== */
typedef struct Vector Vector;

Vector *vec_new(size_t esz);
void    vec_free(Vector *v, FreeFn f, void *ctx);
int     vec_push(Vector *v, const void *pt);
int     vec_pop(Vector *v, void *ra);
void   *vec_at(const Vector *v, size_t i);
size_t  vec_size(const Vector *v);
int     vec_insert(Vector *v, size_t i, const void *pt);
int     vec_remove(Vector *v, size_t i, void *ra);
void    vec_sort(Vector *v, CmpFn cmp, void *ctx);
long    vec_find(const Vector *v, PredFn p, void *ctx);
void    vec_foreach(Vector *v, ApplyFn f, void *ctx);
int     vec_reserve(Vector *v, size_t n);

/* ===== LIST, lien ket doi ===== */
typedef struct List List;

List *list_new(size_t esz);
void  list_free(List *l, FreeFn f, void *ctx);
int   list_push_front(List *l, const void *pt);
int   list_push_back(List *l, const void *pt);
int   list_pop_front(List *l, void *ra);
int   list_pop_back(List *l, void *ra);
size_t list_size(const List *l);
void  list_foreach(List *l, ApplyFn f, void *ctx);

/* ===== HEAP, hang doi uu tien ===== */
typedef struct Heap Heap;

Heap *heap_new(size_t esz, CmpFn cmp, void *ctx);
void  heap_free(Heap *h, FreeFn f, void *ctx);
int   heap_push(Heap *h, const void *pt);
int   heap_pop(Heap *h, void *ra);
void *heap_peek(const Heap *h);
size_t heap_size(const Heap *h);

/* ===== TREE, cay tim kiem nhi phan ===== */
typedef struct Tree Tree;

Tree *tree_new(size_t esz, CmpFn cmp, void *ctx);
void  tree_free(Tree *t, FreeFn f, void *ctx);
int   tree_insert(Tree *t, const void *pt);
void *tree_find(const Tree *t, const void *khoa);
int   tree_remove(Tree *t, const void *khoa, void *ra);
void  tree_inorder(const Tree *t, ApplyFn f, void *ctx);
size_t tree_size(const Tree *t);

/* ===== HASHMAP ===== */
typedef struct HashMap HashMap;

HashMap *hm_new(size_t ksz, size_t vsz, HashFn h, EqFn eq, void *ctx);
void     hm_free(HashMap *m, FreeFn fk, FreeFn fv, void *ctx);
int      hm_put(HashMap *m, const void *khoa, const void *gt);
void    *hm_get(const HashMap *m, const void *khoa);
int      hm_remove(HashMap *m, const void *khoa, void *ra);
size_t   hm_size(const HashMap *m);
void     hm_foreach(HashMap *m, ApplyFn f, void *ctx);

#endif /* CDS_H */

Vì sao vec_at trả về void * còn vec_pop nhận tham số ra

void *vec_at(const Vector *v, size_t i);    /* tra ve CON TRO vao trong */
int   vec_pop(Vector *v, void *ra);         /* SAO CHEP ra ngoai */

/* vec_at: phan tu VAN nam trong vector, nen tra con tro la dung.
   Nguoi dung doc va sua tai cho.

   NHUNG con tro do TREO sau khi vector realloc:

     int *p = vec_at(v, 0);
     vec_push(v, &x);            /* co the realloc */
     *p = 5;                     /* con tro treo! Bai 52.1 */

   Nen tai lieu phai ghi ro: "con tro tra ve chi con hop le cho toi
   thao tac tiep theo lam thay doi vector".

   vec_pop: phan tu bi XOA khoi vector, nen khong the tra con tro
   vao trong duoc. Phai sao chep ra bo dem nguoi dung cap.

   Va tra ve int de bao loi khi vector rong. */

int x;
if (vec_pop(v, &x) == 0) dung(x);

#Tám nguyên tắc thiết kế thư viện

	Nguyên tắc	Bài đã bàn
1	Kiểu mờ, người dùng không thấy nội tại	39.8
2	Mọi hàm gọi lại có void *ctx	29.6, 55.1
3	Quyền sở hữu ghi rõ trong tài liệu	52.1
4	Mã lỗi nhất quán: 0 là được, âm là lỗi	18.2
5	Không exit trong thư viện	32.4
6	Không printf trong thư viện	55.1
7	Tiền tố tên cho mọi ký hiệu công khai	39.6
8	Header tự đủ, include mọi thứ nó cần	20.2

Nguyên tắc 5 và 6 là hai nguyên tắc hay bị phá nhất

/* SAI: thu vien tu quyet dinh ket thuc chuong trinh */
Vector *vec_new(size_t esz) {
    Vector *v = malloc(sizeof *v);
    if (v == NULL) {
        fprintf(stderr, "het bo nho\n");
        exit(1);                          /* KHONG BAO GIO */
    }
    ...
}

/* Nguoi dung co the muon:
     - thu giai phong bo nho dem roi thu lai
     - luu du lieu dang do truoc khi thoat
     - ghi mot dong nhat ky rieng
     - hoac chi don gian la tra ve loi cho tang tren

   Thu vien khong biet dieu do. Tra ve NULL va de nguoi goi quyet dinh. */

/* DUNG: */
Vector *vec_new(size_t esz) {
    if (esz == 0) return NULL;
    Vector *v = malloc(sizeof *v);
    if (v == NULL) return NULL;
    ...
    return v;
}

/* Va nguyen tac 6, printf: */

/* SAI */
int vec_push(Vector *v, const void *pt) {
    if (v->n == v->cap && !mo_rong(v))
        { printf("khong mo rong duoc\n"); return -1; }
    ...
}

/* Nguoi dung co the dang chay mot chuong trinh khong co man hinh,
   hoac dang dung stdout cho du lieu that.

   DUNG: chi tra ve ma loi. Neu that su can ghi nhat ky thi cho
   nguoi dung DANG KY mot ham: */

typedef void (*LogFn)(int muc, const char *tin, void *ctx);
void cds_dat_log(LogFn f, void *ctx);      /* mac dinh: khong ghi gi */

Nguyên tắc 7: tiền tố, và ba mức

/* Muc 1: tien to cho MOI ham cong khai */
vec_push, list_push_front, hm_get

/* Muc 2: tien to thu vien cho kieu va hang so */
CdsVector, CDS_LOI_BONHO, cds_phien_ban

/* Muc 3: tien to noi bo cho ham khong cong khai */
static void cds_noi_bo_mo_rong(Vector *v);

/* Trong thu vien nho thi "vec_" va "hm_" la du.
   Trong thu vien phat hanh rong rai thi nen co tien to thu vien:
   "cds_vec_push" thay vi "vec_push", vi "vec_push" rat de trung.

   Bai 39.6 da noi ve xung dot ten giua hai thu vien, va do la
   loi kho tim nhat trong nhom do. */

/* Va nho: dat ten macro CHU HOA va cung co tien to */
#define CDS_MANG_LEN(a) ...

Nguyên tắc 8: header tự đủ

/* cds.h */
#ifndef CDS_H
#define CDS_H

#include <stddef.h>       /* cho size_t, PHAI co */

/* KHONG include <stdio.h> hay <stdlib.h> neu header khong dung toi.
   Nguoi dung khong nen bi keo theo nhung thu ho khong can. */

typedef struct Vector Vector;
...

#endif

/* Kiem tra tu du bang mot dong: */
$ echo '#include "cds.h"' | gcc -Iinclude -xc -c - -o /dev/null

/* Neu no dich duoc mot minh thi header tu du.
   Dua dong nay vao he thong dung, cho MOI header cong khai.
   Bai 20.2 da noi. */

#Quy ước mã lỗi

Ba cách, và cách nào cho việc gì

/* Cach 1: int, 0 la duoc, am la loi. Cho ham CO the that bai. */
int vec_push(Vector *v, const void *pt);

if (vec_push(v, &x) != 0) return -1;

/* Cach 2: con tro, NULL la loi. Cho ham TAO ra thu gi do. */
Vector *vec_new(size_t esz);
void   *vec_at(const Vector *v, size_t i);

Vector *v = vec_new(sizeof(int));
if (v == NULL) return -1;

/* Cach 3: khong tra ve gi. Cho ham KHONG THE that bai. */
void   vec_free(Vector *v, FreeFn f, void *ctx);
size_t vec_size(const Vector *v);

/* Va mot cach thu tu, cho ham tra ve chi so: */
long vec_find(const Vector *v, PredFn p, void *ctx);
/* tra ve chi so, hoac -1 neu khong tim thay.
   Dung "long" chu khong "size_t" de co cho cho -1. */

Nguyên tắc thứ tư khó nhất, và đây là mẫu

int vec_push(Vector *v, const void *pt) {
    if (v == NULL || pt == NULL) return -1;

    if (v->n == v->cap) {
        size_t cap = v->cap ? v->cap * 2 : 8;

        /* Kiem tra tran truoc khi nhan, Bai 33.4 */
        if (cap > SIZE_MAX / v->esz) return -1;

        /* Nhan vao bien TAM, khong ghi de v->d */
        void *moi = realloc(v->d, cap * v->esz);
        if (moi == NULL) return -1;      /* v->d CON NGUYEN, khong ro ri */

        v->d = moi;
        v->cap = cap;
    }

    memcpy((char *)v->d + v->n * v->esz, pt, v->esz);
    ++v->n;
    return 0;
}

/* Ba diem:
     1. kiem tra doi so truoc, tra ve som
     2. realloc vao bien tam, Bai 32.4 da noi
     3. chi cap nhat trang thai SAU khi moi thu da thanh cong

   Neu that bai o bat cu buoc nao, vector van dung nhu truoc khi goi. */

Một enum mã lỗi, nếu cần chi tiết hơn

/* Voi X Macro cua Bai 54.3: */

#define CDS_CAC_LOI(X)                                  \
    X(CDS_OK,        0,  "Thanh cong")                  \
    X(CDS_LOI_THAMSO, -1, "Tham so khong hop le")       \
    X(CDS_LOI_BONHO,  -2, "Het bo nho")                 \
    X(CDS_LOI_RONG,   -3, "Container rong")             \
    X(CDS_LOI_BIEN,   -4, "Chi so ngoai bien")          \
    X(CDS_LOI_TRUNG,  -5, "Khoa da ton tai")

typedef enum {
#define X(ten, ma, mota) ten = ma,
    CDS_CAC_LOI(X)
#undef X
} CdsLoi;

const char *cds_loi_mo_ta(CdsLoi e);

/* Uu diem so voi chi tra ve -1:
     - nguoi dung phan biet duoc "het bo nho" voi "tham so sai"
     - thong bao loi cho nguoi cuoi ro rang hon

   Nhuoc diem: moi lan them mot ma loi la mot thay doi API.

   Voi thu vien nho thi -1 la du. Voi thu vien lon thi nen co enum. */

Tự làm thử

Viết sáu kiểu con trỏ hàm và giải thích vì sao mỗi cái có void *ctx.
Viết một hàm so sánh dùng ngữ cảnh để sắp xếp chỉ số theo một mảng khóa ngoài.
Kiểm tra header của bạn tự đủ bằng một dòng lệnh.
Tìm trong một thư viện mã nguồn mở xem nó phá nguyên tắc nào trong tám nguyên tắc.
Viết vec_push sao cho vector không đổi gì khi thất bại.
Dùng X Macro để sinh enum mã lỗi kèm bảng mô tả.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

Sáu kiểu con trỏ hàm, và cả sáu đều có void *ctx ở cuối để không ai phải dùng biến toàn cục.
FreeFn giải phóng tài nguyên bên trong phần tử, không giải phóng chính phần tử: container sở hữu khối.
vec_at trả về con trỏ vào trong và con trỏ đó treo sau khi vector thay đổi; vec_pop sao chép ra bộ đệm người dùng cấp.
Không exit và không printf trong thư viện: trả mã lỗi và để người gọi quyết định.
Trạng thái phải không đổi khi thất bại, và mẫu để đạt được điều đó là chỉ cập nhật sau khi mọi bước đã thành công.