Due: Friday, 12 February, 2016 by 11:59:59 PM.
Programming assignments in CS 485G are individual work. You may discuss approaches with other students, but may not share code or pseudocode for the assignment. If do get ideas from somebody, or use snippets of code from elsewhere, you must cite the source in your documentation.
For this assignment, you are explicitly permitted to share the disassembled code of test-full.o, should you and your classmates wish to work together to figure out exactly what the tests are doing.
See this note if you are using C++ and test case 5 fails only under valgrind (make memcheck).
A new alternative Makefile has been added for C++ users.
The built-in C
string library uses null-terminated strings,
where a "string" is simply (a pointer to) an array of characters, with the
character '\0' (NUL) marking the end of the string. While
this is a convenient representation because a string parameter can be a
simple primitive type (char * or const char *),
it has several problems:
strlen())
is a linear-time operation: it must scan the array until it finds the
first '\0'.'\0' character. That means a
string cannot represent an arbitrary string of bytes, for example the
contents of a binary file.
strcat()
says:
The behavior is undefined if the destination array is not large enough for the contents of both src and dest and the terminating null character.Where "behavior is undefined" here really means that other parts of your program's memory will be overwritten, giving the person who supplied the too-large string complete control over your program.
The most common alternative to null-terminated strings are so-called counted strings. A counted string stores both the data and its length. An example data structure for a counted string (similar to the one you will use in your program) would be:
struct kstring
{
char *data;
size_t length;
};
Your task is to implement a library (as a set of source and header files, documentation, and a Makefile) that provides a few useful functions for working with a counted string data structure. The definition of the data structure and prototypes for all the functions may be found in kstring.h. A set of function stubs, which you may use as the basis for your implementation, is provided in kstring-stubs.c.
kstring.cc or
kstring.cpp
kstring structure, and prototypes for
the functions you will implement.
Your library should implement the following eight functions.
Prototypes for the functions, and the definition of the
kstring struct (like a class, but with public
data and no member functions), are in the provided
kstring.h.
kstring kstralloc(size_t nbytes)
Creates and returns a new kstring object with the
specified length. The .length member of the
returned kstring should be equal to nbytes.
The .data member should be a pointer to
newly-allocated memory; the memory should be initialized
by filling it with nbytes copies of the null
byte ('\0').
If there is an error allocating memory, this function should
call abort() or throw an uncaught exception.
Note: your program must support allocating (and subsequently using and freeing) zero-byte strings.
kstring kstrfrom(const char *cstr)Creates and returns a new kstring object that contains a copy of the contents of a null-terminated C string, including the null terminator.
The .length member of the returned kstring
should be the length of cstr, plus one for
the null terminator. The .data member should
be a pointer to newly-allocated memory, into which you
have copied the contents of cstr, including
the null byte at the end.
If there is an error allocating memory, this function should
call abort() or throw an uncaught exception.
void kstrfree(kstring str)
Frees the memory to which str.data points.
Should correctly handle any kstring created with either
kstralloc() or kstrfrom(), including
those with length 0.
Note: Since the kstring is passed by value, setting its data pointer to NULL would not be reflected in the caller. This means that it is the caller's responsibility not to re-use the kstring it passed to this function.
Note: Remember to free the memory in the way appropriate to
how you allocated it: if you used new char[N],
you should free with delete[]; if you used
malloc() or calloc(), you should use
free().
size_t kstrlen(kstring str)
Returns the length of the kstring str (that is,
str.length).
char kstrget(kstring str, size_t pos)
Returns the character at index pos in str's
data.
If pos is out of bounds (greater than or equal to
the length of str), this function should abort the
program: either by throwing an uncaught exception (C++), or by
calling abort() (C or C++).
void kstrput(kstring str, size_t pos, char ch)
Replaces the character at index pos
in str's data with the character ch.
If pos is out of bounds (greater than or equal to
the length of str), this function should abort the
program: either by throwing an uncaught exception (C++), or by
calling abort() (C or C++).
void kstrextend(kstring *strp, size_t nbytes)
Modifies an existing kstring, pointed to by strp,
to be at least nbytes bytes long.
If strp->length was already nbytes or longer, does
nothing. That is, this function will never reduce the length of
a string, only increase it.
If nbytes is longer than the current length,
this function should take the following steps:
'\0').
strp->data point to the new array.
strp->length to the new size.
malloc() for memory
allocation, the function
realloc()
will take care of steps 1, 2, and 4 with a single function call.
If there is an error allocating memory, this function should
call abort() or throw an uncaught exception.
Note that this function takes a pointer to a kstring rather
than taking a kstring by value. That means
that changes you make to the strp->length and
strp->data members will be visible
to the caller.
void kstrcat(kstring *destp, kstring src)
Concatenates str onto the end of *destp.
First extends *destp to be long enough to hold the
contents of both strings, by calling kstrextend().
Then copies the contents of src into the dest
So, for example, if we execute the following code:
kstring a = kstrfrom("hello"); // 6 bytes including \0
kstring b = kstrfrom("world"); // 6 bytes including \0
kstrcat(&a, b);
Now a should have length 12, and the contents
"hello\0world\0".
Note that this function takes a pointer to the destination kstring.
That means that changes you make to the destp->length
and destp->data members will be visible
to the caller.
Note: Remember to save the original length of *destp before
calling kstrextend(). Otherwise, you won't know where
to copy src's data to!
CFLAGS:
-std=c89: old-school ANSI C (gcc default).
-std=c99: the most commonly-used version of modern C.
-std=c11: the most recent C standard.
-std=c++98: old-school C++ (g++ default).
-std=c++11: modern C++, the newest version supported
by gcc 4.8.
-Wall compiler flag
(enable all warnings), without producing any compiler or linker warnings
or errors.
vector, uniq_ptr, string,
and so on.
new,
delete, and
delete[]
(C++); or
malloc,
calloc,
realloc, and
free
(either C or C++).
strncpy,
strlen, etc.). However, do keep in mind that they do not
properly handle data containing null bytes, so it is probably a mistake
to use them anywhere except kstrfrom (which takes a null
terminated string as its argument).
new if
allocation fails) aborts the program.
In C, you must detect the condition and call
abort().
Simply exiting the program with
exit()
is not enough!
Two test suites are provided for your program. The first,
test-abbrev.c,
contains thirteen functions, each implementing a test cases, as well
as a main() that runs all the tests and tallies the number
of successes (the function returns a positive number), failures (the
function returns zero), and skipped tests (the function returns a
negative number). You are welcome to modify
this file, for example to add your own test cases.
The second test suite is provided as an object file,
test-full.o.
This test suite is similar to test-abbrev, but includes
thirteen additional test cases, for a total of twenty-six. Source code
is not provided for the additional tests, and you may not modify
this file (though you are welcome to reverse-engineer it if you'd like).
A Makefile is provided that will build both test programs, given an object file kstring.o. If you are using C++, use Makefile-cpp instead (and rename it to "Makefile").
Grading will be based in part on the performance of your library under the test-full suite. Your program should pass all twenty-six tests. Note that, if your library causes a test case to crash, you are considered to have failed that test and all the subsequent tests. The three test cases that expect your library to abort are constructed so that aborting does not terminate the test program itself.
The twenty-six test cases in test-full are as follows. The ones marked with an asterisk (*) also appear, with source code, in test-abbrev.c.
The test suites should execute without any memory leaks, crashes,
out-of-bounds memory accesses, or incorrectly freed memory
(freeing the same memory twice, attempting to free
memory that was not dynamically allocated, or in C++ using the
wrong version of delete).
If you are using C++ and the new operator for your project,
make memcheck will report the tests
that throw exceptions (test 5, and possibly tests 14 and 16) as skipped,
because of a limitation in valgrind's C++
support. This will not affect your grade, as long as those tests pass
when run without valgrind.
To test your program for memory errors, you can use valgrind :
valgrind --tool=memcheck --child-silent-after-fork=yes ./test-full
A Makefile rule is provided to run this command for you:
make memcheck.
Near the end of the output you want to see:
==22657== HEAP SUMMARY:
==22657== in use at exit: 0 bytes in 0 blocks
...
==22657== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
You may find it helpful to consult the
Valgrind
manual, especially the Quick Start Guide at the beginning.
Note: It is acceptible for your program to leak memory when it aborts; the three relevant test cases already take that possibility into account.
Your submission should include a README file. This should
be a plain text file with at least the following sections:
Likewise, if you noticed in your own testing any situations that your library does not handle well, even if they are not covered by the test cases, describe them here.
The design of the
frobulate()function benefitted from discussions with my tutor J. Random Hacker, who suggested doing the bit-twiddling before the loop rather than inside the loop.
Likewise, if you used code snippets from sites such as Stack Overflow, describe what you used, explain how it works in your own words, and provide the name of the author and the URL where they posted the code. For example:
Programming assignments are expected to be your own work, so any borrowed code should be very small relative to the total size of your program. You may not borrow code from or share code with other UK students at all.The data-copying loop in
perform_magic()is based on code written by C. Guru at:http://answermyprogrammingquestions.com/0xc0debeef/. The loop casts the character pointer to a integer pointer and uses that to copy four bytes of data at a time. If the number of bytes was not divisible by four, the code then copies the remaining 1-3 bytes individually.
Submit a zip or tar.gz file containing a directory with the following files:
test-full excecutable
combining the test suite in
test-full.o
with your kstring library. This may be the provided
Makefile,
a modified version of it, or a brand new Makefile.
To make a .tar.gz archive of the directory program1, you can use a command like:
tar czvf cs485-program1.tar.gz program1/
To make a .zip archive:
zip -r cs485-program1.zip program1/
Submit your .tar.gz or .zip file at the CS Portal website, under course CS485G006 and assignment "Programming Assignment 1 - kstring library".
This assignment will be scored out of 100 points:
-Wall.kstring.c came out to around 90 lines
not including comments. Yours may be shorter or longer of course, but
if it gets to be more than a few hundred lines, you may be making
the task more complicated than it needs to be.