Back to results
US 11,308,171 B2Granted
Apparatus and method for searching linked lists
AssigneeSilicon Motion, Inc.
InventorsShen-Ting Chiu, Lien-Yu Lee
Life of this patent
Estimating the term…
Abstract
The invention introduces an apparatus for searching linked lists at least including: a memory arranged to operably store a linked list; a linked-list search engine arranged to operably search content of the linked list until a search success or fail and generate a search result; and a processing unit arranged to operably write the content of the linked list into the memory, drive the linked-list search engine to start a search on the linked list and obtain the search result from the linked-list search engine.
Claims16
An apparatus for searching linked lists, comprising:
- a memory arranged to operably store a linked list;
- a linked-list search engine coupled to the memory and arranged to operably search content of the linked list until a search success or fail and generate a search result;
- and
- a processing unit coupled to the memory and the linked-list search engine and arranged to operably write the content of the linked list into the memory, drive the linked-list search engine to start a search on the linked list and obtain the search result from the linked-list search engine for completing logical-to-physical location conversion,
- wherein the linked list comprises a plurality of nodes, each node comprises a forward-node or backward-node address, comparison data and a corresponding result, the comparison data comprises a first host page number associated with a plurality of successive first logical block addresses (LBAs), the corresponding result comprises a physical location in a storage mapping table, which corresponds to the first host page number, and the storage mapping table stores information indicating which physical location that data associated with each host page is physically stored in a NAND flash memory device,
- wherein the linked-list search engine comprises:
- a first writing circuit;
- a second writing circuit;
- a configuration register, wherein the processing unit is arranged to operably set the configuration register to store a memory address of a start node of the linked list, and a search value, wherein the search value comprises a second host page number associated with a plurality of successive second LBAs;
- a first reading circuit coupled to the configuration register and the first writing circuit, and arranged to operably read the nodes of the linked list according to content of the configuration register, and drive the first writing circuit to store information about a search fail when the second host page number in the configuration register is not found in the linked list, thereby enabling the processing unit to obtain the search fail information;
- and
- a comparator coupled to the configuration register, the first reading circuit and the second writing circuit, and arranged to operably drive the second writing circuit to store a corresponding result of a matched node, and information about a search success when the second host page number in the configuration register is the same as the first host page number in one node, wherein the corresponding result of the matched node comprises a physical location in the storage mapping table, which corresponds to the second host page number, thereby enabling the processing unit to obtain the start address and the corresponding result of the matched node, and the search success information.
9 more elements
A method for searching linked lists, performed by a linked-list search engine comprising a first writing circuit, a second writing circuit, a configuration register, a first reading circuit, and a comparator, the method, comprising:
- obtaining, by the first reading circuit, a memory address of a start node of a linked list, and a search value from the configuration register set by a processing unit, wherein the linked list comprises a plurality of nodes and each node comprises a forward-node or backward-node address, comparison data and a corresponding result, the comparison data comprises a first host page number associated with a plurality of successive first logical block addresses (LBAs), the corresponding result comprises a physical location in a storage mapping table, which corresponds to the first host page number, the storage mapping table stores information indicating which physical location that data associated with each host page is physically stored in a NAND flash memory device, and the search value comprises a second host page number associated with a plurality of successive second LBAs;
- repeatedly executing, by the comparator, a loop for driving the first reading circuit to obtain and process a plurality of nodes of the linked list from the start node sequentially until a search success or fail;
- driving, by the comparator, the second writing circuit to store a search result and information about a search success when the second host page number in the configuration register is the same as the first host page number in one node, wherein the search result comprises a physical location in a matched node, which corresponds to the second host page number, thereby enabling the processing unit to obtain the search result and the search success information;
- and
- driving, by the comparator, the first writing circuit to store information about a search fail when the second host page number in the configuration register is not found in the linked list, thereby enabling the processing unit to obtain the search fail information.
2 more elements
Dependencies are inferred from the claim text.