Lessons and the learning game

Data structures without malloc

The containers real firmware uses, every byte fixed at build time, built into a small space shooter on an Uno.

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

  1. Ring buffers: a queue in a fixed array with free-running uint8_t indices and a power-of-two mask, what full means, a static_assert that catches a bad size, and button presses queued for a game tick.
  2. 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.
  3. Intrusive lists: enemies that carry their own next pointer, 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.
  4. Bitsets: sixteen invaders in one uint16_t, testing and setting bits, Kernighan's bit count, and shooting the lowest one with v & (v - 1).
  5. 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.
  6. Priority queues: a binary min-heap in an 8-slot array, the tree with no pointers, sift up and sift down, and uint16_t times 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 int is 16 bits, so 1 << 15 is negative. The sketches write 1u << n for bit masks.
  • The AVR adds no padding inside structs, so sizeof is the sum of the fields.
  • Only pins 2 and 3 have an external interrupt. Anything an interrupt and loop() both touch is volatile, and loop() 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.