Purpose: To provide an introduction to structured programming using the C/C++ language.
CS 2505 Computer Organization I C05: String Type in C
Version 5.00 This is a purely individual assignment! 1
C Programming Creating a String Data Type in C
For this assignment, you will use the struct mechanism in C to implement a data type that models a character string:
struct _String {
char *pData;
dynamically-allocated a
ay to hold the characters
uint32_t length;
number of characters in the string, excluding terminator
};
typedef struct _String String;
Since C a
ays (and C strings are essentially a
ays) don’t automatically keep track of their dimensions or usage, it seems
completely reasonable to capture all of that information inside of a struct, and use that to represent a flexible string type.
A proper String object S satisfies the following conditions:
 S.pData points to an a
ay of dimension S.length + 1 and S.pData[S.length] == '\0'.
 If S.length > 0, then S.data[0:S.length-1] hold the character data for the string.
A raw String object S satisfies the following conditions:
 S.pData may or may not be NULL.
 S.length has no significant value.
Pay close attention to the pre- and post-conditions and the return specifications for the functions declared later in this
assignment; you must make sure that you satisfy all those conditions.
A String object S representing "string" would have the following logical structure:
A few points should be made. First, the character a
ay is sized precisely to the string it represents, so there is no wasted
memory. Second, even though a String object stores the length of the character string, we still zero-terminate that a
ay;
this helps with operations like printing the contents of the String object.
In a proper String object, pData will never be NULL.
Also, the String type raises a deep-copy issue, since the character a
ay is allocated dynamically. Since C does not
provide automatic support for making a deep copy of structured variables, the functions we will implement are designed to
eceive pointers to String objects. This is discussed further on page 4.
The use of pointers as parameters provides an excuse to make good use of the const qualifier, applied to the pointer
and/or its target, as appropriate.
's' 't' 'r' 'i' 'n' 'g' '\0'
0x73 0x74 0x72 0x69 0x6E 0x67 0x00
S pData:
length: 6
CS 2505 Computer Organization I C05: String Type in C
Version 5.00 This is a purely individual assignment! 2
String Operations
A data type consists of a collection of values and a set of operations that may be performed on those values. For a string
type, it would make sense to provide the common string operations; for example:
** Appends the String *pSrc to the String *pDest.
*
* Pre:
* *pDest is a proper String object
* *pSrc is is a proper String object
* pSrc != pDest (i.e., the source and destination are different String objects)
* Post on success:
* pSrc->data is appended to the String pDest->data
* *pDest is a proper String object
* Post on failure:
* *pDest is unchanged
*
* Returns:
* the length of pDest->data, if nothing goes wrong;
* a negative value, if some e
or occurs
*/
int32_t String_strcat(String const *pDest, const String* const pSrc);
The design of String_strcat() follows the expected semantics of concatenating two strings. The function will append
a String *pSrc to the String *pDest, adjusting pDest->data and pDest->length as required. Note that
*pDest must be proper (as defined earlier) both before and after the function is called. And, there must be no memory
leaks.
For example, suppose we have the following String objects:
Then, the call String_strcat(&S1, &S2) should leave S1 as shown below, return the value 7, and leave S2
unchanged:
In the case of the String_strcat() function, there is a logical reason the function needs to modify the contents of the
String object *pDest, but not the pointer to it which is passed into the function, so the pointer is qualified as const,
ut the target of the pointer is not[1].
On the other hand, the same function has no reason to modify the String object pointed to by pSrc, nor to modify where
pSrc points, so both the pointer and its target are qualified as const[1].
There is also the question of whether stated preconditions should be checked within the function. The need for efficiency
would argue against; after all, the preconditions have been stated, so it's the caller's fault if they are not satisfied, and
checking them would require extra steps at runtime. And, some preconditions are essentially impossible to check.
On the other hand, the need for robustness would argue in favor of checking (checkable) preconditions, if violations of
them could result in serious runtime e
ors, especially if those e
ors could occur much later than the call itself.
'c' 'o' 'm' 'p' '\0'
'o' 'r' 'g' '\0'
'c' 'o' 'm' 'p' 'o' 'r' 'g' '\0'
S1 data:
length: 4
S2 data:
length: 3
S1 data:
length: 7
CS 2505 Computer Organization I C05: String Type in C
Version 5.00 This is a purely individual assignment! 3
You should consider these points carefully when designing your solution to this assignment. The testing/grading code will
always honor the stated preconditions, unless there are e
ors in your own code (e.g., creating a String object that is not
proper).
We will copy one aspect of an OO design; it's useful to provide a function that will create and initialize a new String
object:
** The String is initialized to hold the values in *pSrc.
*
* Pre:
* *pSrc is C string with length up to slength (excludes null char)
* Post on success:
* A new, proper String object S is created such that:
* S.data != pSrc->data
* Up to slength characters in *pSrc are copied into S.data
* XXXXXXXXXXafter dynamic allocation) and the new string is terminated
* XXXXXXXXXXwith a '\0'
* S.length is set to the number of characters copied from *pSrc;
* XXXXXXXXXXthis is no more than slength, but will be less if a '\0' is
* XXXXXXXXXXencountered in *pSrc before slength chars have occu
ed
* Post on failure:
* NULL is returned
*
* Returns:
* pointer to the new String object;
* NULL value if some e
or occurs
*/
String* String_Create(const char* const pSrc, uint32_t slength);
To some degree, this plays the roles of an allocator and of a constructor in an OO implementation. In Java, the constructor
does not allocate memory for the object itself (new does that); but the constructor may allocate memory for dynamic
content in the object. This function has both responsibilities.
The parameter slength allows us to initialize a String object from an unterminated char a
ay, or using a selected
part of an existing C-string. It also allows something of a safety net, in that the function will limit the number of characters
ead from *pSrc to slength[2].
The second required function is for comparisons:
** Compares two Strings.
*
* Pre:
* *pLeft is a proper String object
* *pRight is is a proper String object
*
* Returns:
* < 0 if *pLeft precedes *pRight, lexically
* XXXXXXXXXXif *pLeft equals *pRight
* > 0 if *pLeft follows *pRight, lexically
*/
int32_t String_strcmp(const String* const pLeft, const String* const pRight);
The interface is adapted from strcmp() in the C Standard Li
ary. Note that the return specification does not imply that
the values -1, 0 and 1 are the only possible results. That's entirely up to your design, and your solution is not expected to
eturn the same integers as the reference solution.
CS 2505 Computer Organization I C05: String Type in C
Version 5.00 This is a purely individual assignment! 4
The third required function allows a user to append one String to the end of another String:
** Appends the String *pSrc to the String *pDest.
*
* Pre:
* *pDest is a proper String object
* *pSrc is is a proper String object
* pSrc != pDest (i.e., the source and destination are different String
* XXXXXXXXXXobjects)
* Post on success:
* pSrc->pData is appended to the String pDest->data
* *pDest is a proper String object
* Post on failure:
* *pDest is unchanged
*
* Returns:
* the length of pDest->pData, if nothing goes wrong;
* a negative value, if some e
or occurs
*/
int32_t String_strcat(String* const pDest, const String* const pSrc);
Of course, this will normally require making sure that the destination String has a sufficiently large a
ay to hold the
necessary data, and doing so without creating any memory leaks[3].
The fourth required function allows a user to extract a (copy of) a specified substring of a given String:
** Makes an exact, full