Review Sheet for ESE 116, Spring 2008: Quiz 2

Important General Information About the Quiz:

• The quiz will be on Tuesday, March 4th, in Moore 216
• All material up to and including last Tuesday's lecture will be covered, the focus will be on C and C related material.
• The TA's who wrote this review sheet have not seen the test, so this sheet gives no unfair advantage.
• No books, notes, or extra material will be allowed on the test.
• Unless otherwise stated above, any material from labs, homeworks, or lectures is free game.
• This review sheet is extensive, but not exhaustive.  Just because it is not on this review sheet, does not mean it is not on the test.

General Material on the Quiz

• Similarities between C and Java:
  • Both C and Java start from a main() function
  • Both procedural languages (function / method based)
  • All of the flow statements are the same (if, while, etc)
  • Code blocking with {} is the same
  • The math and logic operators are the same (*, /, %, <, <=, ++, --, (cast), &&, |, etc)
  • The Java primitive data types are matched in C (char, int, long, etc)
  • Casting of primitive types works in the same way, with the same syntax
  • Additional information about type casting can be found here, as linked to from the packets hw
• Differences between C and Java:
  • C is compiled into a binary executable, then run on the metal of the machine. 
  • Java is compiled into bytecode, then run by the Java Runtime Environment. 
  • Because Java requires a special environment to run whereas C is compiled to an executable, C is inherently faster than Java.
  • This is also true because of the Java Garbage Collector
  • C has no "final" operator. "const" or #define is used
  • In Java, everything that is a 'primitive' is a non-pointer, and everything that is not a primitive is a 'pointer'. 
  • In C, you can use the * operator to make any data type a pointer, and the & operator to get the address of any variable
  • C has no boolean. 'ints' are used instead.
    • Consequently, test expressions inside of if statements are considered false if 0, true otherwise.
  • for() loops cannot have variables declared inside the for conditional
    • for(int i = 0; i < 100; i++) is not allowed
    • The above code causes a C99 error, variables must be declared outside the for loop
  • C has no garbage collector. Everything created by dynamic memory allocation (malloc) must be freed explicitly by free()
  • In C, function parameters are passed by value
  • For example, if a function called foo() is defined as
    

    void foo(int param){
     param = 5;
    }

    and it is called like

    int x = 0;
    foo(x);

    the value of x is still 0, because when foo() was called, the value was copied into a local variable called param
  • When arrays are passed as parameters, a local copy is not made.  
  • Instead, the location of the array in memory is passed
  • Therefore, when you modify the array in the called function, it is the same array as the calling function
  • More on arrays to follow...
  • C has no function overloading.
    • Function overloading is when two functions have the same name, but different parameters. The compiler chooses the function to call based on the parameters passed to it.
    • In C, all functions must have different names.
  • In general, the C compiler is less strict at compile time then the Java compiler & the running C program is not forgiving at all:
    • Accessing a piece of data off of the end of an array will not show up at compile time, and will result in a crash at runtime, with no indication that it was an arrayOutOfBounds
    • C allows you to get away with stuff like this with no errors or warnings (DO NOT DO THIS):

    • if(x = 1){}

  • C has no objects. On the other hand, all code in Java must be included inside objects. This has many consequences:
    • There are no constructors, member functions, or instance variables in C.
    • C has no encapsulation
    • C has no function scope
    • C has no instanceof, or equivalent
    • C has no "static", as everything is static
    • In Java, all arrays are classes. In C, arrays are pointers to contiguous spots in memory.
