Patent ID: 7360043
Filing Date: 2008-04-15
Classification: G06F

Abstract:
1. A method for managing a least-recently-used (LRU) list, wherein the LRU list can be represented as a sequence of data records, wherein the position of a data record in the sequence is its rank, wherein the data record includes an index field which is used to determine the data record's rank, comprising: initializing the sequence of data records, which involves stepping through the LRU list from the beginning and setting each data record's index field to the rank of the data record; receiving an indication that a data record was accessed; moving the accessed data record to the beginning of the LRU list; appending the value of the accessed data record's index field to a change list, wherein the change list is a list of only the index fields of data records which have been accessed and which have moved to the beginning of the list since initialization; setting the accessed data record's index field to zero; wherein the accessed data record's index field and the change list can be used to efficiently compute the rank of any data record in the LRU list; and wherein the ability to efficiently compute the rank of any data record in the LRU list reduces the frequency with which computationally-expensive initialization operations must be executed.