/*
 * Copyright 2001-2021 Haiku, Inc. All rights reserved.
 * Distributed under the terms of the MIT License.
 *
 * Authors:
 *              Stefano Ceccherini, burton666@libero.it
 *              Axel Dörfler, axeld@pinc-software.de
 *              Marc Flerackers, mflerackers@androme.be
 *              Julun, host.haiku@gmx.de
 *              Michael Lotz, mmlr@mlotz.ch
 *              Oliver Tappe, openbeos@hirschkaefer.de
 */


/*! String class supporting common string operations. */

#ifndef _DEFAULT_SOURCE
#define _DEFAULT_SOURCE
#endif

#include <String.h>

#include <ctype.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

#include <Debug.h>
#include <StringList.h>

#include <StringPrivate.h>
#include <utf8_functions.h>


// define proper names for case-option of _DoReplace()
#define KEEP_CASE false
#define IGNORE_CASE true

// define proper names for count-option of _DoReplace()
#define REPLACE_ALL 0x7FFFFFFF


static const uint32 kPrivateDataOffset = BString::Private::kPrivateDataOffset;

const char* B_EMPTY_STRING = "";


// helper function, returns minimum of two given values (but clamps to 0):
static inline int32
min_clamp0(int32 num1, int32 num2)
{
        if (num1 < num2)
                return num1 > 0 ? num1 : 0;

        return num2 > 0 ? num2 : 0;
}


//! Returns length of given string (but clamps to given maximum).
static inline int32
strlen_clamp(const char* string, int32 max)
{
        // this should yield 0 for max<0:
        return max <= 0 ? 0 : strnlen(string, max);
}


//! Helper function for strlen() that can handle NULL strings.
static inline size_t
string_length(const char* string)
{
        return string != NULL ? strlen(string) : 0;
}


//! helper function, massages given pointer into a legal c-string:
static inline const char*
safestr(const char* string)
{
        return string != NULL ? string : "";
}


//      #pragma mark - PosVect


class BString::PosVect {
public:
        PosVect()
                :
                fSize(0),
                fBufferSize(20),
                fBuffer(NULL)
        {
        }

        ~PosVect()
        {
                free(fBuffer);
        }

        bool Add(int32 pos)
        {
                if (fBuffer == NULL || fSize == fBufferSize) {
                        if (fBuffer != NULL)
                                fBufferSize *= 2;

                        int32* newBuffer =
                                (int32*)realloc(fBuffer, fBufferSize * sizeof(int32));
                        if (newBuffer == NULL)
                                return false;

                        fBuffer = newBuffer;
                }

                fBuffer[fSize++] = pos;

                return true;
        }

        inline int32 ItemAt(int32 index) const
        {
                return fBuffer[index];
        }

        inline int32 CountItems() const
        {
                return fSize;
        }

private:
        int32   fSize;
        int32   fBufferSize;
        int32*  fBuffer;
};


//      #pragma mark - BString


inline int32&
BString::_ReferenceCount()
{
        return Private::DataRefCount(fPrivateData);
}


inline const int32&
BString::_ReferenceCount() const
{
        return Private::DataRefCount(fPrivateData);
}


inline bool
BString::_IsShareable() const
{
        return fPrivateData != NULL && _ReferenceCount() >= 0;
}


BString::BString()
        :
        fPrivateData(NULL)
{
        _Init("", 0);
}


BString::BString(const char* string)
        :
        fPrivateData(NULL)
{
        _Init(string, strlen(safestr(string)));
}


BString::BString(const BString& string)
        :
        fPrivateData(NULL)
{
        // check if source is sharable - if so, share else clone
        if (string._IsShareable()) {
                fPrivateData = string.fPrivateData;
                atomic_add(&_ReferenceCount(), 1);
                        // string cannot go away right now
        } else
                _Init(string.String(), string.Length());
}


BString::BString(const char* string, int32 maxLength)
        : fPrivateData(NULL)
{
        _Init(string, strlen_clamp(safestr(string), maxLength));
}


#if __cplusplus >= 201103L
BString::BString(BString&& string) noexcept
{
        fPrivateData = string.fPrivateData;
        string.fPrivateData = NULL;
}
#endif


BString::~BString()
{
        _ReleasePrivateData();
}


//      #pragma mark - Access


int32
BString::CountChars() const
{
        return UTF8CountChars(fPrivateData, Length());
}


int32
BString::CountBytes(int32 fromCharOffset, int32 charCount) const
{
        return UTF8CountBytes(
                fPrivateData + UTF8CountBytes(fPrivateData, fromCharOffset), charCount);
}


/*static*/ uint32
BString::HashValue(const char* _string)
{
        const uint8* string = (const uint8*)_string;
        if (string == NULL)
                return 0;

        uint32 h = 5381;
        char c;
        while ((c = *string++) != 0)
                h = (h * 33) + c;
        return h;
}


//      #pragma mark - Assignment


BString&
BString::operator=(const BString& string)
{
        return SetTo(string);
}


BString&
BString::operator=(const char* string)
{
        if (!string)
                string = "";
        if (string != String())
                SetTo(string, strlen(string));
        return *this;
}


BString&
BString::operator=(char c)
{
        return SetTo(c, 1);
}


#if __cplusplus >= 201103L
BString&
BString::operator=(BString&& string) noexcept
{
        if (this != &string) {
                _ReleasePrivateData();
                fPrivateData = string.fPrivateData;
                string.fPrivateData = NULL;
        }
        return *this;
}
#endif


BString&
BString::SetTo(const char* string, int32 maxLength)
{
        if (maxLength < 0)
                maxLength = INT32_MAX;

        maxLength = strlen_clamp(safestr(string), maxLength);

        if (_MakeWritable(maxLength, false) == B_OK)
                memcpy(fPrivateData, string, maxLength);

        return *this;
}


BString&
BString::SetTo(const BString& string)
{
        // we share the information already
        if (fPrivateData == string.fPrivateData)
                return *this;

        _ReleasePrivateData();

        // if source is sharable share, otherwise clone
        if (string._IsShareable()) {
                fPrivateData = string.fPrivateData;
                atomic_add(&_ReferenceCount(), 1);
                        // the string cannot go away right now
        } else
                _Init(string.String(), string.Length());

        return *this;
}


BString&
BString::Adopt(BString& from)
{
        SetTo(from);
        from.SetTo("");

        return *this;
}


BString&
BString::SetTo(const BString& string, int32 maxLength)
{
        if (maxLength < 0)
                maxLength = INT32_MAX;
        if (fPrivateData != string.fPrivateData
                // make sure we reassing in case length is different
                || (fPrivateData == string.fPrivateData && Length() > maxLength)) {
                maxLength = min_clamp0(maxLength, string.Length());
                if (_MakeWritable(maxLength, false) == B_OK)
                        memcpy(fPrivateData, string.String(), maxLength);
        }
        return *this;
}


BString&
BString::Adopt(BString& from, int32 maxLength)
{
        SetTo(from, maxLength);
        from.SetTo("");

        return *this;
}


BString&
BString::SetTo(char c, int32 count)
{
        if (count < 0)
                count = 0;

        if (_MakeWritable(count, false) == B_OK)
                memset(fPrivateData, c, count);

        return *this;
}


BString&
BString::SetToChars(const char* string, int32 charCount)
{
        return SetTo(string, UTF8CountBytes(string, charCount));
}


BString&
BString::SetToChars(const BString& string, int32 charCount)
{
        return SetTo(string, UTF8CountBytes(string.String(), charCount));
}


BString&
BString::AdoptChars(BString& string, int32 charCount)
{
        return Adopt(string, UTF8CountBytes(string.String(), charCount));
}


