string.cpp revision d881e3f36a074eb9fd8e353fb5e5e3e539f2d460
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 36#ifndef MAX_SIZE_T 37#define MAX_SIZE_T (~(size_t)0) 38#endif 39 40namespace { 41char kEmptyString[1] = { '\0' }; 42} 43 44namespace std { 45// Implementation of the std::string class. 46// 47// mData points either to a heap allocated array of bytes or the constant 48// kEmptyString when empty and reserve has not been called. 49// 50// The size of the buffer pointed by mData is mCapacity + 1. 51// The extra byte is need to store the '\0'. 52// 53// mCapacity is either mLength or the number of bytes reserved using 54// reserve(int)). 55// 56// mLength is the number of char in the string, excluding the terminating '\0'. 57// 58// TODO: replace the overflow checks with some better named macros. 59// 60// Allocate n + 1 number of bytes for the string. Update mCapacity. 61// Ensure that mCapacity + 1 and mLength + 1 is accessible. 62// In case of error the original state of the string is restored. 63// @param n Number of bytes requested. String allocate n + 1 to hold 64// the terminating '\0'. 65// @return true if the buffer could be allocated, false otherwise. 66bool string::SafeMalloc(size_type n) 67{ 68 // Not empty and no overflow 69 if (n > 0 && n + 1 > n) 70 { 71 value_type *oldData = mData; 72 73 mData = static_cast<value_type *>(::malloc(n + 1)); 74 if (NULL != mData) 75 { 76 mCapacity = n; 77 return true; 78 } 79 mData = oldData; // roll back 80 } 81 return false; 82} 83 84// Resize the buffer pointed by mData if n >= mLength. 85// mData points to an allocated buffer or the empty string. 86// @param n The number of bytes for the internal buffer. 87// Must be > mLength and > 0. 88void string::SafeRealloc(size_type n) 89{ 90 // truncation or nothing to do or n too big (overflow) 91 if (n < mLength || n == mCapacity || n + 1 < n) { 92 return; 93 } 94 95 if (kEmptyString == mData) 96 { 97 if (SafeMalloc(n)) { 98 *mData = '\0'; 99 } 100 return; 101 } 102 103 value_type *oldData = mData; 104 105 mData = static_cast<char*>(::realloc(mData, n + 1)); 106 if (NULL == mData) // reallocate failed. 107 { 108 mData = oldData; 109 } 110 else 111 { 112 mCapacity = n; 113 } 114} 115 116void string::SafeFree(value_type *buffer) 117{ 118 if (buffer != kEmptyString) 119 { 120 ::free(buffer); 121 } 122} 123 124// If the memory is on the heap, release it. Do nothing we we point at the empty 125// string. On return mData points to str. 126void string::ResetTo(value_type *str) 127{ 128 SafeFree(mData); 129 mData = str; 130} 131 132void string::ConstructEmptyString() 133{ 134 mData = kEmptyString; 135 mLength = 0; 136 mCapacity = 0; 137} 138 139void string::Constructor(const value_type *str, size_type n) 140{ 141 Constructor(str, 0, n); 142} 143 144 145void string::Constructor(const value_type *str, size_type pos, size_type n) 146{ 147 // Enough data and no overflow 148 if (SafeMalloc(n)) 149 { 150 memcpy(mData, str + pos, n); 151 mLength = n; 152 mData[mLength] = '\0'; 153 return; // Success 154 } 155 ConstructEmptyString(); 156} 157 158void string::Constructor(size_type n, char c) 159{ 160 // Enough data and no overflow 161 162 if (SafeMalloc(n)) 163 { 164 memset(mData, c, n); 165 mLength = n; 166 mData[mLength] = '\0'; 167 return; // Success 168 } 169 ConstructEmptyString(); 170} 171 172string::string() 173{ 174 ConstructEmptyString(); 175} 176 177string::string(const string& str) 178{ 179 Constructor(str.mData, str.mLength); 180} 181 182string::string(const string& str, size_type pos, size_type n) 183{ 184 if (pos < str.mLength && n <= (str.mLength - pos)) 185 { 186 Constructor(str.mData + pos , n); 187 } 188 else 189 { 190 ConstructEmptyString(); 191 } 192} 193 194string::string(const string& str, size_type pos) 195{ 196 if (pos < str.mLength) 197 { 198 Constructor(str.mData, pos, str.mLength - pos); 199 } 200 else 201 { 202 ConstructEmptyString(); 203 } 204} 205 206string::string(const value_type *str) 207{ 208 if (NULL != str) 209 { 210 Constructor(str, strlen(str)); 211 } 212 else 213 { 214 ConstructEmptyString(); 215 } 216} 217 218string::string(const value_type *str, size_type n) 219{ 220 Constructor(str, n); 221} 222 223// Char repeat constructor. 224string::string(size_type n, char c) 225{ 226 Constructor(n, c); 227} 228 229string::string(const value_type *begin, const value_type *end) 230{ 231 if (begin < end) 232 { 233 Constructor(begin, end - begin); 234 } 235 else 236 { 237 ConstructEmptyString(); 238 } 239} 240 241string::~string() 242{ 243 clear(); // non virtual, ok to call. 244} 245 246void string::clear() 247{ 248 mCapacity = 0; 249 mLength = 0; 250 ResetTo(kEmptyString); 251} 252 253string& string::erase(size_type pos, size_type n) 254{ 255 if (pos >= mLength || 0 == n) 256 { 257 return *this; 258 } 259 // start of the characters left which need to be moved down. 260 const size_t remainder = pos + n; 261 262 // Truncate, even if there is an overflow. 263 if (remainder >= mLength || remainder < pos) 264 { 265 *(mData + pos) = '\0'; 266 mLength = pos; 267 return *this; 268 } 269 // remainder < mLength and allocation guarantees to be at least 270 // mLength + 1 271 size_t left = mLength - remainder + 1; 272 value_type *d = mData + pos; 273 value_type *s = mData + remainder; 274 memmove(d, s, left); 275 mLength -= n; 276 return *this; 277} 278 279void string::Append(const value_type *str, size_type n) 280{ 281 const size_type total_len = mLength + n; 282 283 // n > 0 and no overflow for the string length + terminating null. 284 if (n > 0 && (total_len + 1) > mLength) 285 { 286 if (total_len > mCapacity) 287 { 288 reserve(total_len); 289 if (total_len > mCapacity) 290 { // something went wrong in the reserve call. 291 return; 292 } 293 } 294 memcpy(mData + mLength, str, n); 295 mLength = total_len; 296 mData[mLength] = '\0'; 297 } 298} 299 300string& string::append(const value_type *str) 301{ 302 if (NULL != str) 303 { 304 Append(str, strlen(str)); 305 } 306 return *this; 307} 308 309string& string::append(const value_type *str, size_type n) 310{ 311 if (NULL != str) 312 { 313 Append(str, n); 314 } 315 return *this; 316} 317 318string& string::append(const value_type *str, size_type pos, size_type n) 319{ 320 if (NULL != str) 321 { 322 Append(str + pos, n); 323 } 324 return *this; 325} 326 327string& string::append(const string& str) 328{ 329 Append(str.mData, str.mLength); 330 return *this; 331} 332 333void string::push_back(const char c) 334{ 335 // Check we don't overflow. 336 if (mLength + 2 > mLength) 337 { 338 const size_type total_len = mLength + 1; 339 340 if (total_len > mCapacity) 341 { 342 reserve(total_len); 343 if (total_len > mCapacity) 344 { // something went wrong in the reserve call. 345 return; 346 } 347 } 348 *(mData + mLength) = c; 349 ++mLength; 350 mData[mLength] = '\0'; 351 } 352} 353 354 355int string::compare(const string& other) const 356{ 357 if (this == &other) 358 { 359 return 0; 360 } 361 else if (mLength == other.mLength) 362 { 363 return memcmp(mData, other.mData, mLength); 364 } 365 else 366 { 367 return mLength < other.mLength ? -1 : 1; 368 } 369} 370 371int string::compare(const value_type *other) const 372{ 373 if (NULL == other) 374 { 375 return 1; 376 } 377 return strcmp(mData, other); 378} 379 380bool operator==(const string& left, const string& right) 381{ 382 if (&left == &right) 383 { 384 return true; 385 } 386 else 387 { 388 // We can use strcmp here because even when the string is build from an 389 // array of char we insert the terminating '\0'. 390 return strcmp(left.mData, right.mData) == 0; 391 } 392} 393 394bool operator==(const string& left, const string::value_type *right) 395{ 396 if (NULL == right) 397 { 398 return false; 399 } 400 // We can use strcmp here because even when the string is build from an 401 // array of char we insert the terminating '\0'. 402 return std::strcmp(left.mData, right) == 0; 403} 404 405void string::reserve(size_type size) 406{ 407 if (0 == size) 408 { 409 if (0 == mCapacity) 410 { 411 return; 412 } 413 else if (0 == mLength) 414 { // Shrink to fit an empty string. 415 mCapacity = 0; 416 ResetTo(kEmptyString); 417 } 418 else 419 { // Shrink to fit a non empty string 420 SafeRealloc(mLength); 421 } 422 } 423 else if (size > mLength) 424 { 425 SafeRealloc(size); 426 } 427} 428 429void string::swap(string& other) 430{ 431 if (this == &other) return; 432 value_type *const tmp_mData = mData; 433 const size_type tmp_mCapacity = mCapacity; 434 const size_type tmp_mLength = mLength; 435 436 mData = other.mData; 437 mCapacity = other.mCapacity; 438 mLength = other.mLength; 439 440 other.mData = tmp_mData; 441 other.mCapacity = tmp_mCapacity; 442 other.mLength = tmp_mLength; 443} 444 445const char& string::operator[](const size_type pos) const 446{ 447 return mData[pos]; 448} 449 450char& string::operator[](const size_type pos) 451{ 452 return mData[pos]; 453} 454 455string& string::assign(const string& str) 456{ 457 clear(); 458 Constructor(str.mData, str.mLength); 459 return *this; 460} 461 462string& string::assign(const string& str, size_type pos, size_type n) 463{ 464 if (pos >= str.mLength) 465 { // pos is out of bound 466 return *this; 467 } 468 if (n <= str.mLength - pos) 469 { 470 clear(); 471 Constructor(str.mData, pos, n); 472 } 473 return *this; 474} 475 476string& string::assign(const value_type *str) 477{ 478 if (NULL == str) 479 { 480 return *this; 481 } 482 clear(); 483 Constructor(str, strlen(str)); 484 return *this; 485} 486 487string& string::assign(const value_type *array, size_type n) 488{ 489 if (NULL == array || 0 == n) 490 { 491 return *this; 492 } 493 clear(); 494 Constructor(array, n); 495 return *this; 496} 497 498string& string::operator=(char c) 499{ 500 clear(); 501 Constructor(1, c); 502 return *this; 503} 504 505string::size_type string::find(const value_type *str, size_type pos) const 506{ 507 508 if (NULL == str) 509 { 510 return string::npos; 511 } 512 513 // Empty string is found everywhere except beyond the end. It is 514 // possible to find the empty string right after the last char, 515 // hence we used mLength and not mLength - 1 in the comparison. 516 if (*str == '\0') 517 { 518 return pos > mLength ? string::npos : pos; 519 } 520 521 if (mLength == 0 || pos > mLength - 1) 522 { 523 return string::npos; 524 } 525 526 value_type *idx = std::strstr(mData + pos, str); 527 528 if (NULL == idx) 529 { 530 return string::npos; 531 } 532 533 const std::ptrdiff_t delta = idx - mData; 534 535 return static_cast<size_type>(delta); 536} 537 538} // namespace std 539