The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 09, 2010
Filed:
Jun. 24, 2005
Clark Edward Lubbers, Colorado Springs, CO (US);
Robert Michael Lester, Colorado Springs, CO (US);
Clark Edward Lubbers, Colorado Springs, CO (US);
Robert Michael Lester, Colorado Springs, CO (US);
Seagate Technology LLC, Scotts Valley, CA (US);
Abstract
Apparatus and method for efficiently arranging and searching data in a memory space, such as a cache memory of a data storage array controller. A data structure comprises a skip list of nodes having an array of forward pointers. Each node has a node level derived from an index at which the node is stored in a table in the memory space. The total available number of nodes is preferably selected to be less than half of the largest power of 2 that can be expressed by a number of bits of the index, and the nodes are preferably stored at only even or only odd indices of the table. In such case, a free list of nodes is preferably generated from an array of pairs of counts and indices to identify the available nodes. Additional table structures can further be provided to enhance data arrangement and searching functions.