From f74d9ccfb98a2ac25b4eebbfadf9a16b7a5202e1 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Sun, 9 May 2010 13:49:56 -0400 Subject: [PATCH] Added the functions to combine and remove adjacent Cidrs. Updated combine_all to perform both types (contained, adjacent) of combination. --- src/Cidr.hs | 42 ++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 40 insertions(+), 2 deletions(-) diff --git a/src/Cidr.hs b/src/Cidr.hs index 1b7d1dd..08eebcb 100644 --- a/src/Cidr.hs +++ b/src/Cidr.hs @@ -4,6 +4,8 @@ module Cidr combine_all ) where +import Data.List (nubBy) + import IPv4Address import ListUtils import Maskable @@ -21,6 +23,15 @@ instance Show Cidr where show cidr = (show (ipv4address cidr)) ++ "/" ++ (show (maskbits cidr)) +-- Two CIDR ranges are equivalent if they have the same network bits +-- and the masks are the same. +equivalent :: Cidr -> Cidr -> Bool +equivalent Cidr.None Cidr.None = True +equivalent Cidr.None _ = False +equivalent _ Cidr.None = False +equivalent (Cidr addr1 mbits1) (Cidr addr2 mbits2) = + (mbits1 == mbits2) && ((apply_mask addr1 mbits1) == (apply_mask addr2 mbits2)) + -- Returns the mask portion of a CIDR address. That is, everything -- after the trailing slash. maskbits_from_cidr_string :: String -> Maskbits @@ -109,13 +120,40 @@ redundant :: [Cidr] -> Cidr -> Bool redundant cidrlist cidr = any ((flip contains_proper) cidr) cidrlist --- We want to get rid of all the Cidrs that are properly contained --- in some other Cidr. +-- First, we look at all possible pairs of cidrs, and combine the +-- adjacent ones in to a new list. Then, we concatenate that list with +-- the original one, and filter out all of the redundancies. If two +-- adjacent Cidrs are combined into a larger one, they will be removed +-- in the second step since the larger Cidr must contain the smaller +-- two. combine_all :: [Cidr] -> [Cidr] combine_all cidrs = + combine_contained unique_cidrs + where + unique_cidrs = nubBy equivalent valid_cidr_combinations + valid_cidr_combinations = filter (/= Cidr.None) cidr_combinations + cidr_combinations = + cidrs ++ [ (combine_adjacent x y) | x <- cidrs, y <- cidrs ] + + +-- Take a list of CIDR ranges and filter out all of the ones that are +-- contained entirelt within some other range in the list. +combine_contained :: [Cidr] -> [Cidr] +combine_contained cidrs = filter (not . (redundant cidrs)) cidrs +-- If the two Cidrs are not adjacent, return Cidr.None. Otherwise, +-- decrement the maskbits of cidr1 and return that; it will contain +-- both cidr1 and cidr2. +combine_adjacent :: Cidr -> Cidr -> Cidr +combine_adjacent cidr1 cidr2 + | not (adjacent cidr1 cidr2) = Cidr.None + | (maskbits cidr1 == Zero) = Cidr.None + | otherwise = cidr1 { maskbits = decrement (maskbits cidr1) } + + + -- Determine whether or not two CIDR ranges are adjacent. If two -- ranges lie consecutively within the IP space, they can be -- combined. For example, 10.1.0.0/24 and 10.0.1.0/24 are adjacent, -- 2.44.2