• Basic C concepts
  • C was created by Dennis Ritchie 1969-1973
  • C data types:
    • int: A Integer.
      • In the original C specification, a int was 16 bits wide and could hold numbers from -32,768 to +32,767.
      • However, bit width is now compiler specific.
      • The gcc compiler uses 32 bits for a int, so the range is from -2,147,483,648 to +2,147,483,647.
    • long: A long Integer.
      • In the original C specification, this was 32 bits wide. However in gcc, it is the same as a normal int.
    • float: A floating point number
      • A decimal number with a width of 32bits
    • double: A floating point number with double the width as a float
      • A decimal number with a width of 64 bits.
    • char: A single ASCII character
      • 8 bits wide in gcc, holds a single character.
      • An array of characters that is null terminated ('\0') is a string.
    • short: A short Integer.
      • A signed integer with a width of 16 bits. Holds -32768 to +32767
    • unsigned int: A positive integer (>= 0).
      • In unsigned ints we don't store negative numbers, so the 32 bit range is from 0 to +4,294,967,295
  • Macro Usage
    • Where is the preprocessor?
    • #include:
      • Usage: #include (either <filename> or "filename")
        • Use "" when the file you are including is in the same directory as the C file
        • Use <> when the file you are including is in the default C library directory
        • Typically, use <> for C / ANSI / system libraries, and "" for your own h files
    • #define
      • Usage: #define (thing to replace) (thing to replace it with)
        • Searches through the C file before it is compiled, replaces every instance of the thing to replace with the thing to replace it with. The thing to replace must not have spaces. It will replace it with everything that is between the following space and the end of the line
      • Example:
        • #define FALSE 0
          • Replaces all FALSE statements with 0's before compiling
        • #define TRUE 1
          • Replaces all TRUE statements with 1's before compiling
        • #define MYNAME Luciano Cheng
          • Replaces all MYNAME statements with "Luciano Cheng" before compiling
  • The main() function:
    • Returns an int. The return value can be used to indicate to the OS whether the program completed successfully or not.
    • Can either take no parameters or two parameters:
      • int main(): No parameters
      • int main(int argc, char* argv[]): Two parameters. argv is a array of strings, where a string is an array of characters. argc is the size of the argv array.
    • The main function should return EXIT_SUCCESS or EXIT_FAILURE under all cases.
    • These are defined in stdlib.h
  • The printf() function
    • Format: printf(char* printed_string, <variable for type 1>, <variable for type 2>, ...);
    • printf takes a string as the first argument. 
    • This string may or may not have %?'s in themwhere the ? denotes a certain variable type to be replaced by a variable following the string

      • printf("Hello, my name is %s and I am %d\n", "Luke", 18);

    • There are a number of parameters that printf can take for arguments:
      • %d; decimal: either long, short, or int
      • %s; string: A array of characters or a literal string with ""
      • %f; A float: NOT THE SAME AS A DOUBLE, if you want to print a double you must cast it as a float first
      • %c; A single character
      • %x; A hexadecimal number
      • There are others, you can look up the printf() man page for more information
  • The switch() call
    • The switch call works very similar to the way it works in Java.
      • Each switch call starts with a switch(variable), then an open bracket "{"
      • Inside the bracket are a series of cases, where each case is followed by a literal and then a ":"

        • case 1:

      • A case cannot use any sort of comparison (<, >, etc), and must be a literal
      • Literals are values that are not variables (1, 3, 6, 'x', 'j', 4.434)
        
      • The variable being switched on is compared against each literal in order. 
      • If the variable equals the literal, the case is taken.
      • The case statements fall through, so if there is no "break" call, execution will continue into the next case statement until the end of the switch statement is reached.
      • The "default" case is taken if no other cases are taken.
      • Detailed C switch format can be found in the wikipedia entry, as linked to from the first homework.
  • The getchar() function
  • returns a single byte of data read in from stdin, which for our purposes is the keyboard
  • blocks until the user inputs a character into the keyboard
  • 'blocking' means the program waits for the user to respond
  • returns an int, not a char.  To treat this value as a char, you have to either
  • assign it to a char variable, which will cast it automatically
  • cast it explicitly
  • If the user hits (CTRL+D) it sends an EOF to getchar().  A EOF is #define'd as -1 on most systems, including
    eniac.
  • More information about getchar() can be found on the getchar() man page
  • The scanf() function
    • Same parameters as the printf() call, except it reads in data from stdin (or the terminal, in our case).
    • Addresses are passed instead of variables. For normal (non-pointer) variables, the & operator must be used:

      • int i;
        scanf("%d\n", &i);

  • Arrays:
    • Collections of the same datatype, stored contiguously in memory
    • No mixed types (chars and ints in the same array)
    • Memory addresses where data is stored are next to each other.
    • Accessed using the [] operator

    • int x = 0;
      x = my_array[3];

    • Declared using the following format:

      • int hello[SIZE];

    • Or the following format:
    • data = {18, 33, 14, 5, 2}
    • C arrays have no '.length' option, you must keep track of the array size yourself
    • C will let you go out of bounds on an array, with undefined behavior
    • undefined behavior means it may crash, it may not ... which is bad and best avoided
    • Strings (arrays of chars) are null '\0' terminated. 
    • The last character of the string in the array is followed by a '\0' character.
    • The Array Tutorial (as linked to from the packets homework) is extremely detailed and helpful
  • Compiling:
    • gcc:
      • USAGE: gcc <files> -o <destination output binary>
      • Add the -Wall flag to get warnings

Pointers, Addresses, and Arrays:

• In C, you are given free range to (attempt to) access (read or write) any memory address you can imagine.
  • "With great power, comes great responsibility" - Spiderman
  • Remember, the program is only as smart and safe as the programmer.
• Addresses:
  • At the machine level, the memory the program runs in is accessed by address numbers
  • The address of any variable can be retrieved using the & operator:

    int x = 5;
    printf("The address %d halds the value %d in it\n", &x, x); // address as int which may be negative
    printf("The address %u halds the value %d in it\n", &x, x); // address as unsigned (positive) int
    printf("The address %x holds the value %d in it\n", &x, x); // address in hex (base 16) 

• Pointers:
  • A C pointer is a variable designed to hold a memory address of a particular data type.
  • We say that a pointer points to an address in memory (whereas C arrays are addresses in memory)
  • Pointers are declared using the * operator and the data type you want to point to, e.g.:

    char *x; // x is a pointer to char; its type is char *
    int *y; // y is a pointer to int; its type is int * 

  • Pointers can be assigned values just like any other variable, except they hold addresses:

     char *myPointer;
     char myChar = 'a';
     myPointer = &myChar;            

  • Pointers are dereferenced with the * operator (and in some cases with the [] operator, discussed below)
  • Dereferencing means "getting the value at the address I am pointing to"
  • The * operator takes the address stored in the pointer, and gets the value at that address. Example:

    char *myPointer;
    char myChar = 'b';
    myPointer = &myChar;
    printf("myPointer dereferenced is %c\n", *myPointer); // prints "myPointer dereferenced is b"
        

  • You can also use the dereference operator to assign a value to a pointer

    char a;
    char *myPointer = &a;
    *myPointer = 'b'; 

  • C pointers point to an address in memory (whereas C arrays are addresses in memory)
    • For engineering purposes, and to distinguish address values from other values, we typically use hexadecimal (base 16) values when expressing addresses
    • In C, hexadecimal values are expressed with a '0x' in front. So the hexadecimal value of 1, expressed in 32 bits, is 0x00000001. Each digit represents 4 bits (16 possibilities), with values 0-9 and A-F
  • Pointer arithmetic
    • You can do calculatons ("pointer arithmetic") with pointers, typically to walk them through arrays.
      • You can use an array to calculate an address:
        

        char my_array[3];
        char* my_pointer;
        my_pointer = my_array + 3;

      • BUT, You CAN NOT do pointer arithmatic that changes the address of an array
        

        char my_array[3];
        my_array = my_array + 3; // This will fail; you cannot change the address of an array EVER!

    • A pointer to data type T is incremented by the number of bytes in T
      • For example, the following code would increment myPointer by the number of bytes in an int (machine dependent).
        int a[3] = {0, 1, 2}; int *myPointer = a; myPointer++; printf("myPointer dereferenced is %d\n", *myPointer); // prints "myPointer dereferenced is 1"
    • Other valid operations:
      

         myPointer--;
         myPointer + 1;
         myPointer + i;           

    • Can be used to loop through arrays:
      • Example of an array traversed with pointer notation
        

        char word[] = "hello"
        
        char *p;
        for(p = word; *p != '\0'; p++){
           printf("%c", *p);
        } 

  • Pointers and the [] operator.
    
    • The [] operator may be used in conjuction with a pointer.
    • This works if the pointer is pointing to
      • an array
      • a sequence of data items in contiguous memory, that all have the same type.
    • For a pointer p to type T, the expression p[num] accesses the value at address (p + num*(sizeof T in bytes))
  • myPointer[3] is equivalent to *(myPointer + 3)

    int intArray[5] = {0, 5, 10, 15, 20};
    int *myPointer;
    myPointer = intArray;
    printf("(myPointer+3) dereferenced is %d\n", myPointer[3]); // prints "(myPointer + 3) dereferenced is 15"

  • Pointers with functions
    • A pointer can be passed to a function as an argument.
    • A function can then use the pointer to change the value at the address the pointer has stored.
      • The following example would modify the variable 'myChar' inside main():

        int main(int argc, char* argv[]){
           char myChar;
           foo(&myChar);
        }
        
        void foo(char* myCharPointer){
           *myCharPointer = 'a';
        }               

      • As demonstrated above, typically the & operator and functions with pointer arguments are used to mimic passing values by reference, by passing pointers by value.
    • Functions can also return pointers
      • The following function returns a pointer to the second element in an array:
        

        char* foo(char* myArray){
           return myArray+1;
        }

      • Don't return pointers to local variables declared within the function! They "disappear" when the function exits!
        • Local variables are stored on the stack
        • Once a function returns, the local variables are no longer valid.
        • Moreover, the area on the stack where they were stored may be overwritten by stack frames for subsequent function calls.
  • Pointers to NULL:
    • Typically, if we don't want the pointer pointing out into never-never land, we set the pointer equal to NULL.
      • NULL is #defined in stdlib.h and stdio.h to be '\0'
      • NULL is of value 0x00000000, no variable in our program will ever get allocated at this address, so a pointer will only point there if we explicitly tell it to.
      • We can then compare our pointer to NULL:
        

        if(myPointer == NULL) { do something }

      • Pointers can also be compared to one another, to see if they point to the same thing:
        

        if(myPointer == yourPointer) printf("We're pointing to the same thing!\n");

  • Overloading:
    • The * operator is overloaded; it can mean a number of different things based on the context
      • Multiplication:
        

        int a = 8 * 5; 

      • Pointer Declaration
        

        char *a; 

      • Pointer Dereferencing
        

        *a = 'c'; // where a is a pointer to a char

      • All of these uses are completely different, they just all happen to use the same character. Do not confuse them.
  • sizeof()
    • sizeof() returns the size of a datatype in bytes
      • sizeof(int) will return 4 on a 32 bit machine (where the size of an int is 4 bytes),
      • sizeof(int) would return 2 on a 16 bit machine, 8 on a 64 bit machine..
    • The size of a struct is machine and compiler dependent.