BString&
BString::SetToFormat(const char* format, ...)
{
        va_list args;
        va_start(args, format);
        SetToFormatVarArgs(format, args);
        va_end(args);

        return *this;
}


BString&
BString::SetToFormatVarArgs(const char* format, va_list args)
{
        // Use a small on-stack buffer to save a second vsnprintf() call for most
        // use cases.
        int32 bufferSize = 1024;
        char buffer[bufferSize];

        va_list clonedArgs;
#if __GNUC__ == 2
        __va_copy(clonedArgs, args);
#else
        va_copy(clonedArgs, args);
#endif
        int32 bytes = vsnprintf(buffer, bufferSize, format, clonedArgs);
        va_end(clonedArgs);

        if (bytes < 0)
                return Truncate(0);

        if (bytes < bufferSize) {
                SetTo(buffer);
                return *this;
        }

        bytes = vsnprintf(LockBuffer(bytes), bytes + 1, format, args);
        if (bytes < 0)
                bytes = 0;

        UnlockBuffer(bytes);
        return *this;
}


int
BString::ScanWithFormat(const char* format, ...)
{
        va_list args;
        va_start(args, format);
        int result = ScanWithFormatVarArgs(format, args);
        va_end(args);

        return result;
}


int
BString::ScanWithFormatVarArgs(const char* format, va_list args)
{
        return vsscanf(fPrivateData, format, args);
}


//      #pragma mark - Substring copying


BString&
BString::CopyInto(BString& into, int32 fromOffset, int32 length) const
{
        if (this != &into)
                into.SetTo(fPrivateData + fromOffset, length);
        return into;
}


void
BString::CopyInto(char* into, int32 fromOffset, int32 length) const
{
        if (into) {
                length = min_clamp0(length, Length() - fromOffset);
                memcpy(into, fPrivateData + fromOffset, length);
        }
}


BString&
BString::CopyCharsInto(BString& into, int32 fromCharOffset,
        int32 charCount) const
{
        int32 fromOffset = UTF8CountBytes(fPrivateData, fromCharOffset);
        int32 length = UTF8CountBytes(fPrivateData + fromOffset, charCount);
        return CopyInto(into, fromOffset, length);
}


bool
BString::CopyCharsInto(char* into, int32* intoLength, int32 fromCharOffset,
        int32 charCount) const
{
        if (into == NULL)
                return false;

        int32 fromOffset = UTF8CountBytes(fPrivateData, fromCharOffset);
        int32 length = UTF8CountBytes(fPrivateData + fromOffset, charCount);
        length = min_clamp0(length, Length() - fromOffset);

        if (intoLength != NULL) {
                if (*intoLength < length)
                        return false;
                *intoLength = length;
        }

        memcpy(into, fPrivateData + fromOffset, length);
        return true;
}


bool
BString::Split(const char* separator, bool noEmptyStrings,
        BStringList& _list) const
{
        int32 separatorLength = strlen(separator);
        int32 length = Length();
        if (separatorLength == 0 || length == 0 || separatorLength > length) {
                if (length == 0 && noEmptyStrings)
                        return true;
                return _list.Add(*this);
        }

        int32 index = 0;
        for (;;) {
                int32 endIndex = index < length ? FindFirst(separator, index) : length;
                if (endIndex < 0)
                        endIndex = length;

                if (endIndex > index || !noEmptyStrings) {
                        BString toAppend(String() + index, endIndex - index);
                        if (toAppend.Length() != endIndex - index
                                || !_list.Add(toAppend)) {
                                return false;
                        }
                }

                if (endIndex == length)
                        break;

                index = endIndex + separatorLength;
        }

        return true;
}


//      #pragma mark - Appending


BString&
BString::operator+=(const char* string)
{
        if (string) {
                int32 length = strlen(string);
                if (length > 0)
                        _DoAppend(string, length);
        }
        return *this;
}


BString&
BString::operator+=(char c)
{
        _DoAppend(&c, 1);
        return *this;
}


BString&
BString::Append(const BString& string, int32 length)
{
        if (&string != this) {
                length = min_clamp0(length, string.Length());
                if (length > 0)
                        _DoAppend(string.fPrivateData, length);
        }
        return *this;
}


BString&
BString::Append(const char* string, int32 length)
{
        if (string) {
                length = strlen_clamp(string, length);
                if (length > 0)
                        _DoAppend(string, length);
        }
        return *this;
}


BString&
BString::Append(char c, int32 count)
{
        int32 oldLength = Length();
        if (count > 0 && _DoAppend("", count))
                memset(fPrivateData + oldLength, c, count);
        return *this;
}


BString&
BString::AppendChars(const BString& string, int32 charCount)
{
        return Append(string, UTF8CountBytes(string.String(), charCount));
}


BString&
BString::AppendChars(const char* string, int32 charCount)
{
        return Append(string, UTF8CountBytes(string, charCount));
}


//      #pragma mark - Prepending


BString&
BString::Prepend(const char* string)
{
        if (string)
                _DoPrepend(string, strlen(string));
        return *this;
}


BString&
BString::Prepend(const BString& string)
{
        if (&string != this)
                _DoPrepend(string.String(), string.Length());
        return *this;
}


BString&
BString::Prepend(const char* string, int32 length)
{
        if (string)
                _DoPrepend(string, strlen_clamp(string, length));
        return *this;
}


BString&
BString::Prepend(const BString& string, int32 length)
{
        if (&string != this)
                _DoPrepend(string.fPrivateData, min_clamp0(length, string.Length()));
        return *this;
}


BString&
BString::Prepend(char c, int32 count)
{
        if (count > 0 && _DoPrepend("", count))
                memset(fPrivateData, c, count);
        return *this;
}


BString&
BString::PrependChars(const char* string, int32 charCount)
{
        return Prepend(string, UTF8CountBytes(string, charCount));
}


BString&
BString::PrependChars(const BString& string, int32 charCount)
{
        return Prepend(string, UTF8CountBytes(string.String(), charCount));
}


//      #pragma mark - Inserting


BString&
BString::Insert(const char* string, int32 position)
{
        if (string != NULL && position <= Length()) {
                int32 len = int32(strlen(string));
                if (position < 0) {
                        int32 skipLen = min_clamp0(-1 * position, len);
                        string += skipLen;
                        len -= skipLen;
                        position = 0;
                } else {
                        position = min_clamp0(position, Length());
                }
                _DoInsert(string, position, len);
        }
        return *this;
}


BString&
BString::Insert(const char* string, int32 length, int32 position)
{
        if (string != NULL && position <= Length()) {
                int32 len = strlen_clamp(string, length);
                if (position < 0) {
                        int32 skipLen = min_clamp0(-1 * position, len);
                        string += skipLen;
                        len -= skipLen;
                        position = 0;
                } else {
                        position = min_clamp0(position, Length());
                }
                _DoInsert(string, position, len);
        }
        return *this;
}


BString&
BString::Insert(const char* string, int32 fromOffset, int32 length,
        int32 position)
{
        if (string)
                Insert(string + fromOffset, length, position);
        return *this;
}


BString&
BString::Insert(const BString& string, int32 position)
{
        if (&string != this && string.Length() > 0)
                Insert(string.fPrivateData, position);
        return *this;
}


BString&
BString::Insert(const BString& string, int32 length, int32 position)
{
        if (&string != this && string.Length() > 0)
                Insert(string.String(), length, position);
        return *this;
}


BString&
BString::Insert(const BString& string, int32 fromOffset, int32 length,
        int32 position)
{
        if (&string != this && string.Length() > 0)
                Insert(string.String() + fromOffset, length, position);
        return *this;
}


