DeetCode.

Bit Trie for Longest Prefix Match

Hard C Optimization Asked at Juniper Networks
Solve this problem

Implement a binary trie for IP routing that returns the longest matching prefix for a destination address, which is what a forwarding table lookup does.

Constraints

  • Prefixes are (address, prefix_length, next_hop).
  • Lookup returns the next hop of the longest matching prefix, or -1.
  • The default route 0.0.0.0/0 must match everything.
  • Insert and lookup are both O(32).
  • Statically allocated node pool of 1024 nodes.
  • No recursion.
Starter codeC
1#include <stdint.h>2 3void trie_init(void);4int  trie_insert(uint32_t prefix, int len, int next_hop);5int  trie_lookup(uint32_t address);