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