Method and apparatus for performing a radix search by selecting one of a valid table and a transition table

1. A method for performing a radix search of a data structure stored in a computer readable medium of a computer device, wherein the data structure comprises a plurality of data structure entries grouped into a plurality of related portions, and wherein the radix search includes the step of serially accessing each one of the plurality of related portions of the data structure to obtain a radix search result, wherein the method includes the steps of:

selecting a reference table based on a value of a selectable parameter in a data structure entry, the reference table containing a set of data bits;

receiving base address and a key comprised of a plurality of sets of bits;

indexing the reference table using one of the sets of bits in the key to obtain a reference table entry, wherein at least a subset of bits of the reference table entry is processed as either transition bits or valid bits in accordance with the selectable parameter of an associated data structure entry to provide a processed reference table entry; and

serially indexing the data structure using one of either the base address or a combined address to determine a result index, wherein the combined address is comprised of an address provided in a result of a previous index of the data structure and the processed reference table entry.

2. The method of claim 1 , wherein the data structure is arranged as a search tree.

3. The method of claim 2 , wherein the reference table comprises at least one entry in a memory.

4. The method of claim 2 , wherein the selectable parameter comprises a selectable bit.

5. The method of claim 2 , wherein determining the result index comprises computing an offset value to a pointer field.

6. The method of claim 5 , wherein computing the offset value comprises computing a sum of data bits having a user specified state in the subset of data bits in the reference table.

7. The method of claim 6 , wherein the subset of data bits in the reference table is based on a data bit position of an index to the reference table.

8. The method of claim 5 , wherein the pointer field comprises an address of an entry of a memory.

9. The method of claim 2 , wherein the data structure portion accessed by the result index comprises a data structure entry including at least one of a continue parameter, a selectable parameter, and a pointer field, the continue parameter indicating whether the result is a final result of the radix search.

10. The method of claim 2 , wherein the radix search tree lookup comprises radix 4 search tee lookup.

11. An apparatus for performing a radix search of a data structure stored in a memory, comprising:

a key comprising a plurality of sets of bits, each set of bits associated with one search in a sequence of searches of the radix search;

a memory device configured to store a data structure and a reference table, the data structure comprising a plurality of data structure entries grouped as a plurality of related portions including a result portion, the reference table including

a plurality of reference table entries each comprising a set of data bits, the reference table entries being processed as transition bits or valid bits according to a value of a selectable parameter of an associated data structure entry,

a processor coupled to the memory, the processor configured to perform the radix search to obtain a result index to a result of the radix search, each search in the sequence being performed using one of a base address or a combined address, the combined address including an address provided in a result of a previous search and a processed reference table entry.

12. The apparatus of claim 11 , wherein the plurality of portions of the data structure are arranged in a search tree format.

13. The apparatus of claim 12 , wherein the reference table comprises at least one entry in the memory device.

14. The apparatus of claim 12 , wherein the selectable parameter comprises a selectable bit.

15. The apparatus of claim 12 , wherein the determination of the result index includes computing an offset value to a pointer field.

16. The apparatus of claim 15 , wherein the computation of the offset value includes computing a sum of data bits having a user specified state in the subset of data bits in the reference table.

17. The apparatus of claim 16 , wherein the subset of data bits in the reference table is based on a data bit position of an index to the reference table.

18. The apparatus of claim 15 , wherein the pointer field comprises an address of an entry of the memory device.

19. The apparatus of claim 12 , wherein the data structure entry also includes at least one of a continue parameter and a pointer field, the continue parameter indicating whether the data structure entry includes the result of the radix search.

20. The apparatus of claim 12 , wherein the radix search is a radix 4 search.

21. A computer-readable medium encoded with a program for a computer for execution on a computer processing system, the program code for performing a radix search of a data structure comprised of a plurality of data structure entries grouped into a plurality of related portions, wherein the program code includes:

program code operable to select a reference table based on a value of a selectable parameters in a data structure entry, the reference table containing a set of data bits;

program code operable to retrieve a base address and a key comprised of plurality of sets of bits;

program code operable to index the reference table using one of the sets of bits in the key to obtain a reference table entry, wherein at least a subset of bits of the reference table entry is processed as either transition bits or valid bits in accordance with the selectable parameter of an associated entry in the data structure to provide a processed reference table entry; and

program code operable to serially index the data structure using one of either the base address or a combined address to determine a result index, wherein the combined address is comprised of an address provided in a result of a previous index of the data structure and the processed reference table entry.

22. The computer-readable medium of claim 21 , wherein the data structure is arranged as a search tree.

23. The computer-readable medium of claim 22 , wherein the reference table comprises at least one entry in a memory.

24. The computer-readable medium of claim 22 , wherein the selectable parameter comprises a selectable bit.

25. The computer-readable medium of claim 22 , wherein determining the result index comprises computing an offset value to a pointer field.

26. The computer-readable medium of claim 25 , wherein computing the offset value comprises computing a sum of data bits having a user specified state in the subset of data bits in the reference table entry.

27. The computer-readable medium of claim 26 , wherein the subset of data bits in the reference table is based on a data bit position of an index to the reference table.

28. The computer-readable medium of claim 25 , wherein the pointer field comprises an address of an entry of a memory.

29. The computer-readable medium of claim 22 , wherein the data structure entry also includes at least one of a continue parameter and a pointer field, the continue parameter indicating whether the data structure entry comprises the result of the radix search.

30. The computer-readable medium of claim 22 , wherein the radix search comprises a radix 4 search.