BString&
BString::Insert(char c, int32 count, int32 position)
{
        if (position < 0) {
                count = MAX(count + position, 0);
                position = 0;
        } else
                position = min_clamp0(position, Length());

        if (count > 0 && _DoInsert("", position, count))
                memset(fPrivateData + position, c, count);

        return *this;
}


BString&
BString::InsertChars(const char* string, int32 charPosition)
{
        return Insert(string, UTF8CountBytes(fPrivateData, charPosition));
}


BString&
BString::InsertChars(const char* string, int32 charCount, int32 charPosition)
{
        return Insert(string, UTF8CountBytes(string, charCount),
                UTF8CountBytes(fPrivateData, charPosition));
}


BString&
BString::InsertChars(const char* string, int32 fromCharOffset,
        int32 charCount, int32 charPosition)
{
        int32 fromOffset = UTF8CountBytes(string, fromCharOffset);
        return Insert(string, fromOffset,
                UTF8CountBytes(string + fromOffset, charCount),
                UTF8CountBytes(fPrivateData, charPosition));
}


BString&
BString::InsertChars(const BString& string, int32 charPosition)
{
        return Insert(string, UTF8CountBytes(fPrivateData, charPosition));
}


BString&
BString::InsertChars(const BString& string, int32 charCount, int32 charPosition)
{
        return Insert(string, UTF8CountBytes(string.String(), charCount),
                UTF8CountBytes(fPrivateData, charPosition));
}


BString&
BString::InsertChars(const BString& string, int32 fromCharOffset,
        int32 charCount, int32 charPosition)
{
        int32 fromOffset = UTF8CountBytes(string.String(), fromCharOffset);
        return Insert(string, fromOffset,
                UTF8CountBytes(string.String() + fromOffset, charCount),
                UTF8CountBytes(fPrivateData, charPosition));
}


//      #pragma mark - Removing


BString&
BString::Truncate(int32 newLength, bool lazy)
{
        if (newLength < 0)
                newLength = 0;

        if (newLength < Length()) {
                // ignore lazy, since we might detach
                _MakeWritable(newLength, true);
        }

        return *this;
}


BString&
BString::TruncateChars(int32 newCharCount, bool lazy)
{
        return Truncate(UTF8CountBytes(fPrivateData, newCharCount));
}


BString&
BString::Remove(int32 from, int32 length)
{
        if (length > 0 && from < Length())
                _ShrinkAtBy(from, min_clamp0(length, (Length() - from)));
        return *this;
}


BString&
BString::RemoveChars(int32 fromCharOffset, int32 charCount)
{
        int32 fromOffset = UTF8CountBytes(fPrivateData, fromCharOffset);
        return Remove(fromOffset,
                UTF8CountBytes(fPrivateData + fromOffset, charCount));
}


BString&
BString::RemoveFirst(const BString& string)
{
        if (string.Length() > 0) {
                int32 pos = _ShortFindAfter(string.String(), string.Length());
                if (pos >= 0)
                        _ShrinkAtBy(pos, string.Length());
        }
        return *this;
}


BString&
BString::RemoveLast(const BString& string)
{
        int32 pos = _FindBefore(string.String(), Length(), string.Length());
        if (pos >= 0)
                _ShrinkAtBy(pos, string.Length());

        return *this;
}


BString&
BString::RemoveAll(const BString& string)
{
        if (string.Length() == 0 || Length() == 0 || FindFirst(string) < 0)
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;

        return _DoReplace(string.String(), "", REPLACE_ALL, 0, KEEP_CASE);
}


BString&
BString::RemoveFirst(const char* string)
{
        int32 length = string ? strlen(string) : 0;
        if (length > 0) {
                int32 pos = _ShortFindAfter(string, length);
                if (pos >= 0)
                        _ShrinkAtBy(pos, length);
        }
        return *this;
}


BString&
BString::RemoveLast(const char* string)
{
        int32 length = string ? strlen(string) : 0;
        if (length > 0) {
                int32 pos = _FindBefore(string, Length(), length);
                if (pos >= 0)
                        _ShrinkAtBy(pos, length);
        }
        return *this;
}


BString&
BString::RemoveAll(const char* string)
{
        if (!string || Length() == 0 || FindFirst(string) < 0)
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;

        return _DoReplace(string, "", REPLACE_ALL, 0, KEEP_CASE);
}


BString&
BString::RemoveSet(const char* setOfBytesToRemove)
{
        return ReplaceSet(setOfBytesToRemove, "");
}


BString&
BString::RemoveCharsSet(const char* setOfCharsToRemove)
{
        return ReplaceCharsSet(setOfCharsToRemove, "");
}


BString&
BString::MoveInto(BString& into, int32 from, int32 length)
{
        if (length) {
                CopyInto(into, from, length);
                Remove(from, length);
        }
        return into;
}


void
BString::MoveInto(char* into, int32 from, int32 length)
{
        if (into) {
                CopyInto(into, from, length);
                Remove(from, length);
        }
}


BString&
BString::MoveCharsInto(BString& into, int32 fromCharOffset, int32 charCount)
{
        if (charCount > 0) {
                CopyCharsInto(into, fromCharOffset, charCount);
                RemoveChars(fromCharOffset, charCount);
        }

        return into;
}


bool
BString::MoveCharsInto(char* into, int32* intoLength, int32 fromCharOffset,
        int32 charCount)
{
        if (!CopyCharsInto(into, intoLength, fromCharOffset, charCount))
                return false;

        RemoveChars(fromCharOffset, charCount);
        return true;
}


//      #pragma mark - Compare functions


bool
BString::operator<(const char* string) const
{
        return strcmp(String(), safestr(string)) < 0;
}


bool
BString::operator<=(const char* string) const
{
        return strcmp(String(), safestr(string)) <= 0;
}


bool
BString::operator==(const char* string) const
{
        return strcmp(String(), safestr(string)) == 0;
}


bool
BString::operator>=(const char* string) const
{
        return strcmp(String(), safestr(string)) >= 0;
}


bool
BString::operator>(const char* string) const
{
        return strcmp(String(), safestr(string)) > 0;
}


//      #pragma mark - strcmp()-style compare functions


int
BString::Compare(const BString& string) const
{
        return strcmp(String(), string.String());
}


int
BString::Compare(const char* string) const
{
        return strcmp(String(), safestr(string));
}


int
BString::Compare(const BString& string, int32 length) const
{
        return strncmp(String(), string.String(), length);
}


int
BString::Compare(const char* string, int32 length) const
{
        return strncmp(String(), safestr(string), length);
}


int
BString::CompareAt(size_t offset, const BString& string, int32 length) const
{
        return strncmp(String() + offset, string.String(), length);
}


int
BString::CompareChars(const BString& string, int32 charCount) const
{
        return Compare(string, UTF8CountBytes(fPrivateData, charCount));
}


int
BString::CompareChars(const char* string, int32 charCount) const
{
        return Compare(string, UTF8CountBytes(fPrivateData, charCount));
}


int
BString::ICompare(const BString& string) const
{
        return strcasecmp(String(), string.String());
}


int
BString::ICompare(const char* string) const
{
        return strcasecmp(String(), safestr(string));
}


int
BString::ICompare(const BString& string, int32 length) const
{
        return strncasecmp(String(), string.String(), length);
}


int
BString::ICompare(const char* string, int32 length) const
{
        return strncasecmp(String(), safestr(string), length);
}


//      #pragma mark - Searching


int32
BString::FindFirst(const BString& string) const
{
        return _ShortFindAfter(string.String(), string.Length());
}


