12.7 Towards A Dynamic Array ADT

In the discussion of static data types in section 12.4.1 it was observed that because Modula-2 arrays are static, they cannot be redimensioned at run time. In this section, the first steps are taken toward finding a way around that limitation via a user-defined dynamic array type.

Here, a one-dimensional array type is defined as a record that holds the number of items (the length of a vector) and the address of the first item. The address of subsequent items is calculated using an offset from that first address worked out from the size and position number of the element in the array.

      adr  := ADDADR (vector.first, ( pos - 1 ) * sizeOfElement); 

In this example, the array holds real values and sizeOfElement is just SIZE (REAL). Since every creation of such a one-dimensional vector could use a different length, the location must be of type ADDRESS rather than a specific pointer type. This in turn means that ALLOCATE and DEALLOCATE are employed directly in creating instances of the dynamic array, rather then indirectly through NEW and DISPOSE.

  ALLOCATE (vector.first, sizeOfElement * numElements);

This module contains only the beginning steps toward creating a proper dynamic array ADT. Operations on the type still need to be defined, error handling added, and the whole code encapsulated in a library module and tested. It could also be made more versatile (generic) by extending the record to a third field, containing the size of the elements in the array, and adding a parameter to the Create procedure specifying this value. Such a module could then be used to define dynamic arrays of any type or length. Two-dimensional versions could also be constructed. Here is the code:

MODULE DynVectorDemo;

(* This Module implements a one-dimensional dynamic array of real
    It is a demonstration of dynamic memory use
    by R. Sutcliffe
   modified 1995 05 14 *)

FROM SYSTEM  IMPORT
  ADDRESS, ADDADR;
FROM Storage IMPORT
  ALLOCATE, DEALLOCATE;
FROM STextIO IMPORT
  WriteString, WriteChar, WriteLn;
FROM SRealIO IMPORT
  WriteFixed;

CONST
  sizeOfElement = SIZE (REAL);

TYPE
  DynVector =
    RECORD
      size  : CARDINAL;       (* the size of the vector *)
      first : ADDRESS;        (* the address of the first element *)
    END;

VAR
  vector : DynVector;
  re : REAL;  (* need one of the items *)
  adr : POINTER TO REAL;  (* and a pointer to such *)
  count : CARDINAL;
  numElements : CARDINAL; (* for the demo vector *)

PROCEDURE WriteVector;
(* write out all the items in the vector *)
VAR
  count : CARDINAL;
BEGIN
   FOR count := 1 TO numElements
    DO
      WriteFixed (Fetch (count), 2, 8 );
      WriteChar (",");
    END;
  WriteLn;
END WriteVector;

PROCEDURE Create (numElements : CARDINAL );
  (* create a new dynamic array with 'length' elements *)
BEGIN
  vector.size := numElements;
  ALLOCATE (vector.first, sizeOfElement * numElements);
      (* get enough memory for this many items *)
END Create;

PROCEDURE Destroy (numElements : CARDINAL );
  (* create a new dynamic array with 'length' elements *)
BEGIN
  vector.size := 0;
  DEALLOCATE (vector.first, sizeOfElement * numElements);
      (* give back the memory *)
END Destroy;

PROCEDURE Update (pos : CARDINAL; newValue : REAL );
  (* Pre : pos >= 1 and pos <= vector.size
       Post : if so, item #pos is updated with newValue
                 if not, nothing happens, no error *)
BEGIN
  IF (pos >= 1) AND (pos <= vector.size)
    THEN  (* compute address of this index *)
      adr  := ADDADR (vector.first, ( pos - 1 ) * sizeOfElement); 
      adr^ := newValue;  (* and put the value there *)
    END; (* if *)
END Update;

PROCEDURE Fetch (pos :CARDINAL) : REAL;
  (* Pre : pos >= 1 and pos <= vector.size
       Post : if so, item #pos is returned
                 if not, returns maximum real but no error *)
VAR
  temp : REAL;
BEGIN
  IF (pos >= 1) AND (pos <= vector.size)
    THEN  (* compute address of this index *)
      adr  := ADDADR (vector.first, ( pos - 1 ) * sizeOfElement); 
      temp := adr^; (* get the value there *)
    ELSE
      temp := MAX (REAL);
    END;
  RETURN temp;
END Fetch;

BEGIN (* main part of demo *)
  numElements := 7;
  Create (numElements);

   (* load any old values into the vector *)
  re := 45.0;
  FOR count := 1 TO numElements
    DO
      Update (count, re + FLOAT (count));
    END;

  WriteVector;   (* now read them back to see if all is ok *)
  Destroy (numElements);  (* wipe it all out *)

  numElements := 5; (* and start over *)
  Create (numElements);
  Update (1, 4.5);  (* leave rest uninitialized *)
  WriteVector;   (* and see what happens *)
  Destroy (numElements);  (* erase again before quitting *)

END DynVectorDemo.

Observe that in the testing harness (the main module body here) memory was allocated to a vector of length seven, given back to the system, and then a request for memory for a smaller vector was issued. While one might expect that that a portion of the original allocation might be re-used and some of the values survive from the original use, here is the actual output when this module was run:

** Run log starts here **
   46.00,   47.00,   48.00,   49.00,   50.00,   51.00,   52.00,
    4.50,    0.00,    0.00,1049841000000.00,266780500000000000000.00,

If any of the first piece of memory was indeed used the second time, the starting point of the real numbers was evidently different. In any case, this illustrates that once memory has been deallocated and returned to the system, no assumptions whatever can be made about it afterwards. Even if the second request is for the same amount of memory, the programmer cannot know that the same piece of memory just given back will be reclaimed. No assumptions whatever can be made about the memory manager's handling of requests for dynamic memory.


Contents