CS 241 MP1 First Steps in C

Due: Monday, September 9th, 11:59pm

---

Introduction

In CS 125, CS 225, and other classes, you have used various languages that are considered to be "C based", but up to now you may have very limited experience in C programming. This MP will provide a short programming introduction to pointers, strings, and functions in C.

This machine problem will be divided up into two pieces. In the first piece, you will need to write some code to call some 'creatively defined' functions so that those functions produce the desired output. In the second piece, you will be creating a simple dictionary data structure to parse and hold the values of the parsed strings.

For this MP, you may modify:

• part1.c
• part2.c
• part2_hacker.c
• libdictionary/libdictionary.c
• libdictionary/libdictionary.h

All other files will be replaced with new/different files for grading. If you modify any other files for debugging purposes, please ensure you test your program with the original file.

What you must do...

...for Part 1:

We have pre-uploaded some files to your mp1 svn directory, including mp1-functions.c. Inside mp1-functions.c, you will see ten different functions, including first_step() (re-printed below).

void first_step(int value)
{
  if (value == 81)
    printf("1: Illinois\n");
}

To complete Part 1, you must complete the program part1.c so that part1.c makes calls to all ten functions in mp1-functions.c such that they print their "Illinois" line. Be aware that you are NOT allowed to write any printf statements yourself in part1.c. When running ./part1, your output should look exactly like:

1: Illinois
2: Illinois
3: Illinois
4: Illinois
5: Illinois
6: Illinois
7: Illinois
8: Illinois
9: Illinois
10: Illinois

You should NOT edit the mp1-functions.c file. In fact, when we grade your program, we will replace the mp1-functions.c file with a new version of the file (and we'll change the "Illinois" string so printing out "Illinois" in a for-loop will get you no credit).

...for Part 2:

Now that you have some review of pointers, we're ready to make a simple, but useful library. This library will be a simple "dictionary" that associates a key with value, much like the Map interface in Java (Interface Map<K, V> in Java). While a true library may contain many useful functions, we only require a few very basic functions to be completed in order to complete Part 2: _init(), _destroy(), _add(), _get(), _remove(), and _parse().

In all six functions, the first parameter is a pointer to a dictionary_t struct. You can find this struct defined in the libdictionary.h file inside the /libdictionary/ folder in MP1. You will find the dictionary_t structure, with a single reference to a dictionary_entry_t struct. You may want to add variables to dictionary_t, change it to a pointer, or anything else to work with your data structure. It may be useful to add variables inside the dictionary_entry_t struct in order to store state about your dictionary. You may find that the dictionary_entry_t struct is enough, or you may create any number of other structs inside your .h file. A pointer to the same dictionary_t will be used through the entire use of a single dictionary. Sample code of use of your library can be found in part2.c, re-printed (in part) below:

dictionary_t dictionary;
dictionary_init(&dictionary);

result = dictionary_add(&dictionary, "key", "value");
result = dictionary_add(&dictionary, "key2", "value");
result = dictionary_parse(&dictionary, "Hello: World");
[...]
dictionary_remove(&dictionary, "key3");

You should modify part2.c to include more robust testing your library. We will not use part2.c in grading, but our grader will use a custom file that makes use of your library -- it's up to you to robustly test your dictionary.

To complete Part 2, you must implement the six functions defined in libdictionary/libdictionary.c. These functions are self-descriptive, but a full function outline is provided for in the links below. In this MP, we are looking for correctness over efficiency -- all the test cases are small enough that even an O(n^3) algorithm will run just fine.

• dictionary_init(): [documentation]
• dictionary_add(): [documentation]
• dictionary_parse(): [documentation]
• dictionary_get(): [documentation]
• dictionary_remove(): [documentation]
• dictionary_destroy(): [documentation]

Compile and Run

To compile part1.c (Part 1), libdictionary (the dictionary itself), and part2.c (the dictionary tester), run:

make clean
make

To run Part 1:

./part1

To run Part 2:

./part2

What you can do for fun...

Although we will score your mp for correctness over efficiency, we have provided you with a simple bench-mark to see how fast your data structure can do. However, we highly suggest that you move on to increase your data structure efficiency after you have done extensive testing about its correctness. This part is for fun only, and slow implementation will not affect your sco re. We have provided part2_hacker.c The program will add MAX_ENTRIES unique entries into the dictionary, get each of the entries added, try to add the same entries added just now again, and remove all the entries added. MAX_ENTRIES is defined in part2_hacker.c. The part2_hacker.c is compiled along with the other files when you type

make

. To run part2_hacker:

./part2_hacker

Your will see how fast your dictionary performs. Our implementation of dictionary performs as below:

MAX_ENTRIES 10000 , 0.01 second;
MAX_ENTRIES 100000 , fastest: 0.23 second, slowest: 0.31 second;
MAX_ENTRIES 1000000 , fastest: 1.72 second, slowest: 2.68 second;
MAX_ENTRIES 10000000, fastest: 18.38 second, slowest: 21.63 second;

Grading, Submission, and Other Details

Please fully read mp_grading.html for more details on grading, submission, and other topics that are shared between all MPs in CS 241.