int32
BString::FindFirst(const char* string) const
{
        if (string == NULL)
                return B_BAD_VALUE;

        return _ShortFindAfter(string, strlen(string));
}


int32
BString::FindFirst(const BString& string, int32 fromOffset) const
{
        if (fromOffset < 0)
                return B_ERROR;

        return _FindAfter(string.String(), min_clamp0(fromOffset, Length()),
                string.Length());
}


int32
BString::FindFirst(const char* string, int32 fromOffset) const
{
        if (string == NULL)
                return B_BAD_VALUE;

        if (fromOffset < 0)
                return B_ERROR;

        return _FindAfter(string, min_clamp0(fromOffset, Length()),
                strlen(safestr(string)));
}


int32
BString::FindFirst(char c) const
{
        return FindFirst(c, 0);
}


int32
BString::FindFirst(char c, int32 fromOffset) const
{
        if (fromOffset < 0 || fromOffset >= Length())
                return B_ERROR;

        const void* start = memchr(String() + fromOffset, c, Length() - fromOffset);
        if (start == NULL)
                return B_ERROR;

        return (const char*)start - String();
}


int32
BString::FindFirstChars(const BString& string, int32 fromCharOffset) const
{
        return FindFirst(string, UTF8CountBytes(fPrivateData, fromCharOffset));
}


int32
BString::FindFirstChars(const char* string, int32 fromCharOffset) const
{
        return FindFirst(string, UTF8CountBytes(fPrivateData, fromCharOffset));
}


int32
BString::FindLast(const BString& string) const
{
        return _FindBefore(string.String(), Length(), string.Length());
}


int32
BString::FindLast(const char* string) const
{
        if (string == NULL)
                return B_BAD_VALUE;

        return _FindBefore(string, Length(), strlen(safestr(string)));
}


int32
BString::FindLast(const BString& string, int32 beforeOffset) const
{
        if (beforeOffset < 0)
                return B_ERROR;

        return _FindBefore(string.String(), min_clamp0(beforeOffset, Length()),
                string.Length());
}


int32
BString::FindLast(const char* string, int32 beforeOffset) const
{
        if (string == NULL)
                return B_BAD_VALUE;

        if (beforeOffset < 0)
                return B_ERROR;

        return _FindBefore(string, min_clamp0(beforeOffset, Length()),
                strlen(safestr(string)));
}


int32
BString::FindLast(char c) const
{
        const char* const start = String();
        const char* end = String() + Length() - 1;

        // Scans the string backwards until we found
        // the character, or we reach the string's start
        while (end >= start && *end != c) {
                end--;
        }

        if (end < start)
                return B_ERROR;

        return end - start;
}


int32
BString::FindLast(char c, int32 beforeOffset) const
{
        if (beforeOffset < 0)
                return B_ERROR;

        const char* const start = String();
        const char* end = String() + min_clamp0(beforeOffset + 1, Length()) - 1;

        // Scans the string backwards until we found
        // the character, or we reach the string's start
        while (end >= start && *end != c) {
                end--;
        }

        if (end < start)
                return B_ERROR;

        return end - start;
}


int32
BString::FindLastChars(const BString& string, int32 beforeCharOffset) const
{
        return FindLast(string, UTF8CountBytes(fPrivateData, beforeCharOffset));
}


int32
BString::FindLastChars(const char* string, int32 beforeCharOffset) const
{
        return FindLast(string, UTF8CountBytes(fPrivateData, beforeCharOffset));
}


int32
BString::IFindFirst(const BString& string) const
{
        return _IFindAfter(string.String(), 0, string.Length());
}


int32
BString::IFindFirst(const char* string) const
{
        if (string == NULL)
                return B_BAD_VALUE;

        return _IFindAfter(string, 0, strlen(safestr(string)));
}


int32
BString::IFindFirst(const BString& string, int32 fromOffset) const
{
        if (fromOffset < 0)
                return B_ERROR;

        return _IFindAfter(string.String(), min_clamp0(fromOffset, Length()),
                string.Length());
}


int32
BString::IFindFirst(const char* string, int32 fromOffset) const
{
        if (string == NULL)
                return B_BAD_VALUE;

        if (fromOffset < 0)
                return B_ERROR;

        return _IFindAfter(string, min_clamp0(fromOffset,Length()),
                strlen(safestr(string)));
}


int32
BString::IFindLast(const BString& string) const
{
        return _IFindBefore(string.String(), Length(), string.Length());
}


int32
BString::IFindLast(const char* string) const
{
        if (string == NULL)
                return B_BAD_VALUE;

        return _IFindBefore(string, Length(), strlen(safestr(string)));
}


int32
BString::IFindLast(const BString& string, int32 beforeOffset) const
{
        if (beforeOffset < 0)
                return B_ERROR;

        return _IFindBefore(string.String(), min_clamp0(beforeOffset, Length()),
                string.Length());
}


int32
BString::IFindLast(const char* string, int32 beforeOffset) const
{
        if (string == NULL)
                return B_BAD_VALUE;

        if (beforeOffset < 0)
                return B_ERROR;

        return _IFindBefore(string, min_clamp0(beforeOffset, Length()),
                strlen(safestr(string)));
}


bool
BString::StartsWith(const BString& string) const
{
        return StartsWith(string.String(), string.Length());
}


bool
BString::StartsWith(const char* string) const
{
        return StartsWith(string, strlen(safestr(string)));
}


bool
BString::StartsWith(const char* string, int32 length) const
{
        if (length > Length())
                return false;

        return memcmp(String(), string, length) == 0;
}


bool
BString::IStartsWith(const BString& string) const
{
        return IStartsWith(string.String(), string.Length());
}


bool
BString::IStartsWith(const char* string) const
{
        return IStartsWith(string, strlen(safestr(string)));
}


bool
BString::IStartsWith(const char* string, int32 length) const
{
        if (length > Length() || length > (int32)strlen(safestr(string)))
                return false;

        return _IFindAfter(string, 0, length) == 0;
}


bool
BString::EndsWith(const BString& string) const
{
        return EndsWith(string.String(), string.Length());
}


bool
BString::EndsWith(const char* string) const
{
        return EndsWith(string, strlen(safestr(string)));
}


bool
BString::EndsWith(const char* string, int32 length) const
{
        int32 offset = Length() - length;
        if (offset < 0)
                return false;

        return memcmp(String() + offset, string, length) == 0;
}


bool
BString::IEndsWith(const BString& string) const
{
        return IEndsWith(string.String(), string.Length());
}


bool
BString::IEndsWith(const char* string) const
{
        return IEndsWith(string, strlen(safestr(string)));
}


bool
BString::IEndsWith(const char* string, int32 length) const
{
        int32 offset = Length() - length;
        if (offset < 0)
                return false;

        return _IFindBefore(string, Length(), length) == offset;
}


//      #pragma mark - Replacing


BString&
BString::ReplaceFirst(char replaceThis, char withThis)
{
        int32 pos = FindFirst(replaceThis);
        if (pos >= 0 && _MakeWritable() == B_OK)
                fPrivateData[pos] = withThis;
        return *this;
}


BString&
BString::ReplaceLast(char replaceThis, char withThis)
{
        int32 pos = FindLast(replaceThis);
        if (pos >= 0 && _MakeWritable() == B_OK)
                fPrivateData[pos] = withThis;
        return *this;
}


BString&
BString::ReplaceAll(char replaceThis, char withThis, int32 fromOffset)
{
        fromOffset = min_clamp0(fromOffset, Length());
        int32 pos = FindFirst(replaceThis, fromOffset);

        // detach and set first match
        if (pos >= 0 && _MakeWritable() == B_OK) {
                for( ; pos >= 0; pos = FindFirst(replaceThis, pos + 1))
                        fPrivateData[pos] = withThis;
        }
        return *this;
}


