DOCSEARCHbyAlgolia
Submit Docs

cidranger

repository·master·Indexed 21 days ago

https://github.com/yl2chen/cidranger

A high-performance Golang library for fast IP to CIDR block lookups using a Path-Compressed prefix trie. It provides the Ranger and RangerEntry interfaces to support efficient containment tests, retrieval of containing networks, and custom metadata attachment to CIDR blocks. The library includes NewPCTrieRanger for production use and a bruteRanger implementation for testing and small datasets.

Tokens
3.3K
Snippets
19
Records
20
Agent score
74%

What's inside cidranger

  1. How to attach custom values to CIDR entries

    master

    If you need to associate metadata with a CIDR block, create a custom struct that implements the RangerEntry interface. The interface requires a Network() net.IPNet method.

    type RangerEntry interface {
	Network() net.IPNet
}

// Example of a custom entry
type MyCustomEntry struct {
    net net.IPNet
    Metadata string
}

func (m *MyCustomEntry) Network() net.IPNet {
    return m.net
}

  2. Quickstart: Perform IP to CIDR lookups

    master

    To use cidranger for fast IP lookups, initialize a new ranger using NewPCTrieRanger(), which implements a Path-Compressed prefix trie. You can then insert CIDR blocks using Insert() and perform lookups using Contains() or ContainingNetworks().

    import (
  "net"
  "github.com/yl2chen/cidranger"
)

// 1. Create a new ranger
ranger := cidranger.NewPCTrieRanger()

// 2. Insert CIDR blocks
_, network1, _ := net.ParseCIDR("192.168.1.0/24")
_, network2, _ := net.ParseCIDR("128.168.1.0/24")
ranger.Insert(cidranger.NewBasicRangerEntry(*network1))
ranger.Insert(cidranger.NewBasicRangerEntry(*network2))

// 3. Test if an IP is contained in the ranger
contains, err := ranger.Contains(net.ParseIP("128.168.1.0")) // returns true, nil
contains, err = ranger.Contains(net.ParseIP("192.168.2.0")) // returns false, nil

// 4. Get all networks that contain the given IP
containingNetworks, err := ranger.ContainingNetworks(net.ParseIP("128.168.1.0"))

  3. How prefixTrie lookup and compression works

    master

    The prefixTrie uses a path-compressed (PC) trie structure to optimize IP prefix lookups:

    1. Structure: CIDR blocks are stored in a prefix tree where each node's path from the root represents a CIDR prefix. For IPv4, the maximum depth is 32 bits, ensuring constant-time lookup complexity in Big-O notation.
    2. Path Compression: To reduce the number of lookups, the trie compresses strings of nodes that have only one child into a single node. This is particularly effective during containment tests.
    3. Complexity: Lookups are highly efficient because the tree depth is bounded by the bit-length of the IP version (32 for IPv4, 128 for IPv6).
    4. Limitations: While path compression is implemented, level compression (handling multiple bits per node) is a planned future feature.

  4. Retrieve all covered networks in the ranger

    master

    You can retrieve all networks currently stored in the ranger by using the CoveredNetworks method. Pass either *AllIPv4 or *AllIPv6 to specify the IP version.

    // For IPv4
entries, err := ranger.CoveredNetworks(*cidranger.AllIPv4)

// For IPv6
entries, err := ranger.CoveredNetworks(*cidranger.AllIPv6)

  5. Use bruteRanger for testing and small datasets

    master

    The bruteRanger is a brute-force implementation of the Ranger interface. It is primarily intended for testing purposes because its correctness is easily guaranteed, making it a reliable 'ground truth' for verifying more sophisticated implementations.

    Performance Characteristics:

    • Insertion/Deletion: Constant time $O(1)$ using internal maps.
    • Inclusion Tests (Contains, CoveredNetworks, etc.): Linear time $O(N)$ as it performs a linear scan of recorded networks.

    Use newBruteRanger() to obtain an instance of the Ranger interface.

    // Note: newBruteRanger is unexported in this file, but it returns the Ranger interface.
