Methods and apparatus for maintaining sets of ranges typically using an associative memory and for using these ranges to identify a matching range based on a query point or query range and to maintain sorted elements for use such as in providing priority queue operations

摘要

Sets of ranges typically are maintained using an associative memory and may be used to identify a matching range based on a query point or query range and to maintain sorted elements for use, such as in providing priority queue operations. In one implementation, ranges are added to a set of ranges by determining a longest common prefix of a starting point and an ending point of the range, extending this longest common prefix by appending a bit to create a particular extended longest common prefix, and then storing it in the set of extended longest common prefixes. The set of extended longest common prefixes is then processed based on the query point or range to identify the matching range. Additionally, one implementation uses bands for identifying ranges, where the band is formed from the starting and ending points to the longest common matching prefix of the these points.