Bài 15.724 phút đọc

Struct và cấp phát động

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

Cài cặp hàm tạo và hủy đạt bảo đảm tất cả hoặc không gì cả
Phân biệt sao chép nông với sao chép sâu
Dùng mảng thành viên linh hoạt để gộp một lần cấp phát
Xây một cấu trúc dữ liệu động hoàn chỉnh

Bài cuối của Chương 15 ghép struct với mọi thứ đã học ở Phần 6. Đây là chỗ bạn xây được cấu trúc dữ liệu thật đầu tiên, và là nền tảng trực tiếp cho danh sách liên kết ở Chương 21.

#Cặp hàm tạo và hủy

cap-ham.c

#include <stdlib.h>
#include <string.h>

typedef struct {
    char   *ten;        /* cấp phát riêng */
    double *diem;       /* cấp phát riêng */
    size_t  so_diem;
} SinhVien;

/* Hủy: chấp nhận NULL, và gọi được với đối tượng mới tạo được một nửa. */
void sv_huy(SinhVien *sv)
{
    if (sv == NULL) return;

    free(sv->ten);
    free(sv->diem);
    free(sv);
}

/* Tạo: hoặc thành công hoàn toàn, hoặc trả về NULL và không để lại rác. */
SinhVien *sv_tao(const char *ten, size_t so_diem)
{
    if (ten == NULL) return NULL;

    SinhVien *sv = calloc(1, sizeof *sv);      /* calloc: mọi con trỏ bằng NULL */

    if (sv == NULL) return NULL;

    size_t n = strlen(ten) + 1;

    sv->ten = malloc(n);

    if (sv->ten == NULL) { sv_huy(sv); return NULL; }

    memcpy(sv->ten, ten, n);

    if (so_diem > 0) {
        sv->diem = calloc(so_diem, sizeof *sv->diem);

        if (sv->diem == NULL) { sv_huy(sv); return NULL; }
    }

    sv->so_diem = so_diem;

    return sv;
}

Nhánh lỗi tự dọn từng phần

SinhVien *sv_tao(const char *ten, size_t so_diem)
{
    SinhVien *sv = malloc(sizeof *sv);

    if (sv == NULL) return NULL;

    sv->ten = malloc(strlen(ten) + 1);

    if (sv->ten == NULL) {
        free(sv);           /* phải nhớ dọn đúng những gì đã cấp */
        return NULL;
    }

    sv->diem = calloc(so_diem, sizeof *sv->diem);

    if (sv->diem == NULL) {
        free(sv->ten);      /* càng nhiều trường càng dễ quên */
        free(sv);
        return NULL;
    }

    ...
}

Gọi hàm hủy chung

SinhVien *sv_tao(const char *ten, size_t so_diem)
{
    SinhVien *sv = calloc(1, sizeof *sv);

    if (sv == NULL) return NULL;

    sv->ten = malloc(strlen(ten) + 1);

    if (sv->ten == NULL) { sv_huy(sv); return NULL; }

    sv->diem = calloc(so_diem, sizeof *sv->diem);

    if (sv->diem == NULL) { sv_huy(sv); return NULL; }

    ...
}

terminal

# Ép hàm tạo thất bại ở trường thứ hai để kiểm chứng không rò rỉ

valgrind --leak-check=full ./test-that-bai

All heap blocks were freed -- no leaks are possible

Vẫn phải xử lý riêng khi so_diem bằng 0

sv->diem = calloc(0, sizeof *sv->diem);

/* calloc(0, n) có thể trả về NULL hoặc một con trỏ hợp lệ, tùy cài đặt.
   Nếu nó trả về NULL, hàm tạo tưởng là hết bộ nhớ và thất bại oan. */

/* Cách chữa: chỉ cấp khi thật sự cần */
if (so_diem > 0) {
    sv->diem = calloc(so_diem, sizeof *sv->diem);

    if (sv->diem == NULL) { sv_huy(sv); return NULL; }
}

