Patent ID: 7552271

Claim:
A non-volatile re-programmable memory system, comprising: an array of memory cells grouped into blocks of memory cells that are erased together prior to reprogramming data into pages of the blocks, the blocks being identified by physical block addresses, a controller operably connected with the array of memory cells and which operates in a manner comprising: receives data from outside the memory system and store the received data into one or more of the blocks, maintains a plurality of records for the plurality of blocks, the records individually including values of a plurality of descriptors of different aspects of the data stored in one of the plurality of blocks to which the record pertains as identified by the address of the block, wherein the controller operates to write values of a first descriptor in the records that are amounts of valid data in the corresponding blocks, and additionally operates to write values of a second descriptor in the records that are amounts of erased capacity in the corresponding blocks, maintains a first list that includes pointers by the addresses of the plurality of blocks, the pointers individually pointing to the location within the array of memory cells of one of the records for one of the blocks in response to receiving the address of said one block, and further wherein the pointers are placed in the list of pointers in order of the addresses of their respective plurality of blocks, maintains a second list that includes addresses of the plurality of blocks whose corresponding records contain values of at least first and second descriptors, wherein the addresses of the plurality of blocks in the second list are placed in an order of values of the first descriptor in their corresponding records, maintains a third list that includes addresses of the plurality of blocks whose corresponding records contain at least values of descriptors of at least an amount of valid data in the corresponding blocks and an amount of obsolete data in the corresponding blocks, wherein the controller further operates to place addresses of the plurality of blocks in the third list in an order of values of the amount of valid data in the corresponding blocks, and causes an operation to be performed on data stored in individual ones of the plurality of blocks in the second list in the order in which they appear in the second list.