Skip to content

Garbage collector

Jump to bottom
aaaaaa123456789 edited this page Jan 8, 2020 · 5 revisions

Garbage collector

Since there are more valid 16-bit indexes than there are available 8-bit IDs, the latter will always be in short supply. Without any way of releasing IDs that are no longer in use, the conversion table would hopelessly fill up and become useless after some time.

The garbage collector, therefore, is the component that ensures that IDs are recycled when no longer in use. As shown in the macro functions page, the garbage collector is part of the function that writes indexes to the conversion table and allocates IDs; it is executed automatically by the ID allocation routine when there are no more IDs available.

Definition and requirements

The garbage collector must be defined right after the function that writes indexes to the conversion table. While it is possible to simply write its code underneath that function's macro, declaring a symbol for the garbage collector itself (that is, giving it a function name) is strongly recommended, like so:

_ConvertSomeIndexToID:
	___conversion_table_store wSomethingTable, SOMETHING_TABLE
	; fallthrough
SomethingTableGarbageCollection:
	; garbage collector goes here

The garbage collector function must preserve de; all other registers can be freely clobbered by the function. Also, rSVBK must be set to the bank of the conversion table both on input and on output — in other words, the function will be called with the current WRAMX bank set to the conversion table's bank, and it must preserve that value.

It is permissible to far call a garbage collector; this may be done to take advantage of an idle period (such as before saving the game) in order to execute this relatively expensive operation. The calling convention for such manual calls is the same as the one described in the previous paragraph: rSVBK must be set to the conversion table's WRAMX bank, and the function will preserve that and de and clobber everything else.

Garbage collection is expected to eventually succeed. When the ID allocation routine calls the garbage collector, it expects to find at least one free ID after the call completes. If there are no free IDs, it will simply call the garbage collector again, as the free ID search loop won't find any free IDs. This loop will become endless unless and until the garbage collector frees up at least one ID. (This implies that the conversion table must be large enough to contain all IDs in use and a few extra.)

Overview

Given the requirements mentioned above and the expected behavior of the garbage collector, the high-level approach to this function is usually like so:

  1. Push de and rSVBK.
  2. Initialize the bitmap and mark locked and recent IDs as in use.
  3. Find IDs in use at several known locations and mark them in use in the bitmap.
  4. Restore rSVBK.
  5. Free up all table IDs that weren't marked in use by the previous steps.
  6. Restore de and return.

Steps 1, 4 and 6 come directly from the requirement to preserve those two values; rSVBK is restored early because the macro that frees up table IDs requires rSVBK to be set to the table's WRAM bank. The remaining steps will be described in subsequent sections, along with the helper macros that can be used to define them.

Note that the garbage collector will require a subfunction to set bits in the bitmap used to track IDs in use. (Almost all of the code for this subfunction is identical across all instances of this subfunction; the requirement for a different one for each table comes from the initial check for validity of an ID. Since this subfunction is called very often while the garbage collector runs and it is quite slow, the performance gain brought by having a separate copy for each table is worthwhile.) This subfunction will also be described in a later section.

(WIP)

Clone this wiki locally