Method and apparatus for performing distinct types of radix searches
AssigneeNortel Networks Limited
InventorsRichard P. Modelski, Michael J. Craren, Adrian M. Kristiansen, Richard L. Angle, Geoff B. Ladwig
Life of this patent
Estimating the term…
Abstract
A method performs a radix search data structure. The method receives a key containing a set of data bits. The method determines a reference index based on a first subset of data bits in the key. The method indexes a reference table based on the reference index to locate a reference field. The method determines a result index based on a second subset of data bits in the key and the reference field. The method then indexes a result table based on the result index to locate a result of a radix search data structure.
Claims33
A method for performing a radix search of a data structure, the data structure storing a plurality of filter values, comprising:
- receiving a key containing a set of data bits;
- determining a reference index for the data structure based on a first subset of data bits in the key, wherein the reference index is based on a pointer field for a radix 4 search tree lookup;
- indexing a reference table based on the reference index to locate a reference field;
- determining a result index based on a second subset of data bits in the key and the reference field;
- and
- indexing a result table based on the result index to locate a filter value associated with the key, the filter value indicative of a set of filter operations associated with the key.
A method for performing a radix search of a data structure, the data structure storing a plurality of filter values comprising:
- receiving a key containing a set of data bits;
- determining a reference index for the data structure based on a first subset of data bits in the key, wherein the first subset of data bits in the key comprises 8 data bits in the key for a radix 12 search tree lookup;
- indexing a reference table based on the reference index to locate a reference field;
- determining a result index based on a second subset of data bits in the key and the reference field;
- and
- indexing a result table based on the result index to locate a filter value associated with the key, the filter value indicative of a set of filter operations associated with the key.
A method for performing a radix search of a data structure, the data structure storing a plurality of filter values, comprising:
- receiving a key containing a set of data bits;
- determining a reference index for the data structure based on a first subset of data bits in the key wherein the first subset of data bits in the key comprises 12 data bits in the key for a radix 16 search tree lookup;
- indexing a reference table based on the reference index to locate a reference field;
- determining a result index based on a second subset of data bits in the key and the reference field;
- and
- indexing a result table based on the result index to locate a filter value associated with the key, the filter value indicative of a set of filter operations associated with the key.
An apparatus for performing a radix search of a data structure, the data structure comprising a plurality of filter values, the apparatus comprising:
- a key comprised of a set of data bits,
- a reference table, coupled to the key;
- and a result table, coupled to the reference table and the key;
- and
- a processor configured
- to determine a reference index based on a first subset of data bits in the key, wherein the reference index is based on a pointer field for a radix 4 search tree lookup,
- to index the reference table based on the reference index to locate a reference field,
- to determine a result index based on a second subset of data bits in the key and the reference field, and
- to index the result table based on the result index to locate a filter value, the filter value indicative of a set of filter operations associated with the key.
An apparatus for performing a radix search of a data structure, the data structure comprising a plurality of filter values the apparatus comprising:
- a key comprised of a set of data bits,
- a reference table, coupled to the key;
- and a result table, coupled to the reference table and the key;
- and
- a processor configured
- to determine a reference index based on a first subset of data bits in the key, wherein the first subset of data bits in the key comprise 8 data bits in the key for a radix 12 search tree lookup,
- to index the reference table based on the reference index to locate a reference field,
- to determine a result index based on a second subset of data bits in the key and the reference field, and
- to index the result table based on the result index to locate a filter value, the filter value indicative of a set of filter operations associated with the key.
An apparatus for performing a radix search of a data structure, the data structure comprising a plurality of filter values, the apparatus comprising:
- a key comprised of a set of data bits,
- a reference table coupled to the key;
- and a result table, coupled to the reference table and the key;
- and
- a processor configured
- to determine a reference index based on a first subset of data bits in the key, wherein the first subset of data bits in the key comprises 12 data bits in the key for a radix 16 search tree lookup,
- to index the reference table based on the reference index to locate a reference field,
- to determine a result index based on a second subset of data bits in the key and the reference fields, and
- to index the result table based on the result index to locate a filter value, the filter value indicative of a set of filter operations associated with the key.
A computer-readable medium encoded with a program for a computer, the program performing the steps of:
- receiving a key containing a set of data bits;
- determining a reference index based on a first subset of data bits in the key, wherein the reference index is based on a pointer field for a radix 4 search tree lookup;
- indexing a reference table based on the reference index to locate a reference field;
- determining a result index based on a second subset of data bits in the key and the reference field;
- and
- indexing a result table based on the result index to locate a filter value indicative of a set of filter operations associated with the key.
A computer-readable medium encoded with a program for a computer, the program performing the steps of:
- receiving a key containing a set of data bits;
- determining a reference index based on a first subset of data bits in the key, wherein the first subset of data bits in the key comprises 8 data bits in the key for a radix 12 search tree lookup;
- indexing a reference table based on the reference index to locate a reference field;
- determine a result index based on a second subset of data bits in the key and the reference field;
- and
- indexing a result table based on the result index to locate a filter value indicative of a set of filter operations associated with the key.
A computer-readable medium encoded with a program for a computer, the program performing the steps of:
- receiving a key containing a set of data bits;
- determining a reference index based on a first subset of data bits in the key, wherein the first subset of data bits in the key comprises 12 data bits in the key for a radix 16 search tree lookup;
- indexing a reference table based on the reference index to locate a reference field;
- determining a result index based on a second subset of data bits in the key and the reference field;
- and
- indexing a result table based on the result index to locate a filter value indicative of a set of filter operations associated with the key.
Dependencies are inferred from the claim text.