3.1 Overview

This chapter focuses on arrays and structures, which are C’s primary aggregate types. Arrays aggregate variables of the same type, whereas structures can do the same for variables of different types. Structures can be array elements, and a structure may embed arrays. Together these aggregate types make it possible for programmers to define arbitrarily rich data types (e.g., Employee, Game, Species) that meet application needs.

Pointers—address constants and variables—come into play naturally with both arrays and structures, and the code examples throughout the chapter get into the details. Among modern general-purpose languages, C (together with C++) stands out by giving the programmer so much control over—and, therefore, responsibility for—memory addresses and the items stored at these addresses. All of the chapters after this one have examples that, in one way or another, illustrate the power of pointers.

3.2 Arrays

A second example builds on the first by introducing pointer variables and showing how C supports pointer arithmetic by having data types for pointers.

3.3 Arrays and Pointer Arithmetic

A pointer is allowed to point one element beyond the end of the array, although nothing should be stored at that location. In this example, the array’s initialization now uses a while rather than a for loop, and the loop’s condition compares the two pointers, ptr and end: looping continues so long as ptr < end. At the bottom of the loop, ptr is incremented by 1—by one int, which is 4 bytes. The pointer ptr is a variable, unlike the pointer constant arr, and so can have its value changed. Eventually ptr points to the same location as does end, which makes the loop condition false.

because ptr then would take on values such as 1,2,3,…,8, which almost surely are not addresses within the program’s address space. The aim is to initialize the array element to which ptr points, not ptr itself.

3.4 More on the Address and Dereference Operators

The address operator computes an in-memory address, in this case the address of array element arr[0].

The pointer expression arr + 2 points to two int elements beyond the first in the array, which holds 7. Dereferencing the pointer expression *(arr + 2) yields the int contents, in this case 7.

3.5 Multidimensional Arrays

Arrays of any dimension are possible, but more than three dimensions is unusual. The array nums_table is two-dimensional. The arrays nums and nums_table hold the same number of integer values (128), but they do not have the same number of elements: array nums has 128 elements, each an int value; by contrast, array nums_table has four elements, each a subarray of 32 int values. The sizeof operator, when applied to an array’s name, does the sensible thing: it gives the number of bytes required for all of the array elements, not the size in bytes of the array’s name as pointer. In this case, for example, the sizeof array nums is the same as the sizeof array nums_table: 512 because there are 128 int values in each array and each int is 4 bytes.

The data type of table is pointer to an array of subarrays, each with four integer elements. In memory, the array is laid out contiguously, with the int values in sequence, one table row (subarray) after the other.

The table program traverses the multidimensional array twice. The first traversal uses nested for loops : the outer for loop iterates over the rows, and the inner for loop iterates over the columns in each row. The C compiler lays out the table in row-major order: the first row with all of its columns, then the second row with all of its columns, and so on. A Fortran compiler, by contrast, would lay out a multidimensional array in column-major order.

acknowledges to the compiler that pointer constant table and pointer variable ptr may point to the very same byte, but that the two differ in type. As an int* pointer, ptr can be used to iterate over the individual int values in the array, rather than over the four-element subarrays that make up each table row.

The first and second addresses differ by 16 bytes, as do the third and fourth. The variable table[0] points to the first of the three rows in the table, and each row has four int values of 4 bytes apiece; hence, table[1] points 16 bytes beyond where table[0] points.

The first index picks out the row, and the second index picks out the column in the row. Any expressions involving table, but with fewer than two pairs of brackets, are pointers rather than int values. In particular, table points to the first subarray, as does table[0]; pointer table[1] points to the second subarray; and pointer table[2] points to the third subarray. A quick review exercise is to explain, in plain terms or through a code segment, the difference between the data type of table and the data type of table[0]. Both pointer expressions point to the same byte, but the two differ in type.

To pass the array’s name as an argument is thus to pass a pointer to the array, not a copy of it. Passing a copy of 100,000 4-byte integers would be expensive, maybe prohibitively so. It is possible to pass a copy of an array to a function, another issue for later analysis.

3.6 Using Pointers for Return Values

The safeMult function (see Listing 3-6) introduces in-line assembly with a call to the library function asm. The architecture-specific assembly code is in AT&T style and targets an Intel machine; the code detects overflow in integer multiplication, returning a flag to indicate whether overflow occurred.

The syntax of the in-line assembly code needs a quick analysis. The percentage sign % used to identify a CPU register sometimes occurs twice, in this case to identify the 1-byte, special-purpose register %%bl. The double percentage signs are there to prevent the assembler from confusing this register identifier with something else. One percentage sign might do, but two are safer.

The in-line assembly code does its job.

The main function for the safeMult program (see Listing 3-7) makes two calls against the function. The first, with 16 and 48 as the values to be multiplied, does not cause overflow. The second call, however, passes INT_MAX as both arguments, with overflow as the expected and, because of safe_mult, the now detected overflow.

3.7 The void* Data Type and NULL

In the second example shown previously, the void in the declaration of some_function signals only that this function expects no arguments; the void once again is not a type, but another way of writing an empty argument list.

There is a very important data type in C that has void in its name: void* , or pointer to void. This type is a generic pointer type: any other pointer type can be converted to and from void* without explicit casting. Why is this useful? A short example provides one answer, and the next section provides another.

The array happens to hold six strings, each of which is a char* in C. For example, the first array element is a pointer to the “e” in “eins”. To write a loop that traverses this array without going beyond the end requires a count of how many elements are in the array; in this case, there are six.

Because NULL is of type void*, it can occur in an array of any pointer type, including the char* element type in the strings array. By the way, the 0 as shorthand for NULL is the only numeric value that would work in this case. Were 987 used instead of 0, for instance, the code segment would not compile. C programmers, in order to save on typing, are fond of using 0 for NULL.

The loop condition is true until strings[i] is NULL, which is 0: the value 0 in C is overloaded, and one of the overloads means false in a test context. The use of NULL to mark the end of pointer arrays is common in C.

evaluates to true, but only because the compiler converts the 8-bit null terminator (zero) to the 32-bit or 64-bit zero.

test from the preceding example is one such idiom.

3.8 Structures

Arrays aggregate variables of the same data type, whereas structures can aggregate variables of different types. The variables in a structure are known as its fields. There can be arrays of structures, and structures that embed arrays and even other structures. As a result, programmer-defined data structures can be arbitrarily rich.

The data type is struct {...}, and variable s1 is of this structure type; hence, s1 has two fields: an int named n and a double named k. The member operator, the period, is used to access the structure’s fields, in this case the int field n and the double field k. The compiler is not bound to lay out storage for the fields in a way that matches the structure’s declaration. Although field n occurs before field k in the structure declaration shown previously, this may not be the case after compilation. The member operator should be used to access the fields by name.

The bigStruct program (see Listing 3-11) declares a structure, five of whose fields are large arrays. The function main then creates a local variable bns of this structure type and passes the variable to function bad. Recall that C uses call by value in function calls; hence, a byte-per-byte copy of bns is passed to function bad, a copy that is about 2.8MB (megabytes) in size.

By contrast, main then calls function good by passing the address of bns rather than a copy of this BigNumsStruct instance. The address is 4 or 8 bytes, depending on whether the underlying machine uses 32-bit or 64-bit addresses.

This syntax is cleaner and is idiomatic in C.

In the bigStruct program, the sizeof of the BigNumsStruct is reported to be 2,800,008 bytes. The arrays account for 2,800,000 of these bytes, and int field n requires only 4 bytes. What accounts for the extra 4 bytes? A simpler example explains.

The minimum storage required for a variable such as test is 13 bytes, but most implementations would report sizeof(test) to be 16 rather than 13. Modern C compilers typically align storage for scalar variables on multibyte boundaries, for example, on 4-byte (32-bit) boundaries. The char field named c thus is implemented with four bytes rather than just one.

3.9 String Conversions with Pointers to Pointers

The challenge arises in converting between strings, an aggregate rather than a scalar type, and other basic types. Because a string in C is an array, converting an array to a single integer or floating-point value is nontrivial. C provides library functions to do the heavy lifting.

The const qualifier signals that the pointer argument is not used to change the string itself, only to convert the string to a numeric value. The a in atoi and the others is for ASCII, the default character encoding in C.

The str2num program (see Listing 3-13) has three examples of strings that convert straightforwardly. The pointers to these are s1, s2, and s3. The string to which s3 points is the most interesting in that it begins with blanks; but the atoi functions ignore the leading whitespace. The challenging cases are the strings to which e1 and e2 point, as these strings contain nonnumeric characters other than whitespace. (Numeric characters include the numerals, the plus and minus signs, and the decimal point.)

The strtol function determines where to break the source string to which e3 points: at the first ! character. The library function then sets pointer bad_chars to this character. In an idiom analyzed earlier, the strtol function thus uses an argument, in this case the pointer-to-pointer variable bad_chars, in order to return a value—the first character (the !) that cannot be used in the string-to-number conversion. The return value for strtol is, of course, the converted number. A pointer-to-pointer type allows the strtol function to return two pieces of information.

The scanPrint program (see Listing 3-14) illustrates the basics of converting to and from strings using the printing and scanning functions. The print and scan functions differ markedly in their arguments. The print functions (printf, sprintf, and fprintf for printing to a file) take nonpointer values as the arguments after the format string. By contrast, the scan functions (scanf, sscanf, and fscanf for scanning data from a file) take pointers as the arguments after the format string. The scanning functions require a pointer to indicate where a scanned (and perhaps converted) value should be stored. For functions in both families, the format string specifies the desired type for either printing or scanning. As even this short code example shows, sprintf and sscanf provide a general-purpose solution to the problem of converting to and from strings.

Finally, the header file ctype.h has various functions for determining properties of individual characters. For instance, the library function isdigit(c) checks whether character c is a decimal digit, function isprint(c) checks whether character c is printable, and so on.

3.10 Heap Storage and Pointers

The examples so far have not covered the third category, the heap. The compiler figures out how much storage is required for the read-only area and the stack; hence, the details about such storage are determined at compile time—no extra programmer intervention is required. By contrast, the programmer uses designated operators (e.g., new in many modern languages) or functions (e.g., malloc and its relatives in C) to allocate storage from the heap, an allocation traditionally described as dynamic because it is done explicitly at runtime.

The sumArray program (see Listing 3-15) has two functions, main and sum_array, each of which needs stack storage for scratchpad. The main function has a local array of nine elements, each an int; these elements are stored on the stack. This function also has a local variable n to store the value returned from a call to the sum_array function. Depending on how optimizing the compiler happens to be, variable n could be implemented as a CPU register instead of as a stack location.

The sum_array function works with a pointer to the array declared and populated in main, but sum_array does need some local storage of its own: the integers sum and i, the loop counter. Both sum and i are scalars rather than aggregates, and so CPU registers would be ideal; but the stack is the fallback for the compiler.

For readability, the resulting assembly code has been pared down; for instance, most of the directives are omitted. The first code display is the assembly code for main, and the following display is the assembly code for sum_array. To begin, however, a look at the syntax for pointers in assembly code will be useful.

Several points about the code deserve mention. For one thing, the code sometimes references the 64-bit register %rdx but sometimes references only the lower 32 bits of this register under the name %edx. This can be confusing but works just fine because the upper-order bits in register %rdx have been zeroed out.

This instruction updates the loop counter %rdx by one integer, not by 4 bytes. Accordingly, the addl instruction’s first operand is the expression (%rdi,%rdx,4). Register %rdi points to the start of the array; in the C code, this is the parameter arr in the function sum_array. The offset from this base address is %rdx × 4, where %rdx is the loop counter (in C, the index i) and 4 is sizeof(int).

The assembly code confirms that the stack requirements for the sumArray program are determined at compile time. The stack management is thus automatic from the programmer’s perspective: the programmer declares local variables and parameters, makes a function call, executes a print statement, and so on. The compiler manages the details when it comes to providing scratchpad storage on the stack and, in this example, in CPU registers as well.

This function takes three arguments: a pointer to the storage to be initialized, the value to be stored in each byte, and the number of bytes to be initialized. The memset function is yet another library routine that works at the byte level.

