Back

string.cpp coverage

overall coverage: 100.0%

line# code(run#)
1 #include <cstring>
2 #include <algorithm>
3 #include <stdexcept>
4 #include <iomanip>
5
6 #ifndef NO_MEMTRACE
7 #include "memtrace.h"
8 #endif
9
10 #include "myString.h"
11
12 void String::deleteDataBlockList(DataBlock *from)(315)
13 {
14 DataBlock *tmp = from; // just a simple linked list delete algorithm(315)
15 while (tmp != nullptr)(886)
16 {
17 DataBlock *toDelete = tmp;(571)
18 tmp = tmp->next;(571)
19 delete toDelete;(571)
20 }
21 }(315)
22
23 String::String() : size(0), startBlock(new DataBlock), endBlock(startBlock), cache(*this) {}(40)
24
25 String::String(char c) : size(1), startBlock(new DataBlock), endBlock(startBlock), cache(*this) // allocate memory for datablock(29)
26 {
27 startBlock->data[0] = c; // set first character(29)
28 }(29)
29
30 String::String(const char *s) : cache(*this)(99)
31 {
32 if (s == nullptr) // check if input is not nullptr(99)
33 {
34 size = 0;(2)
35 startBlock = new DataBlock;(2)
36 endBlock = startBlock;(2)
37 return; // set string params and return(2)
38 }
39
40 size = std::strlen(s); // set length(97)
41 size_t blockCount = size / 20 + 1; // minimum number of blocks to store data(97)
42 auto *prevDB = new DataBlock; // allocate block(97)
43 startBlock = prevDB; // and link it to the string(97)
44 endBlock = prevDB;(97)
45 std::strncpy(prevDB->data, s, std::min<size_t>(20, size)); // copy first (max 20) chars to the first block (less chars will be copied if the length of the source is less)(97)
46 for (size_t dbi = 1; dbi < blockCount; dbi++) // step through the rest of the datablocks and fill the with data(230)
47 {
48 auto *tmp = new DataBlock; // allocate and link new datablock(133)
49 prevDB->next = tmp;(133)
50 tmp->prev = prevDB;(133)
51 endBlock = tmp;(133)
52 prevDB = tmp;(133)
53
54 std::strncpy(tmp->data, s + dbi * 20, std::min<size_t>(20, size - dbi * 20)); // copy data to new block(133)
55 }
56
57 cache.reset(); // reset cache because the first block changed(97)
58 }
59 String::String(const String &s) : size(s.size), cache(*this)(129)
60 {
61 auto *tmp = new DataBlock; // allocate new block and link to string(129)
62 startBlock = tmp;(129)
63 endBlock = tmp;(129)
64 DataBlock *srctmp = s.startBlock; // source data(129)
65 std::strncpy(tmp->data, srctmp->data, 20); // copy first block (don't have to check for length, just copy some junk data in the worst case)(129)
66 while (srctmp != s.endBlock) // while not at the end of source string(202)
67 {
68 auto *newtmp = new DataBlock; // allocate new datablokc and link to string(73)
69 tmp->next = newtmp;(73)
70 newtmp->prev = tmp;(73)
71 endBlock = tmp = newtmp;(73)
72
73 srctmp = srctmp->next; // advance source pointer(73)
74
75 std::strncpy(tmp->data, srctmp->data, 20); // copy data(73)
76 }
77
78 cache.reset(); // reset cache because first block changed(129)
79 }(129)
80
81 String &String::operator=(char c)(2)
82 {
83 size = 1; // set size of string(2)
84 startBlock->data[0] = c; // set content of first datablock(2)
85 deleteDataBlockList(startBlock->next); // delete rest of the datablocks (if exist)(2)
86 startBlock->next = nullptr; // set pointer to next block to nullptr(2)
87 endBlock = startBlock; // and set entblock to startblock(2)
88
89 cache.reset(); // reset cache, because we could have removed some blocks(2)
90
91 return *this;(2)
92 }
93
94 String &String::operator=(const char *s)(12)
95 {
96 if (s == nullptr) // if nullptr was given(12)
97 {
98 size = 0; // construct an empty string(3)
99 deleteDataBlockList(startBlock->next);(3)
100 startBlock->next = nullptr;(3)
101 endBlock = startBlock;(3)
102
103 cache.reset();(3)
104
105 return *this;(3)
106 }
107
108 size = std::strlen(s); // set length(9)
109 size_t blockCount = size / 20 + 1; // number of blocks required(9)
110 auto tmp = startBlock;(9)
111
112 for (size_t blockIndex = 0; blockIndex < blockCount; blockIndex++)(27)
113 {
114 std::strncpy(tmp->data, s + blockIndex * 20, std::min(size_t(20), size - blockIndex * 20)); // copy data to block, do not overindex original char*(18)
115
116 if (tmp->next == nullptr) // if this is the last block(18)
117 {
118 auto newBlock = new DataBlock; // link new block to linked list(13)
119 tmp->next = newBlock;(13)
120 newBlock->prev = tmp;(13)
121 }
122
123 tmp = tmp->next; // go to next block(18)
124 }
125
126 endBlock = tmp->prev; // set end block(9)
127 endBlock->next = nullptr;(9)
128
129 deleteDataBlockList(tmp); // free remaining blocks (if remained from previous string)(9)
130
131 cache.reset();(9)
132
133 return *this;(9)
134 }
135
136 String &String::operator=(const String &s) // same as prevoius operator=(), this is just simpler(5)
137 {
138 if (this == &s)(5)
139 return *this;(1)
140
141 size = s.size;(4)
142 const size_t blockCount = size / 20 + 1;(4)
143 auto tmp = startBlock;(4)
144 auto srctmp = s.startBlock;(4)
145
146 for (size_t blockIndex = 0; blockIndex < blockCount; blockIndex++)(20)
147 {
148 std::strncpy(tmp->data, srctmp->data, 20);(16)
149
150 srctmp = srctmp->next;(16)
151
152 if (tmp->next == nullptr)(16)
153 {
154 auto newBlock = new DataBlock;(10)
155 tmp->next = newBlock;(10)
156 newBlock->prev = tmp;(10)
157 }
158
159 tmp = tmp->next;(16)
160 }
161
162 endBlock = tmp->prev;(4)
163 endBlock->next = nullptr;(4)
164 deleteDataBlockList(tmp);(4)
165
166 cache.reset();(4)
167
168 return *this;(4)
169 }
170
171 char &String::operator[](size_t idx)(47)
172 {
173 return cache.getChar(idx);(47)
174 }
175
176 char String::operator[](size_t idx) const(736)
177 {
178 return cache.getChar(idx);(736)
179 }
180
181 bool String::operator==(char c) const(20)
182 {
183 if (size != 1)(20)
184 return false;(8)
185 return startBlock->data[0] == c;(12)
186 }
187
188 bool String::operator==(const char *s) const(48)
189 {
190 if (s == nullptr)(48)
191 return false; // nullptr is invalid char*, cannot be equal with that(8)
192 size_t len = std::strlen(s);(40)
193 if (size != len)(40)
194 return false; // cannot be equal if lengths don't match(18)
195
196 size_t dataBlockCount = size / 20 + 1; // number of datablocks to check for equality(22)
197 auto dataBlock = startBlock;(22)
198
199 for (size_t dataBlockIndex = 0; dataBlockIndex < dataBlockCount; dataBlockIndex++)(38)
200 {
201 if (std::strncmp(s + dataBlockIndex * 20, dataBlock->data, std::min(size_t(20), len - 20 * dataBlockIndex)) != 0) // compare relevant data(28)
202 return false; // isn't equal if relevant data is different(12)
203 dataBlock = dataBlock->next; // go to next block(16)
204 }
205
206 return true;(10)
207 }
208
209 bool String::operator==(const String &s) const // almost same as prevoius compare(16)
210 {
211 if (this == &s)(16)
212 return true; // string is equal to itself(4)
213 if (size != s.size)(12)
214 return false;(4)
215
216 size_t dataBlockCount = size / 20 + 1;(8)
217 auto dataBlock0 = startBlock;(8)
218 auto dataBlock1 = s.startBlock;(8)
219
220 for (size_t dataBlockIndex = 0; dataBlockIndex < dataBlockCount; dataBlockIndex++)(36)
221 {
222 if (std::strncmp(dataBlock0->data, dataBlock1->data, std::min(size_t(20), size - 20 * dataBlockIndex)) != 0)(32)
223 return false;(4)
224 dataBlock0 = dataBlock0->next;(28)
225 dataBlock1 = dataBlock1->next;(28)
226 }
227
228 return true;(4)
229 }
230
231 bool String::operator!=(char c) const(10)
232 {
233 return !operator==(c);(10)
234 }
235
236 bool String::operator!=(const char *s) const(24)
237 {
238 return !operator==(s);(24)
239 }
240
241 bool String::operator!=(const String &s) const(8)
242 {
243 return !operator==(s);(8)
244 }
245
246 String String::operator+(char c) const(80)
247 {
248 String s0(*this);(80)
249 s0 += c;(80)
250 return s0;(80)
251 }
252
253 String String::operator+(const char *s) const(32)
254 {
255 String s0(*this);(32)
256 s0 += s;(32)
257 return s0;(32)
258 }
259
260 String String::operator+(const String &s) const(9)
261 {
262 String s0(*this);(9)
263 s0 += s;(9)
264 return s0;(9)
265 }
266
267 String &String::operator+=(char c)(349)
268 {
269 unsigned char offset = size % 20; // index of last free char in last block(349)
270 endBlock->data[offset] = c; // set that char to c (string always has 1 non-full block)(349)
271 size++; // increase size(349)
272 if (offset == 19) // if tthis was the last char of the block(349)
273 {
274 auto tmp = new DataBlock; // add new block to string(11)
275 endBlock->next = tmp;(11)
276 tmp->prev = endBlock;(11)
277 endBlock = tmp;(11)
278 }
279 return *this;(349)
280 }
281
282 String &String::operator+=(const char *c)(44)
283 {
284 if (c == nullptr)(44)
285 return *this; // cannot add nothing(8)
286
287 size_t len = std::strlen(c);(36)
288 unsigned char offset = size % 20; // index of last free char in last block(36)
289 unsigned char freeChars = 20 - offset; // number of free chars in last block(36)
290 size += len; // increase size of string(36)
291 std::strncpy(endBlock->data + offset, c, std::min((unsigned char)20, freeChars)); // fill last block with data(36)
292
293 if (len >= freeChars) // if last block was filled completely (length of c was more of equal to free space)(36)
294 {
295 size_t dataBlockCount = (len - freeChars) / 20 + 1; // number of new blocks to add to the string(12)
296 auto dataBlock = endBlock; // current end block(12)
297 for (size_t dataBlockIndex = 0; dataBlockIndex < dataBlockCount; dataBlockIndex++)(27)
298 {
299 auto newBlock = new DataBlock; // link new block(15)
300 dataBlock->next = newBlock;(15)
301 newBlock->prev = dataBlock;(15)
302 dataBlock = newBlock;(15)
303
304 std::strncpy(dataBlock->data, c + freeChars + dataBlockIndex * 20, std::min(size_t(20), len - freeChars - dataBlockIndex * 20)); // copy data to new block(15)
305 }
306 }
307 return *this;(36)
308 }
309
310 String &String::operator+=(const String &s)(15)
311 {
312 if (this == &s)(15)
313 return *this; // self append, doesn't make sense(1)
314
315 unsigned char offset = size % 20;(14)
316 unsigned char freeChars = 20 - offset;(14)
317 if (offset == 0) // current string ends with a complete free block(14)
318 {
319 std::strncpy(endBlock->data, s.startBlock->data, 20); // copy data to last block(3)
320
321 auto dataBlock = endBlock;(3)
322 auto sourceBlock = s.startBlock->next;(3)
323 while (sourceBlock != nullptr) // while there is a source block(6)
324 {
325 auto newBlock = new DataBlock; // link new block(3)
326 newBlock->prev = dataBlock;(3)
327 dataBlock->next = newBlock;(3)
328 dataBlock = newBlock;(3)
329
330 std::strncpy(dataBlock->data, sourceBlock->data, 20); // copy all data(3)
331 // may copy junk, but the size will take care of that
332
333 sourceBlock = sourceBlock->next; // go to next source block(3)
334 }
335 endBlock = dataBlock; // set end block(3)
336 size += s.size; // increase size(3)
337 return *this;(3)
338 }
339 else
340 {
341 std::strncpy(endBlock->data + offset, s.startBlock->data, freeChars); // fill remaining space(11)
342
343 if (s.size < freeChars)(11)
344 {
345 size += s.size;(1)
346 return *this; // return if there are no more data to copy(1)
347 }
348
349 unsigned char sOffset = s.size % 20; // index of first empty char in source string(10)
350 auto dataBlock = endBlock; // current end block(10)
351 auto sourceBlock = s.startBlock; // current source block(10)
352 while (true)
353 {
354 auto newBlock = new DataBlock; // link new block(16)
355 dataBlock->next = newBlock;(16)
356 newBlock->prev = dataBlock;(16)
357 dataBlock = newBlock; // and make it the current block(16)
358
359 std::strncpy(dataBlock->data, sourceBlock->data + freeChars, offset); // copy remaining data from prevoius source block(16)
360
361 sourceBlock = sourceBlock->next; // go to next source blcok(16)
362 if (sourceBlock == nullptr) // return if no more source blocks(16)
363 {
364 endBlock = dataBlock;(4)
365 size += s.size;(4)
366 return *this;(4)
367 }
368
369 std::strncpy(dataBlock->data + offset, sourceBlock->data, freeChars); // fill current block with data from next source blcok(12)
370
371 if (sourceBlock == s.endBlock && freeChars > sOffset) // source block has no more important data(12)
372 {
373 endBlock = dataBlock;(6)
374 size += s.size;(6)
375 return *this;(6)
376 }
377 }(6)
378 }
379 }
380
381 String String::substr(size_t from, size_t len) const(6)
382 {
383 String ss;(6)
384 for (size_t idx = from; idx < from + len; idx++)(215)
385 ss += operator[](idx);(212)
386
387 return ss;(3)
388 }
389
390 const char *String::c_str(bool autoFree) const(122)
391 {
392 auto *a = new char[size + 1]; // allocate memory for string(122)
393 size_t dataBlockCount = size / 20 + 1; // number of datablocks to go through(122)
394 auto dataBlock = startBlock; // current datablcok(122)
395 for (size_t dataBlockIndex = 0; dataBlockIndex < dataBlockCount; dataBlockIndex++)(368)
396 {
397 std::strncpy(a + dataBlockIndex * 20, dataBlock->data, std::min(size_t(20), size - dataBlockIndex * 20)); // copy valid data to new string(246)
398 dataBlock = dataBlock->next; // go to next block(246)
399 }
400 a[size] = '\0'; // close c-string(122)
401 if (autoFree) // store pointer if autofree(122)
402 {
403 delete[] cString; // free current string before storing(108)
404 cString = a;(108)
405 }
406 return a;(122)
407 }
408
409 void String::free_c_str() const(2)
410 {
411 delete[] cString;(2)
412 cString = nullptr;(2)
413 }(2)
414
415 size_t String::length() const(18)
416 {
417 return size;(18)
418 }
419
420 size_t String::find(char c) const(5)
421 {
422 size_t idx = 0;(5)
423 while (true)
424 {
425 if (operator[](idx) == c) // will throw exception if at end of string(158)
426 return idx;(3)
427 idx++;(153)
428 }
429 }
430
431 size_t String::find(const char *s) const(9)
432 {
433 if (s == nullptr)(9)
434 throw std::out_of_range("invalid input"); // cannot find nullptr(1)
435
436 size_t sLen = std::strlen(s);(8)
437 size_t idx = 0;(8)
438 while (true)
439 {
440 if (operator[](idx) == s[0]) // if first character matches, will throw if end of string(314)
441 {
442 bool allMatch = true;(10)
443 for (size_t sIdx = 1; sIdx < sLen; sIdx++) // check if rest of the characters match(33)
444 allMatch = operator[](idx + sIdx) == s[sIdx] ? allMatch : false; // will throw if end of string(40)
445 if (allMatch)(10)
446 return idx; // return index if all matched(4)
447 }
448 idx++;(306)
449 }(306)
450 }(17)
451
452 size_t String::find(const String &s) const(4)
453 {
454 const char *c = s.c_str(false); // convert to c string, autofree disabled to not mess with original string(4)
455 try
456 {
457 size_t idx = find(c); // find c string(4)
458 delete[] c; // free memory(2)
459 return idx; // return index(2)
460 }
461 catch (...) // if something bad(4)
462 {
463 delete[] c; // free memory(2)
464 throw; // let the rest of the program deal with it...(2)
465 }
466 }
467
468 String::Iterator String::begin()(2)
469 {
470 return Iterator(0, *this);(2)
471 }
472
473 String::ConstIterator String::begin() const(2)
474 {
475 return ConstIterator(0, *const_cast<String *>(this)); // const cast for cache in iterator, iterator won't return char&, only char(2)
476 }
477
478 String::Iterator String::end()(2)
479 {
480 return Iterator(size, *this);(2)
481 }
482
483 String::ConstIterator String::end() const(2)
484 {
485 return ConstIterator(size, *const_cast<String *>(this)); // const cast for cache in iterator, iterator won't return char&, only char(2)
486 }
487
488 String::~String()(297)
489 {
490 deleteDataBlockList(startBlock);(297)
491 delete[] cString;(297)
492 }(297)
493
494 std::ostream &operator<<(std::ostream &os, const String &s)(4)
495 {
496 auto dataBlock = s.startBlock;(4)
497 char tmp[21]; // temporary to hold data to write to stream
498 while (dataBlock->next != nullptr) // go through linked list(10)
499 {
500 std::strncpy(tmp, dataBlock->data, 20); // copy data(6)
501 tmp[20] = '\0';(6)
502 os << tmp; // write to stream(6)
503 dataBlock = dataBlock->next; // go to next block(6)
504 }
505
506 std::strncpy(tmp, s.endBlock->data, s.size % 20); // copy last chars(4)
507 tmp[s.size % 20] = '\0'; // set end of string properly(4)
508 os << tmp; // write to stream(4)
509 return os;(4)
510 }
511
512 std::istream &operator>>(std::istream &is, String &s)(3)
513 {
514 int c = is.get(); // get char from stream(3)
515 while (c != '\n' && c != '\r' && c != EOF) // char not end chars(23)
516 {
517 s += (char)c; // append to string(20)
518 c = is.get(); // read new char(20)
519 }
520
521 return is;(3)
522 }