Cách hoạt động
Cấu trúc dữ liệu không cần malloc chạy mọi bài học trên một bàn code: một bo mạch Arduino Uno với đèn đỏ ở chân 13, đèn vàng ở chân 12, đèn xanh lá ở chân 11 và một nút nhấn ở chân 2. Mỗi bài học là một mảnh của một trò chơi: nút nhấn bắn, các đèn cho thấy cấu trúc đang làm gì, và serial monitor in ra bên trong của nó.
Mỗi bài học mở ra một sketch C chạy được. Bạn chạy nó, nhấn nút, đọc serial monitor, rồi đổi một dòng và chạy lại. Phần kiểm tra đọc đầu ra serial, nên mỗi dòng mà bài học trích dẫn đều là dòng mà bo mạch thực sự in ra.
Các bài học
- Ring buffer: một hàng đợi trong một mảng cố định với các chỉ số
uint8_ttự chạy và một bitmask luỹ thừa của hai, "đầy" nghĩa là gì, mộtstatic_assertbắt lỗi kích thước, và các lần nhấn nút được xếp hàng đợi cho một tick của trò chơi. - Pool cố định: sáu viên đạn được tạo lúc biên dịch, một danh sách rảnh xuyên qua các ô chưa dùng, alloc và release chỉ trong vài lệnh, và một khẩu súng kêu click khi pool cạn.
- Danh sách intrusive: các kẻ địch tự mang con trỏ
nextcủa mình, được chuyển giữa danh sách sống và danh sách chết mà không cần chép, và tháo nút bằng con trỏ tới con trỏ nên phần đầu không cần xử lý riêng. - Bitset: mười sáu kẻ xâm lăng trong một
uint16_t, kiểm tra và đặt bit, đếm bit theo Kernighan, và bắn con thấp nhất bằngv & (v - 1). - Bảng trạng thái: các quy tắc TITLE, PLAYING, PAUSED và GAMEOVER của một trò chơi gom vào một bảng
NEXT[state][event]12 byte, các hành động khi vào trạng thái, sự kiện phát ra từ handler, và một quy tắc đổi được chỉ bằng sửa một ô. - Hàng đợi ưu tiên: một binary min-heap trong một mảng 8 ô, cây không cần con trỏ, sift up và sift down, và các thời điểm
uint16_tso bằng hiệu để vẫn đúng khi bị wrap.
Trùm cuối: một hàng đợi sự kiện cho một trò chơi
Bài học cuối là Mokxi Invaders. Ngắt của nút nhấn đẩy các sự kiện FIRE vào một ring, một heap bộ đếm thời gian đẩy các sự kiện MARCH và LAND vào cùng ring khi đến hạn, và loop() đưa mỗi sự kiện cho handler của trạng thái hiện tại, lấy từ một bảng hàm. Đạn lấy từ một pool gồm ba viên và đám tám kẻ xâm lăng là một bitset trong một byte: tổng cộng 43 byte hàng đợi. Bạn mở một đợt tấn công, bắn, dọn sạch, mất một mạng, và bật chế độ khó bằng một hằng số. Nút nhấn rung như nút thật, và ngắt cho thấy cách đếm một lần nhấn là một phát bắn.
Những điều bo mạch Uno làm khác
- Chỉ có 2 KB SRAM. Một heap bị phân mảnh có thể hỏng dù còn nhiều byte rảnh, nên firmware cố định bộ nhớ ngay lúc biên dịch, nơi báo cáo bộ nhớ của bản build đếm nó.
- Một con trỏ dài 2 byte và một
intlà 16 bit, nên1 << 15là số âm. Các sketch ghi1u << ncho bitmask. - AVR không thêm padding bên trong struct, nên
sizeoflà tổng của các trường. - Chỉ chân 2 và chân 3 có ngắt ngoài. Mọi thứ mà cả ngắt và
loop()cùng chạm tới đều làvolatile, vàloop()tắt ngắt trong khoảnh khắc nó đẩy vào ring dùng chung. millis()wrap sau mỗi 49.7 ngày. So các thời điểm bằng hiệu số, không bao giờ bằng<, để vẫn chạy đúng qua cột mốc wrap.
Sau khóa học này
Toán điểm cố định và số nguyên là nửa còn lại của việc lập trình cho một chip nhỏ: phân số, co giãn và toán nhanh chỉ với số nguyên.