Method and apparatus for performing radix lookups using transition bits and fields in transition tables
AssigneeNortel Networks Limited
InventorsGeoff Ladwig, Richard Angle
Life of this patent
Estimating the term…
Abstract
A method, apparatus, and article of manufacture for performing compressed radix search tree lookups using transition tables. The key is used as a transition index into the transition table. A sum of transition bits in the transition table below the transition index is used as a result index into the result table. The result index into the result table may be used to reference a result of the radix search tree lookup.
Claims21
A method for performing a radix search tree lookup on a radix search tree of a data structure stored in a computer to obtain a result, the method comprising:
- using a key as a transition index into a transition table;
- using a sum of transition bits in the transition table below the transition index as a result index into a result table;
- and
- using the result index into the result table to reference the result of the radix search tree lookup.
An apparatus for performing a radix search tree lookup on a radix search tree of a data structure stored in a digital computer to obtain a result, the apparatus comprising:
- the digital computer having an input device and a processor,
- the input device to receive a key into the digital computer;
- the processor to use the key as a transition index into a transition table;
- the processor to sum transition bits in the transition table below the transition index, the sum providing a result index into a result table;
- and
- the processor to use the result index into the result table to reference the result of the radix search tree lookup.
An article of manufacture for use in a computer system for performing a radix search tree lookup on a radix search tree of a data structure stored in a digital computer to obtain a result, the article of manufacture comprising:
- a computer usable medium having computer readable program code means embodied in the medium, the computer readable program code means to use a key as a transition index into a transition table;
- use a sum of transition bits in the transition table below the transition index as a result index into a result table;
- and use the result index into the result table to reference the result of the radix search tree lookup.
A method of efficiently searching and reducing required storage space in performing a lookup on a radix search tree of a data structure stored in a computer, the method comprising:
- providing a transition table and a result table of the radix search tree in the computer;
- accepting a key, the key a transition index into the transition table;
- computing a sum of transition bits in the transition table below the transition index of the key, the sum of transition bits a result index into a result table;
- and
- using the result index to reference a result of the lookup in the result table.
A method of performing a lookup on a table stored in a computer to obtain a result, the method comprising:
- providing a compressed radix table having one or more entries in the computer, each of the one or more entries in the compressed radix table including a transition field, a pointer field and a continue/vector bit;
- accepting a key;
- using a first subset of bits of the key as an index into the transition field to find a first entry in the compressed radix table, the first subset of bits of the key selecting a bit position in the transition field, the first entry including a first pointer in the pointer field;
- computing a first sum of lower significant bits in the transition field below the selected bit position of the first entry, the first sum of lower significant bits being an offset into the compressed radix table;
- adding the value of the first pointer and the first sum of lower significant bits together to select the next entry in the compressed radix table;
- and
- wherein if the continue/vector bit of the next entry is set to vector then the next entry has a result pointer in the pointer field, else,
- the continue/vector bit is set to continue and the next entry has a second pointer in the pointer field.
A method of performing a lookup on a table stored in a computer to obtain a result, the method comprising:
- providing a first and second transition bit tables having one or more entries in the computer, each of the one or more entries in the first and second transition bit tables including a transition bit and a pointer field;
- accepting a key;
- using a first subset of bits of the key as an index into the first transition bit table to find a first entry in the first transition bit table, the first subset of bits of the key selecting a bit position in the first transition bit table and a first pointer in the pointer field;
- computing a first sum of lower significant bits in the first transition bit table below the selected bit position of the first entry, the first sum of lower significant bits being a first offset;
- adding the value of the first pointer and the first sum of lower significant bits together to select a first result in a first result table, the first result in the first result table pointing to a beginning of the second transition bit table;
- using a second subset of bits of the key as an index into the second transition bit table to find a second entry in the second transition bit table, the second subset of bits of the key selecting a bit position in the second transition bit table and a second pointer in the pointer field;
- computing a second sum of lower significant bits in the second transition bit table below the selected bit position of the second entry, the second sum of lower significant bits being a second offset;
- and
- adding the value of the second pointer and the second sum of lower significant bits together to select a second result in a second result table.
Dependencies are inferred from the claim text.