CNAME / Redirect Chain Resolver (C)
Topics: chain following, cycle detection, hop budget
Problem
Follow a CNAME / redirect chain from a starting name to its canonical target,
detecting loops and capping the number of hops. The mapping is a flat array of
(name -> target) pairs.
typedef enum { RESOLVE_OK, RESOLVE_LOOP, RESOLVE_TOO_LONG } ResolveStatus;
typedef struct { const char *name; const char *target; } CName;
ResolveStatus cname_resolve(const CName *cnames, int n, const char *start, int max_hops,
const char **out_target, const char **chain, int *chain_len);
RESOLVE_OK — a name with no CNAME entry is the canonical target; set
*out_target to it (a name not in the map resolves to itself, 0 hops).RESOLVE_LOOP — a name is revisited; fill chain[0..*chain_len) with the names
visited (in order) before the repeat.RESOLVE_TOO_LONG — following the next link would exceed max_hops.
Key concepts
- Record what you leave, not where you are: before following
cur -> target,
remember cur. Seeing cur again later is the loop signal (a self-pointing name
loops with a one-element chain).
- Order of checks matters: test "no further redirect" first, then the hop
budget, then the loop — so a chain that is exactly
max_hops long still
resolves instead of being rejected.
- No allocation: the
chain[] buffer doubles as the visited set (linear scan).
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/cname && /tmp/cname
Sign in to submit your solution.