What solutions are there for circular references?

Question

When using reference counting, what are possible solutions/techniques to deal with circular references?

The most well-known solution is using weak references, however many articels about the subject imply that there are other methods as well, but keep repeating the weak-referencing example. Which makes me wonder, what are these other methods?

• I am not asking what are alternatives to reference counting, rather what are solutions to circular references when using reference counting.

• This question isn't about any specific problem/implementation/language rather a general question.

Answer 1

I've looked at the problem a dozen different ways over the years, and the only solution I've found that works every time is to re-architect my solution to not use a circular reference.

Edit:

Can you expand? For example, how would you deal with a parent-child relation when the child needs to know about/access the parent? – OB OB

As I said, the only good solution is to avoid such constructs unless you are using a runtime that can deal with them safely.

That said, if you must have a tree / parent-child data structure where the child knows about the parent, you're going to have to implement your own, manually called teardown sequence (i.e. external to any destructors you might implement) that starts at the root (or at the branch you want to prune) and does a depth-first search of the tree to remove references from the leaves.

It gets complex and cumbersome, so IMO the only solution is to avoid it entirely.

Answer 2

There are couple of ways I know of for walking around this:

The first (and preferred one) is simply extracting the common code into third assembly, and make both references use that one

The second one is adding the reference as "File reference" (dll) instead of "Project reference"

Hope this helps

Answer 3

Here is a solution I've seen:

Add a method to each object to tell it to release its references to the other objects, say call it Teardown().

Then you have to know who 'owns' each object, and the owner of an object must call Teardown() on it when they're done with it.

If there is a circular reference, say A <-> B, and C owns A, then when C's Teardown() is called, it calls A's Teardown, which calls Teardown on B, B then releases its reference to A, A then releases its reference to B (destroying B), and then C releases its reference to A (destroying A).

Answer 4

I guess another method, used by garbage collectors, is "mark and sweep":

1. Set a flag in every object instance
2. Traverse the graph of every instance that's reachable, clearing that flag
3. Every remaining instance which still has the flag set is unreachable, even if some of those instances have circular references to each other.

Answer 5

For solution to circular references, see here. :-)

Answer 6

I'd like to suggest a slightly different method that occured to me, I don't know if it has any official name:

Objects by themeselves don't have a reference counter. Instead, groups of one or more objects have a single reference counter for the entire group, which defines the lifetime of all the objects in the group.

In a similiar fashion, references share groups with objects, or belong to a null group.

A reference to an object affects the reference count of the (object's) group only if it's (the reference) external to the group.

If two objects form a circular reference, they should be made a part of the same group. If two groups create a circular reference, they should be united into a single group.

Bigger groups allow more reference-freedom, but objects of the group have more potential of staying alive while not needed.