#Sao chép nông và sao chép sâu

Sao chép nông

Chép từng byte của struct. Con trỏ bên trong được chép nguyên giá trị, nên hai bản cùng trỏ vào một vùng nhớ.

Sao chép sâu

Chép struct và cấp phát vùng nhớ mới cho mọi thứ mà con trỏ bên trong trỏ tới, rồi chép nội dung sang. Hai bản hoàn toàn độc lập.

nong.c

SinhVien *a = sv_tao("An", 3);

SinhVien b = *a;              /* sao chép NÔNG: chỉ chép các trường */

b.ten[0] = 'B';
printf("%s\n", a->ten);      /* "Bn": sửa qua b thì a cũng đổi */

sv_huy(a);
printf("%s\n", b.ten);       /* b.ten treo: vùng đó đã bị giải phóng */

sau.c

/* Sao chép sâu: cấp vùng mới cho mọi con trỏ bên trong. */
SinhVien *sv_ban_sao(const SinhVien *goc)
{
    if (goc == NULL) return NULL;

    SinhVien *moi = sv_tao(goc->ten, goc->so_diem);

    if (moi == NULL) return NULL;

    if (goc->so_diem > 0)
        memcpy(moi->diem, goc->diem, goc->so_diem * sizeof *moi->diem);

    return moi;
}

SinhVien *a = sv_tao("An", 3);
SinhVien *b = sv_ban_sao(a);

b->ten[0] = 'B';
printf("%s\n", a->ten);      /* "An": hoàn toàn độc lập */

sv_huy(a);
printf("%s\n", b->ten);      /* "Bn": vẫn hợp lệ */

sv_huy(b);

	Sao chép nông	Sao chép sâu
Cú pháp	b = *a, tức dấu bằng	Phải viết hàm riêng
Chi phí	Bằng sizeof struct	Bằng tổng mọi thứ được trỏ tới
Hai bản độc lập	Không	Có
Ai giải phóng	Không rõ, và đó là vấn đề	Mỗi bản tự lo phần của mình
An toàn	Chỉ khi struct không chứa con trỏ	Luôn

Khi nào sao chép nông là đủ

/* Struct không chứa con trỏ nào: sao chép nông hoàn toàn an toàn */
typedef struct { double x, y, z; } Vec3;

Vec3 a = { 1, 2, 3 };
Vec3 b = a;              /* độc lập hoàn toàn, không cần hàm gì */

/* Struct chỉ chứa mảng cố định: cũng an toàn */
typedef struct { char ten[64]; int tuoi; } NguoiDonGian;

NguoiDonGian c = { "An", 20 };
NguoiDonGian d = c;      /* chép cả 64 byte của ten, độc lập */

Quy tắc: nếu struct không có con trỏ nào thì dấu bằng là đủ. Ngay khi có một con trỏ, bạn phải quyết định rõ ai sở hữu và có cần hàm sao chép sâu hay không.

Ngăn sao chép nông vô tình

/* C không có cách nào cấm dấu bằng. Nhưng bạn giảm rủi ro được. */

/* Cách 1: chỉ cho người dùng thấy kiểu mờ, xem Bài 15.3.
   Họ chỉ có con trỏ, không khai báo được biến nên không gán được. */
typedef struct SinhVien SinhVien;

/* Cách 2: ghi rõ trong chú thích ngay tại khai báo */
typedef struct {
    char *ten;      /* SỞ HỮU. Đừng gán struct này bằng dấu bằng,
                       hãy dùng sv_ban_sao. */
    size_t n;
} SinhVien;

#Mảng thành viên linh hoạt

Mảng thành viên linh hoạt

Một mảng không ghi độ dài, đặt ở cuối struct. Nó cho phép cấp phát struct và dữ liệu của nó trong đúng một lần malloc. Tính năng của C99.

linh-hoat.c

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    size_t n;
    int    du_lieu[];      /* mảng thành viên linh hoạt, không có số trong ngoặc */
} Mang;

