Due Friday, July 4, 2014 @ 23:59:59
This assignment aims to give you a better understanding of C memory allocation as well as more programming practice.
Submit your solution by creating a directory named
hw2 that contains the file
(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.
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
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.
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.cworks to complete the assignment. We have also provided you a struct,
timeHM_t, defined in
timeHM.hthat is used to represent time in hours and minutes. It also contains several useful functions.
For this assignment, you should ONLY modify
A skeleton has been provided for you (along with
but you will need to define the structs
implement the following functions:
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)
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.
allocation_failed (given in
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):
- list of airports -- airport names, one on each line (no guarantees about name length!)
- 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".
- 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
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
completed, the program should be able to give the correct times for when routes (given in
should finish, or say that it's not possible. The correct output is given in
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.