• Arrays:
  • C arrays are contiguous blocks of memory, where the array name is the address of the beginning of the block
    • Allocating an array of ten chars called temp, starting at memory space 0x00000050 would:
      • occupy addresses 0x00000050 to 0x00000059 (assuming (sizeof char) is 1)
      • cause the value of temp to be 0x00000050
  • Arrays are declared using the [] notation and the name of the element datatype
    • The Code char hello[5];
      • Allocates 5x(the byte size of char) memory spaces
      • Points 'hello' to the first space
    • The & operator can be used in conjunction with the [] operator, to return an address at a offset:
      • &hello[2] will return the address at hello offset by 2
      • Same thing as hello + 2
    • A array name in C is similar but not exactly the same as a pointer in C.
      • In particular, Arrays automatically allocate space, but can't be relocated.
      • Eg, the following would be invalid:
        

           char a[50] = "hello";
           a++;
                

      • For more information about the differences between pointers and array names, read this fantastic FAQ
  • Array names point to the first address in a set of contiguous memory addresses, pointers point to a memory address...
    • Therefore, a pointer can be assigned to the address the first element in an array, or any element if you use pointer arithmetic

      char* myPointer;
      char myString[50] = "hello";
      myPointer = myString;

  • 2D arrays can be declared and accessed using 2 sets of []'s:
    

        int myMatrix[4][4];
        myMatrix[0][0] = 1;

Strings, string.h and NULL termination:

• Definition:
  • A string in C is a NULL terminated sequence of characters
    • NULL is represented as '\0', ASCII number 0, or 'NULL' which is #defined in stdio.h
  • In C, strings are stored in arrays of chars
  • If a character array is to hold a string, it must be at least of size (string length + 1) to handle the NULL character at the end.
• Declaring a string:
  • If you use the double quotes when you declare, C will NULL terminate the declared string automatically. Otherwise, you must do it yourself.

       char myString[80] = "I am a string yay!";
       char myString[] = "I am a string yay!";
       char myString[] = {'I', ' ', 'a', 'm', ' ', 'a', ' ', 's', 't', 'r', 'i', 'n', 'g', ' ', 'y', 'a', 'y', '!', '\0'};

  • Using the * method of string declaration will declare allocate the string in the static / stoic data area.
    • It will not get reallocated every time the function is called.
    • The string values cannot be changed:

      char *myString = "I am a unchangeable string yay!";