Mang *mang_tao(size_t n)
{
    /* Kiểm tra tràn trước khi nhân, đúng như Bài 14.6 */
    if (n > (SIZE_MAX - sizeof(Mang)) / sizeof(int)) return NULL;

    Mang *m = malloc(sizeof *m + n * sizeof *m->du_lieu);

    if (m == NULL) return NULL;

    m->n = n;

    return m;
}

void mang_huy(Mang *m)
{
    free(m);      /* MỘT lần free duy nhất */
}

Mang *m = mang_tao(100);

if (m != NULL) {
    for (size_t i = 0; i < m->n; ++i)
        m->du_lieu[i] = (int)i;

    mang_huy(m);
}

	struct chứa con trỏ	Mảng thành viên linh hoạt
Số lần malloc	Hai	Một
Số lần free	Hai	Một
sizeof struct	16 byte, gồm cả con trỏ	8 byte, không có con trỏ
Dữ liệu nằm ở đâu	Vùng riêng, rời struct	Ngay sau struct, liền nhau
Thân thiện bộ nhớ đệm	Kém	Rất
Đổi kích thước sau khi tạo	Được, bằng realloc trường đó	Phải realloc cả struct
Chia sẻ dữ liệu với struct khác	Được	Không

Bốn quy tắc bắt buộc

Phải là thành viên cuối cùng. Không được có trường nào sau nó.
Chỉ được có một. Một struct không thể có hai mảng linh hoạt.
Struct phải có ít nhất một thành viên khác.
sizeof struct không tính mảng đó. Nó luôn bằng 0 phần tử về mặt kích thước.

typedef struct { size_t n; int a[]; int b; } Sai1;   /* LỖI: có trường sau */
typedef struct { size_t n; int a[]; char b[]; } Sai2;/* LỖI: hai mảng linh hoạt */
typedef struct { int a[]; } Sai3;                    /* LỖI: không có thành viên khác */

typedef struct { size_t n; int a[]; } Dung;

printf("%zu\n", sizeof(Dung));      /* 8, không tính mảng a */

Ứng dụng: chuỗi có độ dài

chuoi.c

typedef struct {
    size_t len;
    char   ky_tu[];      /* nội dung nằm ngay sau, kèm byte kết thúc */
} Chuoi;

Chuoi *chuoi_tao(const char *s)
{
    if (s == NULL) return NULL;

    size_t len = strlen(s);
    Chuoi *c = malloc(sizeof *c + len + 1);

    if (c == NULL) return NULL;

    c->len = len;
    memcpy(c->ky_tu, s, len + 1);

    return c;
}

Chuoi *c = chuoi_tao("xin chao");

printf("%s co %zu ky tu\n", c->ky_tu, c->len);   /* không cần gọi strlen */

free(c);

Không sao chép struct chứa mảng linh hoạt bằng dấu bằng

Chuoi *a = chuoi_tao("xin chao");
Chuoi  b = *a;              /* chỉ chép trường len, KHÔNG chép ky_tu */

printf("%s\n", b.ky_tu);   /* đọc ra ngoài vùng của b */

Vì sizeof không tính mảng linh hoạt, phép gán chỉ chép các trường trước nó. Muốn sao chép, phải cấp một vùng mới đủ lớn rồi memcpy cả struct lẫn mảng.

#Một cấu trúc dữ liệu hoàn chỉnh

danhba.h

#ifndef DANHBA_H
#define DANHBA_H

#include <stddef.h>

typedef struct DanhBa DanhBa;

/* Vòng đời */
DanhBa *db_tao(void);
void    db_huy(DanhBa *db);

/* Thao tác. Mọi hàm trả về 0 nếu thành công, âm một nếu thất bại. */
int db_them(DanhBa *db, const char *ten, const char *so_dt);
int db_xoa(DanhBa *db, const char *ten);

/* Truy vấn. Con trỏ trả về CHỈ hợp lệ tới lần sửa đổi tiếp theo. */
const char *db_tim(const DanhBa *db, const char *ten);
size_t      db_so_luong(const DanhBa *db);

