1. Goals for this week

  • Learn how to use a C library from reading documentation in its header file (.h file).

  • Practice with signals and signal handler functions.

  • Understanding global variables in C.

  • Introduction (or reminder) of circular arrays and practice implementing a fixed-size queue in C.

2. Starting Point Code

Start by creating a 10 directory in your cs31/weeklylabs subdirectory and copying over some files:

$ cd ~/cs31/weeklylabs
$ mkdir week10
$ cd week10
$ pwd
$ cp ~newhall/public/cs31/week10/* ./
$ ls

3. Using a C library

C libraries consist of two parts:

  1. A header file (libraryname.h). The header file is an ascii file that is readable in vim. It contains definitions exported by the library, including global variable definitions, function prototypes, type definitions (like structs), and constant definitions (#defines). The header file is #include 'ed at the top of any .c file that use the library. It also contains detailed comments written for users of the library.

  2. The library binary file (.o, .a, or .so). It contains compiled versions of library functions. The binary is built from one or more C source files (.c files). Often times the library source code (its .c files) is not distributed with the library.

3.1. The parscmd library

With the files you copied over is the parsecmd library header file (parsecmd.h) and if you open Makefile in vim, you can see where the path to its binary file (parsecmd.o) is. The test program (testparsecmd.c) that uses the library.

parsecmd is a library that parses a command line string into its substrings.

Open up parsecmd.h in vim and let’s look at its contents. You can see a function prototype for the parse_cmd function. Reading the comment tells us that this function takes as input a string, and it parses the string into a list of strings, one string per argument in the input string. There are also constant definitions in the header file. These constants can be used by any code that #includes parsecmd.h.

Note, that the implementation of this function is not given to you. Instead, only a compiled version of the function is provided in parsecmd.o.

To use this library, you need to:

  1. #include it in a C source file (we will look at how this is done in testparsecmd.c).

    #include <stdio.h>;       // use this syntax for standard header files
                              // (most located in /usr/include/)
    #include "parsecmd.h"     // use this syntax for other header files
  2. link in the library file (parsecmd.o) as part of the gcc command to build the executable (this is included in the Makefile):

    # LIBDIR is the path to the directory containing the parsecmd.o file
     gcc -g -Wall -o testparsecmd testparsecmd.c $(LIBDIR)/parsecmd.o

    Let’s open testparsecmd.c and see how it includes the header file and how it makes uses of definitions and function prototypes defined in the parsecmd library. Then, let’s compile and run it.

Here is some more information about C libraries (see "Using and Linking C Library Code"). Section 2.9.5 of the textbook also has this information.

4. Signals and Signal Handlers

Let’s first look at the program signals.c. This program has some examples of registering a signal handler function on a signal, and of some examples of ways in which you can send signals to processes (for example, alarm can be used to send a SIGALRM to one’s self).

We will try running this and use the kill command to send the process signals:

ps                # get the process' pid, let's say its 345

kill -CONT 345    # sends a SIGCONT signal to process 345
kill -18   345    # or -18 is another way to specify the SIGCONT signal

kill -INT 345    # sends a SIGINT signal to process 345
kill -2   345    # or -2 is another way to specify SIGINT signal

Let’s try running the program and see what it is doing.

The man page for signal lists the signals on this system and describes the signal system call in more detail.

You can also try changing some of the handler code to see what happens. Try changing the SIGINT handler to not call exit, and to print out some other message. Then see what happens when you type (assume 345 is the pid):

kill -INT 345

To kill the process now, you need to send it a SIGKILL signal:

kill -9 345

5. Reminder: Global Variables

A reminder about global variables example from last week’s lab session (in globalvars.c).

Using Global Variables

In general, you should avoid using global variables. Instead, always design functions to take as parameters the values they need; if a function needs a value, pass it in, and if a caller needs a value from the function return it (or pass in pass-by-pointer style parameters through which the function can modify the caller’s argument values). This makes your code more generic than using globals, and it avoids allocation of space for the entire run of your program when it is not needed.

In the Unix shell lab, we’ll allow you to use global variables to implement a circular queue of the command history, but you should not use them for any other purposes.

6. Circular Arrays in C

A queue is a data structure whose values are ordered in FIFO order (first-in-first-out). New items are added to the end of the queue and removed from the beginning of the queue (FIFO semantics for adding and removing).

You are going to implement a fixed-size overwriting queue as a fixed-size circular array of int values. This is an overwriting version of a fixed-size queue, where each time a new value is added to a full array, it replaces (or overwrites) the item that is currently first in the array (the oldest value added to the queue). This type of data structure is useful for keeping a list of the N most recent values; as a new value is added, the previous first value (the oldest) is removed from the set to make room for a new last (newest) value.

As values are added and removed the first and last bucket index values of the queue change. When the very last bucket is filled the first time, the next value added will replace the value in bucket 0 (the new end of the list) and the first bucket in the list now becomes bucket 1 (the next bucket to replace). When the next value after that is added, it is added to bucket 1 (the new end of the list) and the new start of the list becomes bucket 2. And, so on. This is a circular array implementation of a queue because the first and last bucket indices cycle around the array indexes (0, 1, …​, 4, 0, 1, …​, 4, 0, 1, …​).

For example, for a circular queue of int values of size 5:

after adding values: 3, 6, 17: the queue has 3 elements, and the
                               next bucket to insert into is bucket 3
0   1    2    3    4
---------------------          first value in the queue is in bucket 0
 3 | 6 | 17 |   |   |
---------------------          last value in the queue is in bucket 2

after adding values: 10, 4:    the queue has 5 elements, and the
                               next bucket to insert into is bucket 0
0   1    2    3    4
----------------------         the first value in the queue is in bucket 0
 3 | 6 | 17 | 10 | 4 |
----------------------         the last value in the queue is in bucket 4

after adding the value 7:      the list has 5 elements, and the
                               next bucket to insert into is bucket 1
0   1    2    3    4
----------------------         the first value in the queue is in bucket 1
 7 | 6 | 17 | 10 | 4 |
----------------------         the last value in the queue is in bucket 0

after adding the value 9:      the list has  5 elements, and the
                               next bucket to insert into is bucket 2
0   1    2    3    4
----------------------         the first value in the queue is in bucket 2
 7 | 9 | 17 | 10 | 4 |
----------------------         the last value in the queue is in bucket 1

printing out the queue from first to last value is:  17  10  4  7  9

In circqueue.c is the starting point of a circular queue implementation. You are going to implement and test two functions:

void add_queue(int value): add a new value to the queue (and update queue state)
                           the value added should replace the first item
                           in the queue when the array is full
void print_queue(): print out the values in the queue from first to last

This code uses global variables for the queue (implemented as an array of ints) and for other state associated with the queue (and feel free to add more state variables if you need them).

This example is also not an obvious need for a global variable, but if this code was being used to implement a single queue library, then declaring the queue and its state as a global might be necessary. For now, I just want you to get some practice with global variables.

Remember, you should always avoid using global variables in your program, and only do so when explicitly allowed in this class.

7. Lab 6 Intro

Lets talk through the next Lab 6 Assignment, where you will implement a unix shell program that uses runs commands entered by the user. Part of implementing the shell program requires that you implement a circular queue and a signal handler, and use the parse_cmd library.

In Part 2 of the lab, which we will discuss next week, you will implement some of the parse_cmd library functions that you use in your Part 1 shell program that is the focus of this week.

8. Handy References