BString&
BString::Replace(char replaceThis, char withThis, int32 maxReplaceCount,
        int32 fromOffset)
{
        fromOffset = min_clamp0(fromOffset, Length());
        int32 pos = FindFirst(replaceThis, fromOffset);

        if (maxReplaceCount > 0 && pos >= 0 && _MakeWritable() == B_OK) {
                for( ; maxReplaceCount > 0 && pos >= 0;
                        pos = FindFirst(replaceThis, pos + 1)) {
                        fPrivateData[pos] = withThis;
                        maxReplaceCount--;
                }
        }
        return *this;
}


BString&
BString::ReplaceFirst(const char* replaceThis, const char* withThis)
{
        if (replaceThis == NULL || FindFirst(replaceThis) < 0)
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;

        return _DoReplace(replaceThis, withThis, 1, 0, KEEP_CASE);
}


BString&
BString::ReplaceLast(const char* replaceThis, const char* withThis)
{
        if (replaceThis == NULL)
                return *this;
        if (withThis == NULL)
                withThis = "";

        int32 replaceThisLength = strlen(replaceThis);
        int32 pos = _FindBefore(replaceThis, Length(), replaceThisLength);

        if (pos >= 0) {
                int32 withThisLength = strlen(withThis);
                int32 difference = withThisLength - replaceThisLength;

                if (difference > 0) {
                        if (!_OpenAtBy(pos, difference))
                                return *this;
                } else if (difference < 0) {
                        if (!_ShrinkAtBy(pos, -difference))
                                return *this;
                } else {
                        if (_MakeWritable() != B_OK)
                                return *this;
                }
                memcpy(fPrivateData + pos, withThis, withThisLength);
        }

        return *this;
}


BString&
BString::ReplaceAll(const char* replaceThis, const char* withThis,
        int32 fromOffset)
{
        if (replaceThis == NULL || FindFirst(replaceThis) < 0)
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;

        return _DoReplace(replaceThis, withThis, REPLACE_ALL,
                min_clamp0(fromOffset, Length()), KEEP_CASE);
}


BString&
BString::Replace(const char* replaceThis, const char* withThis,
        int32 maxReplaceCount, int32 fromOffset)
{
        if (replaceThis == NULL || maxReplaceCount <= 0
                || FindFirst(replaceThis) < 0)
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;

        return _DoReplace(replaceThis, withThis, maxReplaceCount,
                min_clamp0(fromOffset, Length()), KEEP_CASE);
}


BString&
BString::ReplaceAllChars(const char* replaceThis, const char* withThis,
        int32 fromCharOffset)
{
        return ReplaceAll(replaceThis, withThis,
                UTF8CountBytes(fPrivateData, fromCharOffset));
}


BString&
BString::ReplaceChars(const char* replaceThis, const char* withThis,
        int32 maxReplaceCount, int32 fromCharOffset)
{
        return Replace(replaceThis, withThis, maxReplaceCount,
                UTF8CountBytes(fPrivateData, fromCharOffset));
}


BString&
BString::IReplaceFirst(char replaceThis, char withThis)
{
        char tmp[2] = { replaceThis, '\0' };

        int32 pos = _IFindAfter(tmp, 0, 1);
        if (pos >= 0 && _MakeWritable() == B_OK)
                fPrivateData[pos] = withThis;
        return *this;
}


BString&
BString::IReplaceLast(char replaceThis, char withThis)
{
        char tmp[2] = { replaceThis, '\0' };

        int32 pos = _IFindBefore(tmp, Length(), 1);
        if (pos >= 0 && _MakeWritable() == B_OK)
                fPrivateData[pos] = withThis;
        return *this;
}


BString&
BString::IReplaceAll(char replaceThis, char withThis, int32 fromOffset)
{
        char tmp[2] = { replaceThis, '\0' };
        fromOffset = min_clamp0(fromOffset, Length());
        int32 pos = _IFindAfter(tmp, fromOffset, 1);

        if (pos >= 0 && _MakeWritable() == B_OK) {
                for( ; pos >= 0; pos = _IFindAfter(tmp, pos + 1, 1))
                        fPrivateData[pos] = withThis;
        }
        return *this;
}


BString&
BString::IReplace(char replaceThis, char withThis, int32 maxReplaceCount,
        int32 fromOffset)
{
        char tmp[2] = { replaceThis, '\0' };
        fromOffset = min_clamp0(fromOffset, Length());
        int32 pos = _IFindAfter(tmp, fromOffset, 1);

        if (maxReplaceCount > 0 && pos >= 0 && _MakeWritable() == B_OK) {
                for( ; maxReplaceCount > 0 && pos >= 0;
                        pos = _IFindAfter(tmp, pos + 1, 1)) {
                        fPrivateData[pos] = withThis;
                        maxReplaceCount--;
                }
        }

        return *this;
}


BString&
BString::IReplaceFirst(const char* replaceThis, const char* withThis)
{
        if (replaceThis == NULL || IFindFirst(replaceThis) < 0)
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;
        return _DoReplace(replaceThis, withThis, 1, 0, IGNORE_CASE);
}


BString&
BString::IReplaceLast(const char* replaceThis, const char* withThis)
{
        if (replaceThis == NULL)
                return *this;
        if (withThis == NULL)
                withThis = "";

        int32 replaceThisLength = strlen(replaceThis);
        int32 pos = _IFindBefore(replaceThis, Length(), replaceThisLength);

        if (pos >= 0) {
                int32 withThisLength = strlen(withThis);
                int32 difference = withThisLength - replaceThisLength;

                if (difference > 0) {
                        if (!_OpenAtBy(pos, difference))
                                return *this;
                } else if (difference < 0) {
                        if (!_ShrinkAtBy(pos, -difference))
                                return *this;
                } else {
                        if (_MakeWritable() != B_OK)
                                return *this;
                }
                memcpy(fPrivateData + pos, withThis, withThisLength);
        }

        return *this;
}


BString&
BString::IReplaceAll(const char* replaceThis, const char* withThis,
        int32 fromOffset)
{
        if (replaceThis == NULL || IFindFirst(replaceThis) < 0)
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;

        return _DoReplace(replaceThis, withThis, REPLACE_ALL,
                min_clamp0(fromOffset, Length()), IGNORE_CASE);
}


BString&
BString::IReplace(const char* replaceThis, const char* withThis,
        int32 maxReplaceCount, int32 fromOffset)
{
        if (replaceThis == NULL || maxReplaceCount <= 0
                || FindFirst(replaceThis) < 0)
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;

        return _DoReplace(replaceThis, withThis, maxReplaceCount,
                min_clamp0(fromOffset, Length()), IGNORE_CASE);
}


BString&
BString::ReplaceSet(const char* setOfBytes, char with)
{
        if (!setOfBytes || strcspn(fPrivateData, setOfBytes) >= uint32(Length()))
                return *this;

        if (_MakeWritable() != B_OK)
                return *this;

        int32 offset = 0;
        int32 length = Length();
        for (int32 pos;;) {
                pos = strcspn(fPrivateData + offset, setOfBytes);

                offset += pos;
                if (offset >= length)
                        break;

                fPrivateData[offset] = with;
                offset++;
        }

        return *this;
}


