How it works
Data structures without malloc runs every lesson on the code bench: an Arduino Uno with a red lamp on pin 13, yellow on 12, green on 11 and a button on pin 2. Each lesson is one piece of a game: the button fires, the lamps show what the structure is doing, and the serial monitor prints its insides.
Every lesson opens a working C sketch. You run it, press the button, read the serial monitor, then change a line and run again. The checks read the serial output, so every line a lesson quotes is one the board really printed.
The lessons
- Ring buffers: a queue in a fixed array with free-running
uint8_tindices and a power-of-two mask, what full means, astatic_assertthat catches a bad size, and button presses queued for a game tick. - Fixed pools: six bullets made at build time, a free list threaded through the unused slots, alloc and release in a few instructions, and a gun that clicks when the pool runs dry.
- Intrusive lists: enemies that carry their own
nextpointer, moved between an alive list and a dead list with no copies, and unlinking with a pointer to a pointer so the head needs no special case. - Bitsets: sixteen invaders in one
uint16_t, testing and setting bits, Kernighan's bit count, and shooting the lowest one withv & (v - 1). - State tables: a game's TITLE, PLAYING, PAUSED and GAMEOVER rules as one
12-byte
NEXT[state][event]table, entry actions, events raised from handlers, and a rule changed by editing one cell. - Priority queues: a binary min-heap in an 8-slot array, the tree with no
pointers, sift up and sift down, and
uint16_ttimes compared so they survive the wrap.
The boss: an event queue for a game
The last lesson is Mokxi Invaders. The button's interrupt pushes FIRE events
into a ring, a heap of timers pushes MARCH and LAND events into the same ring
when they come due, and loop() hands each event to the current state's
handler from a table of functions. Bullets come from a pool of three and the
wave of eight invaders is a bitset in one byte: 43 bytes of queues in all.
You start a wave, shoot, clear it, lose one, and turn on hard mode with one
constant. The button bounces like a real one, and the interrupt shows how to
count one press as one shot.
What the Uno does differently
- There are only 2 KB of SRAM. A heap that fragments can fail with plenty of bytes free, so firmware fixes its memory at build time, where the build's memory report counts it.
- A pointer is 2 bytes and an
intis 16 bits, so1 << 15is negative. The sketches write1u << nfor bit masks. - The AVR adds no padding inside structs, so
sizeofis the sum of the fields. - Only pins 2 and 3 have an external interrupt. Anything an interrupt and
loop()both touch isvolatile, andloop()turns interrupts off for the moment it pushes into the shared ring. millis()wraps every 49.7 days. Comparing times by their difference, never with<, keeps working across the wrap.
After this course
Fixed-point and integer math is the other half of writing for a small chip: fractions, scaling and fast math with integers only.