Next: , Previous: , Up: Referable Objects   [Index]


4.2.7.4 Detecting Cycles

Whenever a reference to an object referring objects and being referred itself is removed, sets of objects referring one another and not being referred from outside the set may form. Such sets, here referred as cycles, need detected and the objects belonging to them destroyed.

The cycle detection method is simple: trace up the references until a reference being made by a 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 had been found, and the cycle needs to be dismantled.

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 libaime type system objects maintain lists of objects holding references to themselves.

Determing whether an object is variable referred is trivial: the objects observing the libaime type system maintain a reference count and a list of references to themselves 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 variables.

To prevent the cycle detection algorithm from cycling itself endlessly it is required to track the already examined references. The libaime type system tracking method is flagging: it sets a flag for visited references to know not to examine them again. Flagging requires some space reserved with each flagged item. This space is reserved with the object in the libaime type system. Such, each object reserves storage space for flagging purposes.

The set up flags need to be removed once the cycle detection algorithm completes - at least when no cycles were detected they need. This requirement brings about the nature of the libaime type system flags: pointer data. The flags are pointers, set to NULL when indicating a not previously visited object, the previously visited object when one exists. When resetting the flags, the linked list of flags is traversed and reset.

See Reference Tracking Mechanics.


Next: , Previous: , Up: Referable Objects   [Index]