In this paper, the authors have proposed a novel algorithm and data structures to improve the speed of firewall policy verification. It is called the Policy MAPping (PMAP). Time complexity of the proposed technique is O (1) to verify incoming-outgoing packets against the firewall policy. Be-sides, the algorithm is not limited to handle IP network classes as IPSET which is the top of high-speed firewall open source today. PMAP can also optimize the firewall rule decision by employing the Firewall Decision State Diagram (FDSD) to clarify ordering of policy verifying.