Skip to content

Instantly share code, notes, and snippets.

@camathieu
Created October 7, 2014 08:08
Show Gist options
  • Save camathieu/7ade7e530307ae0d5c37 to your computer and use it in GitHub Desktop.
Save camathieu/7ade7e530307ae0d5c37 to your computer and use it in GitHub Desktop.
CIDR tree for blacklist matching purpose.
package utils
/*
* Charles-Antoine.Mathieu <skatkatt@root.gg>
* CIDR tree for blacklist matching purpose.
*
* It's actually a simple binary tree with each node matching a byte
* of the cidr until the mask is exhausted. The tree has to be walked
* from the root following one of the two available pointers depending
* if the ip to be matched is above of below the median stored in the node.
* So it will take maximum 32 call to match an ip against a /32.
*
* Any data can be attached to a node but at least something different than
* nil must be attached to differentiate empty nodes ( just here to link
* with higher levels ).
*/
import (
"net"
"errors"
"log"
)
/*
* This is a node in the tree, it gets 2 pointer
*/
type CidrNode struct {
Cidr *CIDR
Median uint32
Data interface{}
NextLeft *CidrNode
NextRight *CidrNode
}
/*
* Constructor
*/
func NewCidrNode(cidr *CIDR, data interface {}) (this *CidrNode) {
this = new(CidrNode)
this.Cidr = cidr
this.Data = data
if (this.Cidr.Size == 1) {
// /32
this.Median = 0
} else {
this.Median = this.Cidr.First + uint32( ( this.Cidr.Size + 1 ) / 2 )
}
return
}
/*
* Constructor using string representation of the CIDR.
*/
func NewCidrNodeFromString(str string, data interface {}) (*CidrNode, error) {
if cidr, err := NewCIDRFromString(str, false) ; err == nil {
return NewCidrNode(cidr,data), nil
} else {
return nil, err
}
}
/*
* Insert a higher node at the left or at the right.
*/
func (this *CidrNode) SetNext(node *CidrNode) {
if (node.Cidr.First >= this.Median) {
if (this.NextRight != nil) {
this.NextRight.Data = node.Data
} else {
this.NextRight = node
}
} else {
if (this.NextLeft != nil) {
this.NextLeft.Data = node.Data
} else {
this.NextLeft = node
}
}
}
/*
* Return the next node.
*/
func (this *CidrNode) GetNext(ip uint32) *CidrNode{
if (ip >= this.Median) {
return this.NextRight
} else {
return this.NextLeft
}
}
/*
* Display the CIDR of the node
* TODO : display the data too
*/
func (this *CidrNode) String() string {
return this.Cidr.String()
}
/*
* This is the actual tree. It has to be walked
* from the root to the last matching node.
*/
type CidrTree struct {
root *CidrNode
}
/*
* Constructor
* The root of the tree is at 0.0.0.0/0
*/
func NewCidrTree(data interface {}) (this *CidrTree) {
this = new(CidrTree)
var err error
if this.root, err = NewCidrNodeFromString("0.0.0.0/0", data) ; err != nil {
log.Fatal(err)
}
return
}
/*
* Add a cidr to the tree.
*/
func (this *CidrTree) AddNode(node *CidrNode) {
parent := this.root
//fmt.Println("add " + node.Cidr.String())
// Skip all already inserted nodes
for {
if next := parent.GetNext(node.Cidr.First) ; next != nil {
if next.Cidr.Slash < node.Cidr.Slash {
//fmt.Println("skip " + next.String())
parent = next
} else {
return
}
} else {
break
}
}
// Insert all missing empty nodes
for parent.Cidr.Slash != node.Cidr.Slash - 1 {
nextCidr := parent.Cidr
cidr := new(net.IPNet)
// Increment mask ( add one true bit at the end )
cidr.Mask = net.IPMask(ItoN(NtoI(net.IP(parent.Cidr.Cidr.Mask)) >> 1 | 0x80000000))
// The new CIDR is either the firt or the last half of the parent CIDR
if (node.Cidr.First >= parent.Median){
cidr.IP = ItoN(parent.Median)
} else {
cidr.IP = parent.Cidr.Cidr.IP
}
nextCidr, _ = NewCIDR(cidr,false)
tmpNode := NewCidrNode(nextCidr, nil)
//fmt.Println("add tmp node " + tmpNode.String())
parent.SetNext(tmpNode)
parent = tmpNode
}
// Insert the real node
//fmt.Println("add node " + node.String())
parent.SetNext(node)
}
func (this *CidrTree) AddNodeFromString(str string, data interface {}) error {
if node, err := NewCidrNodeFromString(str,data) ; err == nil {
this.AddNode(node)
return nil
} else {
return err
}
}
/*
* Look for a node matching the IP ( a CIDR embracing this IP
* has been added to the tree before ).
*/
func (this *CidrTree) Match(ip uint32) (node *CidrNode) {
current := this.root
for {
if next := current.GetNext(ip) ; next != nil {
current = next
if ( current.Data != nil ) {
//fmt.Println("found " + current.String())
node = current
} else {
//fmt.Println("matched " + current.String())
}
} else {
break
}
}
return
}
/*
* Look for a node matching the IP ( a CIDR embracing this IP
* has been added to the tree before ).
*/
func (this *CidrTree) MatchFromString(str string) (*CidrNode, error) {
if ip := net.ParseIP(str).To4() ; ip != nil {
//fmt.Printf("matching %s %d\n",str, NtoI(ip))
return this.Match(NtoI(ip)), nil
} else {
return nil, errors.New("Invalid IP : " + str)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment