All of Programming [ PART I ]

8.4.2 NULL: A Pointer to Nothing At the bottom of Figure 8.4, there is a blank space below the code segment, which is an invalid area of the program’s memory. You might wonder why the code does not start at address 0, rather than wasting this space. The reason is that programs use a pointer with the numeric value of 0—which has the special name NULL7 to mean “does not point at anything.” By not having any valid portion of the program placed at (or near) address 0, we can be sure that nothing will be placed at address 0. This means no properly initialized pointer that actually points to something would ever have the value NULL. Knowing that a pointer does not point at an actual thing is useful for a variety of reasons. For one, we may sometimes have algorithms that need to answer “there is no answer.” For example, if we think about our closest point example from Video 1.4, when the set of points is empty, we must return “there is no answer”—with pointers, we can return a pointer to a point, and return NULL in the case where “there is no answer.” We may also have functions, whose job it is to create something, that return NULL if they fail to do so—in Chapter 11, we will see functions that open files (so we can read data from the disk), which fail in this manner, and in Chapter 12 we will see functions that dynamically allocate memory, which also return NULL if the memory cannot be allocated. In Chapter 21, we will begin to learn about linked structures, which store data with pointers from one item to the next and use NULL to indicate the end of the sequence. Figure 8.5: Conceptual depiction of NULL: a flat-headed arrow. When we use NULL, we will represent it as an arrow with a flat head (indicating that it does not point at anything), as shown in Figure 8.5. Whenever we have NULL, we can use the pointer itself (which just has a numeric value of zero); however, we cannot follow the arrow (as it does not point at anything). If we

attempt to follow the arrow (i.e., dereference the pointer), then our program will crash with a segmentation fault—an error indicating we attempted to access memory in an invalid way (in fact, if our program tries to access any region of memory that is “blank” in Figure 8.4, it will crash with a segmentation fault). The NULL pointer has a special type that we have not seen yet—void *. A void pointer indicates a pointer to any type, and is compatible with any other pointer type—we can assign it to an int *, a double *, or any other pointer type we want. Likewise, if we have a variable of type void *, we can assign any other pointer type to it. Because we do not know what a void * actually points at, we can neither dereference it (the compiler has no idea what type of thing it should find at the end of the arrow), nor do pointer arithmetic on it (see Section 8.7). 8.5 Pointers to Sophisticated Types So far, we have primarily talked about pointers to the most basic types, such as int or double. However, we can have a pointer to any type—including to a struct, or even to another pointer. We can even have a pointer to a pointer to a pointer to a struct (which may be useful for certain things). 8.5.1 Structs When we have pointers to structs, we can just use the * and . operators that we have seen so far; however, the order of operations means that . happens first. If we write *a.b, it means *(a.b)—a should be a struct, which we look inside to find a field named b (which should be a pointer), and we dereference that pointer. If we have a pointer to a struct (c, and we want to refer to the field d in the struct at the end of the arrow, we would need parenthesis, and write (*c).d (or the -> operator we will learn about momentarily).

Figure 8.6: Structs and Pointers: *a.b dereferences the b field inside of struct a. Dereferencing q, then selecting field x requires either parenthesis, or the -> operator. Figure 8.6 illustrates. Here, we have a struct that has a field p (which is a pointer to an int), and a field x, which is an int. We then declare y (an int), a (a struct), and q (a pointer to a struct), and initialize them. When we write *a.p, the order of operations is to evaluate a.p (which is an arrow pointing at y), then dereference that arrow. If we wrote *q.x, we would receive a compiler error, as q is not a struct, and the order of operations would say to do q.x first (which is not possible, since q is not a struct). We could write parentheses, as in the figure ((*q).x). However, pointers to structs are incredibly common, and the above syntax gets quite cumbersome, especially with pointers to structs that have pointers to structs, and so on. For (*q).x, it may not be so bad, but if we have (*(*(*q).r).s).t, it becomes incredibly ugly and confusing. Instead, we should use the -> operator, which is shorthand for dereferencing a pointer to a struct and selecting a field—that is, we could write q->x (which means exactly the same thing as (*q).x). For our more complex example, we could instead write q->r->s->t (which is easier to read and modify). 8.5.2 Pointers to Pointers We can have pointers to pointers (or pointers to pointers to pointers etc.). For example, an int** is a pointer to a pointer to an int. An int*** is a pointer to a pointer to a pointer to an int. We can have as many levels of “pointer” as we want (or need); however, the usefulness drops of quite quickly (int** is quite common, int*** moderately common, but neither author has ever had a use for an int**********). The rules for pointers to pointers are no different from anything else we have seen so

far: the * operator dereferences a pointer (follows an arrow), and the & operator takes the address of something (gives an arrow pointing at that thing). Figure 8.7: An illustration of pointers to pointers. Figure 8.7 illustrates pointers to pointers. Here we have four variables, a (which is an int), p (which is an int*), q (which is an int **), and r (which is an int***). If we were to write *r, it would refer to q’s box (because we would follow the arrow from r’s box, and end up at q’s box. We could write **r, which would refer to p’s box—because *r is an arrow pointing at p, and the second * dereferences that pointer. Likewise, ***r would refer to a’s box. It would be a compiler error to write ****r, because that would attempt to follow the arrow in a’s box, which is not an arrow, but rather a number (sure, everything is a number—but our types have told the compiler that a is just a plain number, not a number that means an arrow). You may wonder why8 we might want pointers to pointers. One answer to this question is “for all the same reasons we want pointers”—a pointer gives us the ability to refer to the location of a thing, rather than to have a copy of that thing. Anytime we have a variable that tells us the location of a thing, we can change the original thing through the pointer. Just as we might want to write swap for integers, we might also want to write swap for int *s (in which case, our swap function would take int **s as parameters). In Section 10.2, we will see that we might want pointers to pointers to store data in two (or more) dimensional structures (e.g., a grid-like fashion). When we get to Chapter 21 and Chapter 22 and begin manipulating linked data structures, we will see that pointers to pointers give us elegant and efficient ways to accomplish a variety of tasks.

Notice how the types work out (i.e. match up so that the compiler type check the program). Whenever we take the address of an lvalue of type T, we end up with a pointer of type T * (e.g., p has type int *, so &p has type int **). Whenever we take the address of something, we “add a star” to the type. This rule makes intuitive sense because we have a pointer to whatever we had before. Whenever we dereference an expression of type T*, we end up with a value of type T—we “take a star off the type” because we followed the arrow. For the expression… *e &e e must be… a pointer an lvalue if e’s type is T* T …then the resulting type is T T* conceptually, this means: Follow the arrow Give me an arrow pointing at e that is e’s value Table 8.1: Rules for pointers. Table 8.1 summarizes these rules about pointers. Note that * and & are inverse operations—if we write *&e or &*e, they both just result in e (whenever they are legal). The first would mean “give me an arrow pointing at e, then follow it back (to e),” while the second would mean “follow the arrow that is e’s value, then give me an arrow pointing at wherever you ended up.” 8.5.3 const As we discuss pointers to various types, it is a good time to introduce the notion of const data—data that we tell the compiler we are not allowed to change. When we declare a variable, we can add const to its type to specify that the compiler should not allow us to change the data: 1 const int x = 3; //assigning to x is illegal If we try to change the value of x, the compiler will produce an error. Declaring data as const can be useful, as it removes a

certain class of mistakes that we can make in our program: changing things we should not. When we have pointers, there are two different things that can be const: the data that the pointer points at (what is in the box at the end of the arrow) or the pointer itself (where it points). If we write: 1 const int * p = &x; we have declared p as a pointer to a const int—that is, p points at an int, and we are not allowed to change that int. We can change where p points (e.g., p = &y; is legal—if y is an int). However, changing the value in the box that p points at (e.g., *p = 4;) is illegal—we have said that the int p points at is const. If we do try to write something like *p = 4;, we will get a compiler error like this: assignment of read-only location ’*p’ We can achieve exactly the same effect by writing:9 1 int const * p = &x; //same as const int * p If we want to specify that we can change *p, but not p itself, we would write: 1 int * const p = &x; This declaration says that p is a const pointer to a (modifiable) int. Writing *p = 4; would be legal, but writing p = &y; would be illegal. If we so desire, we can combine both to prevent changing either where the pointer points or the value it points at: 1 const int * const p = &x; The same principle applies to pointers to pointers (to pointers to pointers …). For example, with an int **, we have the following combinations:

Can we change… **p *p p int **p Yes Yes Yes const int **p int *const*p No Yes Yes int **const p const int *const *p Yes No Yes const int ** const p int * const * const p Yes Yes No const int * const * const p No No Yes No Yes No Yes No No No No No Note that a declaration of const tells the compiler to give us an error only if we try to change the data through the variable declared as const or perform an operation where the const-ness gets dropped. For example, the following is legal: 1 int x = 3; 2 const int * p = &x; 3 x = 4; Here, we are not allowed to change *p, but the value we find at *p can still be changed by assigning to x (since x is not const, it is not an error to assign to it). However, if we write: 1 const int y = 3; 2 int * q = &y; 3 *q = 4; then we will receive a compiler warning (which we should treat as an error): initialization discards ’const’ qualifier from pointer target type [enabled by default] The error is on line 2, in which we assign &y (which has type const int *) to q (which has type int *)—discarding the const qualifier (const is called a qualifier because it modifies a type). This snippet of code is an error because *q = 4; (on line 3) would be perfectly legal (q is not declared with the const

qualifier on the type it points to) but would do something we have explicitly said we do not want to do: modify the value of y. Novice programmers often express some confusion at the fact that the first example is legal and the second is not—in both cases, we have tried to declare a variable and a pointer (to that variable), with one const and the other not. We have then tried to modify the value in that box through whichever is not const— but one is ok, and the other is not. These rules do actually make sense: in the second case, we have said “y cannot be modified,” then we try to say “q is a pointer (which I can use to modify or read a value) to y”—that clearly violates what we said about y (that it cannot be modified). In the first case, however, we are saying “x is a variable that can be modified,” and then “p is a pointer, which we can only use to read the value it points at, not modify it”—this does not impose new (nor violate existing) restrictions on x; it only tells us what we can and cannot do with p. 8.6 Aliasing: Multiple Names for a Box In our discussion of pointers, we have alluded to the fact that we may now have multiple names for the same box; however, we have not explicitly discussed this fact. For example, in Figure 8.7, we have four names for a’s box: a, *p, **q, and ***r. Whenever we have more than one name for a box, we say that the names alias each other—that is, we might say *p aliases **q.10 Aliasing plays a couple of important roles in our programming. First, when we are working through Step 2 of our programming process, we may find that we changed a value, but there are multiple ways we can name what value we changed. When we write down precisely what we did, it is crucial to think about which name we used to find the box when we worked the problem by hand in Step 1. If we are not sure, we should make note of the other names we might have used— then if we have trouble generalizing, we can consider whether we should have be using some other name instead.

When we are debugging (or executing code by hand), it is also important to understand aliasing. Novice C programmers often express surprise and confusion at the fact that a variable changes its value without being directly assigned to: “I wrote x = 4;, then look I don’t assign to x anywhere in this code, but now it is 47!” Generally such behavior indicates that you alias the variable in question (although you may not have meant to). If you have problems of this type, using watch commands in GDB (see Section D.2 for more about GDB) can be incredibly helpful. If we want to live dangerously, we can even have aliases with different types. Consider the following code: 1 float f = 3.14; 2 int * p = (int *) &f; //generally a bad idea! 3 printf(\"%d\\n\", *p); Here, f is an alias for *p, although f is declared to be a float, while p is declared to be a pointer to an int (so we have told the compiler that *p is an int). What will happen when you run this code? Your first reaction might be to say that it prints 3—after all, from what we learned in Chapter 3, the following (similar-ish) code would print 3: 1 float f = 3.14; 2 int x = (int) f; 3 printf(\"%d\\n\", x); Figure 8.8: Aliasing with different types. Storing the floating-point bit encoding for 3.14 in f, then reading it out as though it represented an integer.

However, if we run the first code snippet on the computer, we will get 1078523331! This result may seem like the computer is just giving us random nonsense; however, what happened is perfectly logical (if a bit low-level). When we cast a float to an int (in the second snippet of code), we ask the compiler to insert instructions that convert from a float to an int. However, when we dereference a pointer to an int, the compiler just generates instructions to read the bit pattern at that location in memory as something that is already an int. In the first snippet of code, initializing float f = 3.14; writes the bit pattern of the floating point encoding of 3.14 into f’s box. Without going into the details (which are discussed in Section 3.2.3), the floating point encoding of 3.14 works out to 0100 0000 0100 1000 1111 0101 1100 0011 (=0x4048F5C3 in hex, 1078523331 in decimal). When we dereference the pointer as an int, the program reads out that bit pattern, interprets it as though it were an integer, and prints 1078523331 as output. Figure 8.8 illustrates. This last example is not something you need to use in programs you write, but rather a caution against abusing pointers. Unless/until you understand exactly what is happening here and have a good reason to do it11, you should not cast between pointer types. 8.7 Pointer Arithmetic Like all types in C, pointers are variables with numerical values. The precocious programming student may wonder if the value of variables can be manipulated the way one can manipulate the value of integers and floating point numbers. The answer is a resounding “Yes!” Consider the following code: 1 int x = 4; 2 float y = 4.0; 3 int *ptr = &x; 4 5 x = x + 1; 6 y = y + 1; 7 ptr = ptr + 1;

Lines 1–3 initialize the values of three variables of various types (integer, floating-point number, and pointer to an integer). Lines 5–7 add 1 to each of these variables. For each type, adding 1 has a different meaning. For x, adding 1 performs integer addition, resulting in the value 5. For y, adding 1 requires converting the 1 into a floating point number (1.0) and then performing floating point addition, resulting in 5.0. For both integers and floating-point numbers, adding 1 has the basic semantics of “one larger”. For the integer pointer ptr (which initially points to x), adding 1 has the semantics of “one integer later in memory”. Incrementing the pointer should have it point to the “next” integer in memory. In order to do this, the compiler emits instructions that actually add the number of bytes that an integer occupies in memory (e.g., +1 means to change the numerical value of the pointer by +4). Likewise, when adding to a pointer to any type T, the compiler generates instructions that add ( times the number of bytes for values of type T) to the numeric value of the pointer —causing it to point Ts further in memory. This is why pointer arithmetic does not work with pointers to void; since the compiler has no idea how big a “thing” is, it does not know how to do the math to move by “things”. The code we have written here is legal as far as the compiler is concerned; however, our use of pointer arithmetic is rather nonsensical in this context. In particular, we have no idea what box ptr actually points at when this snippet of code finishes. If we had another line of code that did *ptr = 3;, the code would still compile but would have undefined behavior— we could not execute it by hand and say with certainty what happens. Specifically, when ptr = &x, it is pointing at one box (for an integer) that is all by itself—it is not part of some sequence of multiple integer boxes (which we will see shortly). Incrementing the pointer will point it at some location in memory, we just do not know what. It could be the box for y, the return address of the function, or even the box for ptr itself. The fact that we do not know what happens here is not simply a matter of the fact that we have not learned what happens—it is a matter of the fact that the rules of C give the

compiler a lot of freedom in how it lays out the variables in memory. One compiler may place one piece of data after x, while another may place some other data after x. In fact, the same compiler may change how it arranges variables in memory when given different command line options, changing its optimization levels. We will consider all code with undefined behavior, such as this, to be erroneous. Accordingly, if you were to execute this code by hand, when you perform ptr = ptr + 1;, you should change the value of ptr to just be a note that it is &x + 1, and not any valid arrow. If you then dereference a pointer that does not validly point at a box, you should stop, declare your code broken, and go fix it. We will note that simply performing arithmetic on pointers such that they do not point to a valid box is not, by itself, an error—only dereferencing the pointer while we do not know what it points at is the problem. We could perform ptr = ptr - 1; right after this code, and know with certainty that ptr points at x again. We might also just go past a valid sequence of boxes at the end of a loop, but not use the invalid pointer value. We will generally not do these things (although we will see an example of the latter in Video 9.1), and you should know the difference between what is and is not acceptable coding practice. 8.8 Use Memory Checker Tools Now that you are starting to use pointers, it is crucial to use memory checker tools, such as Valgrind and/or - fsanitize=address (see Section D.3). These will help you find erroneous behavior and make fixing your program easier. Use them all throughout the testing process. 8.9 Practice Exercises Selected questions have links to answers in the back of the book.

• Question 8.1 : What is a pointer? How should you think about one conceptually? How are they actually implemented? • Question 8.2 : Is “pointer” a type? • Question 8.3 : What is NULL? Why is it useful? What is the type of NULL? What does this type mean? • Question 8.4 : What does the -> operator mean? Specifically, if a program has a->b, then (1) what must be true of the type of a for this code to be legal? (2) How do you find the box named by a->b? (3) How could you write a->b without the arrow operator (using other operators you have learned before to get the same effects)? • Question 8.5 : What does const mean? • Question 8.6 : What does aliasing mean? • Question 8.7 : Suppose I told you that *p is an alias for *q before executing the lines *p = 5; and then *q = 42;. After executing these lines, what is the value of *p? Why? • Question 8.8 : Consider the following code (which does not compile for many reasons): 1 int f(int a, int * b, int * c) { 2 a = &b; 3 &b = &c; 4 *b = a; 5 &c = b; 6 c = a; 7 return b; 8} For each line in the table below, determine if that line is legal or not. If it is legal, write “legal” in the table. If not, describe why the line is illegal. 2: a = &b; 3: &b = &c; 4: *b = a; 5: &c = b; 6: c = a; 7: return b; • Question 8.9 : Suppose that you have three int *s: p, q, and r. Of these, p and q are NULL, and r points at a valid box belonging to an int. Which of the following lines of

code will cause the program to segfault (consider each line separately: not the cumulative effects of executing them all sequentially)? 1. p = q; 2. *p = 3; 3. *r = *q; 4. r = q; 5. p = r; • Question 8.10 : What is the output when the following code is run? 1 void g(int x, int * y) { 2 printf(\"In g, x = %d, *y = %d\\n\", x, *y 3 x++; 4 *y = *y - x; 5 y = &x; 6} 7 void f(int * a, int b) { 8 printf(\"In f, *a = %d, b = %d\\n\", *a, b 9 *a += b; 10 b *= 2; 11 g(*a, &b); 12 printf(\"Back in f, *a = %d, b = %d\\n\", 13 } 14 int main(void) { 15 int x = 3; 16 int y = 4; 17 f(&x, y); 18 printf(\"In main: x = %d, y = %d\\n\", x, 19 return EXIT_SUCCESS; 20 } • Question 8.11 : What is the output when the following code is run? 1 int main(void) { 2 int a = 3; 3 int b = 4; 4 int c = 5; 5 int * p = &a; 6 int * q = &b; 7 int * r = &c; 8 int ** s = &p; 9 int ** t = &q; 10 printf(\"**s = %d\\n\", **s); 11 printf(\"**t = %d\\n\", **t); 12 *s = r; 13 r = *t; 14 **s = 55;

15 **t = 99; 16 printf(\"a = %d\\n\", a); 17 printf(\"b = %d\\n\", b); 18 printf(\"c = %d\\n\", c); 19 printf(\"*p = %d\\n\", *p); 20 printf(\"*q = %d\\n\", *q); 21 printf(\"*r = %d\\n\", *r); 22 printf(\"**s = %d\\n\", **s); 23 printf(\"**t = %d\\n\", **t); 24 return EXIT_SUCCESS; 25 } 7 Recursion9 Arrays Generated on Thu Jun 27 15:08:37 2019 by L T XML

I Introduction to Programming in C8 Pointers10 Uses of Pointers

Chapter 9 Arrays Section 8.7 implied that pointer arithmetic is most useful when we have sequences of boxes that are guaranteed to be one after the other. Such sequences, called arrays, are incredibly useful. Arrays allow us to solve a wide variety of useful and interesting problems—we frequently want to write programs that operate on a lot of data of the same type. Arrays let us bundle this data together, refer to it with a single variable, and easily traverse each element in our bundle. An understanding of arrays also enables us to understand the details of strings (which we will learn about in Section 10.1). 9.1 Motivating Example As a motivating example, suppose we wanted to write a program to break a simple cryptographic system,1 such as a Caesar cipher or a Vigenère cipher. The first of these, the Caesar cipher, named after the ancient Roman emperor Julius Caesar, encrypts a message by adding a fixed shift (e.g., add three) to each letter. For example, encrypting Hello would yield Khoor, as K is three letters after H, h is three letters after e, and so on. The Vigenère cipher applies the same concept of shifting each letter but uses a key with more than one amount to shift by. For example, we might have a key of (3, 5, 7, 2, 9), in which case we would add three to the first, sixth, eleventh, sixteenth, and so on letters of the message; we would add five to the second, seventh, twelfth, seventeenth, and so on letters; etc. We will note that for a long time,

Vigenère was regarded as unbreakable and that many novice programmers think of variants of it when trying to devise their own encryption schemes. However, it is easily broken. Breaking both of these ciphers relies on frequency counting—determining how often each letter appears in the encrypted message—and then using the fact that the frequency distribution of letters in natural language is highly uneven. In English, e is by far the most common letter, while letters such as q, x, z are quite uncommon (if you are curious, we give the frequency distribution of letters in this book in Table 24.1). If we were trying to break a Caesar cipher, once we have frequency counted the message, we can guess that the most frequently occurring letter is e, and then try to decrypt the message. If all characters (not just letters) are encrypted, we would guess that the most frequently occurring symbol is space and try to decrypt the message. If the decrypted message does not make sense, we can try again with the second most common letter/symbol. Although it might take a few tries, we would typically succeed on the first attempt (as long as the message is long enough to give reasonable frequency counts). If we actually wanted to break such messages, we would want to write a program to do it—specifically, an algorithm that would take an encrypted message as input and output the decrypted message (if we are worried about needing multiple tries, we could have it output the decrypted message for the top few possibilities). Writing this program requires a few pieces. First, we need to frequency count the encrypted message, and then we need to find out which letter’s count is the largest. Since we do not know how to work with strings yet (our message would be a string—and we cannot learn about strings until we know about arrays), let us just look at the

problem of finding the largest of the frequency counts—of which there would be 26, one for each letter. You could write a function to implement this algorithm right now; however, it would be horrendously ugly: 1 char highestFrequency(unsigned numAs, uns 2 unsigned numDs, uns 3 ... //many parameters 4 unsigned numXs, uns 5 char bestLetter = ’a’; 6 unsigned bestCount = numAs; 7 if (numBs > bestCount) { 8 bestLetter = ’b’; 9 bestCount = numBs; 10 } 11 if (numCs > bestCount) { 12 bestLetter = ’c’; 13 bestCount = numCs; 14 } 15 if (numDs > bestCount) { 16 bestLetter = ’d’; 17 bestCount = numDs; 18 } 19 ... //many lines of code omitted 20 if (numZs > bestCount) { 21 bestLetter = ’z’; 22 bestCount = numZs; 23 } 24 return bestLetter; 25 } We sketch this code out but leave out large parts of it —in particular, there are 17 other parameters (never write a function that takes 26 parameters!) and 84 lines of code (also, never write a function that is 100+ lines long)—for the cases ’e’–’y’, which are missing. This approach would work, but it is tedious and error-prone to write (how likely are you to miss changing something as you copy/paste 24 cases?). Matters would get even worse if we were dealing with 1000 items instead of 26—could

you imagine trying to write this function to find the max of 1000 things? Looking at it, we can see that we are repeating almost the same thing over and over— suggesting there should be a way to generalize this code into an algorithm where the program can do the repetitive work, instead of you doing it. It seems like there has to be a better way, and fortunately there is—we can use an array! 9.2 Array Declaration An array is a sequence of items of the same type (e.g., an array of ints is a sequence of ints). When an array is created, the programmer specifies its size (i.e., the number of items in the sequence)—so we might make an array of 26 ints for our frequency counting example. If we wanted to declare an array of four ints called myArray, we would write: 1 int myArray[4]; Note that this line of code looks just like any other variable declaration, except that it has [4] after the variable name—that specifies we are declaring an array of size four (i.e., four ints in a sequence, rather than just one int). When we make this declaration, we end up with a slightly different semantics than we are used to. The variable name (in this case, myArray) is a pointer to the four boxes that make up the array. Unlike other variables, myArray is not an lvalue—we cannot change where it points. Instead, it just names a pointer to the first box in the array. Starting with C99 (the “version” of C defined in 1999), arrays may be declared with a non-constant expression as the size, i.e., we can write int myArray[x];, where x is a previously declared (and initialized!) integer variable. As we mentioned in Chapter 5, you will generally want to give GCC the command line

option --std=gnu99 to enable features defined in C99— this is one such feature. Figure 9.1: Depiction of an array of four ints, resulting from the declaration of myArray. Figure 9.1 illustrates the effects of this declaration. We have created the array (which has four uninitialized boxes for ints), and myArray names a pointer to it. Unlike other variables, we draw myArray without a box of its own, to underscore the fact that the value of myArray is not necesarily stored in the program’s memory, and cannot be changed. While not storing the value explicitly may sound like it is difficult to use, it is not—the compiler just translates the array name into a fixed offset from the start of the function’s stack frame. That is, the compiler treats all uses of myArray as if they were frame + offset, where frame is the start of the stack frame, and offset is the particular location in the frame the compiler chooses. The C standard says that myArray is an lvalue, but not a modifiable lvalue. This distinction may sound a bit strange, especially as myArray does not have a box of its own. However, &myArray is legal (and evaluates to the same numerical value as myArray, although of a slightly different type, as we shall see shortly). As with other variables, we can initialize an array in the same line that we declare it. However, as the array holds multiple values, we write the initialization data inside of curly braces. For example, we might write: 1 int myArray[4] = {42, 39, 16, 7};

You might think that writing the wrong number of elements in the initializer (e.g., 5 or 7 in the above example) would result in an error from the compiler; however, you will only receive a warning if you write too many elements in the initializer. If you write too few elements, the compiler will silently fill the remaining ones in with 0. This behavior can be a useful feature for zero- initialing the entire array—we can write just a single 0 in the curly braces and the compiler will fill in as many zeros as there are elements of the array: 1 int myArray[4] = {0}; //initialize all elements to Note that most compilers will also accept int myArray[4] = {};; however, GCC will warn you for it if you compile with -pedantic, as its not strictly allowed by the language standard. If we provide an initializer, we can also omit the array size and instead write empty square brackets—the compiler will count the elements of the initializer and fill in the array size: 1 int myArray[] = {42, 39, 16, 7}; //compiler figures We’ll also note that you can use a similar syntax to initialize structs. For example, the following will initialize the first field of p to 3 and the second field to 4: 1 point p = {3, 4}; However, for structs, this form of initialization is very brittle–if you add another field to the struct before or in between these two, you will no longer be initializing the fields the way you intend. In C99 (e.g., what you get when you compile with -std=gnu99), you can designate which element you are initializing:

1 point p = {.x = 3, .y = 4}; Now, if another field is added to the struct, it will be zero- initialized, and the x and y fields will still be initialized properly. If you are initializing an array of structs, these two techniques work particularly well together (an example of composability—which you learned about in Section 4.5.1). For example, we could declare and initialize an array of three points: 1 point myPoints[] = { {.x = 3, .y = 4}, 2 {.x = 5, .y = 7}, 3 {.x = 9, .y = 2} }; 9.2.1 What Is The Type of An Array Suppose you have declared myArray as follows: 1 int myArray[4] = {42, 39, 16, 7}; A natural question is “what is the type of myArray?” As we told you earlier, myArray names a pointer to the first element of the array, so int * is a natural choice. For most practical purposes, this is the type of myArray. The type is actually int [4]. However, almost anything you do with an array will cause the type to decay into int *. That is, the compiler will effectively “forget” that the type is specifically an array of ints, and just treat it as a generic int pointer. In fact, there are three ways that an array can be used without causing its type to decay to a pointer. However, to discuss two of these, we will need to see some more concepts later on. When we reach the appropriate times, we will mention these situations. In all other cases, the array gets used like a pointer.

The third operation that does not cause decay, which we can discuss now, is &. As we said earlier, myArray and &myArray evaluate to the same numerical value, but with slightly different types. When used as a pointer, myArray will evaluate to a pointer to an int. However, &myArray will evaluate to a pointer to 4 ints. This difference is primarily significant if you attempt to do pointer arithmetic: if ints are 4 bytes, then myArray+1 will be numerically 4 larger than myArray, while &myArray+1 will be numerically 16 larger than myArray. 9.3 Accessing an Array We can access the elements of an array in a couple different ways (which are actually the same under the hood!). We have already learned that the name of the array is a pointer to its first element, that we can do arithmetic on pointers, and that we can dereference pointers to access the data at the end of the arrow. We can put these concepts together to see one way we could access elements in the array. Video 9.1 illustrates. Video 9.1: Array access with pointer arithmetic. Accessing an array element using pointer arithmetic works fine and sometimes is the natural way to access elements. However, sometimes we just want the element of an array, and it would be cumbersome to declare a pointer, add to it, then dereference it. We can accomplish this goal more succinctly by indexing the array. When we index an array, we write the name of the array, followed by square brackets containing the number of the element we want to refer to: e.g., myArray[3]. Indexing an array names the specific box within the sequence and can be used as either an lvalue or an

rvalue. It is important to note that in C (and C++ and Java), array indexes are zero-based—the first element of the array is myArray[0]. Some programming languages have one-based array indexing, but zero-based is generally more common. Video 9.2 illustrates the execution of code (which has the same behavior as the code in Video 9.1) using array indexing. Video 9.2: Array access with indexing. We will note that accessing an array out of bounds (at any element that does not exist) is an error that the compiler cannot detect. If you write such code, your program will access some box, but you do not know what box it actually is. This behavior is much the same as the erroneous behavior we discussed when we talked about pointer arithmetic. In fact, pointer arithmetic and array indexing are exactly the same under the hood: the compiler turns myArray[i] into *(myArray + i).2 Note that a consequence of this rule is that if we take &myArray[i], it is equivalent to &*(myArray + i), and the & and * cancel (as we learned previously, they are inverse operators), so it is just myArray + i. This result is fortunate, as it lines up with what we would hope for: &myArray[i] says “give me an arrow pointing at the box of myArray,” while myArray + i says “give me a pointer boxes after where myArray points”—these are two different ways to describe the same thing. 9.4 Passing Arrays as Parameters In general, when we want to pass an array as a parameter, we will want to pass a pointer to the array, as well as an integer specifying how many elements are in the array, such as this:

1 int myFunction(int * myArray, int size) { 2 //whatever code... 3} There is no way to get the size of an array in C, other than passing along that information explicitly, and we often want to make functions that are generic in the size of the array they can operate on (i.e., we do not want to hardcode a function to only work on an array of a particular size). If we wanted, we could make a struct that puts the array and its size together as one piece of data —then pass that struct around. When we pass a pointer that actually points at an array, we can index it like an array (because it is an array —remember the name of an array variable is just a pointer) and perform pointer arithmetic on it. Such pointer arithmetic will be well-defined, as long as the resulting pointer remains within the bounds of the array, as we are guaranteed that the array elements are sequential in memory. We can also pass an array as a parameter with the square bracket syntax: 1 int myFunction(int myArray[], int size) { 2 //whatever code... 3} This definition is functionally equivalent to the one we saw before with the pointer syntax. Some people prefer it, as it indicates more explicitly that myArray is intended to be an array. We can also write a size in the []; however, the compiler will not make any attempt to check if that size is actually correct, thus it is easy to write something incorrect there (or something that becomes incorrect as you change your code), and may confuse a reader.

When you call a function that takes an array, you can pass any expression that evaluates to a pointer to a sequence of elements. Typically, this expression is just the name of the array (which is a pointer to the first element). However, we could perform pointer arithmetic on an array (to get a pointer to an element in the middle of it—which is a valid, but shorter, array), or we might retrieve the pointer out of some other variable—it might be a field in a struct, or even an element in another array (we will see how to do this in Section 10.2). 9.5 Writing Code with Arrays When we write code with arrays, we need to look for patterns in where we access the array. A common pattern is to access each element of the array in order (the , then the , etc.). Such a pattern generally lends itself naturally to counting over the elements of the array with a for loop. However, we might have other patterns—as always, we should work the problem ourselves, write down what we did, and look for the patterns. If we have complicated data (e.g., arrays of structs that have arrays inside them) it is very important to think carefully about how we can name the particular box we want to manipulate. For problems with complex data structures, drawing a diagram with the appropriate pointers and arrays can be an important aspect of working an example of the problem ourselves (Step 1). Then, when we write down exactly what we did (Step 2), we can think carefully about how we can name each box that we manipulate. As we mentioned in Section 8.6, sometimes a box will have multiple names, in which case we need to think about how we picked that box—what “route” we took to get to it, to figure out what name is most appropriate. If we are unsure, we should make a

note of the other names for the box that we can think of; then in Step 3, we may realize that we prefer another way to name the same box, as it creates a more consistent pattern with other “almost repetitive” parts of our algorithm. 9.5.1 Index of the Largest Element Video 9.3: Devising the code to find the index of the largest element of an array. In our motivating example (breaking simple cryptographic systems), we discussed solving the problem of finding the largest of 26 numbers. Now that we know about arrays, we can implement a much better version of this function. We can also make our function slightly more general—instead of only operating on 26 pieces of data, we can make it work on an array of any size. Video 9.3 walks through the creation of such a function. 9.5.2 Closest Point As another example, we can return to the closest point algorithm we considered in Video 1.4. When we first considered this example back in Section 1.7.4, we worked through the design of the algorithm for this problem. However, at that time, we did not know how to write any C code, so we stopped there. Now, however, we are ready to complete that example. Video 9.4 walks through the translation of this algorithm to code. Video 9.4: Translating our closest point algorithm to code.

9.5.3 Dangling Pointers When you write code with arrays, you may be tempted to return an array from a function (after all, it is natural to solve problems where an array is your answer). However, we must be careful, because the storage space for the arrays we have created in this chapter live in the stack frame and thus are deallocated after the function returns. The value of the expression that names the array is just a pointer to that space, so all that gets copied to the calling function is an arrow pointing at something that no longer exists. Whenever you have a pointer to something whose memory has been deallocated, it is called a dangling pointer. Dereferencing a dangling pointer results in undefined behavior (and thus represents a serious problem with your code) because you have no idea what values are at the end of the arrow. Video 9.5: Illustration of a dangling pointer caused by attempting to return an array. Video 9.5 illustrates this problematic behavior. If we were to try to compile the code in the video, the compiler would warn us that our code is broken: warning: function returns address of local variable [-Wreturn-local-addr] return myArray; ^ However, you should understand why the compiler is giving this warning and never write code that exhibits this bad behavior, rather than relying on the compiler to find it. The compiler’s ability to detect this sort of problem is rather limited.3 Consider the following code, which is still broken, and has the exact same effect as the code in the video:

1 //Still broken 2 int * initArray(int howLarge) { 3 int myArray[howLarge]; 4 for (int i = 0; i < howLarge; i++) { 5 myArray[i] = i; 6} 7 int * p = myArray; 8 return p; 9} GCC produces no warning, even though the code is equally broken. If you execute a call to this function by hand (recommended), you will find that its return value is dangling. One thing to be particularly wary of with respect to dangling pointers is that sometimes you can get away with using them without observing any problematic effects—your code is still broken, it just does not look (or even behave) broken. Having the code seem fine is particularly dangerous for two reasons. First, when there is a problem in our code, we want to find it. We want to fix it, so that our code is correct, and we do not have danger lurking inside. Second, the “but I did that before and it was fine” effect is dangerous to novices—if you learn that something is ok, you keep doing it. You do not want to form bad habits. To understand why you only see problems sometimes, remember that a value stored in memory will remain there until changed by the program—and a deallocated memory location may not be reused immediately. Once a function returns and its frame is destroyed, the memory locations that were part of that frame will not be reused until more values must be placed on the stack. If we call another function, its frame will be placed in the next available stack slots, overwriting the recently deallocated memory. Only at this point will the values associated with the deallocated stack frame

change (due to assignments to variables in the new frame). Now writing to memory through the dangling pointer will change variables in that frame in unpredictable ways. Note that is not safe to use a dangling pointer into a deallocated frame even when you have not called another function—even though most stack allocations will come from calling a function, there is nothing to guarantee that those are the only way that the stack is used. In Chapter 12, we will learn how to allocate memory in the heap, rather than in a stack frame. Memory in the heap will remain allocated until we explicitly deallocate it —persisting beyond the lifetime of the function that performed the allocation. 9.6 Sizes of Arrays: size_t In various examples so far, we have represented the size and indices of an array with an int—a signed integer, meaning it can hold positive or negative values. If we think very carefully about this situation, we might wonder why we use a signed int—a negative array index would not be legal, as there is not myArray[-1] (this would be out of bounds).4 This analysis suggests that we should use an unsigned int. However, while we are thinking very carefully about what type we might use, we may as well ask “what is the most correct type to use?” In particular, there are a variety of sizes of unsigned integers—do we want eight bits? 16 bits? 32 bits? 64 bits? For a four- element array, any of these will work just fine. However, we might want to write a more general array manipulation function that works with any size of array. In that case, how large of an unsigned int would we want to use to describe the size of the array and/or index it?

In C, the number of bits we would need varies from one platform to another—on a 32-bit platform (meaning memory addresses are 32 bits), we would want a 32-bit unsigned int; on a 64-bit platform, we would want a 64 bit unsigned int. Fortunately, the designers of C realized this possibility and decided to make a type name for “unsigned integers that describe the size of things”— size_t. Whenever you see size_t, you should think “unsigned int with the right number of bits to describe the size or index of an array.” For example, our closestPoint function would be slightly more correct if we wrote (note the code is the same as in Video 9.4, except that we changed the type of n and i to be size_t instead of int): 1 point * closestPoint(point * s, size_t n, 2 if (n == 0) { 3 return NULL; 4} 5 double bestDistance = computeDistance(s 6 point * bestChoice = &s[0]; 7 for (size_t i = 1; i < n ; i++) { 8 double currentDistance = computeDista 9 if (currentDistance < bestDistance) { 10 bestChoice = &s[i]; 11 bestDistance = currentDistance; 12 } 13 } 14 return bestChoice; 15 } What does “slightly more correct” mean? Practically speaking, it would only make a difference for very large arrays—ones whose size can be represented by a size_t but not an int (e.g., typically more than two billion elements). Such situations will not come up in any of the problems you will do in this book, nor many situations you are likely to encounter as a novice programmer. However, if you become a professional programmer working at a company that routinely deals with huge data sets, it may matter—being in the habit of being precisely correct will

then be an asset to you. You will also see size_t frequently in the C library, so you should know what it means. While we are discussing the sizes of data, it is a good time to introduce the sizeof operator. Recall that you do not actually know how many bytes an int or a pointer is, as their actual sizes can vary from one platform to another. Instead of writing a numerical constant that represents the size on one platform, you should let the C compiler calculate the size of a type for you with the sizeof operator. The sizeof operator takes one operand, which can either be a type name (e.g., sizeof(double)) or an expression (e.g., sizeof(*p)). If the operand is an expression, the compiler figures out the type of that expression (remember expressions have types) and evaluates the size of that type. In either case, sizeof evaluates the number of bytes the type requires. The type of this number of bytes is size_t. Note that sizeof is an operator and not a function. While you will often see it written with parenthesis (e.g., sizeof(expr)) for clarity, it is legal to write it without (e.g., sizeof expr). Recall that earlier, we said that there are certain operations that can be performed on arrays without causing array-to-pointer decay. The sizeof operator is the second such operation that we have seen. If myArray is an array of 4 ints, then sizeof(myArray) will be 4 * sizeof(int), the number of bytes in memory that allocated in the stack frame due to the declaration of myArray. However, you should NOT use sizeof to attempt to determine the number of elements in an array. You may even see such a practice recommended on certain websites that make suggestions to novice programmers,

in the form sizeof(myArray)/sizeof(myArray[0]). Even though it may “seem to work” in some cases, it is a bad idea to use it even in those cases. In particular, it will work in exactly the situations where no array-to-pointer decay has happened, and the compiler “remembers” the original size of the array. This restriction basically means it will have to be in the same function (if you pass the array to another function, it undergoes array-to-pointer decay) and you have the size handy from wherever you declared it. Even if you think that it would be convient to do so in the same function, you are making your code incredibly brittle—if you later decide to pull that code out of the function, you will break it. For example, if you write 1 int myFunction(int x) { 2 int myArray[x+1]; 3 //...some code that fills in myArray 4 size_t size = sizeof(myArray)/ 5 sizeof(myArray[0]); 6 for (size_t i = 0; i < size; i++) { 7 //code using myArray 8} 9 //more code 10 } everything may seem fine. However, if you later decide that the function is growing too large, and you want to abstract it out, you will break your code unless you remember to fix the array size calculation: 1 int myOtherFunction(int * myArray) { 2 //now will compute sizeof(int*)/sizeof(int) 3 //probably size=1 or 2 depending on platform 4 size_t size = sizeof(myArray)/ 5 sizeof(myArray[0]); 6 for (size_t i = 0; i < size; i++) { 7 //code using myArray 8} 9} 10 int myFunction(int x) {

11 int myArray[x+1]; 12 //...some code that fills in myArray 13 int result = myOtherFunction(myArray); 14 //more code 15 } However, if we just wrote this code cleanly to begin with: 1 int myFunction(int x) { 2 size_t size = x+1; 3 int myArray[size]; 4 //...some code that fills in myArray 5 for (size_t i = 0; i < size; i++) { 6 //code using myArray 7} 8 //more code 9} Then we would not have any problems—we would be forced to pass in size to our new function, as if we forgot, the compiler would remind us. The last thing we will note about sizeof is that it is evaluated at compile time. That is, when the compiler translates your code into assembly, it evaluates all sizeof operators. When the program runs, there is no “measurement” of objects at runtime, just use of whatever the compiler determined the size was. 9.7 Practice Exercises Selected questions have links to answers in the back of the book. • Question 9.1 : What is an array? How are arrays stored in C? When you write the name of an array in C, what does it mean conceptually? • Question 9.2 : If you write int x[5];, in the array named x, how many elements are there that are

initialized, and what are the values of the ones that are initialized? • Question 9.3 : If you write int x[5] = \\{4, 6\\};, in the array named x, how many elements are there that are initialized, and what are the values of the ones that are initialized? • Question 9.4 : If you write int x[] = \\{4, 6\\};, in the array named x, how many elements are there that are initialized, and what are the values of the ones that are initialized? • Question 9.5 : What is a “dangling pointer”? What happens if you try to dereference one? • Question 9.6 : Write a main function that calls the closestPoint function we wrote in Video 9.4 and prints out its answer. Put the code for the closestPoint function, as well as an appropriate definition for the point struct and the computeDist function into your file (as well as any #includes you need) so you can run your code. • Question 9.7 : Rewrite the closestPoint function to access the elements of the array with pointer arithmetic, instead of indexing (the resulting code should not use the [] operator). Use the main you wrote in the previous question to test the code out. • Question 9.8 : What is size_t? Why is it more correct to use size_t instead of int to describe the size or index of an array? • Question 9.9 : Write the function: int sumArray(int * array, size_t n);, which returns the sum of the elements in the array passed in (whose length is n). Of course, you should also write a main function that tests your code. • Question 9.10 : Write the function: int arrayContains(int * array, size_t n, int t oFind);, which returns 1 if array

(which has n elements) contains a value equal to toFind, and 0 if it does not. • Question 9.11 : Write the function: size_t maxSeq(int * array, size_t n);, which returns the length of the maximum increasing contiguous subsequence in the array. The parameter n specifies the length of the array. For example, if the array passed in were \\{1, 2, 1, 3, 6, 7, 2, 4, 6, 9\\}, this function would return 4 because the longest sequence of (strictly) increasing numbers in that array is \\ {1, 3, 6, 7\\}, which has length 4. Note that \\ {1, 3, 6, 7, 9\\} is an increasing subsequence but is not contiguous (finding non-contiguous ones efficiently takes techniques we haven’t learned yet). Of course, you should also write a main function that tests your code. • Question 9.12 : Given the following snippet of code: 1 int array[3]; 2 int a; 3 int * p = &array[1]; 4 int * q = &a; 5 int ** r = &p; Group these names a, p, *p, p[1], array[0], array[1], array[2], q, *q, **r, and *r into sets based on the box they name—that is, divide the names in groups such that all names in one group alias each other but do not alias any of the names in other groups. 8 Pointers10 Uses of Pointers Generated on Thu Jun 27 15:08:37 2019 by L T XML

I Introduction to Programming in C9 Arrays11 Interacting with the User and System

Chapter 10 Uses of Pointers Now that we have learned about pointers and arrays, we are ready to see a variety of applications of them: strings, multidimensional arrays, and function pointers. We will also briefly discuss security hazards that can arise in programs with errors related to these topics at the end of this chapter. 10.1 Strings Now that we have learned about pointers and memory, we are finally ready to dive into strings. A string is a sequence of characters, terminated by the null terminator character, ’\\0’ (it has numerical value 0, but the character literal for it is written with a backslash, since you cannot type that character normally. Do not confuse it with ’0’, the digit zero). Since the string is a sequence of characters, it is stored in memory as an array and referenced via a pointer to its first character. The array of characters can be accessed and manipulated in the same ways as any other array. 10.1.1 Strings Literals We have seen string literals so far—a sequence of characters written down in quotation marks, such as \"Hello World\\n\". Now that we understand pointers, we can understand their type: const char *, that is, a pointer to characters that cannot be modified (recall that here, the const modifies the chars that are pointed to). That is, if we wanted to store a string literal in a variable, we might write: 1 const char * str = \"Hello World\\n\"; Figure 10.1: A variable pointing at a string literal. Figure 10.1 illustrates the effect of such a statement and the layout of the string in memory. str is a pointer, pointing at an array of characters. These characters appear in the order of the string and are followed by the null terminator character \\ (note that we do not need to write this character down in the string literal—the compiler adds it for us for literals only). Below the conceptual representation of the string, Figure 10.1 shows its numeric representation—the string is just a sequence of bytes (eight-bit numbers) in memory, the last of which has a numeric value of 0 (do not forget: Everything Is a Number!). Notice that we used const indicating that we cannot modify the characters pointed to by str (that is, assignment to str[i] will result in a compiler error). If we forget the const modifier, unfortunately, the code will still compile (we can receive a warning for this type of mistake with -Wwrite-strings, which is not enabled by default with -Wall because many programmers are sloppy about const anyways—which is not to say that you should be).

However, if we omit const and try to modify the string, the program will crash with a segmentation fault. Figure 10.2: String literals are typically placed in a read-only portion of the static data section. The reason the program will crash if you attempt to modify a string literal is that the data for the string literal is stored into a read-only portion of the static data section. Figure 10.2 shows the variable pointing at the string literal from Figure 10.1 in the context of the “picture of memory” you learned about in Chapter 8. The data for the string literal (the actual bytes that make up the string) reside in the read-only portion of the static data section for the entire lifetime of the program—from the time it is loaded into memory until it exits. This data is placed into memory by the loader—the portion of the operating system that reads the executable file from the disk and initializes its memory appropriately. The loader knows what to write for the string literals (and where they should go in memory) because the compiler writes information into the executable file describing the contents of the data section. After the loader finishes initializing memory, it marks the read-only portions of the static data section as non-writeable in the page table— the structure that the operating system maintains to describe the program’s memory to the hardware. Attempting to write to a read-only portion of memory will behave much like writing to an invalid region of memory—it will cause the hardware to trap into the operating system— transferring execution control from your program to the OS kernel (conceptually, the hardware takes the execution arrow out of your program and puts it into a particular function in the OS, noting where the execution arrow was in case the OS wants to return control to your program). The OS then sees that the program was attempting to access memory in invalid ways and kills it with a segmentation fault. The compiler puts the string literals into a read-only region of memory because the literal may get reused and thus should not be changed. Consider the following code: 1 char * str1 = \"Hello\"; 2 str1[0] = ’J’; //this would crash, but suppose it did not 3 //... 4 char * str2 = \"Hello\"; printf(\"%s\\n\" str2);

5 printf(\"%s\\n\", str2); Both occurrences of the literal \"Hello\" evaluate to pointers to the location where the characters of that string is stored. The compiler is free to put the two identical string literals in one location, meaning str1 and str2 would point at the same memory. If modifying this memory were allowed, printing str2 would print \"Jello\", which would be confusing. In a worse case, modifying string literals could pose a wide range of issues, from strange behaviors to security problems. Note that even if the literal appears in only one place in the program, it may get re-used multiple times (inside a loop, in a function that is called more than once, etc.)—in such a case, our expectation as a programmer is that the literal will always be what we wrote, and it has not been changed by previous code. 10.1.2 Mutable Strings When we want to modify a string, we need the string to reside in writeable memory, such as the frame of a function (or memory that is dynamically allocated by malloc, which we will learn about in Chapter 12). To make space for a string in a function’s frame, we need to declare an array of chars with sufficient space to hold all of its characters plus its null terminator. One way we can declare and initialize our array of characters is like this: 1 char str[] = \"Hello World\\n\"; This code behaves exactly as if we wrote: 1 char str[] = {’H’, ’e’, ’l’, ’l’, ’o’, ’ ’, 2 ’W’, ’o’, ’r’, ’l’ ’d’, ’\\n’, ’\\0’}; That is, it declares a variable str, which is an array of 13 characters (remember that the size of an array may be implicit if we provide an initializer from which the compiler can determine the size), and initializes it by copying the characters of the string \"Hello World\\n\" (including the null terminator) into that array. Being slightly more explicit, one could think of this code as doing: 1 char str[13]; 2 str[0] = ’H’; 3 str[1] = ’e’; 4 str[2] = ’l’; 5 str[3] = ’l’; 6 str[4] = ’o’; 7 str[5] = ’ ’; 8 str[6] = ’W’; 9 str[7] = ’o’; 10 str[8] = ’r’; 11 str[9] = ’l’; 12 str[10] = ’d’; 13 str[11] = ’\\n’; 14 str[12] = ’\\0’; We will note that this type of initialization of an array is the third case in which an array can be used without array-to-pointer decay occuring. The string literal on the left side is treated as an array of characters, not just a pointer to the first one.

Figure 10.3: The difference between a string declared as a pointer to a literal (left) and as an array initialized by a literal (right). Figure 10.3 illustrates the difference between declaring str as const char * str versus char str[]. We can declare the array str with an explicit size, but we must be careful—if we do not include enough space for the null terminator (i.e., we declare it char str[12] = \"Hello World\\n\";), the compiler will not complain. Instead, it will initialize the character array exactly as we have requested, but there will be no ’\\0’ placed at the end. The compiler allows this behavior since it makes for a perfectly valid array of characters, even though it is not a valid string. If we only compute on the array in such ways that it only accesses those 12 characters, our program is fine. However, if we use that array for anything (e.g., pass it to printf or any of the string library functions we will learn about soon) that expects an actual string (i.e., one with a null terminator on the end), then the array will be accessed past its bounds. Failing to terminate the string may not always appear in testing—you might “get lucky” and have the next byte of memory already be 0 anyways. While this may seem nice—your program “works”—it is actually quite a dangerous sort of problem. You may test your program a thousand times and not see any errors, then deploy it and have it crash or produce incorrect results. We strongly recommend the use of tools such as Valgrind, which are capable of detecting this sort of error. It is perfectly fine, however, to request more space than is required for your string. For example, char str[100] = \"Hello World\\n\"; is entirely legitimate. We may wish to request extra space in this fashion if we plan to add to the string, making it longer. Of course, whenever we do so, we must be sure that we have enough space for whatever we may want our string to hold. (Remember that the programmer is responsible for keeping track of the size of her arrays. There is no way to inspect an array and derive its size.) 10.1.3 String Equality Figure 10.4: Applying the == operator to two strings just compares the pointers for equality. Often, programmers want to compare two strings to see if they are equal. Our first inclination might be to use the == operator, which we have already seen. However, the == operator will compare pointer equality. That is, if we write str1 == str2, it will check if str1 and str2 are arrows pointing at the same place. Sometimes pointer equality is what we mean, but more often, we want to check to see if the two strings have the same sequence of characters, even if they are in different locations in memory. This concept is illustrated in Figure 10.4. Video 10.1: Writing a function to compare two strings.

Video 10.1 shows an example of how we might write a function ourselves to test if two strings have the same contents—that is, if they contain exactly the same sequence of characters. Of course, this task is common enough that there is already a function to do it— called strcmp—in string.h of the C library. That function behaves slightly differently than the one we wrote in the example—it returns 0 if the strings are equal and non-zero if they are different. In fact, it returns a positive number if the first string is “greater than” the second string and a negative number if the first string is “less than” the second string. Here “greater than” and “less than” refer to lexicographic order—what you would think of as “alphabetical ordering,” but extended to encompass the fact that strings may have non-letters. The comparison is case-sensitive (so abc is different from Abc), but there is another function strcasecmp, which performs case-insensitive comparison. 10.1.4 String Copying Figure 10.5: Assigning one pointer to another follows the same rules we have always seen. You identify the box named by the left side (in this case str1), evaluate the right side to a value (in this case an arrow pointing at the B in Blueberry, and copy that value (arrow) into the box from the left. Take a moment to look at the situation depicted in Figure 10.5. In this figure, the execution arrow is immediately before the assignment statement str1 = str2;. What do you think will happen when this assignment statement is executed? The short answer is: we will follow the same rules we always have. The right side of the assignment statement (str2) evaluates to an arrow pointing at the second string (\"Blueberry\"). We will take that value (the arrow) and copy it into the box named by the left side of the assignment statement (in this case, str1). The result is that both str1 and str2 point at the same memory location. If we change the contents of one (e.g., we execute str1[0] = ’x’;) then if we “look at” that memory location through its other name (str2[0]), we will “see” the change (remember aliasing from Chapter 8). We may, however, want to actually copy the contents of the string from one location to another. As with comparing for equality, doing this copy yourself requires iterating through the characters of the string and copying them one by one to the destination. In doing so, we must be careful that the destination has sufficient space to receive the string being copied into it. Video 10.2 walks through creating a function to perform this task. Video 10.2: Writing a function to deep copy a string. The C library has a function strncpy, which performs this task for us—it copies a string from one location to another and takes a parameter ( ) telling it the maximum number of characters it is allowed to copy. If the length of the source string is greater than or equal to , then the destination is not null-terminated—a situation the programmer must typically rectify before using the string for any significant purpose. Note that there is a similarly named function, strcpy (the previous one had an “n” in the middle of its name—this one does not). The strcpy function is more dangerous, as there is no way to tell it how much space is available in the destination. If insufficient space is available, then strcpy will simply overwrite whatever follows it in memory, creating a variety of problems. Some of these problems may result in security hazards, as we will discuss in Section 10.4. There is another function strdup, which allocates space for a copy of the string and copies it into that space. However, to understand how strdup works, we need to discuss dynamic allocation in Chapter 12.

10.1.5 Converting from Strings to ints One important thing to remember when using strings is that they cannot be implicitly converted to integers (or floating point types) by casting—either implicit or explicit. Consider the following code fragment: 1 const char * str = \"12345\"; 2 int x = str; Attempting to compile this piece of code results in the error message: initialization makes integer from pointer without a cast This error arises because the assignment does not convert the number the string represents textually into an integer (that is, it does not result in x = 12345). Instead, it would take the numerical value of str (which is a pointer, thus its numerical value is the address in memory where the sequence of characters 12345 is stored) and assign it to x. This behavior follows exactly the rules we have learned for assignment statements: evaluate the right side to a value (which is an arrow, meaning its numerical value is an address), and write it in the box named by the left side. Figure 10.6: Illustration of the difference between 12345 and \"12345\". To help understand why simple assignment does not work, Figure 10.6 gives a peek “under the hood” for code with a char * pointing at the string \"12345\" and an int with the value 12345. The left side of the figure shows the conceptual representation, which we typically work with. On the right side, the figure shows the same state of the program, but with addresses and the numeric values contained in those addresses. The variable str (whose bytes are colored in red) is a pointer, which is eight bytes on this particular system. Its numeric value is the address in memory of the bytes of the string literal \"12345\", which is 0x100000f40. The contents of memory locations 0x100000f40–0x100000f45 are the characters of that string—the numeric values for the characters ’1’ (0x31), ’2’ (0x32), ’3’ (0x33), ’4’ (0x34), ’5’ (0x35), and ’\\0’ (0x00) in that order. The variable x, which is an int, occupies four bytes that hold the value 0x00003039, which is 12345 in decimal. If we were to convince the compiler to allow us to assign x = str, we would copy the value from str (which is 0x100000f40) into x. Of course, since x cannot hold this entire value (remember that on this particular system, pointers are eight bytes, but ints are four bytes), the value will be truncated. x would end up being assigned the value 0x0000f40 (the lowest four bytes of 0x100000f40), which is 3904 in decimal—still not what we want.

Another incorrect (at least for this task) approach would be to write x = *str, dereferencing str to get the value at the end of the arrow, rather than the pointer itself. Here, we would read one character out of the string (*str evaluates to ’1’, which is 0x31). We would then assign this value (0x31) to x. Now, we would end up with x being 0x31 (which is 49 in decimal)—also not what we desire! While the previous example may seem a bit contrived due to the use of a literal string (why not just write int x = 12345;?), consider a more useful example: 1 printf(\"Please enter a number: \"); 2 char * str = readAStringFromTheUser(); //we’ll learn how later 3 int x = str; //they will enter a string. 4 //we’d like to store it as an int... This example not only illustrates why we might want to perform this sort of operation but also leads us into understanding one of the complexities in such a task. What if the user enters xyz? How do we then convert that to a number? For that matter, what if our code instead read (note the “in hexadecimal”): 1 printf(\"Please enter a number in hexadecimal: \"); 2 char * str = readAStringFromTheUser(); //we’ll learn how later 3 int x = str; //they will enter a string. 4 //we’d like to store it as an int... Now, if the user enters the sequence of characters 12345, they do not mean the number 12345 (twelve thousand, three hundred, forty-five), since we told them we would interpret it as hexadecimal. Instead it is 74565 in decimal (you can work out this conversion yourself for practice). If we wanted to perform such a conversion ourselves by hand, we would need to iterate over the characters in the string and perform math. However, as this type of conversion is a common task, there are C library functions that perform it for us. The atoi function is the simplest of these—it converts a string to an integer by interpreting the sequence of characters as a decimal number. If there is no valid number at the start, it returns 0. A slightly more complex function is strtol, which lets you specify the base (decimal, hexadecimal, etc.), as well as to pass in the address of a char *, which it will fill in with a pointer to the first character after the number. That is, if you give it the string \"123xyz\", it will set this pointer to point at the x (you can also pass in NULL if you do not need this extra information, in which case it skips this part). This concept can be a little bit confusing at first, as you are used to seeing the textual representation of a number (e.g., its decimal form written on paper and thinking of it as the number itself). The best way to understand this concept is to write these functions that convert from strings to ints yourself (in general, it is best to learn by doing). See the practice questions at the end of this chapter. 10.1.6 Standard Library Functions We have already seen a few examples of string-related functions from the C library. However, there are many more available, as string manipulation is a common task in programming. As a general rule of thumb, if you think “I bet all programmers want to do (something) to strings regularly,” then it is quite likely that the C library has a function to do that thing to strings—concatenate them, find a character in them, find their length, look for one string inside another, etc. You can read about all of these functions in their man pages (if you are not familiar with man pages, see Section B.2). You can also consult man string for a list of all of the string-

related functions and their respective prototypes to help you find what you are looking for if you do not know its name. 10.2 Multidimensional Arrays In Chapter 9, we learned about arrays, which let us store a sequence of elements of the same type and access a particular element by indexing into the array. We can expand on this concept with multidimensional arrays. For example, we might want to represent a mathematical matrix (which is conceptually rectangular, rather than linear) as a two- dimensional array of numbers or an image with a two-dimensional array of colors. If we wanted to have an array of strings, we would actually end up with a two-dimensional array of characters, as strings are themselves arrays of characters. As always, deciding how to represent your data is part of Step 2 of your algorithmic design process, in which you figure out exactly what it was that you did in Step 1. In Chapter 8, you learned that data that is represented as a sequence of elements of the same type is naturally represented as an array. This concept extends to multidimensional arrays whenever your data naturally occurs in a higher dimensional organization. You can create multidimensional arrays with any number of dimensions, so you can represent data of any number of dimensions that you want. For example, if your program works with data that is organized by day of the year, then within each day, by hour of the day, and within each hour by room number within a building, then a natural representation would be a three- dimensional array: . 10.2.1 Declaration In C, multidimensional arrays are arrays of arrays—a two-dimensional array is an array whose elements are one-dimensional arrays; a three-dimensional array is an array whose elements are two-dimensional arrays; and so on. Accordingly, we declare them with multiple sets of square brackets, each indicating the size of the corresponding dimension. For example, we might declare a two-dimensional array of doubles that is four elements by three elements (e.g., to use as a mathematical matrix) like this: 1 double myMatrix[4][3]; Figure 10.7: Left: conceptual layout of a matrix. Right: in-memory layout of myMatrix[4][3]. Declaring myMatrix in this fashion results in an array with four elements. Each of the elements of myMatrix is an array of three doubles. Accordingly, myMatrix occupies (4 * 3 * sizeof(double)) bytes of memory, with the three elements of myMatrix[0] appearing together, followed by the three elements of myMatrix[1], and so on. Figure 10.7 depicts this layout on the right, as well as the conceptual (i.e., rectangular) layout of the matrix on the

left. In both sides of the figure, the zeroth element (“row”) of myMatrix is colored green, the first is colored pink, the second blue, and the third orange, so that you can easily see how the data is laid out. The particular addresses are not important (and are just examples—they would change from program to program), but are intended to show how the elements are all consecutive in memory. 10.2.2 Indexing Multidimensional Arrays If we were to write myMatrix[i] (where i is some integer type), then we would expect that expression to evaluate to the element of myMatrix according to the rules that we learned in Section 8.7. For example, if we wrote myMatrix[2], we would expect that to evaluate to the second element of myMatrix, which is the three blue boxes in Figure 10.7. This element is an array of three doubles, so we would expect the type to be double *, and as the first element of that array is at 0x7fff5c346b30 (in this particular example), we would expect that to be the value of the expression (as we represent arrays by a pointer to their first element). If you expect all of these things (based on what you have already learned), you would be correct. We may wish to index the two-dimensional array twice, such as myMatrix[2][1]. When the program evaluates this expression, it will first evaluate myMatrix[2], obtaining a pointer to the three-element array that is the second element of myMatrix. Then, it will index that array (which is an array of doubles), and evaluate to a double. Of course, myMatrix[2][1] is an lvalue, as it names a particular box, so we can use it on the left side of an assignment, e.g, myMatrix[2][1] = 3.14;. However, we should note that myMatrix[2] behaves just like any other array. While the C standard calls it an lvalue, but not a modifiable lvalue, it does not have a box of its own (as you should recall from Chapter 8). The pointer that myMatrix[2] evaluates to is not actually stored anywhere, it is just calculated by pointer arithmetic from myMatrix. 10.2.3 Multidimensional Array Initializers We can initialize a multidimensional array in the same line that we declare it by using a braced initializer, as we can for a one-dimensional array. In the case of a multidimensional array, we should remember that each element of the array is itself an array, and write a braced initializer for it:1 1 double myMatrix[4][3] = { {1.0, 2.5, 3.2}, //elements of myMatrix[0] 2 {7.9, 1.2, 9.9}, //elements of myMatrix[1] 3 {8.8, 3.4, 0.0}, //elements of myMatrix[2] 4 {4.5, 9.2, 1.6} }; //elements of myMatrix[3] When we initialize an array in this fashion we can leave off the first dimension, as the compiler can determine how many elements there are from the initializer: 1 //also legal: removed the 4 from the [] //elements of myMatrix[0] //elements of myMatrix[1] 2 double myMatrix[][3] = { {1.0, 2.5, 3.2}, //elements of myMatrix[2] 3 {7.9, 1.2, 9.9}, //elements of myMatrix[3] 4 {8.8, 3.4, 0.0}, 5 {4.5, 9.2, 1.6} }; You may not elide the second dimension’s size specification, even when you provide a complete initializer. You may also elide the first dimension’s size when you are declaring a parameter for a function, but may not elide any other dimension’s size. A multidimensional array is not limited to two dimensions. For more dimensions, you can write additional []s specifying the size of each additional dimension: 1 int x[4][2][7]; //x is a 3D array, with 4 elements, each of which is //an array with 2 elements

//a a ay w t e e e ts 32 // (whose elements are 7-element arrays of ints) 4 char s[88][99][122][44]; //s is a 4D array of chars: 88 x 99 x 122 x 44. All of the same rules apply to these arrays with more dimensions. If we write x[1], we get a pointer to the two-dimensional array that is the first element of x. If we write x[1][1], we get a pointer to the one-dimensional array of ints that is the first element of that array, and if we write x[1][1][4], we get the int that is the fourth element of that array. We can also initialize these arrays with braced initializers if we want to (although writing the initializer for a large array with many dimensions will likely take a significant amount of time). 10.2.4 Array of Pointers (to Arrays) We can also represent multidimensional data with arrays that explicitly hold pointers to other arrays. For example, we might write the following: 1 double row0[3]; 2 double row1[3]; 3 double row2[3]; 4 double row3[3]; 5 double * myMatrix[4] = {row0, row1, row2, row3}; Here, we again have a matrix; however, this matrix is represented in a rather different fashion in memory. Here, myMatrix is an array of four pointers, each of which explicitly points at an array that represents a row of the matrix. Figure 10.8: Left: conceptual layout of a matrix as an array of pointers. Right: in-memory layout of this array of pointers. Figure 10.8 illustrates the layout of this data structure. On the left, this figure depicts the conceptual representation of this data structure: myMatrix is an array of four pointers, and each of these pointers points at one of the arrays row0–row3. The right side of this figure depicts the in-memory layout of this data structure. Here, each of the row arrays may not be next to each other in memory (they might be, but do not have to be). The four entries of myMatrix now hold pointers to (the addresses of) the four row arrays. Elements of the arrays are accessed in similar ways for both representations. For either representation, myMatrix[2], evaluates to a pointer to the array that is the second row of the matrix. Likewise, myMatrix[2][1] evaluates to the double in the first column of the second row of the matrix.

However, there are some significant differences. First, in this array of pointers representation, the pointers to the rows are explicitly stored in memory. Accordingly, evaluating myMatrix[i] actually involves reading a value from memory, not just computing an offset. This difference has performance implications, which we will not go into here, as we are not prepared to discuss performance (such a discussion requires a detailed knowledge of hardware). Explicitly storing the pointers to the rows of the matrix allows us to do some things with this representation we cannot do with the first representation. First, we are not constrained to having each row be the same size as the other rows. Second, in the array of pointers representation, myMatrix[i] is a modifiable lvalue (recall that it is not if we just declare an array with multiple dimensions), and has a “box” (memory location) of its own. Accordingly, we can change where the pointers point if we so desire. Third, we can have two rows point at the exact same array (aliasing each other). While these abilities may not be terribly useful for a mathematical matrix, they can be incredibly useful for a variety of other tasks that have data with multiple dimensions. This array of pointers representation will also prove quite useful when we learn about dynamic allocation in Chapter 12. 10.2.5 Incompatibility of Representation One aspect of multidimensional arrays that often confuses novice C programmers is that these two ways to represent multidimensional data are not compatible with each other—they are different types and cannot be implicitly converted from one to the other. In fact, if you try to explicitly convert from one to the other (via a cast), you will get results ranging from nonsensical answers to your program crashing. This common problem underscores the importance of knowing the exact meaning of the types you declare and fully understanding the semantics of every line of code that you write. Video 10.3: An illustration of why casting between incompatible representations can cause your program to crash. Video 10.3 illustrates an example of what can go wrong when a programmer naïvely inserts a cast to “fix” a compiler error without understanding the implications of what he is doing. In this example, the program crashes, although far worse consequences are possible. Recall from Section 6.1.4 that a program that gives the wrong answer (with no indication that something went wrong) is often far worse than a program that crashes. It is possible that we could instead read or write values we did not intend to and produce bogus results. 10.2.6 Arrays of Strings As we mentioned earlier, an array of strings is inherently a multidimensional array of characters, as strings themselves are really just arrays of characters. Accordingly, all the same rules apply to arrays of strings, and we can use either representation that we want. However, as arrays of strings are fairly important (among other things as we shall see in Section 11.2, the program can access its command line arguments via an array of strings), it is worth discussing them explicitly. Consider the following two statements, each of which declares a multidimensional array of chars, and initializes it with a braced array of string literals: 1 char strs[3][4] = {\"Abc\", \"def\", \"ghi\"}; 2 char chrs[3][3] = {\"Abc\", \"def\", \"ghi\"}; Observe that the difference between the two declarations is the size of the second dimension of the array—which is four in the first statement and three in the second. The first statement (which declares strs) includes space for the null terminator, which is required to make the

sequence of characters a valid string. The second statement, which declares chrs, does not include such space and only stores the characters that were written (with no null terminator). Figure 10.9 illustrates the effects of the two statements. Figure 10.9: Two declarations of multidimensional arrays of characters, initialized with strings. This second statement is correct if (and only if) we intend to use chrs only as a multidimensional array of characters and not use its elements for anything that expects a null-terminated string. As the second makes a valid multidimensional array of chars, it is not illegal and will not produce an error or a warning. This behavior is much the same as we discussed in Section 10.1.2 for just declaring arrays of characters and initializing them from string literals. However, a significant difference is that in the multidimensional case, we cannot omit the size from the second dimension (which is the number of characters in each string), as C allows us to omit only the first dimension of a multidimensional array. If you declare a multidimensional array of chars to hold strings of different lengths, then you must size the second dimension according to the length of the longest string. For example, we might declare the following array: 1 char words[4][10] = {\"A\", \"cat\", \"likes\", \"sleeping.\"}; In this example, words requires 40 characters of storage despite the fact that the strings used to initialize it only occupy 22 characters. This representation wastes some space. While that waste may not be significant in this example, if we were instead looking at millions of strings with lengths that vary greatly, we might be wasting megabytes. Figure 10.10: An array of strings (i.e., an array of pointers to sequences of chars ending in a null terminator). We might instead use the array-of-pointers representation for an array of strings. As we previously discussed, representing multidimensional data with an array of pointers allows us to have items of different lengths, which naturally solves the problem of wasted space. To represent our array of strings in this fashion, we might declare and initialize words as follows: 1 const char * words[] = {\"A\", \"cat\", \"likes\", \"sleeping.\"}; Observe that here, we declare words as an array of const char *s—the elements of the array are pointers to const chars, and thus the chars they point to may not be modified. We should include the const (and must include it to be const-correct) as we have indicated that words should be initialized to pointers to string literals, which are in read-only memory (as discussed in Section 10.1.1). Figure 10.10 illustrates the layout of words.