Bài 55.432 phút đọc

Project: thư viện cds hoàn chỉnh

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

Gộp năm container vào một thư viện có tiền tố nhất quán
Viết bộ kiểm thử phủ cả đường lỗi
Chạy sạch với sanitizer và bộ cờ nghiêm ngặt
Chạy qua danh sách nghiệm thu của cả phần

Năm container, một giao diện, một bộ kiểm thử phủ cả đường lỗi, và tài liệu nói rõ ai sở hữu cái gì. Đây là bài gói lại toàn bộ Phần 19, và cũng là thứ dùng được thật trong dự án của bạn.

#Đề bài

Năm container, một giao diện nhất quán
Vector, list, heap, tree, hashmap. Cùng quy ước đặt tên, cùng quy ước mã lỗi, cùng bộ con trỏ hàm.
Kiểu mờ hoàn toàn
Header chỉ có typedef struct X X; và nguyên mẫu hàm. Người dùng không thấy một trường nào.
Bộ kiểm thử phủ cả đường lỗi
Mỗi container ít nhất bốn bài kiểm thử cho đường lỗi: con trỏ NULL, chỉ số ngoài biên, container rỗng, tham số không hợp lệ.
Chạy sạch với sanitizer và cờ nghiêm ngặt
-Wall -Wextra -Wpedantic -Wshadow -Wconversion, không một cảnh báo. Và ASan cộng UBSan im lặng.
Tài liệu nói rõ quyền sở hữu
Mọi hàm trả về con trỏ phải ghi rõ người gọi sở hữu hay mượn. Bài 52.1.

#Cây thư mục

Cấu trúc dự án

cds/
  include/
    cds.h              giao dien cong khai, DUY NHAT tep nay duoc cai dat

  src/
    vec.c              vector dong
    list.c             danh sach lien ket doi
    heap.c             hang doi uu tien
    tree.c             cay tim kiem nhi phan
    hashmap.c          bang bam do tuyen tinh
    noibo.h            khai bao dung chung TRONG thu vien

  test/
    chay_thu.c         bo kiem thu

  Makefile
  README.md
  cds.pc.in            mau pkg-config, Bai 39.12

Một tệp .c cho mỗi container, và đó là quyết định có lý do

/* Bai 39.1 da do: trinh lien ket lay CA TEP .o, khong lay tung ham.

   Nen neu ban gop het vao mot "cds.c" thi mot chuong trinh chi dung
   vector cung keo theo ca bang bam, cay, heap va list.

   Voi nam tep rieng:
     gcc app.c libcds.a -o app
   chi keo vao vec.o neu app chi dung vector.

   Do bang nm: */

$ nm app.exe | grep -c ' T hm_'
0                                  /* khong co ham nao cua hashmap */

/* Va neu ban muon chia nho hon nua: */
gcc -ffunction-sections -fdata-sections -c src/*.c
gcc app.o -Wl,--gc-sections libcds.a -o app

src/noibo.h, phần dùng chung

#ifndef CDS_NOIBO_H
#define CDS_NOIBO_H

#include <stddef.h>

/* Ham nay duoc vec.c va heap.c cung dung, nhung KHONG lo ra ngoai.
   static khong dung duoc vi can hai tep. Bai 39.6. */

#if defined(__GNUC__)
  #define CDS_NOI_BO __attribute__((visibility("hidden")))
#else
  #define CDS_NOI_BO
#endif

CDS_NOI_BO void cds_doi_cho(void *a, void *b, size_t n);

/* Tinh suc chua moi, kem kiem tra tran. Bai 33.4. */
CDS_NOI_BO int cds_suc_chua_moi(size_t cu, size_t esz, size_t *ra);

#endif

/* Tep nay nam trong src/, KHONG trong include/, va KHONG duoc cai dat.
   Do la ranh gioi vat ly giua API va cai dat. Bai 39.12. */

#Makefile

Makefile

TEN       = cds
CHINH     = 1
PHU       = 0
VA        = 0
PHIEN_BAN = $(CHINH).$(PHU).$(VA)

PREFIX    ?= /usr/local
LIBDIR    ?= $(PREFIX)/lib
INCDIR    ?= $(PREFIX)/include
DESTDIR   ?=

CC        ?= gcc
AR        ?= ar
CFLAGS    ?= -O2