/* Duyệt bằng hàm gọi lại, xem Bài 13.6 */
int db_duyet(const DanhBa *db,
             int (*xu_ly)(const char *ten, const char *so_dt, void *nc),
             void *ngu_canh);

#endif

danhba.c

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "danhba.h"

typedef struct {
    char *ten;
    char *so_dt;
} MucTu;

struct DanhBa {
    MucTu *muc;
    size_t n;
    size_t suc_chua;
};

/* Hàm phụ: nhân bản một chuỗi. Trả về NULL nếu thất bại. */
static char *nhan_ban(const char *s)
{
    size_t n = strlen(s) + 1;
    char  *p = malloc(n);

    if (p != NULL) memcpy(p, s, n);

    return p;
}

DanhBa *db_tao(void)
{
    return calloc(1, sizeof(DanhBa));
}

void db_huy(DanhBa *db)
{
    if (db == NULL) return;

    for (size_t i = 0; i < db->n; ++i) {
        free(db->muc[i].ten);
        free(db->muc[i].so_dt);
    }

    free(db->muc);
    free(db);
}

static int bao_dam(DanhBa *db, size_t can)
{
    if (can <= db->suc_chua) return 0;

    size_t moi = db->suc_chua ? db->suc_chua : 4;

    while (moi < can) {
        if (moi > SIZE_MAX / 2) return -1;

        moi *= 2;
    }

    if (moi > SIZE_MAX / sizeof *db->muc) return -1;

    MucTu *tam = realloc(db->muc, moi * sizeof *tam);

    if (tam == NULL) return -1;

    db->muc      = tam;
    db->suc_chua = moi;

    return 0;
}

int db_them(DanhBa *db, const char *ten, const char *so_dt)
{
    if (db == NULL || ten == NULL || so_dt == NULL) return -1;
    if (bao_dam(db, db->n + 1) != 0)                return -1;

    char *t = nhan_ban(ten);

    if (t == NULL) return -1;

    char *s = nhan_ban(so_dt);

    if (s == NULL) { free(t); return -1; }

    db->muc[db->n].ten   = t;
    db->muc[db->n].so_dt = s;
    ++db->n;

    return 0;
}

const char *db_tim(const DanhBa *db, const char *ten)
{
    if (db == NULL || ten == NULL) return NULL;

    for (size_t i = 0; i < db->n; ++i)
        if (strcmp(db->muc[i].ten, ten) == 0)
            return db->muc[i].so_dt;

    return NULL;
}

int db_xoa(DanhBa *db, const char *ten)
{
    if (db == NULL || ten == NULL) return -1;

    for (size_t i = 0; i < db->n; ++i)
        if (strcmp(db->muc[i].ten, ten) == 0) {
            free(db->muc[i].ten);
            free(db->muc[i].so_dt);

            memmove(&db->muc[i], &db->muc[i + 1],
                    (db->n - i - 1) * sizeof *db->muc);

            --db->n;

            return 0;
        }

    return -1;
}

size_t db_so_luong(const DanhBa *db)
{
    return db != NULL ? db->n : 0;
}

