CS61C Summer 2016 Project 1: Flights

TA: Brian Kim

Due Sunday, July 3, 2016 @ 11:59pm

Goals

This project aims to get you more familiar with C, especially C memory management.

Update (6/27, 11:11 AM): The submission process has been updated to reflect the fact that you should push to master, not a proj1 branch.

Update (7/1, 12:53 AM): Your code will be tested on the Hive machines. Please make sure that your code works as intended on the Hive machines before submitting (this includes using Valgrind to check for memory problems).

Update (7/3, 1:17 PM): The resubmission process has been updated to reflect the fact that you should push to master, not a proj1 branch.

Setup

To get the starter code for this project, we will be using git. You should have received an invitation to a private repository shared with your partner. First, create a local copy of your private project repository (repeat lab0 with the new repo). Enter the repo directory and run the following:

git remote add proj1-starter git@github.com:cs61c-summer2016/proj1-starter
git fetch proj1-starter
git merge proj1-starter/master -m "merge proj1 skeleton code"

Once you complete these steps, you will have all the skeleton files inside of your repository.

As you develop your code, you should make commits in your git repo and push them as you see fit.

In addition to using git, you will need to use a tool called Valgrind for testing purposes (details can be found later in the specs). You can ssh into a Hive machine (any from hive1 to hive28) to use Valgrind.

$  ssh cs61c-xx@hive10.cs.berkeley.edu 

C and Memory Allocation

You will be completing the implementation of flights.c, a flight system that keeps track of the flights between a series of airports. The flight system, represented by the struct flightSys_t, will hold all the airports in this system. Each airport, represented by the struct airport_t, will hold both its name (as a string) and a schedule of all the flights departing from it. Each entry in the schedule should contain:

We have provided a program, RouteTime.c, which will both provide the data to your flight system and use the data you store to figure out the cost of flying via a certain route. You do not need to know how RouteTime.c works to complete the assignment. We have also provided you a struct, timeHM_t, defined in timeHM.h that is used to represent time in hours and minutes. It also contains several useful functions.

For this assignment, you should ONLY modify flights.c. A skeleton has been provided for you, but you will need to define the structs flightSys_t and airport_t, and implement the following functions:

Descriptions for each function can be found in flights.c.

You have the freedom to design the structs and the way you store the information however you like (so have fun!). However, your code must be able to handle an arbitrary number of airports and schedule entries; in other words, your data structures must be able to grow dynamically. You are not allowed to use a statically sized array. One possibility is linked list structures. Another is to use arrays but create larger ones to replace ones that are out of space (in which case you may find realloc useful). If you are out of memory (e.g. malloc fails), call allocation_failed (given in flights.c).

You should comment your code so readers can give feedback and possibly partial credit easier.

Testing & Debugging

A Makefile is provided for you. Standard usage is as follows:

// creates executable RouteTime
$  make 
// run program with provided files -- (1) list of airports, (2) schedules, (3) routes
$  ./RouteTime airports.txt schedules.txt routes.txt

// does the two commands above at once
$  make run

The program takes 3 arguments (see provided files for formatting):

  1. list of airports -- airport names, one on each line (no guarantees about name length!)
  2. schedules -- listed by airport and separated by blank lines. "AIRPORT: source_airport_name" starts a schedule, followed by lines of the format "destination_airport departure_time arrival_time $cost_of_flight".
  3. routes -- each route begins with "ROUTE: route_name start_airport time_now" and subsequent lines are airport names along the route.

You should test each part individually as you go along. Once you have completed printAirports(), RouteTime should echo the airports listed in airports.txt correctly. Similarly, once you have completed printSchedule(), the schedules in schedules.txt should be echoed. With getNextFlight() completed, the program should be able to give the correct times for when routes (given in routes.txt) should finish, or say that it's not possible. The correct output is given in flights.out.

Having just the correct output will not be enough, though! We'll check that your code doesn't access memory it shouldn't be and that it doesn't leak any memory. We'll check with Valgrind's memcheck tool. This is a tool that can help you catch memory problems too:

// runs Valgrind on RouteTime with default arguments
$  make flights-memcheck

The tool will tell you where you are making invalid reads or writes and what memory is leaked (memory that you've lost all pointers to). The program should not have any of these errors nor leaked memory (don't worry about Valgrind's report on "still reachable" or "suppressed").

If you run into bugs, try using gdb and Valgrind. gdb will let you set breakpoints, step through your code, and check values of variables. Valgrind's memcheck will help you catch bad reads and writes. If you run into a segfault, using gdb and Valgrind in combination can point you to exactly where it happened.

IMPORTANT: We will grade your solution using different input files so you should test your code carefully! In particular, you will notice that the input files we have provided do not thoroughly test your code. These input files should be used as a sanity check only. In addition, we will make no guarantees on the length of airport names, schedules, or routes or the size of the airport system. Finally, any changes you make to files other than flights.c will NOT be used in grading.

Submission

There are two steps required to submit proj1. Failure to perform both steps will result in loss of credit:

First, you must submit using the standard unix submit program on the instructional servers. This assumes that you followed the earlier instructions and did all of your work inside of your git repository. To submit, follow these instructions after logging into your cs61c-XX class account:

$ cd <proj1 repo directory>                         # Your proj1 git repo, should contain all the files for the project
$ submit proj1

Once you type submit proj1, follow the prompts generated by the submission system. It will tell you when your submission has been successful and you can confirm this by looking at the output of glookup -t.

Second, you must submit proj1 to your GitHub repository. To do so, follow these instructions after logging into your cs61c-XX class account:

$ cd <proj1 repo directory>                         # Your proj1 git repo, should contain all the files for the project
$ git add -u                                        # Should add all modified files in proj1 directory
$ git commit -m "your commit message here"
$ git tag -f "proj1-sub"                            # The tag MUST be "proj1-sub". Failure to do so will result in loss of credit.
$ git push origin master --tags                      # Note the "--tags" at the end. This pushes tags to github

Resubmitting

If you need to re-submit, you can follow the same set of steps that you would if you were submitting for the first time. The only exception to this is in the very last step, git push origin proj1 --tags, where you may get an error like the following:

(21:28:08 Sun Feb 01 2015 cs61c-ta@hive12 Linux x86_64)
~/work $ git push origin proj1 --tags
Counting objects: 22, done.
Delta compression using up to 8 threads.
Compressing objects: 100% (19/19), done.
Writing objects: 100% (21/21), 9.73 KiB | 0 bytes/s, done.
Total 21 (delta 4), reused 0 (delta 0)
To git@github.com:cs61c-summer2015/cs61c-ta
   bf20433..d1ff9ed  proj1 -> proj1
 ! [rejected]        proj1-sub -> proj1-sub (already exists)
error: failed to push some refs to 'git@github.com:cs61c-summer2015/cs61c-ta'
hint: Updates were rejected because the tag already exists in the remote.

If this occurs, simply run the following instead of git push origin proj1 --tags:

$ git push -f origin master --tags

Note that in general, force pushes should be used with caution. They will overwrite your remote repository with information from your local copy. As long as you have not damaged your local copy in any way, this will be fine.