Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 13.620 phút đọc

Hàm gọi lại

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

  • Viết hàm nhận hàm gọi lại làm tham số
  • Dùng qsort và bsearch với hàm so sánh tự viết
  • Truyền ngữ cảnh kèm theo hàm gọi lại
  • Nhận ra mẫu này trong các thư viện thật

Bình thường mã của bạn gọi thư viện. Với hàm gọi lại thì ngược lại: bạn đưa cho thư viện một hàm và nó gọi mã của bạn. Cách nghĩ lộn ngược này là nền tảng của mọi thư viện tổng quát trong C.

#Đảo ngược quyền điều khiển

Hàm gọi lại
Một hàm mà bạn truyền địa chỉ vào một hàm khác, để hàm đó gọi lại nó vào lúc thích hợp.
dao-nguoc.c
/* Hàm tổng quát: nó biết cách duyệt, bạn biết cách xử lý. */
void voi_moi(int *a, size_t n, void (*xu_ly)(int *, void *), void *ngu_canh)
{
    if (a == NULL || xu_ly == NULL) return;

    for (size_t i = 0; i < n; ++i)
        xu_ly(&a[i], ngu_canh);
}

static void nhan_doi(int *x, void *nc)
{
    (void)nc;

    *x *= 2;
}

static void cong_don(int *x, void *nc)
{
    long long *tong = nc;

    *tong += *x;
}

int       a[5] = { 1, 2, 3, 4, 5 };
long long tong = 0;

voi_moi(a, 5, nhan_doi, NULL);
voi_moi(a, 5, cong_don, &tong);

printf("%lld\n", tong);      /* 30 */
Ai biết gìHàm tổng quátMã của bạn
Cách duyệt dữ liệuBiếtKhông cần biết
Việc cần làm với mỗi phần tửKhông biếtBiết
Khi nào gọiQuyết địnhKhông kiểm soát
Dữ liệu phụ cần dùngKhông biếtTruyền qua ngữ cảnh

#qsort và bsearch

#include <stdlib.h>

void  qsort(void *base, size_t n, size_t co,
            int (*so_sanh)(const void *, const void *));

void *bsearch(const void *khoa, const void *base, size_t n, size_t co,
              int (*so_sanh)(const void *, const void *));
Tham sốÝ nghĩa
baseĐịa chỉ đầu mảng
nSố phần tử
coKích thước một phần tử tính bằng byte
so_sanhHàm gọi lại, nhận địa chỉ hai phần tử
qsort.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char   ten[32];
    int    tuoi;
    double diem;
} SinhVien;

static int theo_ten(const void *x, const void *y)
{
    const SinhVien *a = x;
    const SinhVien *b = y;

    return strcmp(a->ten, b->ten);
}

static int theo_tuoi(const void *x, const void *y)
{
    const SinhVien *a = x;
    const SinhVien *b = y;

    return (a->tuoi > b->tuoi) - (a->tuoi < b->tuoi);
}

static int theo_diem_giam(const void *x, const void *y)
{
    const SinhVien *a = x;
    const SinhVien *b = y;

    return (a->diem < b->diem) - (a->diem > b->diem);
}

int main(void)
{
    SinhVien sv[] = {
        { "Cuong", 20, 8.5 },
        { "An",    22, 7.0 },
        { "Binh",  19, 9.0 },
    };

    size_t n = sizeof sv / sizeof sv[0];

    qsort(sv, n, sizeof sv[0], theo_ten);
    qsort(sv, n, sizeof sv[0], theo_tuoi);
    qsort(sv, n, sizeof sv[0], theo_diem_giam);

    for (size_t i = 0; i < n; ++i)
        printf("%-8s %d %.1f\n", sv[i].ten, sv[i].tuoi, sv[i].diem);

    return 0;
}
terminal
./qsort
Binh     19 9.0
Cuong    20 8.5
An       22 7.0

bsearch phải dùng cùng hàm so sánh

bsearch.c
SinhVien khoa;

strcpy(khoa.ten, "Binh");

qsort(sv, n, sizeof sv[0], theo_ten);

SinhVien *tim = bsearch(&khoa, sv, n, sizeof sv[0], theo_ten);

if (tim != NULL)
    printf("Tim thay: %s %d\n", tim->ten, tim->tuoi);
else
    printf("Khong tim thay\n");

#Truyền ngữ cảnh kèm theo

Hạn chế lớn nhất của qsort là hàm so sánh không nhận được dữ liệu phụ nào. Muốn sắp theo tiêu chí do người dùng chọn lúc chạy, bạn gặp vấn đề.

Dùng biến toàn cục
static int g_tang_dan = 1;      /* biến toàn cục, không an toàn đa luồng */

static int so_sanh(const void *x, const void *y)
{
    int a = *(const int *)x;
    int b = *(const int *)y;
    int d = (a > b) - (a < b);

    return g_tang_dan ? d : -d;
}

g_tang_dan = 0;
qsort(a, n, sizeof a[0], so_sanh);
Nhận ngữ cảnh qua tham số
/* Hàm tự viết nhận thêm tham số ngữ cảnh. */
void sap_xep(void *base, size_t n, size_t co,
             int (*so_sanh)(const void *, const void *, void *),
             void *ngu_canh);

static int so_sanh(const void *x, const void *y, void *nc)
{
    int  tang_dan = *(const int *)nc;
    int  a = *(const int *)x;
    int  b = *(const int *)y;
    int  d = (a > b) - (a < b);

    return tang_dan ? d : -d;
}

int tang = 0;

sap_xep(a, n, sizeof a[0], so_sanh, &tang);

Mẫu ngữ cảnh tổng quát

ngu-canh.c
/* Kiểu hàm gọi lại luôn có tham số cuối là void sao. */
typedef int (*XuLy)(const void *phan_tu, void *ngu_canh);

/* Duyệt và gọi lại, dừng sớm nếu hàm gọi lại trả về khác 0. */
int duyet(const void *base, size_t n, size_t co, XuLy xu_ly, void *nc)
{
    if (base == NULL || xu_ly == NULL) return -1;

    const char *p = base;

    for (size_t i = 0; i < n; ++i) {
        int kq = xu_ly(p + i * co, nc);

        if (kq != 0) return kq;      /* cho phép dừng sớm */
    }

    return 0;
}

/* Dùng: đếm số phần tử lớn hơn một ngưỡng do người gọi đặt. */
typedef struct { int nguong; size_t dem; } BoDem;

static int dem_lon_hon(const void *pt, void *nc)
{
    const int *x = pt;
    BoDem     *b = nc;

    if (*x > b->nguong) b->dem++;

    return 0;
}

int   a[5] = { 1, 9, 3, 7, 5 };
BoDem b = { 4, 0 };

duyet(a, 5, sizeof a[0], dem_lon_hon, &b);

printf("%zu\n", b.dem);      /* 3 */

#Bốn mẫu thường gặp

Mẫu 1: so sánh, dùng cho sắp xếp và tìm kiếm

int (*so_sanh)(const void *, const void *);

Mẫu 2: biến đổi, áp lên từng phần tử

void (*bien_doi)(void *phan_tu, void *ngu_canh);

Mẫu 3: lọc, quyết định giữ hay bỏ

loc.c
typedef int (*Loc)(const void *phan_tu, void *nc);

size_t giu_lai(void *base, size_t n, size_t co, Loc giu, void *nc)
{
    char  *p = base;
    size_t ghi = 0;

    for (size_t doc = 0; doc < n; ++doc)
        if (giu(p + doc * co, nc)) {
            if (ghi != doc)
                memmove(p + ghi * co, p + doc * co, co);

            ++ghi;
        }

    return ghi;
}

static int la_chan(const void *pt, void *nc)
{
    (void)nc;

    return *(const int *)pt % 2 == 0;
}

int a[6] = { 1, 2, 3, 4, 5, 6 };

size_t n = giu_lai(a, 6, sizeof a[0], la_chan, NULL);
/* a giờ là 2 4 6, n bằng 3 */

Mẫu 4: dọn dẹp, gọi khi hủy đối tượng

typedef void (*Huy)(void *);

typedef struct {
    void **phan_tu;
    size_t n;
    Huy    huy_phan_tu;      /* NULL nếu phần tử không cần dọn */
} DanhSach;

void ds_huy(DanhSach *ds)
{
    if (ds == NULL) return;

    if (ds->huy_phan_tu != NULL)
        for (size_t i = 0; i < ds->n; ++i)
            ds->huy_phan_tu(ds->phan_tu[i]);

    free(ds->phan_tu);
}

Mẫu thứ tư là nền tảng của mọi cấu trúc dữ liệu tổng quát. Chương 30 sẽ xây một container đầy đủ dựa trên nó.

#Nhận ra mẫu này trong thư viện thật

HàmHàm gọi lại làm gìCó ngữ cảnh không
qsort, bsearchSo sánh hai phần tửKhông
atexitChạy khi chương trình kết thúcKhông
signalXử lý tín hiệu hệ điều hành gửi tớiKhông
pthread_createThân của luồng mớiCó, một void sao
nftw trên POSIXGọi cho từng file khi duyệt cây thư mụcKhông
atexit.c
#include <stdio.h>
#include <stdlib.h>

static void don_dep(void)
{
    printf("dang don dep\n");
}

static void tam_biet(void)
{
    printf("tam biet\n");
}

int main(void)
{
    atexit(don_dep);
    atexit(tam_biet);      /* gọi theo thứ tự NGƯỢC lại lúc đăng ký */

    printf("dang chay\n");

    return 0;
}
terminal
./atexit
dang chay
tam biet
dang don dep

Tự làm thử

  1. Cài hàm voi_moi nhận ngữ cảnh, dùng nó để nhân đôi mảng và để tính tổng.
  2. Sắp mảng struct sinh viên theo ba tiêu chí, viết ba hàm so sánh khác nhau.
  3. Viết hàm so sánh sai kiểu return a - b với hai giá trị cực trị, chạy dưới -fsanitize=undefined.
  4. Sắp theo tên rồi gọi bsearch với hàm so sánh theo tuổi, quan sát kết quả sai.
  5. Cài hàm duyet có ngữ cảnh và cho phép dừng sớm, dùng nó để tìm phần tử đầu tiên thỏa điều kiện.
  6. Cài hàm giu_lai tổng quát, dùng nó lọc số chẵn và lọc chuỗi bắt đầu bằng một chữ cái.
  7. Đăng ký ba hàm bằng atexit và xác nhận thứ tự gọi là ngược lại với thứ tự đăng ký.

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

  • Hàm gọi lại đảo ngược quyền điều khiển: thư viện biết cách duyệt, mã của bạn biết cách xử lý.
  • Hàm so sánh cho qsort phải nhất quán, bắc cầu và đối xứng. Viết (a > b) - (a < b), không viết a - b.
  • bsearch đòi mảng đã sắp bằng đúng cùng hàm so sánh, nếu không nó im lặng cho kết quả sai.
  • Luôn thêm tham số void *ngu_canh vào hàm gọi lại tự thiết kế, để tránh biến toàn cục.
  • Bốn mẫu thường gặp là so sánh, biến đổi, lọc và dọn dẹp. Chúng xuất hiện trong mọi thư viện tổng quát.