Addressing Array Elements
Introduction: Array elements can be accessed quickly if they are stored in a block of consecutive locations. In C and Java, array elements are numbered 0 , 1 , . . . , n — 1, for an array with n elements. If the width of each array element is w, then the iih element of array A begins in location
base i x w (1)
where base is the relative address of the storage allocated for the array. That is, base is the relative address of ^4.
The formula (6.2) generalizes to two or more dimensions. In two dimensions, we write A[ii][i2] in C and Java for element i2 in row ii. Let w\ be the width of a row and let w2 be the width of an element in a row. The relative address of .A[zi][z2] can then be calculated by the formula
base ii x wi i2 x w2 (2)
In k dimensions, the formula is
base ii x w± i2 x w2 -I f- ik x wk (3)
where Wj, for 1 < j < k, is the generalization of Wi and w2 in (2). Alternatively, the relative address of an array reference can be calculated in terms of the numbers of elements rij along dimension j of the array and the width w = Wk of a single element of the array. In two dimensions (i.e., k = 2 and w = w2), the location for A[n][i2 ] is given by
base (h x n2 i2) x w (4)
In k dimensions, the following formula calculates the same address as (3):
base ( ( . . . (zi x n2 i2) x n3 i3) . . . x nk ik) x w (5)
More generally, array elements need not be numbered starting at 0. In a one-dimensional array, the array elements are numbered low, low 1 , . . . , high and base is the relative address of A[low}. Formula (6.2) for the address of A[i] is replaced by:
base (i — low) x w (6)
The expressions (1) and (6) can be both be rewritten as i x w c, where the subexpression c = base — low x w can be pre calculated at compile time. Note that c = base when low is 0. We assume that c is saved in the symbol table entry for A, so the relative address of A[i] is obtained by simply adding i x w to c.
Compile-time pre calculation can also be applied to address calculations for elements of multidimensional arrays; see Exercise 6.4.5. However, there is one situation where we cannot use compile-time pre calculation: when the array's size is dynamic. If we do not know the values of low and high (or their generalizations in many dimensions) at compile time, then we cannot compute constants such as c. Then, formulas like (6.7) must be evaluated as they are written, when the program executes.
The above address calculations are based on row-major layout for arrays, which is used in C and Java. A two-dimensional array is normally stored in one of two forms, either row-major (row-by-row) or column-major (column-by column). Figure 6.21 shows the layout of a 2 x 3 array A in (a) row-major form and (b) column-major form. Column-major form is used in the Fortran family of languages. We can generalize row- or column-major form to many dimensions. The generalization of row-major form is to store the elements in such a way that, as we scan down a block of storage, the rightmost subscripts appear to vary fastest, like the numbers on an odometer. Column-major form generalizes to the opposite arrangement, with the leftmost subscripts varying fastest.