Priority search trees

摘要

A processor implements a priority search tree on data elements. A data point having two component values is stored for each data element. A comparison is performed to determine an order for two data points. When the first component values of the two data points are equal, a comparison is made using the second component values. When the second component values of the two data points are equal, a comparison is made using the first component values.

主权项

1. An apparatus arranged to implement prefix matching on a set of Internet Protocol (IP) addresses, the apparatus comprising:
a memory; and a processor comprising:
a storage unit for storing in the memory for each of said IP addresses a corresponding data point for a priority search tree, said data point having a first component value and a second component value;a tree-processing module for performing at least one function operation on the data points, the at least one function operation including using a comparison module to perform a comparison operation to determine a longest prefix of an IP address in the set based on a first data point preceding a second data point in an ordering for the data points, the comparison operation comprising one of:determining the relative positions of a first data point and a second data point based on a comparison of the respective first component values of the first and second data points and, in response to the first component value of the first data point being equal to the first component value of the second data point, determining that the second component value of the first data point is greater than the second component of the second data point; ordetermining the relative positions of a first data point and a second data point based on a comparison of the respective second component values of the first and second data points and, in response to the second component value of the first data point being equal to the second component value of the second data point, determining that the first component value of the first data point is greater than the first component value of the second data point;wherein each IP address is represented by a respective binary string of a length of at most m bits and the storage unit is arranged to store in the memory the corresponding data point having the first component value equal to the m-bit number whose binary representation has most significant bits equal to the respective binary string and remaining bits equal to 1 bits and having the second component value equal to the m-bit number whose binary representation has most significant bits equal to the respective binary string and remaining bits equal to 0 bits.