BString&
BString::ReplaceSet(const char* setOfBytes, const char* with)
{
        if (!setOfBytes || !with
                || strcspn(fPrivateData, setOfBytes) >= uint32(Length()))
                return *this;

        // delegate simple case
        int32 withLen = strlen(with);
        if (withLen == 1)
                return ReplaceSet(setOfBytes, *with);

        if (_MakeWritable() != B_OK)
                return *this;

        int32 pos = 0;
        int32 searchLen = 1;
        int32 len = Length();

        PosVect positions;
        for (int32 offset = 0; offset < len; offset += (pos + searchLen)) {
                pos = strcspn(fPrivateData + offset, setOfBytes);
                if (pos + offset >= len)
                        break;
                if (!positions.Add(offset + pos))
                        return *this;
        }

        _ReplaceAtPositions(&positions, searchLen, with, withLen);
        return *this;
}


BString&
BString::ReplaceCharsSet(const char* setOfChars, const char* with)
{
        if (!setOfChars || !with)
                return *this;

        int32 setCharCount = UTF8CountChars(setOfChars, -1);
        if ((uint32)setCharCount == strlen(setOfChars)) {
                // no multi-byte chars at all
                return ReplaceSet(setOfChars, with);
        }

        BString setString(setOfChars);
        BString result;

        int32 withLength = strlen(with);
        int32 charCount = CountChars();
        for (int32 i = 0; i < charCount; i++) {
                int32 charLength;
                const char* sourceChar = CharAt(i, &charLength);
                bool match = false;

                for (int32 j = 0; j < setCharCount; j++) {
                        int32 setCharLength;
                        const char* setChar = setString.CharAt(j, &setCharLength);
                        if (charLength == setCharLength
                                && memcmp(sourceChar, setChar, charLength) == 0) {
                                match = true;
                                break;
                        }
                }

                if (match)
                        result.Append(with, withLength);
                else
                        result.Append(sourceChar, charLength);
        }

        *this = result;
        return *this;
}


//      #pragma mark - Unchecked char access


#if __GNUC__ == 2
char&
BString::operator[](int32 index)
{
        if (_MakeWritable() != B_OK) {
                static char invalid;
                return invalid;
        }

        _ReferenceCount() = -1;
                // mark string as unshareable

        return fPrivateData[index];
}
#endif


const char*
BString::CharAt(int32 charIndex, int32* bytes) const
{
        int32 offset = UTF8CountBytes(fPrivateData, charIndex);
        if (bytes != NULL)
                *bytes = UTF8NextCharLen(fPrivateData + offset);
        return fPrivateData + offset;
}


bool
BString::CharAt(int32 charIndex, char* buffer, int32* bytes) const
{
        int32 length;
        const char* charAt = CharAt(charIndex, &length);
        if (bytes != NULL) {
                if (*bytes < length)
                        return false;
                *bytes = length;
        }

        memcpy(buffer, charAt, length);
        return true;
}


//      #pragma mark - Fast low-level manipulation


char*
BString::LockBuffer(int32 maxLength)
{
        int32 length = Length();
        if (maxLength > length)
                length = maxLength;

        if (_MakeWritable(length, true) != B_OK)
                return NULL;

        _ReferenceCount() = -1;
                // mark unshareable

        return fPrivateData;
}


BString&
BString::UnlockBuffer(int32 length)
{
        if (length > 0)
                length = min_clamp0(length, Length());
        else
                length = fPrivateData == NULL ? 0 : strlen(fPrivateData);

        if (_Resize(length) != NULL) {
                fPrivateData[length] = '\0';
                _ReferenceCount() = 1;
                        // mark shareable again
        }

        return *this;
}


BString&
BString::SetByteAt(int32 pos, char to)
{
        if (pos < Length() && _MakeWritable() == B_OK)
                fPrivateData[pos] = to;

        return *this;
}


//      #pragma mark - Uppercase <-> Lowercase


BString&
BString::ToLower()
{
        int32 length = Length();
        if (length > 0 && _MakeWritable() == B_OK) {
                for (int32 count = 0; count < length; count++)
                        fPrivateData[count] = tolower(fPrivateData[count]);
        }
        return *this;
}


BString&
BString::ToUpper()
{
        int32 length = Length();
        if (length > 0 && _MakeWritable() == B_OK) {
                for (int32 count = 0; count < length; count++)
                        fPrivateData[count] = toupper(fPrivateData[count]);
        }
        return *this;
}


BString&
BString::Capitalize()
{
        int32 length = Length();

        if (length > 0 && _MakeWritable() == B_OK) {
                fPrivateData[0] = toupper(fPrivateData[0]);
                for (int32 count = 1; count < length; count++)
                        fPrivateData[count] = tolower(fPrivateData[count]);
        }
        return *this;
}


BString&
BString::CapitalizeEachWord()
{
        int32 length = Length();

        if (length > 0 && _MakeWritable() == B_OK) {
                int32 count = 0;
                do {
                        // Find the first alphabetical character...
                        for (; count < length; count++) {
                                if (isalpha(fPrivateData[count])) {
                                        // ...found! Convert it to uppercase.
                                        fPrivateData[count] = toupper(fPrivateData[count]);
                                        count++;
                                        break;
                                }
                        }

                        // Now find the first non-alphabetical character,
                        // and meanwhile, turn to lowercase all the alphabetical ones
                        for (; count < length; count++) {
                                if (isalpha(fPrivateData[count]))
                                        fPrivateData[count] = tolower(fPrivateData[count]);
                                else
                                        break;
                        }
                } while (count < length);
        }
        return *this;
}


//      #pragma mark - Escaping and De-escaping


BString&
BString::CharacterEscape(const char* original,
                                                 const char* setOfCharsToEscape, char escapeWith)
{
        if (setOfCharsToEscape)
                _DoCharacterEscape(original, setOfCharsToEscape, escapeWith);
        return *this;
}


BString&
BString::CharacterEscape(const char* setOfCharsToEscape, char escapeWith)
{
        if (setOfCharsToEscape && Length() > 0)
                _DoCharacterEscape(fPrivateData, setOfCharsToEscape, escapeWith);
        return *this;
}


BString&
BString::CharacterDeescape(const char* original, char escapeChar)
{
        return _DoCharacterDeescape(original, escapeChar);
}


BString&
BString::CharacterDeescape(char escapeChar)
{
        if (Length() > 0)
                _DoCharacterDeescape(fPrivateData, escapeChar);
        return *this;
}


//      #pragma mark - Trimming


BString&
BString::Trim()
{
        if (Length() <= 0)
                return *this;

        const char* string = String();

        // string is \0 terminated thus we don't need to check if we reached the end
        int32 startCount = 0;
        while (isspace(string[startCount]))
                startCount++;

        int32 endIndex = Length() - 1;
        while (endIndex >= startCount && isspace(string[endIndex]))
                endIndex--;

        if (startCount == 0 && endIndex == Length() - 1)
                return *this;

        // We actually need to trim

        ssize_t length = endIndex + 1 - startCount;
        ASSERT(length >= 0);
        if (startCount == 0 || length == 0) {
                _MakeWritable(length, true);
        } else if (_MakeWritable() == B_OK) {
                memmove(fPrivateData, fPrivateData + startCount, length);
                fPrivateData[length] = '\0';
                _SetLength(length);
        }

        return *this;
}


//      #pragma mark - Insert


BString&
BString::operator<<(const char* string)
{
        if (string != NULL) {
                int32 length = strlen(string);
                if (length > 0)
                        _DoAppend(string, length);
        }
        return *this;
}


BString&
BString::operator<<(const BString& string)
{
        if (string.Length() > 0)
                _DoAppend(string.String(), string.Length());
        return *this;
}


BString&
BString::operator<<(char c)
{
        _DoAppend(&c, 1);
        return *this;
}


