C-Lab 1 - Introduction to C

CS3410 Spring 2014

Please submit required documents to CMS

To receive participation credit, you must sign in!

You must work ALONE for this and all other labs and homeworks. Failure to adhere to this rule will result in an Academic Integrity Violation. You will only be able to work in groups for projects. Updates to this assignment will be posted on the course web page.

We recommend that you work on CSUG machines for this lab.
For Linux and Mac users, simply type: 'ssh netid@csugXX.csuglab.cornell.edu' into the terminal. (Replace XX with a number between 01-14 and netid with your netID. Do not include quotes.)
For Windows users, download an SSH client.
The recommended SSH client is PuTTY. To connect to CSUG machines using PuTTY:
1.) Open PuTTY
2.) Under Host Name enter: 'netid@csugXX.csuglab.cornell.edu' (Replace XX with a number between 01-14 and netid with your netID. Do not include quotes.)
3.) Press Open
4.) A window labeled 'PuTTY Security Alert' should pop-up which provides a warning about the host key. Click Yes.
5.) You are connected.

Overview

In this lab we will write a C program that manipulates memory with pointers and test it with Valgrind.

References. Searching the Internet will generally find an answer to nearly any conceivable question about the C programming language. However, information on the Web is not always accurate or complete. We recommend reference books over web sites. In particular, C: A Reference Manual (5th Edition) by Samuel P. Harbison and Guy L. Steele Jr. is a required textbook for this class and should be your first source for reliable information on C. For more information relating to today's lab see pages 136-140 in Chapter 5.

The structure of a C module

Preprocessor directives
Global declarations
Global variables
Function declarations

A C module is a text .c file containing a collection of related functions and an associated .h file containing corresponding function declarations. The source code (text) is in the .c file which is transformed by the C compiler into a .o object file. A C module may reference or call a function in a different C module by including its .h file (header). Finally, a linker combines several .o files into an executable binary (a program).

A C program is created by the following steps:

In this lab you will follow some of these steps to build a complete C program from scratch. Have a TA check off your work before the end of lab and submit your project files to CMS as soon as possible.

Main Module

This module will consist of two functions, a function to reverse a string and the special main function.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char *strrevdup(const char *s) {
  /* declare variables at the top */
  int i,n;
  char *result,*dest;
  const char *src;

  /* allocate space for the new string */
  n=strlen(s);
  result=(char *)malloc(n);
  /* check for an allocation error */
  if(result==0) return(0);
  /* loop initialization: */
  /*   set i to zero */
  /*   set src pointer to start of old string */
  /*   set dest pointer to end of new string */
  /* loop termination: */
  /*   loop while i<n */
  /* loop step: */
  /*   at each step increment i and update the pointers */
  /* loop body: */
  /*   copy one byte from the src pointer location to the dest pointer location */
  for(i=0,src=s,dest=result+n-1;i<n;i++,src++,dest--) { (*dest)=(*src); }
  /* terminate the new string with a zero */
  result[n]=0;
  /* return the new string */
  return(result);
}

int main(int argc, char *argv[]) {
  char *s;

  s=strrevdup("Hello, world.");
  if(s==0) { perror("strrevdup"); return(1); }
  printf("%s\n",s);
  return(0);
}

In this lab we will be working with the preceeding code listing. Copy it into a file called main.c and walk through the code to understand the program. The program creates a new string which is the reversed version of the input string.

A C string is a sequence of bytes. The end of a string is marked by a zero byte (aka NULL or '\0'). In general, string operations in C consist of one or more for loops which iterate over a string until the zero byte is found. The library function strlen does exactly that to determine the length of a string. By convention, a C string which holds 5 characters (e.g. "apple") is actually 6 bytes but strlen will report the "length" as 5. The final terminating zero byte is not considered part of a C string even though it exists in the computer's memory and is typically used to test for terminating a string processing loop.

