Firewall Rule Matcher for IPv4 CIDR Rules

Context and Assumptions

You are to design and implement a firewall rule matcher that decides whether to accept or deny traffic for IPv4 addresses based on a list of CIDR-prefix rules. Each rule is tagged accept or deny. Assume:

• IPv4 (32-bit addresses).
• Precedence: longest-prefix match wins (typical for CIDR-based routing). For ties (same prefix length), earlier rule definition wins. If nothing matches, default is deny.
• Rules can overlap (e.g., 10.0.0.0/8 accept and 10.0.0.0/16 deny).

Tasks

1. Design and implement a matcher that evaluates a single IPv4 address against a list of CIDR rules (accept/deny). Explain the data structures and algorithms used.
2. Follow-up: extend the solution to handle evaluating an incoming CIDR range against the rule set. Discuss and propose efficient data structures for range intersection checks.

Inputs/Outputs

• Input (single-IP case): list of rules like [("10.0.0.0/8", accept), ("10.0.0.0/16", deny), ...] and a query IP (e.g., "10.1.2.3").
• Output: accept or deny according to precedence.
• Follow-up input: an incoming CIDR (e.g., "10.1.0.0/17").
• Follow-up output: either a single decision if uniform over the range, or a decomposition into subranges with decisions; and a discussion of efficient data structures for range intersection.