• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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