CS61C Summer 2014 Homework 2

Due Friday, July 4, 2014 @ 23:59:59

Goals

This assignment aims to give you a better understanding of C memory allocation as well as more programming practice.

Submission

Submit your solution by creating a directory named hw2 that contains the file flights.c. (File names are case-sensitive and the submission program will not accept your submission if your file names differ at all from those specified). From within that directory, type submit hw2. Partners are not allowed on this assignment.

Setup

Copy the contents of ~cs61c/hw/02 to a suitable location in your home directory to obtain files you will want for this homework.

$  cp -r ~cs61c/hw/02 ~/hw2 

For testing, you'll need to use a tool called Valgrind. It's not fully setup on the Macs yet but you can ssh into a Hive machine (any from hive1 to hive28) to use it:

$  ssh hive10.cs.berkeley.edu 

Exercises

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:

• a destination airport,
• time of departure,
• time of arrival,
• and the cost of the flight.

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 (along with flights.h), but you will need to define the structs flightSys_t and airport_t, and implement the following functions:

• flightSys_t* createSystem()
• void deleteSystem(trainSys_t* s)
• void addAirport(flightSys_t* s, char* name)
• airport_t* getAirport(flightSys_t* s, char* name)
• void printAirports(flightSys_t* s)
• void addFlight(airport_t* src, airport_t* dst, timeHM_t* departure, timeHM_t* arrival)
• void printSchedule(airport_t* s)
• bool getNextFlight(station_t* src, station_t* dst, timeHM_t* now, timeHM_t* departure, timeHM_t* arrival, int* cost)

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).

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_station 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 stations 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"). Note: There are a few issues with Valgrind's output on the Orchard machines, so you should run Valgrind on one of the Hive machines. Grading will take place on the Hive machines as well.

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.