cidr_trie package

Submodules

cidr_trie.bits_util module

Contains various utility functions for interacting/manipulating integers on a bit-level.

cidr_trie.bits_util.bit_not(n: int, numbits: int = 32) → int

Return the bitwise NOT of ‘n’ with ‘numbits’ bits.

cidr_trie.bits_util.ffs(x: int) → int

Find first set - returns the index, counting from 0 (from the right), of the least significant set bit in x.

cidr_trie.bits_util.fls(val: int, v6: bool) → int

Find last set - returns the index, counting from 0 (from the right) of the most significant set bit in val.

cidr_trie.bits_util.is_set(b: int, val: int, v6: bool) → bool

Return whether b-th bit is set in integer ‘val’.

Special case: when b < 0, it acts as if it were 0.

cidr_trie.cidr_util module

Contains various utility functions for interacting/manipulating IP and CIDR addresses.

cidr_trie.cidr_util.cidr_atoi(cidr_string: str) → Tuple[int, int]

Convert a CIDR string to a network and prefix length tuple. Supports IPv4 and IPv6.

Parameters:cidr_string – The CIDR as a string, i.e. “192.168.0.0/16”
Returns:A tuple containing the integer IP address of the network (the lowest IP inside) and the prefix length. i.e. (int(192.168.0.0), 16) for “192.168.0.0/16”.
cidr_trie.cidr_util.get_subnet_mask(subnet: int, v6: bool) → int

Get the subnet mask given a CIDR prefix ‘subnet’.

cidr_trie.cidr_util.ip_atoi(ip_string: str) → int

Converts an IP string ‘ip_string’ to an integer.

cidr_trie.cidr_util.ip_itoa(ip: int, v6: bool) → str

Converts an IP integer ‘ip’ to a string.

cidr_trie.cidr_util.is_v6(ip_string: str) → bool

Returns True if a given IP string is v6, False otherwise.

cidr_trie.cidr_util.longest_common_prefix_length(a: int, b: int, v6: bool) → int

Find the longest common prefix length of ‘a’ and ‘b’.

Module contents

Store CIDR IP addresses (both v4 and v6) in a PATRICIA trie for easy lookup.

A Patricia trie can be created, inserted to, and searched like this

trie = PatriciaTrie()
trie.insert("0.0.0.0/0", "Internet")
trie.insert("32.0.0.0/9", "RIR-A")
trie.insert("32.128.0.0/9", "RIR-B")
trie.insert("32.32.0.0/16", "another")
trie.insert("32.32.32.0/24", "third")
trie.insert("32.32.32.32/32", "you")
trie.insert("192.168.0.1/32", "totally different")
trie.insert("33.0.0.0/8", "RIR3")
trie.insert("64.0.0.0/8", "RIR2")

# find all node values on the way down
print(trie.find_all("32.32.32.32"))
class cidr_trie.PatriciaNode(ip: int = 0, bit: int = 0, masks: Dict[int, Any] = {})

Bases: object

A node in the Patricia trie.

ip

The IP address associated with this node.

Type:int
bit

How many bits along the IP the decision is made to branch.

Type:int
masks

The data stored on this node. Maps netmasks to data.

Type:Dict[int, Any]
left

The left subtrie of this node. Self pointer if no left node.

Type:PatriciaNode
right

The right subtrie of this node. Self pointer if no right node.

Type:PatriciaNode
parent

The parent node of this node. None if root node.

Type:PatriciaNode
get_child_values(prefix: str) → List[Tuple[str, Any]]

Get all child values from this node by iterating through netmasks and checking to see if the given prefix is larger than the given netmask.

Parameters:prefix – The prefix to use to check, i.e. “192.168.0.0/16”
Returns:list of tuples of prefixes and values, i.e. [(“192.168.0.0/16”, 2856), …]
Return type:List[Tuple[str, Any]]
get_values(prefix: str) → List[Tuple[str, Any]]

Get values from this node by iterating through netmasks and checking to see if the given prefix is contained within.

Parameters:prefix – The prefix to use to check, i.e. “192.168.0.0/16”
Returns:list of tuples of prefixes and values, i.e. [(“192.168.0.0/16”, 2856), …]
Return type:List[Tuple[str, Any]]
class cidr_trie.PatriciaTrie

Bases: object

A Patricia trie that stores IP addresses and data.

root

The root element of the trie. Always exists as 0.0.0.0.

Type:PatriciaNode
v6

Whether this trie stores IPv6 addresses or not.

Type:bool
size

The number of nodes in this trie, not counting the root node.

Type:int

A Patricia trie can be created, inserted to, and searched like this

