</>EmbeddedInterview

Order device initialisation with a topological sort.

Medium"Coding: Systems, Bitmaps & Virtualization"
#include <stdio.h>

/* edge u -> v means "u must be initialised before v" (e.g. clock -> i2c -> pmic -> display) */
#define MAXN 16
static int adj[MAXN][MAXN], deg[MAXN], indeg[MAXN];

void add_dep(int before, int after) { adj[before][deg[before]++] = after; indeg[after]++; }

/* Kahn's algorithm: returns number of devices ordered; less than n means a cycle */
int init_order(int n, int *order)
{
    int queue[MAXN], qh = 0, qt = 0, cnt = 0;
    int in[MAXN];
    for (int i = 0; i < n; i++) { in[i] = indeg[i]; if (in[i] == 0) queue[qt++] = i; }
    while (qh < qt) {
        int u = queue[qh++];
        order[cnt++] = u;
        for (int k = 0; k < deg[u]; k++)
            if (--in[adj[u][k]] == 0) queue[qt++] = adj[u][k];
    }
    return cnt;
}

Points: start with devices that depend on nothing, "initialise" them, and remove their outgoing edges; any device whose remaining dependency count reaches zero becomes ready. If fewer than n devices come out, there is a dependency cycle (report it). O(V + E). Real systems: the Linux driver core handles probe ordering with deferred probing (a driver returns -EPROBE_DEFER when a supplier such as a clock or regulator is not ready) and fw_devlink, which builds supplier/consumer links from the device tree; systemd orders units with the same idea; Zephyr uses initialisation levels and priorities.