All paths

Data structures without malloc

The containers firmware really uses, every byte fixed at build time: ring buffers, pools, intrusive lists, bitsets, state tables and heaps. Ends with an event queue that runs a space shooter.

Arduino Uno R3Free7 lessons5 h4 chapters2,705 XPCoding · Advanced+250 XP

0 of 7 done

What you will build

3 projects, built step by step

7 lessons in 4 chapters, about 5 hours on a simulated Arduino Uno R3. Free, in your browser, every step checked by the simulator.

Chapter 1 project

Fixed pools

Every bullet the game will ever have, made at build time: a free list threaded through the slots, alloc and release in a few instructions, and what happens when it runs dry.

Open it in the simulator
Chapter 2 project

Bitsets

Sixteen invaders in one uint16_t: test, set and clear a bit, count them with Kernighan's trick, and shoot the lowest one with v & (v - 1).

Open it in the simulator
Chapter 3 project

Priority queues

A binary min-heap of timed game events in an 8-slot array: the tree with no pointers, sift up and down, swap counts, and time comparisons that survive the wrap.

Open it in the simulator
The map

Chapter by chapter

Each lesson opens when the one before it is done, and each chapter ends in a project.

Chapter 1

Queues and pools

A ring buffer for events and a pool of bullets, with no heap.

  1. Open250 XP

    Ring buffers

    A fixed-size queue that never moves its data: free-running uint8_t indices, a power-of-two mask, what full means, and button presses queued for a game tick.

    0 of 5 steps

  2. ProjectLocked500 XP

    Fixed pools

    Every bullet the game will ever have, made at build time: a free list threaded through the slots, alloc and release in a few instructions, and what happens when it runs dry.

    0 of 5 steps

4 questions, graded as you go.
Chapter 2

Links and bits

Lists threaded through the objects, and sixteen answers in two bytes.

  1. Locked250 XP

    Intrusive lists

    Enemies that carry their own next pointer: lists that cost no memory, moving a node between lists with two pointer writes, and unlinking with a pointer to a pointer.

    0 of 5 steps

  2. ProjectLocked576 XP

    Bitsets

    Sixteen invaders in one uint16_t: test, set and clear a bit, count them with Kernighan's trick, and shoot the lowest one with v & (v - 1).

    0 of 6 steps

4 questions, graded as you go.
Chapter 3

Rules and order

A game run by a table, and a heap that knows what is due next.

  1. Locked250 XP

    State tables

    A game's TITLE, PLAYING, PAUSED and GAMEOVER rules as one NEXT[state][event] table: transitions that are data, entry actions, and changing a rule by editing one cell.

    0 of 5 steps

  2. ProjectLocked576 XP

    Priority queues

    A binary min-heap of timed game events in an 8-slot array: the tree with no pointers, sift up and down, swap counts, and time comparisons that survive the wrap.

    0 of 6 steps

4 questions, graded as you go.
Chapter 4

Boss

Everything in one event queue: Mokxi Invaders.

  1. Locked303 XP

    Boss: an event queue for a game

    Mokxi Invaders with no malloc: a button interrupt and a heap of timers feed one ring of events, handled by a table of state functions, with a bullet pool and a bitset wave.

    0 of 7 steps

3 questions, graded as you go.
Syllabus

Every lesson in the course

All 7 lessons, in order, each with what it covers. Any of them opens in the editor right away.

Chapter 1

Queues and pools

  1. Ring buffersA fixed-size queue that never moves its data: free-running uint8_t indices, a power-of-two mask, what full means, and button presses queued for a game tick.
  2. Fixed poolsEvery bullet the game will ever have, made at build time: a free list threaded through the slots, alloc and release in a few instructions, and what happens when it runs dry.
Chapter 2

Links and bits

  1. Intrusive listsEnemies that carry their own next pointer: lists that cost no memory, moving a node between lists with two pointer writes, and unlinking with a pointer to a pointer.
  2. BitsetsSixteen invaders in one uint16_t: test, set and clear a bit, count them with Kernighan's trick, and shoot the lowest one with v & (v - 1).
Chapter 3

Rules and order

  1. State tablesA game's TITLE, PLAYING, PAUSED and GAMEOVER rules as one NEXT[state][event] table: transitions that are data, entry actions, and changing a rule by editing one cell.
  2. Priority queuesA binary min-heap of timed game events in an 8-slot array: the tree with no pointers, sift up and down, swap counts, and time comparisons that survive the wrap.
Chapter 4

Boss

  1. Boss: an event queue for a gameMokxi Invaders with no malloc: a button interrupt and a heap of timers feed one ring of events, handled by a table of state functions, with a bullet pool and a bitset wave.
Kits

Build it on your bench too

Every lesson runs in the simulator with nothing to buy. When you want the real thing, these kits have the parts.

Have a kit already?

Find your kit

Pick the starter kit you own and run every lesson in its manual with the same parts on the same pins.

See every kit
Questions

About Data structures without malloc

Is Data structures without malloc free?

Yes. All 7 lessons of Data structures without malloc are free and run in your browser, with nothing to install and no parts to buy before you start.

Do I need a real Arduino Uno R3?

No. Every lesson runs on a simulated Arduino Uno R3 with its parts on the canvas, and the simulator checks each step as you go. When you want to build it for real, the same wiring and code work on a real board.

How long does Data structures without malloc take?

About 5 hours: 7 lessons in 4 chapters, each one a few short steps. Your progress is kept, so you can stop after any lesson and pick up where you left off.

What will I build?

Each chapter ends in a project that puts it together: Fixed pools, Bitsets and Priority queues.

Where do I start?

With "Ring buffers", and each lesson builds on the one before it. New to circuits? Electronics basics is the course that starts from zero.