trie = PatriciaTrie()
trie.insert("0.0.0.0/0", "Internet")
trie.insert("32.0.0.0/9", "RIR-A")
trie.insert("32.128.0.0/9", "RIR-B")
trie.insert("32.32.0.0/16", "another")
trie.insert("32.32.32.0/24", "third")
trie.insert("32.32.32.32/32", "you")
trie.insert("192.168.0.1/32", "totally different")
trie.insert("33.0.0.0/8", "RIR3")
trie.insert("64.0.0.0/8", "RIR2")

# find all node values on the way down
print(trie.find_all("32.32.32.32"))
check_value_exists(prefix: str) -> (<class 'bool'>, <class 'bool'>)

Check to see if a value exists in the trie already. Returns 2 bools, the first to indicate whether the IP existed in the trie, and the second to indicate whether the mask existed on that IP.

There can only be one of any IP stored in the trie, if you stored 2 prefixes, “192.168.0.0/16”, and “192.168.0.0/24”, the data would be stored on the same node, as the IP address “192.168.0.0” is the same. Even though these refer to 2 separate networks.

This method exists so you can check to see if this will happen. The first boolean returned indicates if an IP address is already present, for example in the case above, if called after inserting “192.168.0.0/16”, this method would return True in the first boolean for a prefix of “192.168.0.0/24” and other netmasks, and False for the second boolean. The second boolean is for checking if the mask is present – if called after inserting “192.168.0.0/16” with a prefix of “192.168.0.0/16” it would return True for both booleans.

Parameters:prefix – The prefix to find in the trie, i.e. “192.168.0.0/16”
Returns:A 2-tuple of bools indicating whether the IP existed and the mask existed, respectively.
Return type:(bool, bool)
Raises:ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.
find(prefix: str) → cidr_trie.PatriciaNode

Find a value in the trie.

Parameters:prefix – The prefix to find in the trie, i.e. “192.168.0.0/16”
Returns:The node if found, None otherwise.
Return type:PatriciaNode
Raises:ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.
find_all(prefix: str, children: bool = False) → List[Tuple[str, Any]]

Find all values for this prefix, traversing the trie at all levels.

With get all values from common prefixes of ‘prefix’, then traverse all children of ‘prefix’ to get their values too.

Parameters:
  • prefix – The prefix to find in the trie.
  • children – Whether to find all child values of the exact node found. (Defaults to False, as this isn’t performant in large tries)
Returns:

list of tuples of prefixes and values, i.e. [(“192.168.0.0/16”, 2856), …]

Return type:

List[Tuple[str, Any]]

Raises:

ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.

insert(prefix: str, data: Any) → cidr_trie.PatriciaNode

Insert an IP and data into the trie.

If the IP was already in the trie it will overwrite the value.

trie = PatriciaTrie()
trie.insert("192.168.0.0/16", 1234)
Parameters:
  • prefix – The prefix to insert, i.e. “192.168.0.0/16”
  • data – The value to associate with the IP and netmask.
Returns:

The node that was inserted in the trie.

Return type:

PatriciaNode

Raises:

ValueError – When trying to store an IPv4 address in a trie currently storing IPv6 addresses, and vice-versa.

traverse(prefix: str) → cidr_trie.PatriciaNode

Traverse the entire trie (from root) using a prefix.

Parameters:prefix – The prefix to find in the trie, i.e. “192.168.0.0/16”
Yields:PatriciaNode – The next node traversed when searching for ‘prefix’.
Raises:ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.
traverse_from_node(node: cidr_trie.PatriciaNode, prefix: str) → cidr_trie.PatriciaNode

Traverse the trie from a specific node using a prefix.

Parameters:
  • node – The node to start traversing from.
  • prefix – The prefix to find in the trie, i.e. “192.168.0.0/16”
Yields:

PatriciaNode – The next node traversed when searching for ‘prefix’.

Raises:

ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.

traverse_inorder() → cidr_trie.PatriciaNode

Perform an inorder traversal of the trie from the root node.

Yields:PatriciaNode – The next node in the traversal.
Raises:ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.
traverse_inorder_from_node(node: cidr_trie.PatriciaNode) → cidr_trie.PatriciaNode

Perform an inorder traversal of the trie from a given node.

Parameters:node – The node to traverse from.
Yields:PatriciaNode – The next node in the traversal.
Raises:ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.
traverse_preorder() → cidr_trie.PatriciaNode

Perform a preorder traversal of the trie from the root node.

Yields:PatriciaNode – The next node in the traversal.
Raises:ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.
traverse_preorder_from_node(node: cidr_trie.PatriciaNode) → cidr_trie.PatriciaNode

Perform a preorder traversal of the trie from a given node.

Parameters:node – The node to traverse from.
Yields:PatriciaNode – The next node in the traversal.
Raises:ValueError – When trying to find an IPv4 address in a v6 trie and vice-versa.
validate_ip_type_for_trie(ip: str) → None

Make sure this IP is valid for this trie.

Raises:ValueError – if trying to insert a v4 address into a v6 trie and vice-versa.