• Constructing a string from chars:
  • A string is just a sequence of chars that is NULL terminated
    • You can construct a string from chars by storing them correctly in a char array
    • You must remember to NULL terminate!
      

        char myString[5];
        myString[0] = 'H';
        myString[1] = 'i';
        myString[2] = '\0';
            

  • Any data stored after the NULL in the string is in the array, but not considered part of the string.
    • For C strings, the '\0' is where the sidewalk ends
  • Other useful chars / #defines:
    • '\n' is a newline
    • '\t' is a tab
    • EOF means End of File, which is #define'd as -1
• string.h library:
  • string.h is a library filled with useful functions that operate on strings.
  • All functions in string.h require NULL terminated string parameters.
    • Non NULL-terminated parameters will cause the function to run off the edge of the array looking for the NULL, causing segmentation faults
    • You must pass the string.h functions a character array or a pointer to a character array
      • You cannot pass a char ... it will crash
      • You cannot pass NULL ... it will crash
  • You cannot use the '==' operator when comparing strings
    • The '==' compares the addresses of the arrays / pointers, not their contents
  • Functions that we expect you to know, code, and debug:
    • strlen()
      • Format: int strlen(char* str)

        int result = 0;
        char test[10] = "hello";
        result = strlen(test); 

      • Returns the length of the string
      • Does not include the NULL character in the length
    • strcmp()
      • Format: int strcmp(char* str1, char* str2)

        int result = 0;
        char test1[10] = "hello";
        result = strcmp(test1, "goodbye");

      • Returns 0 if the strings are equal
      • Returns > 0 if first non-matching char in str1 > first non-matching char in str2
        • Meaning, returns > 0 if str1 > str2 in ASCII order
        • Meaning, returns > 0 if str2 is alphanumerically before str1
      • Otherwise, returns < 0
    • strncmp()
      • Format: int strncmp(char* str1, char* str2, size_t num);
        

        int result = 0;
        char test1[10] = "good";
        result = strcmp(test1, "goodbye", 4);

      • Same as strcmp, except only compares it for the first n characters
      • size_t is the same as unsigned int
    • strcpy()
      • Format: char* strcpy(char* dest, char* src);
        

        char source[10] = "mytest";
        char destination[10];
        char* ptr_to_dest;
        ptr_to_dest = strcpy(destination, source);

      • Returns dest
      • Copies the string in src to dest.
      • dest must be large enough to hold the string in src + the NULL
    • strncpy()
      • Format: char* strncpy(char* dest, char* src, size_t num);
        

        char source[10] = "mytest";
        char destination[10];
        char* ptr_to_dest;
        ptr_to_dest = strncpy(destination, source, 3);

      • Returns dest
      • Copies the string in src to dest for the first num characters, then NULL terminates the string in dest
      • dest must be large enough to hold the string up to num characters + the NULL
      • size_t is the same as unsigned int
• Functions that we expect you to recognize and understand, but not code:
  • strcat()
    • Format: char* strcat(char* dest, char* src);
      

      char str1[20] = "hello ";
      char str2[20] = "world";
      char* ptr_to_dest;
      ptr_to_dest = strcat(str1, str2);

    • Returns dest
    • Concatenates src onto dest
    • src must be big enough to hold src + dest + NULL
  • strrchr()
    • Format: char* strrchr(char* str, char c);
      

      char str1[20] = "abcdefg";
      char* ptr_to_found_char;
      ptr_to_dest = strcat(str1, 'c');

    • Returns a pointer to the last occurrence of the char c in str

• The Memory / Stack Model
• C gives you free access to memory, whereas Java tends to keep you in a safe sandbox. However, with great power comes great responsibility:
  • In C, you are free to access the address of any variable using the & operator. This includes system space and other things you should not be accessing. 
  • You must be careful in writing your code to make sure your memory accesses are accurate, there is no throwing of exceptions in C.
    • C is not type safe: The C compiler will allow you to assign any other variable to any other variable, no matter the type, with little more than a warning. It assumes you know what you are doing. You must be careful.
  • Dynamic variables are created using the malloc() operator, like the "new" operator in Java
  • Memory is freed with the "free()" function. In Java this is handled automatically
• When a C program is first started, through the magic of Virtual Memory, the OS gives the program a contiguous address space on which to run.
  • The DATA is initially stored in the memory space. This contains all the information relating to the instructions in the functions, and the amount of memory each function requires on the stack
  • The HEAP grows downward. The heap contains all the memory you allocate using the malloc() call
  • The STACK grows upward. The stack contains all the memory you allocate with your function calls.
  • This diagram is extremely helpful in explaining this topic