1 /*
2 * Copyright (C) 2009 The Android Open Source Project
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in
12 * the documentation and/or other materials provided with the
13 * distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29 #include <string>
30 #include <algorithm>
31 #include <climits>
32 #include <cstddef>
33 #include <cstring>
34 #include <malloc.h>
35 #include <ostream>
36
37 #ifndef MAX_SIZE_T
38 #define MAX_SIZE_T (~(size_t)0)
39 #endif
40
41 namespace {
42 char kEmptyString[1] = { '\0' };
43 // Dummy char used in the 'at' accessor when the index is out of
44 // range.
45 char sDummy;
46 }
47
48 namespace std {
49 // Implementation of the std::string class.
50 //
51 // mData points either to a heap allocated array of bytes or the constant
52 // kEmptyString when empty and reserve has not been called.
53 //
54 // The size of the buffer pointed by mData is mCapacity + 1.
55 // The extra byte is need to store the '\0'.
56 //
57 // mCapacity is either mLength or the number of bytes reserved using
58 // reserve(int)).
59 //
60 // mLength is the number of char in the string, excluding the terminating '\0'.
61 //
62 // TODO: replace the overflow checks with some better named macros.
63 //
64 // Allocate n + 1 number of bytes for the string. Update mCapacity.
65 // Ensure that mCapacity + 1 and mLength + 1 is accessible.
66 // In case of error the original state of the string is restored.
67 // @param n Number of bytes requested. String allocate n + 1 to hold
68 // the terminating '\0'.
69 // @return true if the buffer could be allocated, false otherwise.
SafeMalloc(size_type n)70 bool string::SafeMalloc(size_type n)
71 {
72 // Not empty and no overflow
73 if (n > 0 && n + 1 > n)
74 {
75 value_type *oldData = mData;
76
77 mData = static_cast<value_type *>(::malloc(n + 1));
78 if (NULL != mData)
79 {
80 mCapacity = n;
81 return true;
82 }
83 mData = oldData; // roll back
84 }
85 return false;
86 }
87
88 // Resize the buffer pointed by mData if n >= mLength.
89 // mData points to an allocated buffer or the empty string.
90 // @param n The number of bytes for the internal buffer.
91 // Must be > mLength and > 0.
SafeRealloc(size_type n)92 void string::SafeRealloc(size_type n)
93 {
94 // truncation or nothing to do or n too big (overflow)
95 if (n < mLength || n == mCapacity || n + 1 < n) {
96 return;
97 }
98
99 if (kEmptyString == mData)
100 {
101 if (SafeMalloc(n)) {
102 *mData = '\0';
103 }
104 return;
105 }
106
107 value_type *oldData = mData;
108
109 mData = static_cast<char*>(::realloc(mData, n + 1));
110 if (NULL == mData) // reallocate failed.
111 {
112 mData = oldData;
113 }
114 else
115 {
116 mCapacity = n;
117 }
118 }
119
SafeFree(value_type * buffer)120 void string::SafeFree(value_type *buffer)
121 {
122 if (buffer != kEmptyString)
123 {
124 ::free(buffer);
125 }
126 }
127
128 // If the memory is on the heap, release it. Do nothing we we point at the empty
129 // string. On return mData points to str.
ResetTo(value_type * str)130 void string::ResetTo(value_type *str)
131 {
132 SafeFree(mData);
133 mData = str;
134 }
135
ConstructEmptyString()136 void string::ConstructEmptyString()
137 {
138 mData = kEmptyString;
139 mLength = 0;
140 mCapacity = 0;
141 }
142
Constructor(const value_type * str,size_type n)143 void string::Constructor(const value_type *str, size_type n)
144 {
145 Constructor(str, 0, n);
146 }
147
148
Constructor(const value_type * str,size_type pos,size_type n)149 void string::Constructor(const value_type *str, size_type pos, size_type n)
150 {
151 // Enough data and no overflow
152 if (SafeMalloc(n))
153 {
154 memcpy(mData, str + pos, n);
155 mLength = n;
156 mData[mLength] = '\0';
157 return; // Success
158 }
159 ConstructEmptyString();
160 }
161
Constructor(size_type n,char c)162 void string::Constructor(size_type n, char c)
163 {
164 // Enough data and no overflow
165
166 if (SafeMalloc(n))
167 {
168 memset(mData, c, n);
169 mLength = n;
170 mData[mLength] = '\0';
171 return; // Success
172 }
173 ConstructEmptyString();
174 }
175
string()176 string::string()
177 {
178 ConstructEmptyString();
179 }
180
string(const string & str)181 string::string(const string& str)
182 {
183 Constructor(str.mData, str.mLength);
184 }
185
string(const string & str,size_type pos,size_type n)186 string::string(const string& str, size_type pos, size_type n)
187 {
188 if (pos < str.mLength)
189 {
190 if (n > (str.mLength - pos)) {
191 n = str.mLength - pos;
192 }
193 Constructor(str.mData + pos , n);
194 }
195 else
196 {
197 ConstructEmptyString();
198 }
199 }
200
string(const string & str,size_type pos)201 string::string(const string& str, size_type pos)
202 {
203 if (pos < str.mLength)
204 {
205 Constructor(str.mData, pos, str.mLength - pos);
206 }
207 else
208 {
209 ConstructEmptyString();
210 }
211 }
212
string(const value_type * str)213 string::string(const value_type *str)
214 {
215 if (NULL != str)
216 {
217 Constructor(str, traits_type::length(str));
218 }
219 else
220 {
221 ConstructEmptyString();
222 }
223 }
224
string(const value_type * str,size_type n)225 string::string(const value_type *str, size_type n)
226 {
227 Constructor(str, n);
228 }
229
230 // Char repeat constructor.
string(size_type n,char c)231 string::string(size_type n, char c)
232 {
233 Constructor(n, c);
234 }
235
string(const value_type * begin,const value_type * end)236 string::string(const value_type *begin, const value_type *end)
237 {
238 if (begin < end)
239 {
240 Constructor(begin, end - begin);
241 }
242 else
243 {
244 ConstructEmptyString();
245 }
246 }
247
~string()248 string::~string()
249 {
250 clear(); // non virtual, ok to call.
251 }
252
clear()253 void string::clear()
254 {
255 mCapacity = 0;
256 mLength = 0;
257 ResetTo(kEmptyString);
258 }
259
erase(size_type pos,size_type n)260 string& string::erase(size_type pos, size_type n)
261 {
262 if (pos >= mLength || 0 == n)
263 {
264 return *this;
265 }
266 // start of the characters left which need to be moved down.
267 const size_t remainder = pos + n;
268
269 // Truncate, even if there is an overflow.
270 if (remainder >= mLength || remainder < pos)
271 {
272 *(mData + pos) = '\0';
273 mLength = pos;
274 return *this;
275 }
276 // remainder < mLength and allocation guarantees to be at least
277 // mLength + 1
278 size_t left = mLength - remainder + 1;
279 value_type *d = mData + pos;
280 value_type *s = mData + remainder;
281 memmove(d, s, left);
282 mLength -= n;
283 return *this;
284 }
285
Append(const value_type * str,size_type n)286 void string::Append(const value_type *str, size_type n)
287 {
288 const size_type total_len = mLength + n;
289
290 // n > 0 and no overflow for the string length + terminating null.
291 if (n > 0 && (total_len + 1) > mLength)
292 {
293 if (total_len > mCapacity)
294 {
295 reserve(total_len);
296 if (total_len > mCapacity)
297 { // something went wrong in the reserve call.
298 return;
299 }
300 }
301 memcpy(mData + mLength, str, n);
302 mLength = total_len;
303 mData[mLength] = '\0';
304 }
305 }
306
append(const value_type * str)307 string& string::append(const value_type *str)
308 {
309 if (NULL != str)
310 {
311 Append(str, traits_type::length(str));
312 }
313 return *this;
314 }
315
append(const value_type * str,size_type n)316 string& string::append(const value_type *str, size_type n)
317 {
318 if (NULL != str)
319 {
320 Append(str, n);
321 }
322 return *this;
323 }
324
append(const value_type * str,size_type pos,size_type n)325 string& string::append(const value_type *str, size_type pos, size_type n)
326 {
327 if (NULL != str)
328 {
329 Append(str + pos, n);
330 }
331 return *this;
332 }
333
append(const string & str)334 string& string::append(const string& str)
335 {
336 Append(str.mData, str.mLength);
337 return *this;
338 }
339
340 // Specialization to append from other strings' iterators.
341 template<>
append(__wrapper_iterator<const char *,string> first,__wrapper_iterator<const char *,string> last)342 string& string::append<__wrapper_iterator<const char *,string> >(
343 __wrapper_iterator<const char *,string> first,
344 __wrapper_iterator<const char *,string> last) {
345 Append(&*first, std::distance(first, last));
346 return *this;
347 }
348 template<>
append(__wrapper_iterator<char *,string> first,__wrapper_iterator<char *,string> last)349 string& string::append<__wrapper_iterator<char *,string> >(
350 __wrapper_iterator<char *,string> first,
351 __wrapper_iterator<char *,string> last) {
352 Append(&*first, std::distance(first, last));
353 return *this;
354 }
355
push_back(const char c)356 void string::push_back(const char c)
357 {
358 // Check we don't overflow.
359 if (mLength + 2 > mLength)
360 {
361 const size_type total_len = mLength + 1;
362
363 if (total_len > mCapacity)
364 {
365 reserve(total_len);
366 if (total_len > mCapacity)
367 { // something went wrong in the reserve call.
368 return;
369 }
370 }
371 *(mData + mLength) = c;
372 ++mLength;
373 mData[mLength] = '\0';
374 }
375 }
376
377
compare(const string & other) const378 int string::compare(const string& other) const
379 {
380 if (this == &other)
381 {
382 return 0;
383 }
384 else if (mLength == other.mLength)
385 {
386 return memcmp(mData, other.mData, mLength);
387 }
388 else
389 {
390 return mLength < other.mLength ? -1 : 1;
391 }
392 }
393
compare(const value_type * other) const394 int string::compare(const value_type *other) const
395 {
396 if (NULL == other)
397 {
398 return 1;
399 }
400 return strcmp(mData, other);
401 }
402
operator ==(const string & left,const string & right)403 bool operator==(const string& left, const string& right)
404 {
405 if (&left == &right) {
406 return true;
407 }
408 return (left.size() == right.size() &&
409 !char_traits<char>::compare(left.mData, right.mData, left.size()));
410 }
411
operator ==(const string & left,const string::value_type * right)412 bool operator==(const string& left, const string::value_type *right)
413 {
414 if (NULL == right) {
415 return false;
416 }
417 // We can use strcmp here because even when the string is build from an
418 // array of char we insert the terminating '\0'.
419 return std::strcmp(left.mData, right) == 0;
420 }
421
reserve(size_type size)422 void string::reserve(size_type size)
423 {
424 if (0 == size)
425 {
426 if (0 == mCapacity)
427 {
428 return;
429 }
430 else if (0 == mLength)
431 { // Shrink to fit an empty string.
432 mCapacity = 0;
433 ResetTo(kEmptyString);
434 }
435 else
436 { // Shrink to fit a non empty string
437 SafeRealloc(mLength);
438 }
439 }
440 else if (size > mLength)
441 {
442 SafeRealloc(size);
443 }
444 }
445
swap(string & other)446 void string::swap(string& other)
447 {
448 if (this == &other) return;
449 value_type *const tmp_mData = mData;
450 const size_type tmp_mCapacity = mCapacity;
451 const size_type tmp_mLength = mLength;
452
453 mData = other.mData;
454 mCapacity = other.mCapacity;
455 mLength = other.mLength;
456
457 other.mData = tmp_mData;
458 other.mCapacity = tmp_mCapacity;
459 other.mLength = tmp_mLength;
460 }
461
operator [](const size_type pos) const462 const char& string::operator[](const size_type pos) const
463 {
464 return mData[pos];
465 }
466
operator [](const size_type pos)467 char& string::operator[](const size_type pos)
468 {
469 return mData[pos];
470 }
471
at(const size_type pos) const472 const char& string::at(const size_type pos) const
473 {
474 if (pos < mLength) {
475 return mData[pos];
476 } else {
477 sDummy = 'X';
478 return sDummy;
479 }
480 }
481
at(const size_type pos)482 char& string::at(const size_type pos)
483 {
484 if (pos < mLength) {
485 return mData[pos];
486 } else {
487 sDummy = 'X';
488 return sDummy;
489 }
490 }
491
assign(const string & str)492 string& string::assign(const string& str)
493 {
494 clear();
495 Constructor(str.mData, str.mLength);
496 return *this;
497 }
498
assign(const string & str,size_type pos,size_type n)499 string& string::assign(const string& str, size_type pos, size_type n)
500 {
501 if (pos >= str.mLength)
502 { // pos is out of bound
503 return *this;
504 }
505 if (n <= str.mLength - pos)
506 {
507 clear();
508 Constructor(str.mData, pos, n);
509 }
510 return *this;
511 }
512
assign(const value_type * str)513 string& string::assign(const value_type *str)
514 {
515 if (NULL == str)
516 {
517 return *this;
518 }
519 clear();
520 Constructor(str, traits_type::length(str));
521 return *this;
522 }
523
assign(const value_type * array,size_type n)524 string& string::assign(const value_type *array, size_type n)
525 {
526 if (NULL == array || 0 == n)
527 {
528 return *this;
529 }
530 clear();
531 Constructor(array, n);
532 return *this;
533 }
534
insert(iterator iter,char c)535 string::iterator string::insert(iterator iter, char c) {
536 const size_type new_len = mLength + 1;
537 char *base = iter.base();
538
539 if (base < mData || base > mData + mLength || new_len < mLength) {
540 return iterator(&sDummy); // out of bound || overflow
541 }
542
543 const size_type pos = base - mData;
544 if (new_len > mCapacity) {
545 reserve(new_len);
546 if (new_len > mCapacity) {
547 return iterator(&sDummy); // not enough memory?
548 }
549 }
550 // At this point 'iter' and 'base' are not valid anymore since
551 // realloc could have taken place.
552 base = mData + pos;
553 std::memmove(base + 1, base, mLength - pos);
554 *base = c;
555 mLength = new_len;
556 mData[mLength] = 0;
557 return iterator(base);
558 }
559
operator =(char c)560 string& string::operator=(char c)
561 {
562 clear();
563 Constructor(1, c);
564 return *this;
565 }
566
find(const value_type * str,size_type pos) const567 string::size_type string::find(const value_type *str, size_type pos) const
568 {
569
570 if (NULL == str)
571 {
572 return string::npos;
573 }
574
575 // Empty string is found everywhere except beyond the end. It is
576 // possible to find the empty string right after the last char,
577 // hence we used mLength and not mLength - 1 in the comparison.
578 if (*str == '\0')
579 {
580 return pos > mLength ? string::npos : pos;
581 }
582
583 if (mLength == 0 || pos > mLength - 1)
584 {
585 return string::npos;
586 }
587
588 value_type *idx = std::strstr(mData + pos, str);
589
590 if (NULL == idx)
591 {
592 return string::npos;
593 }
594
595 const std::ptrdiff_t delta = idx - mData;
596
597 return static_cast<size_type>(delta);
598 }
599
substr(size_type pos,size_type n) const600 string string::substr(size_type pos, size_type n) const {
601 return string(*this, pos, n);
602 }
603
find_first_of(value_type c,size_type pos) const604 string::size_type string::find_first_of(value_type c, size_type pos) const {
605 if (pos >= mLength) {
606 return npos;
607 }
608 const char *res;
609 // The last parameter represents a number of chars, not a index.
610 res = static_cast<const char *>(std::memchr(mData + pos, c, mLength - pos));
611 return res != NULL ? res - mData : npos;
612 }
613
find_last_of(value_type c,size_type pos) const614 string::size_type string::find_last_of(value_type c, size_type pos) const {
615 if (mLength == 0) {
616 return npos;
617 } else if (pos >= mLength) {
618 pos = mLength - 1; // >= 0
619 }
620
621 const char *res;
622 // Note:memrchr is not in the std namepace.
623 // The last parameter represents a number of chars, not a index.
624 res = static_cast<const char *>(memrchr(mData, c, pos + 1));
625 return res != NULL ? res - mData : npos;
626 }
627
find_first_not_of(value_type c,size_type pos) const628 string::size_type string::find_first_not_of(value_type c, size_type pos) const {
629 char *curr = mData + pos;
630 for (size_type i = pos; i < mLength; ++i, ++curr) {
631 if (c != *curr) {
632 return i;
633 }
634 }
635 return npos;
636 }
637
find_last_not_of(value_type c,size_type pos) const638 string::size_type string::find_last_not_of(value_type c, size_type pos) const {
639 if (mLength == 0) {
640 return npos;
641 } else if (pos >= mLength) {
642 pos = mLength - 1; // >= 0
643 }
644
645 char *curr = mData + pos;
646 size_type i = pos;
647
648 for (;; --i, --curr) {
649 if (c != *curr) {
650 return i;
651 } else if (i == 0) {
652 return npos;
653 }
654 }
655 }
656
operator <(const string & lhs,const string & rhs)657 bool operator<(const string& lhs, const string& rhs) {
658 return lhs.compare(rhs) < 0;
659 }
660
operator <=(const string & lhs,const string & rhs)661 bool operator<=(const string& lhs, const string& rhs) {
662 return lhs.compare(rhs) <= 0;
663 }
664
operator >(const string & lhs,const string & rhs)665 bool operator>(const string& lhs, const string& rhs) {
666 return lhs.compare(rhs) > 0;
667 }
668
operator >=(const string & lhs,const string & rhs)669 bool operator>=(const string& lhs, const string& rhs) {
670 return lhs.compare(rhs) >= 0;
671 }
672
swap(string & lhs,string & rhs)673 void swap(string& lhs, string& rhs) {
674 lhs.swap(rhs);
675 }
676
operator <<(ostream & os,const string & str)677 ostream& operator<<(ostream& os, const string& str) {
678 return os.write_formatted(str.data(), str.size());
679 }
680
681 } // namespace std
682