int db_duyet(const DanhBa *db,
             int (*xu_ly)(const char *, const char *, void *),
             void *ngu_canh)
{
    if (db == NULL || xu_ly == NULL) return -1;

    for (size_t i = 0; i < db->n; ++i) {
        int kq = xu_ly(db->muc[i].ten, db->muc[i].so_dt, ngu_canh);

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

    return 0;
}

main.c

#include <stdio.h>

#include "danhba.h"

static int in_mot(const char *ten, const char *so_dt, void *nc)
{
    size_t *dem = nc;

    printf("%2zu. %-12s %s\n", ++(*dem), ten, so_dt);

    return 0;
}

int main(void)
{
    DanhBa *db = db_tao();

    if (db == NULL) return 1;

    if (db_them(db, "An",    "0901234567") != 0) goto loi;
    if (db_them(db, "Binh",  "0912345678") != 0) goto loi;
    if (db_them(db, "Cuong", "0923456789") != 0) goto loi;

    size_t dem = 0;

    db_duyet(db, in_mot, &dem);

    const char *s = db_tim(db, "Binh");

    printf("Binh: %s\n", s != NULL ? s : "khong co");

    db_xoa(db, "Binh");
    printf("Con lai: %zu\n", db_so_luong(db));

    db_huy(db);

    return 0;

loi:
    db_huy(db);

    return 1;
}

terminal

gcc -std=c17 -Wall -Wextra -g -fsanitize=address,undefined danhba.c main.c -o app && ./app

 1. An           0901234567
 2. Binh         0912345678
 3. Cuong        0923456789
Binh: 0912345678
Con lai: 2

valgrind --leak-check=full ./app

All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts

#Bảy quy tắc của chương

	Quy tắc	Bài
1	Luôn dùng khởi tạo có chỉ định, không dựa vào thứ tự trường	15.1
2	Khai báo trường từ lớn xuống nhỏ khi có nhiều bản sao	15.1
3	typedef struct Ten { ... } Ten; giữ cả tên thẻ	15.2
4	Tham số struct dùng const con trỏ, trừ khi nhỏ hơn mười sáu byte	15.3 và 15.6
5	Dùng kiểu mờ cho mọi cấu trúc dữ liệu trong thư viện	15.3
6	Mỗi hàm tạo có đúng một hàm hủy, và hàm hủy chấp nhận NULL	15.7
7	Struct có con trỏ thì phải quyết định rõ sao chép nông hay sâu	15.7

Chương 15 dẫn tới đâu

Chương sau	Dùng gì từ chương này
16 Enum và 17 Union	Ghép với struct thành union có nhãn
18 File I/O	Ghi và đọc struct ra file, và vấn đề phần đệm
21 Linked List	Struct tự tham chiếu và cặp hàm tạo hủy
24 Tree và 25 Hash Table	Cùng mẫu, cấu trúc phức tạp hơn
30 Generic Programming	Kiểu mờ cộng con trỏ hàm
53 Struct Memory Layout	Phần đệm và căn chỉnh ở mức sâu

Tự làm thử

Cài cặp hàm tạo và hủy cho struct ba trường cấp phát, ép thất bại ở từng trường và kiểm chứng bằng valgrind.
Sao chép struct chứa con trỏ bằng dấu bằng, sửa qua bản sao và quan sát bản gốc đổi theo.
Viết hàm sao chép sâu cho struct đó, kiểm chứng hai bản độc lập hoàn toàn.
Cài struct dùng mảng thành viên linh hoạt, so sizeof với bản dùng con trỏ và đếm số lần free.
Thử vi phạm cả bốn quy tắc của mảng linh hoạt, chép lại bốn thông báo lỗi.
Cài đủ thư viện danh bạ trong bài, chạy dưới cả trình dò lỗi và valgrind.
Mở rộng danh bạ: giữ mảng luôn sắp theo tên và đổi db_tim sang tìm nhị phân, đo chênh lệch với một trăm nghìn mục.

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 tạo dùng calloc và gọi hàm hủy ở mọi nhánh lỗi, để đạt bảo đảm tất cả hoặc không gì cả.
Dấu bằng giữa hai struct là sao chép nông. Ngay khi struct có con trỏ, bạn phải quyết định rõ ai sở hữu.
Sao chép nông sai gây ra cả ba loại lỗi bộ nhớ: giải phóng hai lần, con trỏ treo, và rò rỉ.
Mảng thành viên linh hoạt gộp struct và dữ liệu vào một lần cấp phát, nhưng phải là thành viên cuối và không sao chép bằng dấu bằng được.
Bảy quy tắc của chương gom lại thành ba câu hỏi: có con trỏ không, có cần giấu không, và sẽ có bao nhiêu bản sao.