// In a real usage scenario, you would use the package's exported constructor for the desired implementation.
ranger := cidranger.NewBruteRanger() // Assuming an exported version exists or using the interface

  6. Perform IP containment lookups

    master

    Use the following methods to check if an IP address is covered by the networks stored in the ranger:

    • Contains(ip net.IP) (bool, error): Returns true if the IP is contained within any of the registered CIDR blocks.
    • ContainingNetworks(ip net.IP) ([]RangerEntry, error): Returns a slice of all RangerEntry objects whose networks contain the specified IP.
    ip := net.ParseIP("192.168.0.1")

// Check if IP is contained
contains, err := ranger.Contains(ip)

// Get all networks containing this IP
entries, err := ranger.ContainingNetworks(ip)

  7. Manage CIDR ranges with prefixTrie

    master

    The prefixTrie is a path-compressed trie implementation used for efficient CIDR block lookups. It provides methods to insert, remove, and query IP addresses against a set of registered networks.

    Important Note: A single prefixTrie instance cannot contain both IPv4 and IPv6 addresses. To manage both, use the versionedRanger wrapper (available in the package).

    Core API Methods

    • Insert(entry RangerEntry) error: Adds a new RangerEntry to the trie.
    • Remove(network net.IPNet) (RangerEntry, error): Removes the entry associated with the specified net.IPNet. Returns the removed entry if found.
    • Contains(ip net.IP) (bool, error): Checks if the given IP address is contained within any of the inserted networks.
    • ContainingNetworks(ip net.IP) ([]RangerEntry, error): Returns all RangerEntry objects that contain the given IP, sorted by ascending prefix order (most general to most specific).
    • CoveredNetworks(network net.IPNet) ([]RangerEntry, error): Returns all RangerEntry objects that are completely subsumed by the specified network (networks that are children/subnets of the input).
    • Len() int: Returns the total number of networks currently in the trie.
    // Example usage pattern (conceptual)
// Note: prefixTrie is unexported; you typically interact with it via the Ranger interface
// returned by newPrefixTree or versionedRanger.

err := trie.Insert(myEntry)
if err != nil {
    // handle error
}

isContained, err := trie.Contains(net.ParseIP("192.168.1.1"))

networks, err := trie.ContainingNetworks(net.ParseIP("192.168.1.1"))

  8. Retrieve covered networks with CoveredNetworks

    master

    The CoveredNetworks(network net.IPNet) ([]RangerEntry, error) method returns a list of all CIDR blocks currently in the ranger that are contained within the provided network.

    // Get all networks in the ranger that fall within the IPv4 space
entries, err := ranger.CoveredNetworks(*cidranger.AllIPv4)

  9. Initialize a new CIDR ranger with NewPCTrieRanger

    master

    To create a new instance of a CIDR ranger that supports both IPv4 and IPv6 using a path-compressed trie implementation, use NewPCTrieRanger(). This returns an object implementing the Ranger interface.

    ranger := cidranger.NewPCTrieRanger()

  10. Manage CIDR entries with Insert and Remove

    master

    You can add or remove CIDR blocks from a Ranger instance:

    • Insert(entry RangerEntry) error: Adds a new entry to the ranger.
    • Remove(network net.IPNet) (RangerEntry, error): Removes the entry matching the specified net.IPNet and returns the removed entry.
    _, network, _ := net.ParseCIDR("192.168.0.0/24")

// Insert
ranger.Insert(cidranger.NewBasicRangerEntry(*network))

// Remove
removedEntry, err := ranger.Remove(network)

  11. Reference: Ranger Interface

    master

    The Ranger interface defines the public API for CIDR block containment lookups.

    type Ranger interface {
	Insert(entry RangerEntry) error
	Remove(network net.IPNet) (RangerEntry, error)
	Contains(ip net.IP) (bool, error)
	ContainingNetworks(ip net.IP) ([]RangerEntry, error)
	CoveredNetworks(network net.IPNet) ([]RangerEntry, error)
	Len() int
}