1. A string abstract data type
For this assignment, you are to implement a mutable string type Superstring that provides bounds checking and various other operations.
The interface to your class is given by the header file superstring.h shown below (also available in the directory /c/cs223/Hwk4/template in the Zoo), which declares the functions you should implement in your own file superstring.c. The idea is that a Superstring of size n keeps track of a block of n+1 chars, where the last position is set to '\0' and can't be modified by the user. For more details, see the comments in the header file, or look at examples of use in the test_superstring.c file in the template directory.
The operations on a Superstring include three constructors (a general-purpose one that builds a Superstring of a given size, plus more specialized ones that build a Superstring from a given string or file descriptor); a destructor; a mutator that allows setting individual chars within a Superstring; and three accessors that return the size, contents, and upcased contents of a Superstring. For this last accessor, you should use the toupper routine declared in ctype.h, which computes the upper-case version of a character.
2. Compiling your program
In addition to superstring.h and test_superstring.h, the /c/cs223/Hwk4/template directory contains a Makefile that links your file superstring.c to test_superstring.c and runs the result when you type make test. You should copy all three files in /c/cs223/Hwk4/template to your development directory.
You do not need to submit anything except superstring.c; the test scripts will obtain the other files from the template directory.
3. Template files
1 /* this prevents problems with multiple inclusion */
2 #ifndef __SUPERSTRING_H
3 #define __SUPERSTRING_H 1
4
5 #include <stdio.h>
6
7 typedef struct superstring Superstring;
8
9 /* create a new superstring object initialized to all-nul
10 * that can hold up to size characters plus a final nul
11 */
12 Superstring *
13 superstringCreate(size_t size);
14
15 /* free a superstring and any related data */
16 void
17 superstringDestroy(Superstring *s);
18
19 /* create a new superstring with given initial contents */
20 /* size should be equal to strlen(s) */
21 Superstring *
22 superstringFromString(const char *s);
23
24 /* create a new superstring whose contents are read from a file */
25 /* size will be number of characters read before EOF */
26 Superstring *
27 superstringFromFile(FILE *f);
28
29 /* return the size of a superstring
30 * this will equal the argument passed to superstringCreate */
31 size_t
32 superstringSize(const Superstring *s);
33
34 /* set a byte of a superstring; returns 1 if position is in range */
35 /* if position is out of range, do nothing and return 0 */
36 int
37 superstringSet(Superstring *s, size_t position, int value);
38
39 /* return contents of a superstring as a string */
40 const char *
41 superstringAsString(const Superstring *s);
42
43 /* return upper-cased version of superstring
44 * e.g. puts(superstringUpcased(superstringFromString("abc")))
45 * will print "ABC".
46 *
47 * The user does *not* need to free the returned string,
48 * which should remain usable at least until the next
49 * time the superstring is modified.
50 */
51 const char *
52 superstringUpcased(const Superstring *s);
53
54 #endif
55
(You can download these files by clicking on the filenames.)
4. Submitting your assignment
Submit your file superstring.c using /c/cs223/bin/submit 4 superstring.c as usual. You may run the public test script /c/cs223/Hwk4/test.public on your submission using /c/cs223/bin/testit 4 public.
5. Sample solution
1 #include <stdlib.h>
2 #include <string.h>
3 #include <ctype.h>
4
5 #include "superstring.h"
6
7 struct superstring {
8 size_t size; /* size of this string */
9 char *buffer; /* contents; can hold size+1 bytes */
10 char *upcased_buffer; /* upper-case version of buffer */
11 };
12
13 /* create a new superstring object initialized to all-nul
14 * that can hold up to size characters plus a final nul.
15 */
16 Superstring *
17 superstringCreate(size_t size)
18 {
19 Superstring *s;
20
21 s = malloc(sizeof(struct superstring));
22
23 if(s == 0) {
24 return 0;
25 }
26
27 s->size = size;
28 s->buffer = calloc(size+1, 1);
29 s->upcased_buffer = calloc(size+1, 1);
30
31 if(s->buffer == 0 || s->upcased_buffer == 0) {
32 superstringDestroy(s);
33 return 0;
34 }
35
36 return(s);
37 }
38
39 /* free a superstring and any related data */
40 void
41 superstringDestroy(Superstring *s)
42 {
43 /* tests allows us to call this on incompletely-built superstrings */
44 if(s->buffer) free(s->buffer);
45 if(s->upcased_buffer) free(s->upcased_buffer);
46 free(s);
47 }
48
49 /* create a new superstring with given initial contents */
50 /* size should be equal to strlen(s) */
51 Superstring *
52 superstringFromString(const char *s)
53 {
54 Superstring *s2;
55 int i;
56 int len;
57
58 len = strlen(s);
59
60 s2 = superstringCreate(len);
61
62 if(s2 == 0) {
63 return 0;
64 }
65
66 /* using superstringSet is slow but safe */
67 for(i = 0; i < len; i++) {
68 superstringSet(s2, i, s[i]);
69 }
70
71 return s2;
72 }
73
74 /* internal helper for superstringFromFile */
75 /* resizes a superstring, extending with nulls or truncating
76 * as appropriate.*/
77 /* deallocates and returns 0 on error */
78 static Superstring *
79 superstringResize(Superstring *s, size_t new_size)
80 {
81 s->buffer = realloc(s->buffer, new_size+1);
82 s->upcased_buffer = realloc(s->upcased_buffer, new_size+1);
83
84 if(s->buffer == 0 || s->upcased_buffer == 0) {
85 superstringDestroy(s);
86 return 0;
87 }
88
89 /* put in new null terminator */
90 s->buffer[new_size] = '\0';
91 s->buffer[new_size] = '\0';
92
93 if(new_size > s->size) {
94 memset(s->buffer + s->size, 0, new_size - s->size);
95 memset(s->upcased_buffer + s->size, 0, new_size - s->size);
96 }
97
98 s->size = new_size;
99
100 return s;
101 }
102
103 #define FROMFILE_INITIAL_BUFFER_SIZE (1024)
104
105 /* create a new superstring whose contents are read from a file */
106 /* size will be number of characters read before EOF */
107 Superstring *
108 superstringFromFile(FILE *f)
109 {
110 Superstring *s; /* string under construction */
111 size_t i; /* position of next character */
112 int c; /* character from file */
113
114 s = superstringCreate(FROMFILE_INITIAL_BUFFER_SIZE);
115
116 if(s == 0) return 0;
117
118 for(i = 0; (c = getc(f)) != EOF; i++) {
119 if(i >= superstringSize(s)) {
120 s = superstringResize(s, superstringSize(s)*2);
121 if(s == 0) return 0;
122 }
123
124 superstringSet(s, i, c);
125 }
126
127 /* truncate to actual length */
128 return superstringResize(s, i);
129 }
130
131 /* return the size of a superstring
132 * this will equal the argument passed to superstringCreate */
133 size_t
134 superstringSize(const Superstring *s)
135 {
136 return s->size;
137 }
138
139 /* set a byte of a superstring; returns 1 if position is in range */
140 /* if position is out of range, do nothing and return 0 */
141 int
142 superstringSet(Superstring *s, size_t position, int value)
143 {
144 /* we don't check < 0 because size_t is unsigned */
145 if(position >= s->size) {
146 return 0;
147 } else {
148 s->buffer[position] = value;
149 s->upcased_buffer[position] = toupper(value);
150 return 1;
151 }
152 }
153
154 /* return contents of a superstring as a string */
155 const char *
156 superstringAsString(const Superstring *s)
157 {
158 return s->buffer;
159 }
160
161 /* return upper-cased version of superstring
162 * e.g. puts(superstringUpcased(superstringFromString("abc")))
163 * will print "ABC".
164 *
165 * The user does *not* need to free the returned string,
166 * which should remain usable at least until the next
167 * time the superstring is modified.
168 */
169 const char *
170 superstringUpcased(const Superstring *s)
171 {
172 return s->upcased_buffer;
173 }