BString&
BString::operator<<(bool value)
{
        if (value)
                _DoAppend("true", 4);
        else
                _DoAppend("false", 5);

        return *this;
}


BString&
BString::operator<<(int i)
{
        char num[32];
        int32 length = snprintf(num, sizeof(num), "%d", i);

        _DoAppend(num, length);
        return *this;
}


BString&
BString::operator<<(unsigned int i)
{
        char num[32];
        int32 length = snprintf(num, sizeof(num), "%u", i);

        _DoAppend(num, length);
        return *this;
}


BString&
BString::operator<<(unsigned long i)
{
        char num[32];
        int32 length = snprintf(num, sizeof(num), "%lu", i);

        _DoAppend(num, length);
        return *this;
}


BString&
BString::operator<<(long i)
{
        char num[32];
        int32 length = snprintf(num, sizeof(num), "%ld", i);

        _DoAppend(num, length);
        return *this;
}


BString&
BString::operator<<(unsigned long long i)
{
        char num[64];
        int32 length = snprintf(num, sizeof(num), "%llu", i);

        _DoAppend(num, length);
        return *this;
}


BString&
BString::operator<<(long long i)
{
        char num[64];
        int32 length = snprintf(num, sizeof(num), "%lld", i);

        _DoAppend(num, length);
        return *this;
}


BString&
BString::operator<<(float f)
{
        char num[64];
        int32 length = snprintf(num, sizeof(num), "%.2f", f);

        _DoAppend(num, length);
        return *this;
}


BString&
BString::operator<<(double value)
{
        char num[64];
        int32 length = snprintf(num, sizeof(num), "%.2f", value);

        _DoAppend(num, length);
        return *this;
}


//      #pragma mark - Private or reserved


BString::BString(char* privateData, PrivateDataTag tag)
        :
        fPrivateData(privateData)
{
        if (fPrivateData != NULL)
                atomic_add(&_ReferenceCount(), 1);
}


/*!     Detaches this string from an eventually shared fPrivateData, ie. this makes
        this string writable.
*/
status_t
BString::_MakeWritable()
{
        if (fPrivateData == NULL)
                return B_NO_INIT;

        if (atomic_get(&_ReferenceCount()) > 1) {
                // It might be shared, and this requires special treatment
                char* newData = _Clone(fPrivateData, Length());
                _ReleasePrivateData();
                if (newData == NULL)
                        return B_NO_MEMORY;

                fPrivateData = newData;
        }

        return B_OK;
}


/*!     Makes this string writable, and resizes the buffer to \a length bytes (not
        including the terminating null).

        @param length The length of the new buffer in bytes.
        @param copy If true, the current string will be copied into the new string.
*/
status_t
BString::_MakeWritable(int32 length, bool copy)
{
        char* newData = NULL;

        if (fPrivateData != NULL && atomic_get(&_ReferenceCount()) > 1) {
                // we might share our data with someone else
                if (copy)
                        newData = _Clone(fPrivateData, length);
                else
                        newData = _Allocate(length);

                if (newData == NULL)
                        return B_NO_MEMORY;

                _ReleasePrivateData();
        } else {
                // we don't share our data with someone else
                newData = _Resize(length);

                if (newData == NULL)
                        return B_NO_MEMORY;
        }

        fPrivateData = newData;
        return B_OK;
}


/*!     Allocates a new private data buffer with the space to store \a length bytes
        (not including the terminating null).
*/
/*static*/ char*
BString::_Allocate(int32 length)
{
        if (length < 0)
                return NULL;

        char* newData = (char*)malloc(length + kPrivateDataOffset + 1);
        if (newData == NULL)
                return NULL;

        newData += kPrivateDataOffset;
        newData[length] = '\0';

        // initialize reference count & length
        Private::DataRefCount(newData) = 1;
        Private::DataLength(newData) = length & 0x7fffffff;

        return newData;
}


/*!     Resizes the private data buffer. You must already have a writable buffer
        when you call this method.
*/
char*
BString::_Resize(int32 length)
{
        ASSERT(_ReferenceCount() == 1 || _ReferenceCount() == -1);

        if (length == Length())
                return fPrivateData;

        char* data = fPrivateData ? fPrivateData - kPrivateDataOffset : NULL;
        if (length < 0)
                length = 0;

        data = (char*)realloc(data, length + kPrivateDataOffset + 1);
        if (data == NULL)
                return NULL;

        data += kPrivateDataOffset;

        fPrivateData = data;
        fPrivateData[length] = '\0';

        _SetLength(length);
        _ReferenceCount() = 1;

        return data;
}


void
BString::_Init(const char* src, int32 length)
{
        fPrivateData = _Clone(src, length);
        if (fPrivateData == NULL)
                fPrivateData = _Clone(NULL, 0);
}


char*
BString::_Clone(const char* data, int32 length)
{
        char* newData = _Allocate(length);
        if (newData == NULL)
                return NULL;

        if (data != NULL && length > 0) {
                // "data" may not span over the whole length
                strncpy(newData, data, length);
        }

        return newData;
}


char*
BString::_OpenAtBy(int32 offset, int32 length)
{
        int32 oldLength = Length();

        if (_MakeWritable() != B_OK)
                return NULL;

        memmove(fPrivateData + offset + length, fPrivateData + offset,
                oldLength - offset);
        return _Resize(oldLength + length);
}


char*
BString::_ShrinkAtBy(int32 offset, int32 length)
{
        int32 oldLength = Length();
        if (_MakeWritable() != B_OK)
                return NULL;

        memmove(fPrivateData + offset, fPrivateData + offset + length,
                oldLength - offset - length);
        return _Resize(oldLength - length);
}


void
BString::_SetLength(int32 length)
{
        Private::DataLength(fPrivateData) = length & 0x7fffffff;
}


void
BString::_FreePrivateData()
{
        if (fPrivateData != NULL) {
                free(fPrivateData - kPrivateDataOffset);
                fPrivateData = NULL;
        }
}


void
BString::_ReleasePrivateData()
{
        if (!_IsShareable() || atomic_add(&_ReferenceCount(), -1) == 1)
                _FreePrivateData();
        fPrivateData = NULL;
}


bool
BString::_DoAppend(const char* string, int32 length)
{
        int32 oldLength = Length();
        if (_MakeWritable(oldLength + length, true) == B_OK) {
                strncpy(fPrivateData + oldLength, string, length);
                return true;
        }
        return false;
}


bool
BString::_DoPrepend(const char* string, int32 length)
{
        // TODO: this could be optimized (allocate a new buffer, use memcpy())
        int32 oldLength = Length();
        if (_MakeWritable(oldLength + length, true) == B_OK) {
                memmove(fPrivateData + length, fPrivateData, oldLength);
                if (string && length)
                        strncpy(fPrivateData, string, length);
                return true;
        }
        return false;
}


bool
BString::_DoInsert(const char* string, int32 offset, int32 length)
{
        int32 oldLength = Length();
        if (_MakeWritable(oldLength + length, true) == B_OK) {
                memmove(fPrivateData + offset + length, fPrivateData + offset,
                        oldLength - offset);
                if (string != NULL && length)
                        strncpy(fPrivateData + offset, string, length);
                return true;
        }
        return false;
}


int32
BString::_ShortFindAfter(const char* string, int32 len) const
{
        const char* ptr = strstr(String(), string);

        if (ptr != NULL)
                return ptr - String();

        return B_ERROR;
}


int32
BString::_FindAfter(const char* string, int32 offset, int32 length) const
{
        const char* ptr = strstr(String() + offset, string);

        if (ptr != NULL)
                return ptr - String();

        return B_ERROR;
}


