string.cpp revision cb8eb8e1390d1343563a55c117b5c39cfa87fe1d
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 41namespace { 42char kEmptyString[1] = { '\0' }; 43// Dummy char used in the 'at' accessor when the index is out of 44// range. 45char sDummy; 46} 47 48namespace 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. 70bool 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. 92void 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 120void 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. 130void string::ResetTo(value_type *str) 131{ 132 SafeFree(mData); 133 mData = str; 134} 135 136void string::ConstructEmptyString() 137{ 138 mData = kEmptyString; 139 mLength = 0; 140 mCapacity = 0; 141} 142 143void string::Constructor(const value_type *str, size_type n) 144{ 145 Constructor(str, 0, n); 146} 147 148 149void 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 162void 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 176string::string() 177{ 178 ConstructEmptyString(); 179} 180 181string::string(const string& str) 182{ 183 Constructor(str.mData, str.mLength); 184} 185 186string::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 201string::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 213string::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 225string::string(const value_type *str, size_type n) 226{ 227 Constructor(str, n); 228} 229 230// Char repeat constructor. 231string::string(size_type n, char c) 232{ 233 Constructor(n, c); 234} 235 236string::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 248string::~string() 249{ 250 clear(); // non virtual, ok to call. 251} 252 253void string::clear() 254{ 255 mCapacity = 0; 256 mLength = 0; 257 ResetTo(kEmptyString); 258} 259 260string& 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 286void 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 307string& 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 316string& 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 325string& 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 334string& string::append(const string& str) 335{ 336 Append(str.mData, str.mLength); 337 return *this; 338} 339 340void string::push_back(const char c) 341{ 342 // Check we don't overflow. 343 if (mLength + 2 > mLength) 344 { 345 const size_type total_len = mLength + 1; 346 347 if (total_len > mCapacity) 348 { 349 reserve(total_len); 350 if (total_len > mCapacity) 351 { // something went wrong in the reserve call. 352 return; 353 } 354 } 355 *(mData + mLength) = c; 356 ++mLength; 357 mData[mLength] = '\0'; 358 } 359} 360 361 362int string::compare(const string& other) const 363{ 364 if (this == &other) 365 { 366 return 0; 367 } 368 else if (mLength == other.mLength) 369 { 370 return memcmp(mData, other.mData, mLength); 371 } 372 else 373 { 374 return mLength < other.mLength ? -1 : 1; 375 } 376} 377 378int string::compare(const value_type *other) const 379{ 380 if (NULL == other) 381 { 382 return 1; 383 } 384 return strcmp(mData, other); 385} 386 387bool operator==(const string& left, const string& right) 388{ 389 if (&left == &right) { 390 return true; 391 } 392 return (left.size() == right.size() && 393 !char_traits<char>::compare(left.mData, right.mData, left.size())); 394} 395 396bool operator==(const string& left, const string::value_type *right) 397{ 398 if (NULL == right) { 399 return false; 400 } 401 // We can use strcmp here because even when the string is build from an 402 // array of char we insert the terminating '\0'. 403 return std::strcmp(left.mData, right) == 0; 404} 405 406void string::reserve(size_type size) 407{ 408 if (0 == size) 409 { 410 if (0 == mCapacity) 411 { 412 return; 413 } 414 else if (0 == mLength) 415 { // Shrink to fit an empty string. 416 mCapacity = 0; 417 ResetTo(kEmptyString); 418 } 419 else 420 { // Shrink to fit a non empty string 421 SafeRealloc(mLength); 422 } 423 } 424 else if (size > mLength) 425 { 426 SafeRealloc(size); 427 } 428} 429 430void string::swap(string& other) 431{ 432 if (this == &other) return; 433 value_type *const tmp_mData = mData; 434 const size_type tmp_mCapacity = mCapacity; 435 const size_type tmp_mLength = mLength; 436 437 mData = other.mData; 438 mCapacity = other.mCapacity; 439 mLength = other.mLength; 440 441 other.mData = tmp_mData; 442 other.mCapacity = tmp_mCapacity; 443 other.mLength = tmp_mLength; 444} 445 446const char& string::operator[](const size_type pos) const 447{ 448 return mData[pos]; 449} 450 451char& string::operator[](const size_type pos) 452{ 453 return mData[pos]; 454} 455 456const char& string::at(const size_type pos) const 457{ 458 if (pos < mLength) { 459 return mData[pos]; 460 } else { 461 sDummy = 'X'; 462 return sDummy; 463 } 464} 465 466char& string::at(const size_type pos) 467{ 468 if (pos < mLength) { 469 return mData[pos]; 470 } else { 471 sDummy = 'X'; 472 return sDummy; 473 } 474} 475 476string& string::assign(const string& str) 477{ 478 clear(); 479 Constructor(str.mData, str.mLength); 480 return *this; 481} 482 483string& string::assign(const string& str, size_type pos, size_type n) 484{ 485 if (pos >= str.mLength) 486 { // pos is out of bound 487 return *this; 488 } 489 if (n <= str.mLength - pos) 490 { 491 clear(); 492 Constructor(str.mData, pos, n); 493 } 494 return *this; 495} 496 497string& string::assign(const value_type *str) 498{ 499 if (NULL == str) 500 { 501 return *this; 502 } 503 clear(); 504 Constructor(str, traits_type::length(str)); 505 return *this; 506} 507 508string& string::assign(const value_type *array, size_type n) 509{ 510 if (NULL == array || 0 == n) 511 { 512 return *this; 513 } 514 clear(); 515 Constructor(array, n); 516 return *this; 517} 518 519string& string::operator=(char c) 520{ 521 clear(); 522 Constructor(1, c); 523 return *this; 524} 525 526string::size_type string::find(const value_type *str, size_type pos) const 527{ 528 529 if (NULL == str) 530 { 531 return string::npos; 532 } 533 534 // Empty string is found everywhere except beyond the end. It is 535 // possible to find the empty string right after the last char, 536 // hence we used mLength and not mLength - 1 in the comparison. 537 if (*str == '\0') 538 { 539 return pos > mLength ? string::npos : pos; 540 } 541 542 if (mLength == 0 || pos > mLength - 1) 543 { 544 return string::npos; 545 } 546 547 value_type *idx = std::strstr(mData + pos, str); 548 549 if (NULL == idx) 550 { 551 return string::npos; 552 } 553 554 const std::ptrdiff_t delta = idx - mData; 555 556 return static_cast<size_type>(delta); 557} 558 559string string::substr(size_type pos, size_type n) const { 560 return string(*this, pos, n); 561} 562 563string::size_type string::find_first_of(value_type c, size_type pos) const { 564 if (pos >= mLength) { 565 return npos; 566 } 567 const char *res; 568 // The last parameter represents a number of chars, not a index. 569 res = static_cast<const char *>(std::memchr(mData + pos, c, mLength - pos)); 570 return res != NULL ? res - mData : npos; 571} 572 573string::size_type string::find_last_of(value_type c, size_type pos) const { 574 if (mLength == 0) { 575 return npos; 576 } else if (pos >= mLength) { 577 pos = mLength - 1; // >= 0 578 } 579 580 const char *res; 581 // Note:memrchr is not in the std namepace. 582 // The last parameter represents a number of chars, not a index. 583 res = static_cast<const char *>(memrchr(mData, c, pos + 1)); 584 return res != NULL ? res - mData : npos; 585} 586 587string::size_type string::find_first_not_of(value_type c, size_type pos) const { 588 char *curr = mData + pos; 589 for (size_type i = pos; i < mLength; ++i, ++curr) { 590 if (c != *curr) { 591 return i; 592 } 593 } 594 return npos; 595} 596 597string::size_type string::find_last_not_of(value_type c, size_type pos) const { 598 if (mLength == 0) { 599 return npos; 600 } else if (pos >= mLength) { 601 pos = mLength - 1; // >= 0 602 } 603 604 char *curr = mData + pos; 605 size_type i = pos; 606 607 for (;; --i, --curr) { 608 if (c != *curr) { 609 return i; 610 } else if (i == 0) { 611 return npos; 612 } 613 } 614} 615 616ostream& operator<<(ostream& os, const string& str) { 617 return os.write_formatted(str.data(), str.size()); 618} 619 620} // namespace std 621