This is not a full MP; it is primarily testing your setup and ensuring you are ready for subsequent MPs. It is dramatically easier than other MPs. Don’t plan your time on other MPs based on this one.
This MP has only one goal: to help you understand how C is unlike C++.
We give you a C++ reference implementation of a doubly-linked list, with a simple driver program. We also give you a C header file and driver program for a C version of the doubly-linked list. Your task is to write the corresponding doubly-linked list C source file. This will mostly consist of copying C++ code to the C file, then changing the C++-specific parts to be C-specific instead.
Don’t use AI
AI systems can do this assignment without any trouble. So can our TAs, others who took this course before, and many other people.
Don’t ask them to. Do this assignment yourself.
This MP is primarily intended to help you understand C so that later MPs will be easier to do. If you have someone or something else do the MP for you, that learning won’t happen and you’ll find later MPs (especially MP4) much harder as a consequence.
You might find C without the ++ to be a useful resource when working on this MP.
mp1.zip
contains a reference C++ implementation, a non-functioning C implementation, and build and testing supports like a Makefile and vscode project files.
The provided dll.c
does not compile because it does not define the functions required by dll.h
. Our first recommended step below is add enough that it does compile.
Implement a C version of the provided C++ code.
We recommend the following flow:
Stub out the implementation. That is, do the minimum possible to make it compile, generally by making empty or return-only function bodies.
Copy one function body from C++ to C and edit it to remove compiler errors. Pay particular attention to pointers and initialization: C++ calls initializers and destructors automatically which C does not.
Repeat until all functions are done.
Try it and debug it.
You’ll probably want to use strlen
, free
, and either malloc
or calloc
. Other functions defined in string.h
, like strcmp
and memset
, are also permitted. The tests will verify that those are the only library functions that you use.
You’ll be required to meet all the rules of C. This will be enforced by compiling with the following compiler flags:
-Wall
-Werror
-pedantic-errors
-std=c17
You must not have any memory errors or leaks. This will be enforced in part using valgrind; the following invocation
valgrind --leak-check=full --show-leak-kinds=all ./dll_c whatever other arguments you want
must end with an ERROR SUMMARY
reporting 0 errors
and no other error messages.
In C++, namespaces help different libraries not collide. In C, the tradition is to prefix every function and global variable name with the same prefix, like glViewport
instead of just viewport
in OpenGL or sqlite3_open
instead of open
in SQLite.
We use the prefix dll
in our provided header file.
In C++, foo(int)
and foo(double)
can co-exist; in C they cannot. The traditional solution is to add a type-specific suffix to the function name, like sqrt(double)
and sqrtf(float)
. If there’s just a single parameter, suffixes based on printf
percent codes are common; for anything more complicated there’s no single pattern.
Templated functions can be removed in a similar type-suffix way, but if there’s more than a few types expected it is more common to replace the templated-type argument with something like a type code and a void *
; for example, something like
size_t sizeOfThing(char type, void *value) {
if (type == 'i') {
int val = (int)value;
return val < 0 ? -val : val;
}
if (type == 's') {
char *str = (char *)value;
return strlen(str);
}
// ...
}
We used the suffix c
for what in C++ was a <char>
template, and s
for what was a <std::string>
template.
this
C has no built-in object orientation. As long as you are not using inheritance, this is a relatively small obstacle; just add the this
-argument as the explicit first argument of each method and add a namespace-like renaming.
This C++ class
class Pt2D {
double x,y;
(double x, double y) { this.x = x; this.y = y; }
Pt2Dvoid move(double x, double y) { this.x += x; this.y += y; }
double theta() { return atan2(y, x); }
double r() { return hypot(x,y); }
};
becomes this C code: a .h
file containing
typedef struct {
double x,y;
} Pt2D;
void pt2d_init(Pt2D *self, double x, double y);
void pt2d_move(Pt2D *self, double x, double y);
double pt2d_theta(Pt2D *self);
double pt2d_r(Pt2D *self);
and a .c
file containing
#include "the h file you created.h"
void pt2d_init(Pt2D *self, double x, double y) { self->x = x; self->y = y; }
void pt2d_move(Pt2D *self, double x, double y) { self->x += x; self->y += y; }
double pt2d_theta(Pt2D *self) { return atan2(self->y, self->x); }
double pt2d_r(Pt2D *self) { return hypot(self->y, self->x); }
Note the above assumes a two-step creation: allocate, then initialize. If the intent is to always initialize on the heap (like C++’s new
operator does) then we could instead (or in addition) do something like this:
*pt2d_new(double x, double y) {
Pt2D *self = malloc(sizeof(Pt2D);
Pt2D ->x = x; self->y = y;
selfreturn self;
}
void pt2d_delete(Pt2D *self) { free(self); }
Replace new
with malloc
+ initialization.
Replace delete
with free
(preceded by deinitialization if there’s a destructor).
Replace std::string
with char *
.
Replace operator overloading with explicit function calls: strcat
instead of std::string
’s +
operator, printf
instead of cout
’s <<
operator, and so on.
There are no auto
declarations, iterator loops, or lambda expressions in C.
Replace pass-by-reference code with pass-by-pointer, adding needed *
/->
operators to make that work.
To match prevailing style, move where *
s appear in type declarations. In C it is tradition to write int *x
, not int* x
like in C++. It is also traditional to declare multiple pointers per line, like int *x, *y
.
make
sh tests.sh
make clean
followed by make dll_c
should create dll_c
dll_c
and dll_cpp
should have the same operation as one another, including with the following arguments:
e
e f
one
one two three four five six
--help
one --help two
valgrind
should report no errorsPermissive grading
The provided tests for this MP do not test all features of the MP (intentionally: the goal of this MP is writing C, not writing robust code). If you want to do more robust testing, you can add the following to your local copy of usedll.c
:
After declaring cl
but before calling dllInitc
, add memset(&cl, 0x34, sizeof(dllListc));
(add #include <string.h>
to get access to memset
). If dllInitc
is working correctly, this shouldn’t change anything about the code’s behavior. A similar memset
between declaring and initializing sl
should also not change results.
Add a new test sequence that (a) calls dllPushs
or dllPushc
several times and then (b) calls dllClears
or dllClearc
, without calling shift or pop on that list. If your clear functions work, this should keep the code passing all valgrind
checks.
Add a new test that mixes push, equeue, pop, and shift commands instead of just a simple series of push/enqueue followed by a simple series of pop/shift.
Add a new test that pushes, clears, and then pushes some more and verify that it results in the correct list.
If you’re interested in testing, it might be worth asking yourself what kinds of errors each of these tests would find that the tests we provided do not.
Submit on the submission site. Only submit dll.c
; do not modify any other file.
This assignment is primarily a warm-up, graded fairly loosely. The score crated by tests.sh
is the score you get on this MP.