Block-offset table employing gaps in value set

A computer system that includes memory and comprises:

• A) processor circuitry operable to execute processor instructions;
• B) memory circuitry, to which the processor circuitry is responsive, that contains processor instructions readable by the processor circuitry to configure the computer system as a garbage collector that:
• i) treats at least a portion of a heap in the memory as divided into cards;
• ii) associates respective locator entries with the cards;
• iii) maintains the locator entries by assigning thereto respective values selected from a set of possible locator values with which respective locator-value interpretations are associated, the locator-value interpretation only of each locator value vi in an entry-offset subset {v1, v2, . . . , vN} of the possible locator values being that the location of a block containing the start of the card associated with a given locator entry having that locator value vi can be determined from the locator entry associated with the card located a number D(vi) cards to the left of the card associated with the given entry, the locator-value interpretations of the values v1 through vN in the entry-offset subset being such that D(v1)≦D(v2)≦. . . ≦D(vN) and that there are at least N2 integers d greater than D(vi) but less than D(vN) for which there is no locator value vi in the entry-offset subset such that D(vi)=d;
• and
• C) uses the locator entries to find block locations in accordance with those interpretations.

A storage medium containing instructions readable by a computer that includes memory to configure the computer to operate as a garbage collector that:

• A) treats at least a portion of a heap in the memory as divided into cards;
• B) associates respective locator entries with the cards;
• C) maintains the locator entries by assigning thereto respective values selected from a set of possible locator values with which respective locator-value interpretations are associated, the locator-value interpretation only of each locator value vi in an entry-offset subset {v1, v2, . . . , vN} of the possible locator values being that the location of a block containing the start of the card associated with a given locator entry having that locator value vi can be determined from the locator entry associated with the card located a number D(vi) cards to the left of the card associated with the given entry, the locator-value interpretations of the values v1 through vN in the entry-offset subset being such that D(v1)≦D(v2)≦. . . ≦D(vN) and that there are at least N2 integers d greater than D(v1) but less than D(vN) for which there is no locator value vi in the entry-offset subset such that D(vi)=d;
• and
• D) uses the locator entries to find block locations in accordance with those interpretation.

An electromagnetic signal representing sequences of instructions that, when executed by a computer system that includes memory:

• A) treats at least a portion of a heap in the memory as divided into cards;
• B) associates respective locator entries with the cards;
• C) maintains the locator entries by assigning thereto respective values selected from a set of possible locator values with which respective locator-value interpretations are associated, the locator-value interpretation only of each locator value vi in an entry-offset subset {v1, v2, . . . , vN} of the possible locator values being that the location of a block containing the start of the card associated with a given locator entry having that locator value vi can be determined from the locator entry associated with the card located a number D(vi) cards to the left of the card associated with the given entry, the locator-value interpretations of the values v1 through vN in the entry-offset subset being such that D(v1)≦D(v2)≦. . . ≦D(vN) and that there are at least N2 integers d greater than D(v1) but less than D(vN) for which there is no locator value vi in the entry-offset subset such that D(vi)=d;
• and
• D) uses the locator entries to find block locations in accordance with those interpretations.

A garbage collector comprising:

• A) means for treating at least a portion of a heap in a computer system's memory as divided into cards;
• B) means for associating respective locator entries with the cards;
• C) means for maintaining the locator entries by assigning thereto respective values selected from a set of possible locator values with which respective locator-value interpretations are associated, the locator-value interpretation only of each locator value vi in an entry-offset subset {v1, v2, . . . , vN} of the possible locator values being that the location of a block containing the start of the card associated with a given locator entry having that locator value vi can be determined from the locator entry associated with the card located a number D(vi) cards to the left of the card associated with the given entry, the locator-value interpretations of the values v1 through vN in the entry-offset subset being such that D(v1)≦D(v2)≦. . . ≦D(vN) and that there are at least N2 integers d greater than D(v1) but less than D(vN) for which there is no locator value vi in the entry-offset subset such that D(vi)=d;
• and
• D) means for using the locator entries to find block locations in accordance with those interpretations.