9.4 Example: Matrices
This section presents another complex example of dynamic memory, which includes tasks to create and destroy metrics. In Section 8.5, an example program shows the creation and use of a fixed-size (3 × 3) matrix, and the matrices created in the following example may be used similarly. The advantage of dynamic memory allocation is that the matrix sizes need not be known in advanced, and can be specified at run time.
The first function allocates memory for a matrix with m rows and n columns. It is created as an array of m pointers, where each pointer points to a row of n elements.
1 double **create matrix(int m, int n)
2 /* Dynamically allocate an (m x n) matrix. Returns a pointer to the beginning 3 * of the matrix. This function does not check for memory-allocation errors. */
4 {
5double **p;
6 int i;
7
8 p = (double **)malloc(m * sizeof (double *));
9 for (i = 0; i < m; ++i)
10 p[i] = (double *)malloc(n * sizeof (double));
11 return p;
12 }
The function return value is a pointer-to-a-pointer, so that the matrix elements may be accessed using multi-dimensional array notation as follows.
double **matrix = create_matrix(2,3);
matrix[0][2] = 5.4;
Notice that pointers referring to dynamically allocated memory may be safely returned by a function, as the memory continues to be valid until explicitly destroyed.
The above function will operate correctly unless malloc() returns NULL. Careless function design like this is an all-to-common programming practice and, if malloc() is unable to satisfy the request for more memory, the program will crash. A function that performs appropriate error checking, and returns NULL if malloc() fails, is shown below.
1 double **create matrix(int m, int n)
2 /* Dynamically allocate an (m x n) matrix. Returns a pointer to the 3 * beginning of the matrix, and NULL if allocation fails. */
4 {
5double **p;
6 int i;
7 assert(m>0 && n>0);
8
9/* Allocate pointer array. */
10 p = (double **)malloc(m * sizeof (double *));
11 if (p == NULL) return p;
12
13 /* Allocate rows. */
14 for (i = 0; i < m; ++i) {
15 p[i] = (double *)malloc(n * sizeof (double));
16 if (p[i] == NULL)
17 goto failed;
18 }
19 return p;
20
21 /* Allocation failed, delete already allocated memory. */
22 failed:
23 for (−−i; i >= 0; −−i)
24 free(p[i]);
25 free(p);
26 return NULL;
27 }
7 The assert() checks for logical errors in the program. Specifically, that the calling function does not request matrices of zero or negative size.
10–11 The first memory allocation is the the array of m pointers. If this fails, there is nothing left to do, and the program simply returns NULL.
14–19 The next set of allocations are for each row of the matrix. If any one of these allocations fails, the previous successful allocations must be released before the function returns so as to prevent memory leaks. In the event of an error, the program jumps out of the allocation loop to the error-handling code. This jump demonstrates another legitimate use of goto, which permits simpler code than would be possible without it.
22–26 The error-handling code first loops through each successfully allocated matrix row and frees them. It then frees the array of pointers. It is critical that deallocation is performed in this order as the row pointers would be invalid if the pointer array was freed first.
The next function is a companion to create_matrix(), which performs appropriate deallocation operations to release the memory representing a matrix object. This function takes as arguments a pointer-to-a-pointer reference to the matrix, and the matrix dimensions m and n. It is important that the same dimensions are passed for the matrix destruction as for its creation, otherwise it will not be released correctly.
1 void destroy matrix(double **p, int m, int n)
2 /* Destroy an (m x n) matrix. Notice, the n variable
3 * is not used, it is just there to assist using the function. */
4 {
5 int i;
6 assert(m>0 && n>0);
7
8 for (i = 0; i < m; ++i)
9 free(p[i]);
10 free(p);
11 }
Notice that the argument n is not actually required by the function, and is part of the interface only to match the interface of create_matrix()—to make the function more intuitive to use. If the incorrect value for m were passed to destroy_matrix() the result would be either memory-leaks (m too small) or memory corruption (m too large).
A neat alternative implementation of create_matrix() and destroy_matrix() is shown below, which is both simpler and less error-prone than the previous solutions. These functions illustrate that there are many ways to solve a problem, and often one approach is significantly better than another.
1 double **create matrix(int m, int n)
2 /* Dynamically allocate an (m x n) matrix. Returns a pointer to the 3 * beginning of the matrix, and NULL if allocation fails. */
4 {
5double **p, *q;
6 int i;
7 assert(m>0 && n>0);
8
9/* Allocate pointer array. */
10 p = (double **)malloc(m * sizeof (double *));
11 if (p == NULL) return p;
12
13 /* Allocate entire matrix as a single 1-D array. */
14 q = (double *)malloc(m * n * sizeof (double));
15 if (q == NULL) {
16 free(p);
17 return NULL;
18 }
19
20 /* Assign pointers into appropriate parts of matrix. */
21 for (i = 0; i < m; ++i, q += n)
22 p[i] = q;
23
24 return p;
25 }
1–11 This code is virtually identical to the previous version of create_matrix().
14-18 Instead of assigning each row separately, the memory for the entire matrix has been allocated as a block. If this allocation fails, then it is a simple matter for free P and returns the tap. This implementation completely bypasses the goto and its more complex error-handling code.
21–22 Having allocated memory, the remaining operations cannot fail, and so do not require error check-ing. The pointers in the pointer array are assigned to elements in the double array at n element intervals—thus, defining the matrix.
The destroy_matrix() code is also greatly simplified by allocating the matrix elements as a single block. First, the size of the matrix is not required, removing the possibility of passing incorrect dimension values. And, second, the deallocation operations are performed in two lines. Note, these lines must occur in the right order as p[0] is invalid if p is freed first.
1 void destroy matrix(double **p)
2 /* Destroy a matrix. Notice, due to the method by which this matrix 3 * was created, the size of the matrix is not required. */
4 {
5 free(p[0]);
6 free(p);
7 }
Given the final versions of the matrix create and destroy functions, a matrix might be used as follows.
double **m1, **m2;
m1 = create_matrix(2,3);
m2 = create_matrix(3,2);
/* Initialise the matrix elements. */
/* Perform various matrix operations. */
destroy_matrix(m1);
destroy_matrix(m2);
No comments:
Post a Comment