Radix Trie IPv4 Prefix Matcher

Challenge

Network routers perform Longest Prefix Matching (LPM) on IP routing tables using binary radix tries, branching on each address bit (0 for left, 1 for right).

Your Task

Given the binary trie node:

typedef struct TrieNode {
    struct TrieNode *children[2]; // 0: left, 1: right
    int next_hop;
} TrieNode;

Implement prefix insertion and matching:

int trie_insert(TrieNode *nodes, size_t max_nodes, size_t *node_count, uint32_t prefix, uint8_t prefix_len, int next_hop);
int trie_longest_prefix_match(const TrieNode *root, uint32_t ip);

Rules

1. Node 0 (nodes[0]) is the root node. Initialized with children = {NULL, NULL} and next_hop = -1.
2. In trie_insert:
   • If nodes == NULL, node_count == NULL, prefix_len > 32, or next_hop < 0, return -1.
   • Walk from bit 31 down to bit 32 - prefix_len.
   • For each bit (0 or 1), if child is NULL, allocate next node from nodes[*node_count] (if *node_count >= max_nodes, return -1), increment *node_count, initialize child with children = {NULL, NULL} and next_hop = -1.
   • After walking prefix_len bits, set terminal node's next_hop = next_hop.
   • Return 0.
3. In trie_longest_prefix_match:
   • If root == NULL, return -1.
   • Track best_hop = root->next_hop.
   • Walk 32 bits from bit 31 down to bit 0. At each node, if curr->next_hop != -1, update best_hop = curr->next_hop.
   • If child branch is NULL, break.
   • Return best_hop (or -1 if no prefix matched).

Example

TrieNode arena[64]; size_t count = 1;
arena[0].children[0] = arena[0].children[1] = NULL; arena[0].next_hop = -1;
// 192.168.0.0/16 -> hop 1
trie_insert(arena, 64, &count, 0xC0A80000, 16, 1);
trie_longest_prefix_match(&arena[0], 0xC0A80105); // returns 1

Input format

nodes: static node arena; prefix, ip: 32-bit big endian uint32; prefix_len: 0..32.

Output format

Returns next hop integer (or -1 if no match).

Constraints

Zero heap malloc. Static arena allocator.

Starter code

#include <stddef.h>
#include <stdint.h>

typedef struct TrieNode {
    struct TrieNode *children[2];
    int next_hop;
} TrieNode;

int trie_insert(TrieNode *nodes, size_t max_nodes, size_t *node_count, uint32_t prefix, uint8_t prefix_len, int next_hop) {
    (void)nodes; (void)max_nodes; (void)node_count; (void)prefix; (void)prefix_len; (void)next_hop;
    return -1;
}
int trie_longest_prefix_match(const TrieNode *root, uint32_t ip) {
    (void)root; (void)ip;
    return -1;
}

Common mistakes

Checking bits from 0 up instead of 31 down (MSB first); buffer overflow on arena count.

Edge cases to handle

prefix_len == 0 sets default gateway on root; more specific prefix overrides less specific prefix.

Background lessons

• Binary trees
• htons(), htonl(), inet_pton() — network byte order