13.5.2 The Reference Counter Method

The reference counter method assumes that the first record of every sublist in use has information giving the number of pointers that point to it. This number is called the reference count of the sublist. The pointers can be stored in the name variables or in sublist fields of complex records. A "smart" header record may be used for this purpose. It is assumed here that only sublists may be shared. Each time a new pointer refers to a sublist, the reference count of the sublist must be increased by 1. Each time a pointer that refers to a sublist is changed so that it no longer points to that sublist, the reference count of the sublist must be decreased by 1. After a decrease that leaves the reference count at zero, the storage for records of the sublist may be made known. Again, a data structure traversal may be used to determine which storage elements are to be made known. No traversal algorithm has been given in this text for data structures that allow sublist sharing. Such algorithms differ from the list-structure traversal algorithm because of the possibility of looping or revisiting records. As an exercise you should modify the list-structure traversals of Chapter 6 to work for this more general case. The idea is to mark each accessed record and make sure that marked records are not revisited.

Deletion of a sublist whose reference count has become zero is similar to the traversal of successor lists for an object that has been removed from the bag in the topological sort algorithm. The sublist must be traversed and, in addition to the storage for all records being inserted on the list of available space, each sublist pointed to by a record must have its reference count decremented by 1.

Example 13.8

Associate reference counts with the first record of each of the sublists of Figure 13.6. The list-structures with associated reference counts would appear as shown in Figure 13.8. n

Suppose p1 is set to null. The reference count of its sublist would be reduced to 2. Since it has not gone to zero, no storage is available for reclamation. If p6 is then set to null, the reference count of its sublist would be reduced to 0. Its storage could be reclaimed. This would require that p3's sublist have its reference count reduced by 1. The result would be as shown in Figure 13.8(b).

A problem can occur with the reference counter method whenever loops appear, as demonstrated in the following example.

Example 13.9

Consider the loop in ls1 of Figure 13.9. What happens when p1, p2, and p3 of Figure 13.6 no longer reference the sublist? Then this sublist has no variables referencing it. It cannot be accessed, since we do not know where it is. It is serving no useful purpose, yet its storage was not reclaimed, since the reference count of records 1 and 2 never went to zero. This problem is analogous to the existence of loops in the input for a topological sort. Such unused storage, or garbage, can accumulate and clog the memory. n

It is possible to share individual records as well as sublists. In this case, garbage collection will still work, as will the reference counter method. Now, however, the individual records (not just the sublists) must have reference counters associated with them, requiring additional storage and updating overhead. Loops may cause the same problems for shared records as for shared sublists .

(a) Initial List Structures with Reference Counts

(b) Final List Structures with Reference Counts

Figure 13.8 List-structures of Figure 13.6 with Associated Reference Counts

Figure 13.9 A Lost Loop