Method and apparatus for least recently used (LRU) software cache

Abstract

A data cache has a number of rows. A corresponding list of the rows is maintained, the list including a number of entries, each entry corresponding to a row and including a key uniquely identifying the row, and a count indicating an age of the row. Updating the cache involves sorting the entries by their key, searching the list for an entry having a key to a row to be updated if found or added if not found. If the entry having the key to the row to be updated is found, the entry is removed from the list, the remaining entries are sorted by their count, so that the entry at the beginning of the list is for the oldest row, and the entry at the end of the list is for the newest row, a new entry is appended at the end of the list that replaces the removed entry, the new entry having the same key as the removed entry, and a count indicating the corresponding row is the newest. The corresponding row in the data cache is then updated.

Dependencies are inferred from the claim text.