Despite incredible advances in programming languages over the last 30
years, most serious systems programming is still done in C.
Why is this? Because C gives the programmer more control and power over
the code's execution than do other, higher-level languages like Java
or even C++. Also, C typically has less runtime overhead than higher-level
languages, which can translate into increased performance. Suppose you have
a function that takes an integer and returns a double. In a strongly typed
language, all you can do with this function is call it while passing an
integer and treat the result as a double. Of course, you can do this in C.
But you can also call it with no parameters, call it with 5 parameters,
take the result and store it in an integer. Even better, you could treat
the function as an array and read each instruction as an integer if you like.
Or, you could call not the first instruction in the function, but maybe the
second, or the third, or ... there is a reason why C is sometimes referred
to as a "high-level assembly language".
What's bad about this freedom? Bugs. Forgot a parameter? Maybe you did
it on purpose. Or maybe (and probably) not. In Java, the compiler shows
you your mistake. In C, the compiler is very easy to please, but when
you run the program, it fails, generally in a very cryptic way -
"segmentation violation," and "core dumped" are the principle error messages.
Both mean you made a mistake.
All of this means that you need to program carefully and deliberately
in C. If you do this, you can write programs that are as well
structured and clear as you can in languages like Java. But, if you
don't, you'll quickly have a big mess on your hands. Hard to
debug. Hard to read. Hard to modify.
There are lots of good references for programming in C. The primary
one is "C Programming Language (2nd Edition)" by Kernighan and
Ritchie.
You should do this assignment on a Unix machine, which will provide
you not only with the compiler (cc, or gcc, depending on the
installation) but also a debugger (gdb). You can use any editor you
like, but I recommend that you check out emacs, which has support for
C programming and debugging.
We recommend the use of the
CSE home Linux virtual machine for this assignment.
It's handy to set up, and comes pre-configured with everything you need.
(It's sufficient for all projects in this course, except for Project 1,
which is done on a CSE Linux box devoted to this course and configured
in an odd way.)
Part 1. The Basic Queue
The queue is one of the most important data structures you'll be
dealing with in this class. Consequently, it's a good one to start
working with early.
For this part of the assignment, I will be providing you with a
complete interface and mostly complete implementation for a queue.
Starting with this, you will:
- Find and fix two critical bugs in the implementation. (I've put
these bugs in after getting the code working). You will need to build
a much more intensive test infrastructure than what you will find in main.c.
You should include comments that make it clear what problems you
fixed.
- Implement the two declared, but not implemented, methods:
queue_reverse() and queue_sort(). Both methods must work in-place: they
can't create a new queue and move or copy elements from the original
queue to build the result. The time efficiency of the sorting algorithm
is not important, as long as it's something reasonable (not worse than
O(n^2), not better than O(nlog(n)). queue_reverse() should execute in
O(n) time. queue_sort() sorts in non-descending order.
You must follow the coding style (indentation, naming, etc) that you
find inside queue.c and queue.h
Grading Criteria
|
2 points | Perfect. Two critical bugs found and fixed.
New methods implemented cleanly and correctly.
|
1 point | Slightly less than perfect.
|
0 points | Seriously flawed.
|
Part 2. The Hash Table
Following the same style for the queue, write the code that defines
(.h) and implements (.c) a hash table.
The hash table allows you to store and retrieve values of any kind
(pointers) based on a key value.
You're free to use any hash table implementation you like. You learned
several variations, such as linear probing or separate chaining, in
your data structures course.
The operations (in English) you need to define are:
- Create. Creates and returns a new hash table.
- Set hash function. Establishes the function to be used when
computing a hash value based on a key.
- Set key comparison function. Establishes the function to be used when
comparing two keys for equality. (A common scheme is to return 0 for
equal, -1 for less than, and 1 for greater than, although all you actually
need for this assignment is an indication of equal or not equal.)
Note: You can combine the last two, or three, functions into one if you want.
- Add [key, item] pair. Inserts the given pair into the table.
- Lookup. Given a key, returns the associated item. Indicates
failure in the event that the key is not present.
- IsPresent. Given a key, returns a boolean indicating that the key
is present.
- Remove. Given a key, deletes the associated [key, item] pair from
the hash table.
Grading Criteria
|
2 points | Clean code. Works. Clearly demonstrates an
understanding of the coding style laid out in Part 1.
|
1 point | Code not so clean. Or, maybe doesn't work so well.
|
0 points | Problems abound.
|
Part 3: Tables of functions
This section describes the goals/requirements of Part 3. It uses
familiar C constructs to explain those goals. Your actual implementation
will use some new constructs, not the ones shown here. The actual
implementation strategy is described on another page, linked at the bottom
of this description. You should understand the requirements before moving
on the implementation details page.
It is quite common to put functions into a table and then rely on
indirection to make the call. This allows functions to be dynamically
bound to their names, yet provides a not too intolerable calling
syntax. In addition, it provides the module implementing the
functions with a single point of mediating control.
As a simple example, let's suppose that we have a module which
implements a set of mathematical functions (add, subtract, multiply,
slope, etc).
That is, somewhere in the system the actual functions are defined as follows:
int add(int x, int y);
int sub(int x, int y);
int mult(int x, int y);
int slope(int x1, int y1, int x2, int y2);
but these functions are not directly callable by clients.
Rather than declare these functions
directly in a header file, the module instead declares them
symbolically, for example, using #defines.
#define ADD 1
#define SUB 2
#define MULT 3
#define SLOPE 4
Then, for each of these functions, the header file defines a structure
appropriate for the arguments. For example, add and subtract
each take two arguments and so would require that the header file
define a structure as per:
struct args2 {
int a1;
int a2;
};
The slope function takes four arguments (x1,
y1, x2, y2) and would require a comparable definition.
Lastly, mean takes two arguments, the first of which is simply the address
of the zeroth element in an array of integers, and the second of which
is the number of integers to be "meaned." This too would need to be
expressed explicitly within the header file.
To facilitate invocation, the header file exports a single callable
entry function which takes three arguments: the identifier of the function
to call, a pointer to the structure containing the arguments to be
passed to the function, and a pointer to where the results should be
stored.
int math_call(int function_name, void *args, int *result)
Thus, a client wanting to add two numbers might say:
void main()
{
struct args2 a2;
int result;
a2.a1 = 100;
a2.a2 = 200;
if (math_call(ADD, &a2, &result) < 0) {
printf("Error");
} else
printf("%d\n", result);
}
The implementation of math_call would then:
- Verify that the requested function is legitimate (eg, in the
table).
If not, the function should return -1.
- Based on the number of arguments expected by the called
function, invoke through table indirection the appropriate
function in its native form with the appropriate arguments.
- Store the result of the invocation in the result parameter
specified by the caller.
- Return 0 indicating success.
For part 3, you will implement the math module.
Put it in a file called mathtable.c. Your implementation must
conform to the interface defined in mathtable.h.
In addition, implement a main module (main.c) that shows how to use
all of the methods defined indirectly in mathtable.h.
Details on how to actually implement this part of the assignment are
described in this assignment addendum.
Grading Criteria
|
2 points | Clean code that works.
|
1 point | code maybe not so clean, or maybe doesn't work so well.
|
0 points | seriously flawed.
|