Java Reference
In-Depth Information
where AT is treated as a row-major array with the same address as A,butwith
interchanged row and column sizes (A[n][m] becomes AT[m][n]).
As an example, refer to Figure 12.14. The array on the left represents a
5-by-2 array of integers. In column-major order, the array's elements appear
in the order 1 to 10. Similarly, the array on the right represents a 2-by-5 array
of integers; in row-major order, the array's elements appear in the order 1
to 10. It is easy to see that a value in position [i][j] in the left array always
corresponds to the value at [j][i] in the right (transposed) array.
The most flexible storage allocation mechanism is
heap allocation
. Any num-
ber of data objects can be allocated and freed at any time and in any order. A
storage pool, usually called a
heap
, is used. Heap allocation is enormously
popular. It is di
cult to imagine a non-trivial Java or C program that does not
use new or malloc.
Heap allocation and deallocation is far more complicated than is the case
for static or stack allocation. Complex mechanisms may be needed to satisfy
a request for space. Indeed, in some cases all of the heap (tens or hundreds
of megabytes) may need to be examined.
It takes great care to make heap
management fast and e
cient.
A request for heap spacemay be
explicit
or
implicit
. An explicit request involves
a call to a routine like new or malloc, with a request for a specific number of
bytes. An explicit pointer or reference to the newly allocated space is returned
(or a null pointer if the request could not be honored).
Some languages allow the creation of data objects of unknown size, which
may involve an implicit heap allocation. Assume that in C
, as in Java,
the + operator is overloaded to represent string concatenation. That is, the
expression Str1 + Str2 creates a new string representing the concatenation
of strings Str1 and Str2. There is no compile-time bound on the sizes of Str1
and Str2, so heap space must be allocated to hold the newly created string.
Whether allocation is explicit or implicit, a
heap allocator
is needed. This
routine takes a size parameter and examines unused heap space to find free
space that satisfies the request. A
heapblock
is returned. This blockwill be big
enough to satisfy the space request, but it may well be bigger. Allocated heap
blocks are almost always single- or double-word aligned to avoid alignment
problems in heap-allocated arrays or class instances. Heap blocks contain
a header field (usually a word) that contains the size of the block as well
++
