Sunday, October 11, 2009

Representation of Linear Arrays in Memory (Dope Vector Method)

To implement array data structure, memory bytes must be reserved and the accessing functions must be coded. In case of linear arrays, the declaration statements tell how many cells are needed to store the array. The following characteristics of the array are used to calculate the number of cells needed and to find the location or address of any element of the array.

1. The upper bound (UB) of the index range.

2. The lower bound (LB) of the index range. In C/C++, LB is zero.

3. The location in memory of the first byte in the array, called base address of the array (Base)

4. The number of memory bytes needed for each cell containing one data element in the array (size, denoted by W)

By cell we mean a unit of memory bytes that will be assigned to hold a value of respective data element.

During the compilation of the program, the information about characteristics of the array is stored in a table called DOPE VECTOR. When compiler comes across references to an array element, it uses this information that will calculate the element’s location in memory at runtime.