Patent ID: 6766336
Filing Date: 2004-07-20
Classification: G06F,Y10S

Abstract:
A garbage collection apparatus that performs (1) scavenging processing for specifying unused cell blocks from among a plurality of cell blocks, some of which can be reached from a specified root cell block via one of a set of trays, tracing one or more cell blocks in a chain-like manner by referencing each of the one or more cell blocks, and others of which cannot be reached in this manner and are referred to as the unused cell blocks, each of the set of trays being specified by a second type address and holding a valid first type address, each of the plurality of cell blocks (a) being specified by a first type address and (b) including a plurality of cells that each hold one of a second type address and a numerical value, and (2) compaction processing for relocating each of the specified unused cell blocks so as to form a continuous memory area, and updating each first type address that is held in a tray and corresponds to a cell block so as to specify a cell block following relocation, the garbage collection apparatus comprising:assuming means for making an assumption as to whether a second type address is stored in a cell included in a first cell block, so as to avoid a situation in which the second type address is mistakenly assumed not to be a second type address, wherein a value used for the second type address is limited to within a specific range, and the assuming means makes an assumption that data held by the cell is a second type address only when (i) the data is within the specific range, and (ii) a tray specified by the data, when hypothetically assumed to be a second type address, holds a valid first type address; and specifying means for specifying an unused cell block using the scavenging processing by assuming that a second cell block is referenced by the first cell block, the second cell block being specified by a first type address, the first type address being held in the tray specified by the data assumed to be the second type address.