Challenge Problem and My Answer

Question 2b on exam 1 asked for a scheme that could detect if a list contained a ListElement that had been deleted. However, once deleted, the space for a ListElement could later be reallocated to a new ListElement.

The challenge is:

Invent a scheme which reliably detects the presence of a reallocated OR deleted ListElement on ANY list. Furthermore, the scheme should use a minimum of extra memory, and a minimum of extra time.

Note: "reallocated" here means a ListElement that has been reallocated since being added to the list.

I apologize that the wording of this question can be misinterpreted. The idea is that a test routine should be able to detect a “corrupted” list reliably. A list is “corrupted” when one or more of its elements has been deleted, or replaced by re-allocation while the element is still “on” the list. It is legitimate, and doesn’t corrupt a list, to re-use a memory area once occupied by a ListElement for any other purpose, so long as old pointers to that memory area are not present.

Solutions:

The key to these solutions is to accompany each POINTER to a list element with additional information that indicates the “age” of the pointer, counting age by the number of times the memory area it points to has been re-allocated. (Age can also be measured in other ways.)

One method: Add a field to each ListElement called “tag”, which is assigned the index of a free slot in table “Elements”. Elements is a global table, used for ListElements in all lists. The i-th entry in Elements is a struct, including fields “ptr” and “age”. Each time a table slot is re-used, its “age” field is incremented by 1. Its “ptr” field is NULL, or points to a ListElement that is in use. When a new ListElement is constructed, the constructor finds a free slot in “Elements”, and sets its tag field to the index of this slot; the ~ListElement() should increment the age field of Element[tag]. The list insertion routines must be modified, to obtain and keep track of the “age” from Element, and the age of the “next” pointer of the ListElement needs to be stored in a separate field in that ListElement. A (pointer, age) pair is legal, if:

(a) pointer->tag is a legal index into Element, and

(b) Element[pointer->tag].ptr==pointer, and

(c) Element[pointer->tag].age==age.

A variant on this scheme is to replace pointers in the list structure with (index, age) pairs, where Element[index].ptr is the address of the ListElement (index,age) intends to point to. This allows the test for legitimacy to be simplified, since the value of “index” is always legal. The “tag” field in each ListElement can also be eliminated, although doing this requires that the destructor be passed the index value, rather than a pointer to the ListElement.

In both schemes, if Element[] becomes full, the whole table can be copied into a larger region of memory, so the scheme can be scaled to accommodate large numbers of ListElements in use at once.