Test your program with the following commands. Note: the leading "$" should not be typed; it indicates that the given command should be executed in a UNIX shell. All programs terminate with an exit code. An exit code of zero indicates success.

$ gcc main.c -o main
$ ./main
.dlrow ,olleH
$ echo $?
0

The program appears to be working but it actually has a critical memory bug and a non-critical memory leak. Valgrind is a runtime analyzer that detects most (but not all) memory bugs. It can be run without recompiling or modifying your code so there is no excuse to not test your C programs with Valgrind. Valgrind is installed on the CSUG machines. If you are using the VM valgrind can be installed with yum (run yum install valgrind).

$ valgrind -q --leak-check=full ./main

Valgrind reports both the memory bug and the memory leak. The memory bug must be fixed in the code otherwise this program is incorrect.

A memory leak is when allocated memory is not freed. It is the responsibility of the C programmer to match all calls to malloc with free. More generally, any function call which allocates or reserves a resource must be matched with a corresponding call to a function which frees or releases the resource. After a resource is freed or released it is an error to reference that resource. (More strictly, do not hold a pointer to a freed or released resource.)

How does a C programmer know when a resource function call must be matched with another resource function call? The only way to know is to read the documentation or source code. On a UNIX system the manual page for any standard C function can be viewed with the "man" command.

$ man malloc

Recompile the program with debugging symbols then Valgrind will identify the exact line of code where the invalid memory access occurred.

$ gcc -g main.c -o main
$ valgrind -q --leak-check=full ./main

Most C programming utilities will annotate error messages with "(main.c:XX)". This means the error occured at line XX in main.c. (Starting nano with -c or pressing Meta-C will display line numbers.)

Apply fixes and rerun with Valgrind to verify that the program terminated correctly. Although a modern OS will release all memory when a process terminates you should also fix the memory leak. Fix both bugs before moving on to the next section. If you find yourself stuck for several minutes ask a TA for help.

Ordered String Merge

In this part of the lab you will write a C function which takes two sorted strings as input and outputs a new sorted string which contains all characters from both inputs. First, modify main to call the new function.

int main(int argc, char *argv[]) {
  char *s;

  s=strrevdup("Hello, world.");
  if(s==0) { perror("strrevdup"); return(1); }
  printf("%s\n",s);
  free(s);
  s=strmerge("abcdefg","efghijkl");
  if(s==0) { perror("strmerge"); return(1); }
  printf("%s\n",s);
  free(s);
  return(0);
}

The function strmerge will use two source pointers to examine successive characters of the two inputs in order. Within the loop, write to the destination. At each step the smaller character is written to the destination and the destination pointer is advanced by one. Let us call this the compare-and-write loop.

Q1. If string s1 contains N characters and string s2 contains M characters, how many bytes should be allocated for the destination?

Q2. The compare-and-write loop terminates when either of the source pointers reaches the end of a string (NULL character also written '\0'). What should we do after the compare-and-write loop terminates so that the result of strmerge is correct?

char *strmerge(const char *s1, const char *s2) {
  /* variables you might need, modify as needed */
  int n;
  char *result,*dest;
  const char *src1,*src2;
  char ch1,ch2;

  ... your code here ...
}

Implement strmerge then compile and test your code. All of the C functions and syntax that you need to write strmerge can be found in strrevdup. However, it is okay to use any standard C library function. For example, memcpy is useful for this lab. Be sure that your program will run clean with Valgrind. Have a TA check your code and upload it to CMS.

$ gcc -g main.c -o main
$ valgrind -q --leak-check=full ./main
.dlrow ,olleH
abcdeeffgghijkl
$ echo $?
0

What to Submit

This is an in class lab. You should try to finish before leaving. If you do finish in lab, show your final strmerge method to a TA for evaluation. If you do not finish, you may work on the lab outside of lab period and turn it in on CMS before the deadline. Slipdays may not be used on in-class activities.
To receive participation credit, you must sign in!
Please submit only the source code of the file containing strmerge.