X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=src%2FCidr.hs;h=77f1ae41fe42569d5801c50158aef48f1a595ce7;hb=a767881c16a119a90ff80d9c14106348d8bc310d;hp=266b7c57f8a8e8318124a2518900de75a4d166ca;hpb=b22b30048819a3a53517e44370a97a2e37ba3f10;p=hath.git diff --git a/src/Cidr.hs b/src/Cidr.hs index 266b7c5..77f1ae4 100644 --- a/src/Cidr.hs +++ b/src/Cidr.hs @@ -1,9 +1,13 @@ module Cidr ( Cidr(..), cidr_from_string, + cidr_tests, combine_all ) where +import Data.List (nubBy) +import Test.HUnit + import IPv4Address import ListUtils import Maskable @@ -13,9 +17,23 @@ import Octet data Cidr = None | Cidr { ipv4address :: IPv4Address, maskbits :: Maskbits } - deriving (Eq, Show) + deriving (Eq) + + +instance Show Cidr where + show Cidr.None = "None" + 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 @@ -104,8 +122,70 @@ 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, +-- and can be combined in to 10.1.0.0/23. +adjacent :: Cidr -> Cidr -> Bool +adjacent Cidr.None _ = False +adjacent _ Cidr.None = False +adjacent cidr1 cidr2 + | mbits1 /= mbits2 = False + | mbits1 == Maskbits.Zero = False -- They're equal. + | otherwise = (mbits1 == (most_sig_bit_different addr1 addr2)) + where + addr1 = ipv4address cidr1 + addr2 = ipv4address cidr2 + mbits1 = maskbits cidr1 + mbits2 = maskbits cidr2 + + + + + +-- HUnit Tests + +test_contains :: Test +test_contains = + TestCase $ assertEqual "10.1.1.0/23 contains 10.1.1.0/24" (cidr1 `contains` cidr2) True + where + cidr1 = cidr_from_string "10.1.1.0/23" + cidr2 = cidr_from_string "10.1.1.0/24" + + +cidr_tests :: [Test] +cidr_tests = [ test_contains ]