int32
BString::_IFindAfter(const char* string, int32 offset, int32 length) const
{
        const char* ptr = strcasestr(String() + offset, string);

        if (ptr != NULL)
                return ptr - String();

        return B_ERROR;
}


int32
BString::_FindBefore(const char* string, int32 offset, int32 length) const
{
        if (fPrivateData != NULL) {
#ifdef __HAIKU__
                const char* end = fPrivateData + offset - (length - 1);
                while (end >= fPrivateData) {
                        const char* ptr = (const char*)memrchr(fPrivateData,
                                string[0], end - fPrivateData);
                        if (ptr == NULL)
                                break;

                        if (memcmp(ptr, string, length) == 0)
                                return ptr - fPrivateData;

                        end = ptr;
                }
#else
                const char* ptr = fPrivateData + offset - length;
                while (ptr >= fPrivateData) {
                        if (!memcmp(ptr, string, length))
                                return ptr - fPrivateData;
                        ptr--;
                }
#endif
        }
        return B_ERROR;
}


int32
BString::_IFindBefore(const char* string, int32 offset, int32 length) const
{
        if (fPrivateData != NULL) {
                char* ptr1 = fPrivateData + offset - length;

                while (ptr1 >= fPrivateData) {
                        if (!strncasecmp(ptr1, string, length))
                                return ptr1 - fPrivateData;
                        ptr1--;
                }
        }
        return B_ERROR;
}


BString&
BString::_DoCharacterEscape(const char* string, const char* setOfCharsToEscape,
        char escapeChar)
{
        if (_MakeWritable(string_length(string), false) != B_OK)
                return *this;

        memcpy(fPrivateData, string, Length());

        PosVect positions;
        int32 length = Length();
        int32 pos;
        for (int32 offset = 0; offset < length; offset += pos + 1) {
                pos = strcspn(fPrivateData + offset, setOfCharsToEscape);
                if (pos < length - offset && !positions.Add(offset + pos))
                        return *this;
        }

        uint32 count = positions.CountItems();
        int32 newLength = length + count;
        if (!newLength) {
                _Resize(0);
                return *this;
        }

        char* newData = _Allocate(newLength);
        if (newData) {
                char* oldString = fPrivateData;
                char* newString = newData;
                int32 lastPos = 0;

                for (uint32 i = 0; i < count; ++i) {
                        pos = positions.ItemAt(i);
                        length = pos - lastPos;
                        if (length > 0) {
                                memcpy(newString, oldString, length);
                                oldString += length;
                                newString += length;
                        }
                        *newString++ = escapeChar;
                        *newString++ = *oldString++;
                        lastPos = pos + 1;
                }

                length = Length() + 1 - lastPos;
                if (length > 0)
                        memcpy(newString, oldString, length);

                _FreePrivateData();
                fPrivateData = newData;
        }
        return *this;
}


BString&
BString::_DoCharacterDeescape(const char* string, char escapeChar)
{
        if (_MakeWritable(string_length(string), false) != B_OK)
                return *this;

        memcpy(fPrivateData, string, Length());
        const char escape[2] = { escapeChar, '\0' };
        return _DoReplace(escape, "", REPLACE_ALL, 0, KEEP_CASE);
}


BString&
BString::_DoReplace(const char* findThis, const char* replaceWith,
        int32 maxReplaceCount, int32 fromOffset, bool ignoreCase)
{
        if (findThis == NULL || maxReplaceCount <= 0
                || fromOffset < 0 || fromOffset >= Length())
                return *this;

        int32 findLen = strlen(findThis);
        if (findLen == 0)
                return *this;

        typedef int32 (BString::*TFindMethod)(const char*, int32, int32) const;
        TFindMethod findMethod = ignoreCase
                ? &BString::_IFindAfter : &BString::_FindAfter;

        if (replaceWith == NULL)
                replaceWith = "";

        int32 replaceLen = strlen(replaceWith);
        int32 lastSrcPos = fromOffset;
        PosVect positions;
        for (int32 srcPos = 0; maxReplaceCount > 0
                && (srcPos = (this->*findMethod)(findThis, lastSrcPos, findLen)) >= 0;
                        maxReplaceCount--) {
                positions.Add(srcPos);
                lastSrcPos = srcPos + findLen;
        }
        _ReplaceAtPositions(&positions, findLen, replaceWith, replaceLen);
        return *this;
}


void
BString::_ReplaceAtPositions(const PosVect* positions, int32 searchLength,
        const char* with, int32 withLength)
{
        int32 length = Length();
        uint32 count = positions->CountItems();
        int32 newLength = length + count * (withLength - searchLength);
        if (!newLength) {
                _Resize(0);
                return;
        }

        char* newData = _Allocate(newLength);
        if (newData == NULL)
                return;

        char* oldString = fPrivateData;
        char* newString = newData;
        int32 lastPos = 0;

        for (uint32 i = 0; i < count; ++i) {
                int32 pos = positions->ItemAt(i);
                length = pos - lastPos;
                if (length > 0) {
                        memcpy(newString, oldString, length);
                        oldString += length;
                        newString += length;
                }
                memcpy(newString, with, withLength);
                oldString += searchLength;
                newString += withLength;
                lastPos = pos + searchLength;
        }

        length = Length() + 1 - lastPos;
        if (length > 0)
                memcpy(newString, oldString, length);

        _FreePrivateData();
        fPrivateData = newData;
}


//      #pragma mark - backwards compatibility


/*!     Translates to (missing const):
        BString& BString::operator<<(BString& string)
*/
extern "C" BString&
__ls__7BStringR7BString(BString* self, BString& string)
{
        return self->operator<<(string);
}


#if __GNUC__ > 3

//      #pragma mark - BStringRef backwards compatibility


class BStringRef {
public:
        BStringRef(BString& string, int32 position);
        ~BStringRef() {}

        operator char() const;

        char* operator&();
        const char* operator&() const;

        BStringRef& operator=(char c);
        BStringRef& operator=(const BStringRef& rc);

private:
        BString&        fString;
        int32           fPosition;
};


BStringRef::BStringRef(BString& string, int32 position)
        :
        fString(string), fPosition(position)
{
}


BStringRef::operator char() const
{
        return fPosition < fString.Length() ? fString.fPrivateData[fPosition] : 0;
}


BStringRef&
BStringRef::operator=(char c)
{
        fString._MakeWritable();
        fString.fPrivateData[fPosition] = c;
        return *this;
}


BStringRef&
BStringRef::operator=(const BStringRef &rc)
{
        return operator=(rc.fString.fPrivateData[rc.fPosition]);
}


const char*
BStringRef::operator&() const
{
        return &fString.fPrivateData[fPosition];
}


char*
BStringRef::operator&()
{
        if (fString._MakeWritable() != B_OK)
                return NULL;

        fString._ReferenceCount() = -1;
                // mark as unsharable
        return &fString.fPrivateData[fPosition];
}



extern "C" BStringRef
_ZN7BStringixEi(BString* self, int32 index)

{
        return BStringRef(*self, index);
}
#endif


//      #pragma mark - Non-member compare for sorting, etc.


int
Compare(const BString& string1, const BString& string2)
{
        return strcmp(string1.String(), string2.String());
}


int
ICompare(const BString& string1, const BString& string2)
{
        return strcasecmp(string1.String(), string2.String());
}


int
Compare(const BString* string1, const BString* string2)
{
        return strcmp(string1->String(), string2->String());
}


int
ICompare(const BString* string1, const BString* string2)
{
        return strcasecmp(string1->String(), string2->String());
}