The calloc function takes two arguments: the first is the number of elements to allocate (e.g., 10), and the second is the sizeof each element (e.g., 4 for an int). The calloc function thus can be used to allocate storage for multibyte types such as int and double. This function, unlike malloc, initializes the allocated storage to all 0s. In general, malloc is faster than calloc because malloc does no memory initialization.

The realloc function can be used to grow or shrink previously allocated storage. In this example, the function is used to grow the allocated storage by 8 × sizeof(int) bytes. If realloc succeeds, it leaves the previously allocated storage unchanged and adds or removes the requested number of bytes. In the memalloc program, realloc is called to request an additional 32 bytes (8 int values) to a collection of 20 int values already initialized to -1; hence, the original bytes still have -1 as their value after the reallocation, but the added bytes have arbitrary values.

As the name suggests, the free function deallocates storage allocated with the malloc and calloc functions. The realloc function presupposes a previous call to one of these other functions. To avoid memory leaks, it is critical for a program to free explicitly allocated storage.

3.11 The Challenge of Freeing Heap Storage

Recall the rule of thumb for freeing heap storage: for every malloc or calloc, there should be a free. Putting the rule into practice can be challenging, in particular when dealing with functions that return a pointer to a structure that, in turn, has, among its fields, pointers to heap storage. In short, the heap storage allocation may be nested. If the allocation is nested, then the freeing should be so as well. The documentation on library functions is worth reading carefully, in particular for functions that return a pointer to heap storage. There are different ways for memory-allocating library functions to guard against memory leakage, for example, by providing a utility function that does the freeing to whatever level is appropriate.

The main function for the getname program (see Listing 3-20) declares a char buffer, which is used in the call to function get_name1. The responsibility falls squarely on the caller to provide enough storage for the string to be stored. The second argument, BuffSize, guards against buffer overflow because the char array is of size BuffSize + 1, with the added byte for the null terminator.

The call to get_name2 returns a pointer to the heap storage provided for the name. In this case, the main function does call free, but the logic is complicated: one function allocates, another function frees. The approach works, but it is error-prone.

The last call, to get_name3 , provokes a compiler warning because a pointer to local storage is being returned to main. In this case, the storage for the name is local to the call frame for get_name3. Once the function get_name3 returns to main, the call frame for get_name3 should not be accessed. It is unpredictable whether this third approach works.

3.12 Nested Heap Storage

This code segment allocates heap storage for 5,000 int values, does whatever logic is appropriate, and then frees the storage. The challenge increases when, for example, structure instances are allocated from the heap—and such instances contain fields that are themselves pointers to heap storage. If the heap allocation is nested, the freeing must be nested as well.

The sizeof(HeapStruct) includes the bytes (four on a 32-bit machine, eight on a 64-bit machine) for the heap_nums field, which is a pointer to the float elements in a dynamically allocated array. At issue, then, is whether the malloc delivers the bytes for this structure or NULL to signal failure; if NULL, the get_heap_struct function returns NULL to notify the caller that the heap allocation failed.

After checking that the argument heap_struct is not NULL, the function first frees the heap_nums array, which requires that the heap_struct pointer is still valid. It would be an error to free the heap_struct first. Once the heap_nums have been deallocated, the heap_struct can be freed as well. If heap_struct were freed but heap_nums were not, then the float elements in the array would be leakage: still allocated bytes but with no possibility of access—hence, of deallocation. The leakage would persist until the nestedHeap program exited and the system reclaimed the leaked bytes.

These calls free the allocated storage—but they do not set their arguments to NULL. (The free function gets a copy of an address as an argument; hence, changing the copy to NULL would leave the original unchanged.) For example, after a successful call to free, the pointer heap_struct still holds a heap address of some heap-allocated bytes, but using this address now would be an error because the call to free gives the system the right to reclaim and then reuse the allocated bytes.

3.13 What’s Next?

C variables can be defined inside and outside of blocks, where a block is the by-now-familiar construct that begins with a left brace { and ends with a matching right brace }. Where a variable is defined determines, within options, where its value is stored, how long the variable persists, and where the variable is visible. Every variable has a storage class (with auto and extern as examples) that determines the variable’s persistence and scope. Functions too have a storage class: either extern (the default) or static. The next chapter gets into the details of storage classes.