CHUNG     = -std=c11 -Iinclude -Isrc \
            -Wall -Wextra -Wpedantic -Wshadow -Wconversion \
            -Wcast-qual -Wstrict-prototypes -Wmissing-prototypes \
            -Wwrite-strings -Wformat=2 -Wnull-dereference

NGUON     = $(wildcard src/*.c)
O_TINH    = $(patsubst src/%.c,build/tinh/%.o,$(NGUON))
O_DONG    = $(patsubst src/%.c,build/dong/%.o,$(NGUON))

A         = build/lib$(TEN).a
SO_DAY    = build/lib$(TEN).so.$(PHIEN_BAN)
SO_NAME   = lib$(TEN).so.$(CHINH)

all: $(A) $(SO_DAY)

# --- thu vien tinh ---
$(A): $(O_TINH)
	$(AR) rcs $@ $^

build/tinh/%.o: src/%.c include/cds.h | build/tinh
	$(CC) $(CHUNG) $(CFLAGS) -DCDS_STATIC -c -o $@ $<

# --- thu vien dong ---
$(SO_DAY): $(O_DONG)
	$(CC) -shared -Wl,-soname,$(SO_NAME) $^ -o $@
	ln -sf lib$(TEN).so.$(PHIEN_BAN) build/$(SO_NAME)
	ln -sf $(SO_NAME) build/lib$(TEN).so

build/dong/%.o: src/%.c include/cds.h | build/dong
	$(CC) $(CHUNG) $(CFLAGS) -DCDS_BUILD -fPIC -fvisibility=hidden \
	      -c -o $@ $<

build/tinh build/dong:
	mkdir -p $@

# --- kiem thu, ba luot ---

thu: $(NGUON) test/chay_thu.c
	$(CC) $(CHUNG) -g3 -O1 -DCDS_STATIC \
	      -fno-omit-frame-pointer \
	      -fsanitize=address,undefined \
	      -fsanitize-address-use-after-scope \
	      -fno-sanitize-recover=all \
	      -o build/chay_thu $^
	ASAN_OPTIONS=detect_stack_use_after_return=1:detect_leaks=1 \
	MALLOC_PERTURB_=42 \
	./build/chay_thu

thu_vg: $(NGUON) test/chay_thu.c
	$(CC) $(CHUNG) -g -O1 -DCDS_STATIC -o build/chay_thu_vg $^
	valgrind --leak-check=full --show-leak-kinds=all \
	         --track-origins=yes --error-exitcode=1 \
	         ./build/chay_thu_vg

thu_32: $(NGUON) test/chay_thu.c
	$(CC) $(CHUNG) -m32 -O2 -DCDS_STATIC -o build/chay_thu_32 $^
	./build/chay_thu_32

kiem: thu thu_vg thu_32 kiem_ky_hieu kiem_header

# --- kiem tra ky hieu xuat ra ---
kiem_ky_hieu: $(SO_DAY)
	@xuat=$$(nm -D --defined-only $(SO_DAY) | grep -c ' T '); \
	 khai=$$(grep -cE '^(Vector|List|Heap|Tree|HashMap|void|int|long|size_t) ' \
	         include/cds.h); \
	 echo "xuat ra $$xuat, khai bao $$khai"

# --- kiem tra header tu du ---
kiem_header:
	@echo '#include "cds.h"' | $(CC) -Iinclude -xc -c - -o /dev/null \
	 && echo "header tu du: dat"

sach:
	rm -rf build

.PHONY: all thu thu_vg thu_32 kiem kiem_ky_hieu kiem_header sach

terminal

# Dịch với đủ cờ nghiêm ngặt, không một cảnh báo

gcc -std=c11 -O2 -Wall -Wextra -Wpedantic -Wshadow -Wconversion -o chay_thu.exe vec.c list.c heap.c tree.c hashmap.c chay_thu.c

./chay_thu.exe

[vector]
[list]
[heap]
[tree]
[hashmap]

3121 kiem tra, 0 hong

echo $?

Ba lượt kiểm thử, và mỗi lượt bắt loại lỗi khác nhau

Lượt	Bắt được gì
thu, với ASan và UBSan	Tràn bộ đệm, dùng sau khi giải phóng, rò rỉ, tràn số, dịch bit sai
thu_vg, với Valgrind	Biến chưa khởi tạo, thứ ASan không bắt được. Bài 34.4
thu_32, dịch 32 bit	Giả định về sizeof con trỏ và size_t. Bài 33.7

/* Va MALLOC_PERTURB_=42 trong luot dau:
     - dien 42 vao bo nho vua cap, nen bien chua khoi tao lo ra
     - dien 213 vao bo nho vua free, nen dung sau khi free sap ngay

   Mot bien moi truong, va no bien nhieu loi "thinh thoang"
   thanh loi "luon xay ra". Bai 35.6. */

#Bộ kiểm thử

test/chay_thu.c, khung

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

#include "cds.h"

static int so_kiem = 0, so_hong = 0;

#define KIEM(dk)                                                    \
    do {                                                            \
        ++so_kiem;                                                  \
        if (!(dk)) {                                                \
            ++so_hong;                                              \
            printf("  HONG %s:%d: %s\n", __FILE__, __LINE__, #dk);  \
        }                                                           \
    } while (0)

#define NHOM(t) printf("[%s]\n", t)

/* Ba ky thuat cua Chuong 54 dung o day:
     do while (0)     Bai 54.1
     #dk              Bai 54.2
     __FILE__ va __LINE__ cua NOI GOI   Bai 54.4 */

Bốn nhóm kiểm thử cho mỗi container

static void thu_vec(void) {
    NHOM("vector");

    /* --- 1. TRANG THAI BAN DAU --- */
    Vector *v = vec_new(sizeof(int));
    KIEM(v != NULL);
    KIEM(vec_size(v) == 0);
    KIEM(vec_at(v, 0) == NULL);

    /* --- 2. DUONG THANH CONG --- */
    for (int i = 9; i >= 0; --i) KIEM(vec_push(v, &i) == 0);
    KIEM(vec_size(v) == 10);
    KIEM(*(int *)vec_at(v, 0) == 9);

    vec_sort(v, ss_int, NULL);
    for (size_t i = 0; i < 10; ++i) KIEM(*(int *)vec_at(v, i) == (int)i);

    /* --- 3. HAM GOI LAI VA NGU CANH --- */
    int nguong = 7;
    KIEM(vec_find(v, lon_hon, &nguong) == 8);

    long tong = 0;
    vec_foreach(v, cong_don, &tong);
    KIEM(tong == 45);

    /* --- 4. DUONG LOI --- */
    KIEM(vec_new(0) == NULL);
    KIEM(vec_push(NULL, &nguong) == -1);
    KIEM(vec_insert(v, 100, &nguong) == -1);
    KIEM(vec_remove(v, 100, NULL) == -1);
    KIEM(vec_at(v, 10) == NULL);

    vec_free(v, NULL, NULL);
    vec_free(NULL, NULL, NULL);        /* huy NULL: khong duoc sap */
}

Nhóm 4 chiếm ít dòng nhất và bắt được nhiều lỗi nhất

/* Duong THANH CONG thuong dung ngay tu lan viet dau tien.
   Duong LOI thi khong, vi ban khong nghi toi no khi viet.

   Nam bai kiem thu duong loi phai co cho MOI container:

     1. tao voi tham so vo ly       vec_new(0) == NULL
     2. thao tac tren NULL          vec_push(NULL, &x) == -1
     3. chi so ngoai bien           vec_at(v, 100) == NULL
     4. lay tu container rong       list_pop_front(l, NULL) == -1
     5. huy NULL                    vec_free(NULL, NULL, NULL)

   Bai 5 khong co KIEM nao: no chi can KHONG SAP. Neu ban quen
   kiem tra NULL trong ham huy thi bo kiem thu sap ngay tai do,
   va do la mot bai kiem thu hop le. */

Ba bài kiểm thử bắt lỗi tinh vi nhất

/* 1. Bang bam: xoa mot nua roi tim nua con lai.
      Bat duoc loi o XOA, Bai 55.3. */

for (int i = 0; i < 1000; ++i) { int gt = i * i; hm_put(m, &i, &gt); }
for (int i = 0; i < 500; ++i)  hm_remove(m, &i, NULL);
for (int i = 500; i < 1000; ++i) {
    int *gt = hm_get(m, &i);
    KIEM(gt != NULL && *gt == i * i);
}

/* 2. Heap: kiem tra BAT BIEN, khong kiem tra gia tri cu the. */

int truoc = 1000, ra;
while (heap_pop(h, &ra) == 0) {
    KIEM(ra <= truoc);
    truoc = ra;
}

/* 3. Vector: chen roi xoa o vi tri 0, kiem tra memmove dung. */

int x = 99;
KIEM(vec_insert(v, 0, &x) == 0);
KIEM(*(int *)vec_at(v, 0) == 99);
KIEM(*(int *)vec_at(v, 1) == 0);       /* phan tu cu da dich sang phai */

KIEM(vec_remove(v, 0, &ra) == 0);
KIEM(ra == 99);
KIEM(*(int *)vec_at(v, 0) == 0);       /* da dich nguoc lai */

Rò rỉ chỉ kiểm thử được bằng sanitizer

/* Khong co cach nao viet KIEM() de bat mot cho ro ri:
   ro ri khong lam thay doi ket qua nao ban quan sat duoc.

   Nen bo kiem thu PHAI dich voi -fsanitize=address, va khi chuong trinh
   thoat, LeakSanitizer bao moi khoi chua giai phong.

   Va them mot bai kiem thu lap lai nhieu lan de ro ri lo ro: */

static void thu_ro_ri(void) {
    NHOM("ro ri");

    for (int lan = 0; lan < 1000; ++lan) {
        Vector *v = vec_new(sizeof(int));
        for (int i = 0; i < 100; ++i) vec_push(v, &i);
        vec_free(v, NULL, NULL);
    }

    /* Neu vec_free quen free(v->d) thi day la 1000 * 400 byte ro ri,
       va ASan bao ro rang khi thoat. */
}

/* Bai 34.6 va Bai 35.7 da noi ky ve chuyen nay. */

#Tài liệu

README.md, phần quan trọng nhất

## Quyen so huu

| Ham | Tra ve | Ai so huu |
|---|---|---|
| vec_new     | Vector *     | Nguoi goi. Phai goi vec_free |
| vec_at      | void *       | Thu vien. MUON, va treo sau thao tac tiep theo |
| vec_pop     | qua tham so  | Nguoi goi cap bo dem, thu vien sao chep vao |
| heap_peek   | void *       | Thu vien. MUON, treo sau heap_push hoac heap_pop |
| tree_find   | void *       | Thu vien. MUON, hop le toi khi cay thay doi |
| hm_get      | void *       | Thu vien. MUON, treo sau hm_put lam bam lai |

## Ham goi lai

Moi ham goi lai duoc goi NGAY trong loi goi, va thu vien KHONG
luu con tro ngu canh lai. Nen truyen dia chi bien cuc bo la an toan.

## FreeFn

FreeFn giai phong TAI NGUYEN BEN TRONG mot phan tu, KHONG giai phong
chinh phan tu. Container so huu khoi bo nho.

## Ma loi

- 0 la thanh cong
- so am la loi
- ham doc khong bao gio that bai: tra ve gia tri mac dinh khi con tro NULL
- ham huy chap nhan NULL

## Bat bien khi that bai

Neu mot ham tra ve loi thi trang thai cua container KHONG DOI.
Khong mat phan tu nao va khong ro ri.

Bảng quyền sở hữu là phần đáng giá nhất của tài liệu

/* Bon cau hoi ma nguoi dung thu vien C luon phai hoi:

     1. Toi co phai free cai nay khong?
     2. No song bao lau?
     3. Ham nay co giu con tro cua toi lai khong?
     4. Neu ham that bai thi trang thai the nao?

   Neu tai lieu khong tra loi bon cau nay thi nguoi dung phai
   doc ma nguon, va ho se doan sai.

   Bai 52.1 da noi: quyen so huu phai ghi vao tai lieu cua HEADER,
   vi do la thu duy nhat nguoi dung doc. */

/* Va ghi thang vao header cho nhung cho quan trong: */

/**
 * Tra ve con tro toi phan tu thu i.
 *
 * MUON: thu vien van so huu. KHONG goi free.
 * Con tro chi hop le cho toi thao tac tiep theo lam thay doi
 * vector, vi vec_push co the realloc.
 *
 * Tra ve NULL neu v la NULL hoac i ngoai bien.
 */
void *vec_at(const Vector *v, size_t i);

README.md, phần ví dụ

## Vi du

#include <stdio.h>
#include "cds.h"

static int ss_int(const void *a, const void *b, void *ctx) {
    (void)ctx;
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void) {
    Vector *v = vec_new(sizeof(int));
    if (v == NULL) return 1;

    for (int i = 9; i >= 0; --i)
        if (vec_push(v, &i) != 0) { vec_free(v, NULL, NULL); return 1; }

    vec_sort(v, ss_int, NULL);

    for (size_t i = 0; i < vec_size(v); ++i)
        printf("%d ", *(int *)vec_at(v, i));
    putchar('\n');

    vec_free(v, NULL, NULL);
    return 0;
}

Ket qua: 0 1 2 3 4 5 6 7 8 9

#Danh sách nghiệm thu

Chương 51, chuẩn C

Dịch sạch với -std=c11 -pedantic-errors, không dùng mở rộng nào ngoài chỗ có bọc #if defined(__GNUC__).
Dùng stdint.h ở mọi chỗ độ rộng quan trọng.
Dịch được và chạy đúng với cả -m32 và -m64.

Chương 52, mô hình bộ nhớ

Không con trỏ nào sống lâu hơn đối tượng nó trỏ tới, và tài liệu ghi rõ vòng đời của mọi con trỏ trả về.
Mọi bộ nhớ đến từ malloc, không mảng tĩnh nào bị ép sang kiểu khác.
Không ép con trỏ giữa hai kiểu không tương thích; dùng memcpy.
Căn chỉnh của dữ liệu trong nút được bảo đảm, kiểm tra bằng -fsanitize=alignment.

Chương 53, bố cục struct

Struct nội bộ sắp theo căn chỉnh giảm dần khi nó được cấp phát nhiều lần.
Không memcmp và không băm trực tiếp lên struct có đệm.
Dùng offsetof chứ không sizeof khi tính kích thước cấp phát cho nút có phần đuôi.

Chương 54, bộ tiền xử lý

Macro KIEM dùng do while (0), #dk, __FILE__ và __LINE__.
Không macro nào dài quá mười dòng hoặc lồng quá ba tầng.
Mọi tham số macro có ngoặc, và biểu thức có ngoặc ngoài.

Chương 55, thiết kế thư viện

Năm container, cùng quy ước đặt tên và mã lỗi.
Kiểu mờ hoàn toàn, header không lộ trường nào.
Mọi hàm gọi lại có void *ctx.
Không exit và không printf trong src/.
Trạng thái không đổi khi thất bại, kiểm thử được điều đó.

Chất lượng chung

make sach && make && make kiem chạy từ đầu và trả về mã thoát 0.
Ba lượt kiểm thử đều sạch: sanitizer, Valgrind, 32 bit.
Số ký hiệu xuất ra bằng đúng số hàm trong header, kiểm tra bằng nm -D. Bài 39.12.
Header tự đủ, kiểm tra bằng một dòng lệnh.
README có bảng quyền sở hữu và một ví dụ chạy được.

Tự làm thử

Dựng đủ cây thư mục và chạy make kiem ra 0 hỏng.
Cố tình quên free(v->d) trong vec_free và xác nhận ASan bắt được.
Cố tình cài ô XÓA thành ô TRỐNG và xác nhận bài kiểm thử bảng băm hỏng.
Chạy bộ kiểm thử với -m32 và sửa mọi cảnh báo mới.
Viết bảng quyền sở hữu cho cả năm container.
Thêm tree_remove kèm bài kiểm thử cho cả ba trường hợp: nút lá, nút một con, nút hai con.

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

Một tệp .c cho mỗi container, để chương trình chỉ kéo vào phần nó dùng.
Ba lượt kiểm thử bắt ba loại lỗi khác nhau: sanitizer cho bộ nhớ và UB, Valgrind cho biến chưa khởi tạo, 32 bit cho giả định về kích thước.
Nhóm kiểm thử đường lỗi chiếm ít dòng nhất và bắt được nhiều lỗi nhất.
Rò rỉ chỉ kiểm thử được bằng sanitizer, nên bộ kiểm thử phải dịch với -fsanitize=address.
Bảng quyền sở hữu trả lời bốn câu hỏi mà mọi người dùng thư viện C đều phải hỏi, và nó thuộc về header.