Next: Reference Tracking Mechanics, Previous: How References Are Tracked, Up: Referable Objects
Whenever some reference to some object referring other objects and being referred itself by other objects is removed sets of objects referring one another and not being referred from outside set may form. Such sets, here referred as cycles, need detected and removed (freed, dismantled, that is).
Cycle detection is simple: trace up the references until some reference being made by some variable is met or until there are no more references to trace. In the first case, no cycle had formed, hence no cycle needs dismantling, hence no action is required. In the second case, some cycle has been found, and cycle needs dismantling. There are three fairly trivial tricks here: determining whether some object is referred by some variable, tracking the already examined references (so that the cycle detection algorithm does not cycle itself endlessly) and dismantly the detected cycle.
Up tracing is the references tracing method that follows the references to data hold by other objects (the down tracing would be tracing references hold by data to other objects). The libx1f4i0 type system objects maintain lists of objects holding references to themselves.
How to detect whether some object is variable referred? The objects observing the libx1f4i0 type system maintain a reference count and a list of references to data hold by other objects. The difference of the reference count and the list size is the number of references to data hold by variables (may be zero, one, or more). If the difference is not zero the object is referred by some variable(s).
How to track the already examined references? The libx1f4i0 type system
tracking method is flagging. Set a flag for each visited reference to know not
to examine once more. Flagging requires some space reserved for each flagged
item. This space is reserved with the object in the libx1f4i0 type
system. That is to say that each object reserves some storage space for
exactly this purpose. Also, the set up flags must be removed once the cycle
detection algorithm completes. Which requirement brings about the nature of
the libx1f4i0 type system flags: pointer data. The flags are pointers,
set to NULL when indicating a not visited object, the previously visited
object when indicating a visited object. When resetting flags, the linked list
of flags is traversed and reset.
How to dismantle some detected cycle? There is no method required by the libx1f4i0 type system. Any method will do. A simple one would be just freeing the object with which all started: the object for which some reference removal triggered the cycle detection. Only, care must be taken when doing so, for if the references hold by the object are removed before the object itself some more cycle detection may be triggered by this late reference removal. And the cycle removal will run endlessly, running cycle detection after cycle detection. Preventing that should be as straightforward as setting the associated reference count to zero or otherwise indicating that the object is not itself referred by other objects before proceeding with removal of the hold references.
The actual reference up tracing mechanics are struct x1f4_nodelink_type
centered, the data type is the hold reference description.