Invention Grant
US07162481B2 Method for increasing storage capacity in a multi-bit trie-based hardware storage engine by compressing the representation of single-length prefixes
有权
通过压缩单长度前缀的表示来增加基于多比特特里硬件存储引擎中的存储容量的方法
- Patent Title: Method for increasing storage capacity in a multi-bit trie-based hardware storage engine by compressing the representation of single-length prefixes
- Patent Title (中): 通过压缩单长度前缀的表示来增加基于多比特特里硬件存储引擎中的存储容量的方法
-
Application No.: US10313854Application Date: 2002-12-06
-
Publication No.: US07162481B2Publication Date: 2007-01-09
- Inventor: Nicholas Julian Richardson , Suresh Rajgopal , Lun Bin Huang
- Applicant: Nicholas Julian Richardson , Suresh Rajgopal , Lun Bin Huang
- Applicant Address: US TX Carrollton
- Assignee: STMicroelectronics, Inc.
- Current Assignee: STMicroelectronics, Inc.
- Current Assignee Address: US TX Carrollton
- Agent Lisa K. Jorgenson; William A. Munck
- Main IPC: G06F17/00
- IPC: G06F17/00 ; G06F7/00
Abstract:
Prefixes terminating with end node entries each containing identical length prefix portions in a single child table are compressed by replacing the end node entries with one or more compressed single length (CSL) prefix entries in the child table that contain a bitmap for the prefix portions for the end node entries. A different type parent table trie node entry is created for the child table. Where the prefix portions are of non-zero length, the parent table contains a bitmap indexing the end node entries. Where the prefix portions are of length zero, the parent table may optionally contain a bitmap for the prefix portions, serving as an end node. The number of prefix portions consolidated within the CSL node entry is based upon the prefix portion length.
Public/Granted literature
Information query
