[SOLVED] C++ C data structure compiler Program 1: Counted String Library

Program 1: Counted String Library
Programming assignments in CS 270 areindividual 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, youmust cite the sourcein your README file.
For this assignment, you are explicitly permitted to share the disassembled code oftest-full.o, should you and your classmates wish to work together to figure out exactly what the tests are doing.
Background
The built-inC string library(Links to an external site.)Links to an external site.usesnull-terminated strings, where a string is simply (a pointer to) an array of characters, with the character(NUL) marking the end of the string. While this is a convenient representation because a string parameter can be a simple primitive type (char*orconstchar*), it has several problems:
Determining the length of a C string (withstrlen()(Links to an external site.)Links to an external site.) is a linear-time operation: it must scan the array until it finds the first.
C strings cannot contain thecharacter. That means a string cannot represent an arbitrary string of bytes, for example the contents of a binary file.
C strings are difficult to use securely. For example, the documentation forstrcat()(Links to an external site.)Links to an external site.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 programs 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-calledcounted 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;
};
The C++ library, for example, is based on counted strings.
Your task
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 inkstring.h. A set of function stubs, which you may use as the basis for your implementation, is provided inkstring-stubs.c.
Provided files
Makefilefor building the project.
kstring.h: definition of thekstringstructure, and prototypes for the functions you will implement.
kstring-stubs.c: do-nothing stub implementations of the functions.
test-abbrev.c: code for the test harness and 13 of the 26 test cases
test-full.o: object file containing the test harness and all 26 test cases.
Specifications
Your library should implement the following eight functions. Prototypes for the functions, and the definition of thekstringstruct (like a class, but with public data and no member functions), are in the providedkstring.h.
kstring kstralloc(size_t nbytes)
Creates and returns a new kstring object with the specified length. The.lengthmember of the returned kstring should be equal tonbytes. The.datamember should be a pointer to newly-allocated memory; the memory should be initialized by filling it withnbytescopies of the null byte (). You can do so by hand or by using thememset()(Links to an external site.)Links to an external site.function
If there is an error allocating memory, this function should callabort()(Links to an external site.)Links to an external site..
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.lengthmember of the returned kstring should be the length ofcstr, plus one for the null terminator. The.datamember should be a pointer to newly-allocated memory (using , into which you have copied the contents ofcstr, including the null byte at the end.
If there is an error allocating memory, this function should callabort().
void kstrfree(kstring str)
Frees the memory to whichstr.datapoints. Should correctly handle any kstring created with eitherkstralloc()orkstrfrom(), 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 callers responsibility not to re-use the kstring it passed to this function.
size_t kstrlen(kstring str)
Returns the length of the kstringstr(that is,str.length).
char kstrget(kstring str, size_t pos)
Returns the character at indexposinstrs data.
Ifposis out of bounds (greater than or equal to the length ofstr), this function should abort the program by callingabort().
void kstrput(kstring str, size_t pos, char ch)
Replaces the character at indexposinstrs data with the characterch.
Ifposis out of bounds (greater than or equal to the length ofstr), this function should abort the program by callingabort().
void kstrextend(kstring *strp, size_t nbytes)
Modifies an existing kstring, pointed to bystrp, to be at leastnbytesbytes long.
Ifstrp->lengthwas already nbytes or longer, does nothing. That is, this function will never reduce the length of a string, only increase it.
Ifnbytesis longer than the current length, this function should take the following steps:
Allocate a new array with the larger size.
Copy data over from the old array to the new one.
Free the old array.
Fill the additional elements of the new array with null bytes ().
Makestrp->datapoint to the new array.
Setstrp->lengthto the new size.
Note: if you are usingmalloc()for memory allocation, the functionrealloc()(Links to an external site.)Links to an external site.will take care of steps 1, 2, and 3 with a single function call.
If there is an error allocating memory, this function should callabort().
Note that this function takes a pointer to a kstring rather than taking a kstring by value. That means that changes you make to thestrp->lengthandstrp->datamemberswillbe visible to the caller.
void kstrcat(kstring *destp, kstring src)
Concatenatesstronto the end of*destp. First extends*destpto be long enough to hold the contents of both strings, by callingkstrextend(). 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
kstring b = kstrfrom(world); // 6 bytes including
kstrcat(&a, b);
Nowashould have length 12, and the contentshelloworld.
Note that this function takes a pointer to the destination kstring. That means that changes you make to thedestp->lengthanddestp->datamemberswillbe visible to the caller.
Note: Remember to save the original length of*destpbefore callingkstrextend(). Otherwise, you wont know where to copysrcs data to!
Constraints and technical restrictions
Your library may be written in C,notC++. You may use any version of the C standard, but you must edit the Makefile to use the correct version flag inCFLAGS:
-std=c89: old-school ANSI C (gccdefault).
-std=c99: the most commonly-used version of modern C.
-std=c11: the most recent C standard.
Your library should compile with the-Wallcompiler flag (enable all warnings), without producing any compiler or linker warnings or errors.
Your library must work with the providedkstring.hwithout modification.
All dynamic memory allocation should usemalloc,calloc,realloc, andfree(Links to an external site.)Links to an external site..
You may use the standard C string functions (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 exceptkstrfrom()(which takes a null terminated string as its argument).
It must be possible to link and run your library with the providedtest-full.oon the class virtual machines.
If memory allocation fails, and in certain other conditions, your program should abort by callingabort()(Links to an external site.)Links to an external site.. Simply exiting the program withexit()(Links to an external site.)Links to an external site.is not enough!
Test cases
Two test suites are provided for your program. The first,test-abbrev.c, contains thirteen functions, each implementing a test cases, as well as amain()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 totest-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 youd like).
AMakefileis provided that will build both test programs, given an object file kstring.o. It will also compile kstring.o from a file named kstring.c.
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, intest-abbrev.c.
* kstralloc + kstrfree (simply checks that calling the two functions properly does not crash)
* kstralloc initializes memory to 0
* kstralloc sets length
kstralloc sets length (big)
* kstralloc sets length (0 bytes)
kstralloc aborts on allocation failure (expected to abort)
* kstrlen matches allocation
kstrlen matches allocation (big)
kstrlen matches allocation (0 bytes)
* kstrfrom gives correct length
* kstrfrom contains null byte
kstrfrom contains correct data
kstrfrom copies, not shares, data
* kstrget fetches all indices correctly
kstrget aborts when out of bounds (expected to abort)
* kstrput sets all indices correctly
kstrput aborts when out of bounds (expected to abort)
* kstrextend lengthens kstring
* kstrextend does not shorten kstring
kstrextend supports length-0 kstring
kstrextend copies old contents
kstrextend extends with null bytes
kstrcat of two empty kstrings (empty here means length zero)
* kstrcat with empty kstring (second argument is empty)
kstrcat onto empty kstring (first argument is empty)
* kstrcat has correct data (neither argument is empty)
Memory safety
The test suites should execute without any memory leaks, crashes, out-of-bounds memory accesses, or incorrectly freed memory (freeing the same memory twice, or attempting to free memory that was not dynamically allocated).
To test your program for memory errors, you can usevalgrind:
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 theValgrind manual(Links to an external site.)Links to an external site., 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.
Documentation
Your submission should include aREADMEfile. This should be aplain textfile with at least the following sections:
Author: Your name and email address, and the date the program was finished.
Contents: A list of all the files in your submission, with a brief one-line description of each. For example, kstring.c: implementation of kstring functions, or README: this file.
Running: Brief instructions explaining how to compile and run your program.
Implementation notes: Describe any design decisions you made when implementing your functions. For example: which method do they use to allocate memory, how do you detect and handle errors, and did you implement any additional helper functions?
Limitations: If you have any failing test cases, memory leaks, or other memory errors, describe the problems here. Where do the problems occur, what steps did you take to try to solve them, and what further steps would you take if you had more time?
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.
References: If you discussed the design of your program with anyone, list them here and describe their contribution. For example:
The design of thefrobulate()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:
The data-copying loop inperform_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.
Programming assignments are expected to be your own work, so any borrowed code should bevery smallrelative to the total size of your program. You may not borrow code from or share code with other UK students at all.
What to submit
Submit a zip or tar.gz file containing a directory with the following files:
The source code for your implementation of the kstring library.
A Makefile that builds atest-fullexcecutable combining the test suite intest-full.owith your kstring library. This may be the providedMakefile, a modified version of it, or a brand new Makefile.
Aplain textREADME file as described in Documentation above.
A typescript (a terminal log produced by the programscript) namedscript.txt,that shows the process of building and executing your test program on the class VM.
To make a .tar.gz archive of the directoryprogram1, you can use a command like:
tar czvf cs270-program1.tar.gz program1/
To make a .zip archive:
zip -r cs270-program1.zip program1/
Submit your .tar.gz or .zip file to this assignment.
Grading
This assignment will be scored out of 100 points:
52 points: 2 points per test case passed. Remember that if the test program crashes, all subsequent tests are considered to have failed.
15 points: program compiles with no warnings under-Wall.
15 points: the test cases run without any memory errors or memory leaks,as reported byvalgrind. See section Memory safety above.
9 points: documentation is complete, readable, and error-free.
9 points: code showsgood style(Links to an external site.)Links to an external site.(variable names, formatting, error handling, etc). This includes comments!
Hints and FAQs
I would recommend implementing your functions in the order they appear in the test cases. First get the second test to pass without crashing, then the third test, then the fourth, and so on.
Be sure to usevalgrindto check your program for memory leaks and array bounds exceptions. See section Memory safety above.
My implementation ofkstring.ccame 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.
PreviousNext