Method and apparatus for performing radix lookups using valid bit tables with pointers
US6223174A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jul 1, 1998 |
| Grant date | Apr 24, 2001 |
| Priority date | — |
| Expiry date | Jul 1, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99934
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method, apparatus, and article of manufacture for performing a radix search tree lookup with a key using a valid bit table with pointers. The key is used as a valid bit index into the valid bit table. A first pointer associated with the valid bit index is then used as a pointer into a first block of entries in a result table. A sum of valid bits in the valid bit table below the valid bit index is used as a result index into the first block of entries in the result table. The result index into the first block of entries may be used to reference a result of the radix search tree lookup. Extra space is added in the result table to enable insertion of entries after the first block of entries. A second pointer is used to add redundant entries from the first block of entries into a second block of entries in the result table.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.