nuclear@3: /************************************************************************************
nuclear@3: 
nuclear@3: Filename    :   OVR_String.cpp
nuclear@3: Content     :   String UTF8 string implementation with copy-on-write semantics
nuclear@3:                 (thread-safe for assignment but not modification).
nuclear@3: Created     :   September 19, 2012
nuclear@3: Notes       : 
nuclear@3: 
nuclear@3: Copyright   :   Copyright 2012 Oculus VR, Inc. All Rights reserved.
nuclear@3: 
nuclear@3: Use of this software is subject to the terms of the Oculus license
nuclear@3: agreement provided at the time of installation or download, or which
nuclear@3: otherwise accompanies this software in either electronic or hard copy form.
nuclear@3: 
nuclear@3: ************************************************************************************/
nuclear@3: 
nuclear@3: #include "OVR_String.h"
nuclear@3: 
nuclear@3: #include <stdlib.h>
nuclear@3: #include <ctype.h>
nuclear@3: 
nuclear@3: #ifdef OVR_OS_QNX
nuclear@3: # include <strings.h>
nuclear@3: #endif
nuclear@3: 
nuclear@3: namespace OVR {
nuclear@3: 
nuclear@3: #define String_LengthIsSize (UPInt(1) << String::Flag_LengthIsSizeShift)
nuclear@3: 
nuclear@3: String::DataDesc String::NullData = {String_LengthIsSize, 1, {0} };
nuclear@3: 
nuclear@3: 
nuclear@3: String::String()
nuclear@3: {
nuclear@3:     pData = &NullData;
nuclear@3:     pData->AddRef();
nuclear@3: };
nuclear@3: 
nuclear@3: String::String(const char* pdata)
nuclear@3: {
nuclear@3:     // Obtain length in bytes; it doesn't matter if _data is UTF8.
nuclear@3:     UPInt size = pdata ? OVR_strlen(pdata) : 0; 
nuclear@3:     pData = AllocDataCopy1(size, 0, pdata, size);
nuclear@3: };
nuclear@3: 
nuclear@3: String::String(const char* pdata1, const char* pdata2, const char* pdata3)
nuclear@3: {
nuclear@3:     // Obtain length in bytes; it doesn't matter if _data is UTF8.
nuclear@3:     UPInt size1 = pdata1 ? OVR_strlen(pdata1) : 0; 
nuclear@3:     UPInt size2 = pdata2 ? OVR_strlen(pdata2) : 0; 
nuclear@3:     UPInt size3 = pdata3 ? OVR_strlen(pdata3) : 0; 
nuclear@3: 
nuclear@3:     DataDesc *pdataDesc = AllocDataCopy2(size1 + size2 + size3, 0,
nuclear@3:                                          pdata1, size1, pdata2, size2);
nuclear@3:     memcpy(pdataDesc->Data + size1 + size2, pdata3, size3);   
nuclear@3:     pData = pdataDesc;    
nuclear@3: }
nuclear@3: 
nuclear@3: String::String(const char* pdata, UPInt size)
nuclear@3: {
nuclear@3:     OVR_ASSERT((size == 0) || (pdata != 0));
nuclear@3:     pData = AllocDataCopy1(size, 0, pdata, size);
nuclear@3: };
nuclear@3: 
nuclear@3: 
nuclear@3: String::String(const InitStruct& src, UPInt size)
nuclear@3: {
nuclear@3:     pData = AllocData(size, 0);
nuclear@3:     src.InitString(GetData()->Data, size);
nuclear@3: }
nuclear@3: 
nuclear@3: String::String(const String& src)
nuclear@3: {    
nuclear@3:     pData = src.GetData();
nuclear@3:     pData->AddRef();
nuclear@3: }
nuclear@3: 
nuclear@3: String::String(const StringBuffer& src)
nuclear@3: {
nuclear@3:     pData = AllocDataCopy1(src.GetSize(), 0, src.ToCStr(), src.GetSize());
nuclear@3: }
nuclear@3: 
nuclear@3: String::String(const wchar_t* data)
nuclear@3: {
nuclear@3:     pData = &NullData;
nuclear@3:     pData->AddRef();
nuclear@3:     // Simplified logic for wchar_t constructor.
nuclear@3:     if (data)    
nuclear@3:         *this = data;    
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: String::DataDesc* String::AllocData(UPInt size, UPInt lengthIsSize)
nuclear@3: {
nuclear@3:     String::DataDesc* pdesc;
nuclear@3: 
nuclear@3:     if (size == 0)
nuclear@3:     {
nuclear@3:         pdesc = &NullData;
nuclear@3:         pdesc->AddRef();
nuclear@3:         return pdesc;
nuclear@3:     }
nuclear@3: 
nuclear@3:     pdesc = (DataDesc*)OVR_ALLOC(sizeof(DataDesc)+ size);
nuclear@3:     pdesc->Data[size] = 0;
nuclear@3:     pdesc->RefCount = 1;
nuclear@3:     pdesc->Size     = size | lengthIsSize;  
nuclear@3:     return pdesc;
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: String::DataDesc* String::AllocDataCopy1(UPInt size, UPInt lengthIsSize,
nuclear@3:                                          const char* pdata, UPInt copySize)
nuclear@3: {
nuclear@3:     String::DataDesc* pdesc = AllocData(size, lengthIsSize);
nuclear@3:     memcpy(pdesc->Data, pdata, copySize);
nuclear@3:     return pdesc;
nuclear@3: }
nuclear@3: 
nuclear@3: String::DataDesc* String::AllocDataCopy2(UPInt size, UPInt lengthIsSize,
nuclear@3:                                          const char* pdata1, UPInt copySize1,
nuclear@3:                                          const char* pdata2, UPInt copySize2)
nuclear@3: {
nuclear@3:     String::DataDesc* pdesc = AllocData(size, lengthIsSize);
nuclear@3:     memcpy(pdesc->Data, pdata1, copySize1);
nuclear@3:     memcpy(pdesc->Data + copySize1, pdata2, copySize2);
nuclear@3:     return pdesc;
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: UPInt String::GetLength() const 
nuclear@3: {
nuclear@3:     // Optimize length accesses for non-UTF8 character strings. 
nuclear@3:     DataDesc* pdata = GetData();
nuclear@3:     UPInt     length, size = pdata->GetSize();
nuclear@3:     
nuclear@3:     if (pdata->LengthIsSize())
nuclear@3:         return size;    
nuclear@3:     
nuclear@3:     length = (UPInt)UTF8Util::GetLength(pdata->Data, (UPInt)size);
nuclear@3:     
nuclear@3:     if (length == size)
nuclear@3:         pdata->Size |= String_LengthIsSize;
nuclear@3:     
nuclear@3:     return length;
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: //static UInt32 String_CharSearch(const char* buf, )
nuclear@3: 
nuclear@3: 
nuclear@3: UInt32 String::GetCharAt(UPInt index) const 
nuclear@3: {  
nuclear@3:     SPInt       i = (SPInt) index;
nuclear@3:     DataDesc*   pdata = GetData();
nuclear@3:     const char* buf = pdata->Data;
nuclear@3:     UInt32      c;
nuclear@3:     
nuclear@3:     if (pdata->LengthIsSize())
nuclear@3:     {
nuclear@3:         OVR_ASSERT(index < pdata->GetSize());
nuclear@3:         buf += i;
nuclear@3:         return UTF8Util::DecodeNextChar_Advance0(&buf);
nuclear@3:     }
nuclear@3: 
nuclear@3:     c = UTF8Util::GetCharAt(index, buf, pdata->GetSize());
nuclear@3:     return c;
nuclear@3: }
nuclear@3: 
nuclear@3: UInt32 String::GetFirstCharAt(UPInt index, const char** offset) const
nuclear@3: {
nuclear@3:     DataDesc*   pdata = GetData();
nuclear@3:     SPInt       i = (SPInt) index;
nuclear@3:     const char* buf = pdata->Data;
nuclear@3:     const char* end = buf + pdata->GetSize();
nuclear@3:     UInt32      c;
nuclear@3: 
nuclear@3:     do 
nuclear@3:     {
nuclear@3:         c = UTF8Util::DecodeNextChar_Advance0(&buf);
nuclear@3:         i--;
nuclear@3: 
nuclear@3:         if (buf >= end)
nuclear@3:         {
nuclear@3:             // We've hit the end of the string; don't go further.
nuclear@3:             OVR_ASSERT(i == 0);
nuclear@3:             return c;
nuclear@3:         }
nuclear@3:     } while (i >= 0);
nuclear@3: 
nuclear@3:     *offset = buf;
nuclear@3: 
nuclear@3:     return c;
nuclear@3: }
nuclear@3: 
nuclear@3: UInt32 String::GetNextChar(const char** offset) const
nuclear@3: {
nuclear@3:     return UTF8Util::DecodeNextChar(offset);
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: void String::AppendChar(UInt32 ch)
nuclear@3: {
nuclear@3:     DataDesc*   pdata = GetData();
nuclear@3:     UPInt       size = pdata->GetSize();
nuclear@3:     char        buff[8];
nuclear@3:     SPInt       encodeSize = 0;
nuclear@3: 
nuclear@3:     // Converts ch into UTF8 string and fills it into buff.   
nuclear@3:     UTF8Util::EncodeChar(buff, &encodeSize, ch);
nuclear@3:     OVR_ASSERT(encodeSize >= 0);
nuclear@3: 
nuclear@3:     SetData(AllocDataCopy2(size + (UPInt)encodeSize, 0,
nuclear@3:                            pdata->Data, size, buff, (UPInt)encodeSize));
nuclear@3:     pdata->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: void String::AppendString(const wchar_t* pstr, SPInt len)
nuclear@3: {
nuclear@3:     if (!pstr)
nuclear@3:         return;
nuclear@3: 
nuclear@3:     DataDesc*   pdata = GetData();
nuclear@3:     UPInt       oldSize = pdata->GetSize();    
nuclear@3:     UPInt       encodeSize = (UPInt)UTF8Util::GetEncodeStringSize(pstr, len);
nuclear@3: 
nuclear@3:     DataDesc*   pnewData = AllocDataCopy1(oldSize + (UPInt)encodeSize, 0,
nuclear@3:                                           pdata->Data, oldSize);
nuclear@3:     UTF8Util::EncodeString(pnewData->Data + oldSize,  pstr, len);
nuclear@3: 
nuclear@3:     SetData(pnewData);
nuclear@3:     pdata->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: void String::AppendString(const char* putf8str, SPInt utf8StrSz)
nuclear@3: {
nuclear@3:     if (!putf8str || !utf8StrSz)
nuclear@3:         return;
nuclear@3:     if (utf8StrSz == -1)
nuclear@3:         utf8StrSz = (SPInt)OVR_strlen(putf8str);
nuclear@3: 
nuclear@3:     DataDesc*   pdata = GetData();
nuclear@3:     UPInt       oldSize = pdata->GetSize();
nuclear@3: 
nuclear@3:     SetData(AllocDataCopy2(oldSize + (UPInt)utf8StrSz, 0,
nuclear@3:                            pdata->Data, oldSize, putf8str, (UPInt)utf8StrSz));
nuclear@3:     pdata->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: void    String::AssignString(const InitStruct& src, UPInt size)
nuclear@3: {
nuclear@3:     DataDesc*   poldData = GetData();
nuclear@3:     DataDesc*   pnewData = AllocData(size, 0);
nuclear@3:     src.InitString(pnewData->Data, size);
nuclear@3:     SetData(pnewData);
nuclear@3:     poldData->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: void    String::AssignString(const char* putf8str, UPInt size)
nuclear@3: {
nuclear@3:     DataDesc* poldData = GetData();
nuclear@3:     SetData(AllocDataCopy1(size, 0, putf8str, size));
nuclear@3:     poldData->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: void    String::operator = (const char* pstr)
nuclear@3: {
nuclear@3:     AssignString(pstr, pstr ? OVR_strlen(pstr) : 0);
nuclear@3: }
nuclear@3: 
nuclear@3: void    String::operator = (const wchar_t* pwstr)
nuclear@3: {
nuclear@3:     DataDesc*   poldData = GetData();
nuclear@3:     UPInt       size = pwstr ? (UPInt)UTF8Util::GetEncodeStringSize(pwstr) : 0;
nuclear@3: 
nuclear@3:     DataDesc*   pnewData = AllocData(size, 0);
nuclear@3:     UTF8Util::EncodeString(pnewData->Data, pwstr);
nuclear@3:     SetData(pnewData);
nuclear@3:     poldData->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: void    String::operator = (const String& src)
nuclear@3: {     
nuclear@3:     DataDesc*    psdata = src.GetData();
nuclear@3:     DataDesc*    pdata = GetData();    
nuclear@3: 
nuclear@3:     SetData(psdata);
nuclear@3:     psdata->AddRef();
nuclear@3:     pdata->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: void    String::operator = (const StringBuffer& src)
nuclear@3: { 
nuclear@3:     DataDesc* polddata = GetData();    
nuclear@3:     SetData(AllocDataCopy1(src.GetSize(), 0, src.ToCStr(), src.GetSize()));
nuclear@3:     polddata->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: void    String::operator += (const String& src)
nuclear@3: {
nuclear@3:     DataDesc   *pourData = GetData(),
nuclear@3:                *psrcData = src.GetData();
nuclear@3:     UPInt       ourSize  = pourData->GetSize(),
nuclear@3:                 srcSize  = psrcData->GetSize();
nuclear@3:     UPInt       lflag    = pourData->GetLengthFlag() & psrcData->GetLengthFlag();
nuclear@3: 
nuclear@3:     SetData(AllocDataCopy2(ourSize + srcSize, lflag,
nuclear@3:                            pourData->Data, ourSize, psrcData->Data, srcSize));
nuclear@3:     pourData->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: String   String::operator + (const char* str) const
nuclear@3: {   
nuclear@3:     String tmp1(*this);
nuclear@3:     tmp1 += (str ? str : "");
nuclear@3:     return tmp1;
nuclear@3: }
nuclear@3: 
nuclear@3: String   String::operator + (const String& src) const
nuclear@3: { 
nuclear@3:     String tmp1(*this);
nuclear@3:     tmp1 += src;
nuclear@3:     return tmp1;
nuclear@3: }
nuclear@3: 
nuclear@3: void    String::Remove(UPInt posAt, SPInt removeLength)
nuclear@3: {
nuclear@3:     DataDesc*   pdata = GetData();
nuclear@3:     UPInt       oldSize = pdata->GetSize();    
nuclear@3:     // Length indicates the number of characters to remove. 
nuclear@3:     UPInt       length = GetLength();
nuclear@3: 
nuclear@3:     // If index is past the string, nothing to remove.
nuclear@3:     if (posAt >= length)
nuclear@3:         return;
nuclear@3:     // Otherwise, cap removeLength to the length of the string.
nuclear@3:     if ((posAt + removeLength) > length)
nuclear@3:         removeLength = length - posAt;
nuclear@3: 
nuclear@3:     // Get the byte position of the UTF8 char at position posAt.
nuclear@3:     SPInt bytePos    = UTF8Util::GetByteIndex(posAt, pdata->Data, oldSize);
nuclear@3:     SPInt removeSize = UTF8Util::GetByteIndex(removeLength, pdata->Data + bytePos, oldSize-bytePos);
nuclear@3: 
nuclear@3:     SetData(AllocDataCopy2(oldSize - removeSize, pdata->GetLengthFlag(),
nuclear@3:                            pdata->Data, bytePos,
nuclear@3:                            pData->Data + bytePos + removeSize, (oldSize - bytePos - removeSize)));
nuclear@3:     pdata->Release();
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: String   String::Substring(UPInt start, UPInt end) const
nuclear@3: {
nuclear@3:     UPInt length = GetLength();
nuclear@3:     if ((start >= length) || (start >= end))
nuclear@3:         return String();   
nuclear@3: 
nuclear@3:     DataDesc* pdata = GetData();
nuclear@3:     
nuclear@3:     // If size matches, we know the exact index range.
nuclear@3:     if (pdata->LengthIsSize())
nuclear@3:         return String(pdata->Data + start, end - start);
nuclear@3:     
nuclear@3:     // Get position of starting character.
nuclear@3:     SPInt byteStart = UTF8Util::GetByteIndex(start, pdata->Data, pdata->GetSize());
nuclear@3:     SPInt byteSize  = UTF8Util::GetByteIndex(end - start, pdata->Data + byteStart, pdata->GetSize()-byteStart);
nuclear@3:     return String(pdata->Data + byteStart, (UPInt)byteSize);
nuclear@3: }
nuclear@3: 
nuclear@3: void String::Clear()
nuclear@3: {   
nuclear@3:     NullData.AddRef();
nuclear@3:     GetData()->Release();
nuclear@3:     SetData(&NullData);
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: String   String::ToUpper() const 
nuclear@3: {       
nuclear@3:     UInt32      c;
nuclear@3:     const char* psource = GetData()->Data;
nuclear@3:     const char* pend = psource + GetData()->GetSize();
nuclear@3:     String      str;
nuclear@3:     SPInt       bufferOffset = 0;
nuclear@3:     char        buffer[512];
nuclear@3:     
nuclear@3:     while(psource < pend)
nuclear@3:     {
nuclear@3:         do {            
nuclear@3:             c = UTF8Util::DecodeNextChar_Advance0(&psource);
nuclear@3:             UTF8Util::EncodeChar(buffer, &bufferOffset, OVR_towupper(wchar_t(c)));
nuclear@3:         } while ((psource < pend) && (bufferOffset < SPInt(sizeof(buffer)-8)));
nuclear@3: 
nuclear@3:         // Append string a piece at a time.
nuclear@3:         str.AppendString(buffer, bufferOffset);
nuclear@3:         bufferOffset = 0;
nuclear@3:     }
nuclear@3: 
nuclear@3:     return str;
nuclear@3: }
nuclear@3: 
nuclear@3: String   String::ToLower() const 
nuclear@3: {
nuclear@3:     UInt32      c;
nuclear@3:     const char* psource = GetData()->Data;
nuclear@3:     const char* pend = psource + GetData()->GetSize();
nuclear@3:     String      str;
nuclear@3:     SPInt       bufferOffset = 0;
nuclear@3:     char        buffer[512];
nuclear@3: 
nuclear@3:     while(psource < pend)
nuclear@3:     {
nuclear@3:         do {
nuclear@3:             c = UTF8Util::DecodeNextChar_Advance0(&psource);
nuclear@3:             UTF8Util::EncodeChar(buffer, &bufferOffset, OVR_towlower(wchar_t(c)));
nuclear@3:         } while ((psource < pend) && (bufferOffset < SPInt(sizeof(buffer)-8)));
nuclear@3: 
nuclear@3:         // Append string a piece at a time.
nuclear@3:         str.AppendString(buffer, bufferOffset);
nuclear@3:         bufferOffset = 0;
nuclear@3:     }
nuclear@3: 
nuclear@3:     return str;
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: String& String::Insert(const char* substr, UPInt posAt, SPInt strSize)
nuclear@3: {
nuclear@3:     DataDesc* poldData   = GetData();
nuclear@3:     UPInt     oldSize    = poldData->GetSize();
nuclear@3:     UPInt     insertSize = (strSize < 0) ? OVR_strlen(substr) : (UPInt)strSize;    
nuclear@3:     UPInt     byteIndex  =  (poldData->LengthIsSize()) ?
nuclear@3:                             posAt : (UPInt)UTF8Util::GetByteIndex(posAt, poldData->Data, oldSize);
nuclear@3: 
nuclear@3:     OVR_ASSERT(byteIndex <= oldSize);
nuclear@3:     
nuclear@3:     DataDesc* pnewData = AllocDataCopy2(oldSize + insertSize, 0,
nuclear@3:                                         poldData->Data, byteIndex, substr, insertSize);
nuclear@3:     memcpy(pnewData->Data + byteIndex + insertSize,
nuclear@3:            poldData->Data + byteIndex, oldSize - byteIndex);
nuclear@3:     SetData(pnewData);
nuclear@3:     poldData->Release();
nuclear@3:     return *this;
nuclear@3: }
nuclear@3: 
nuclear@3: /*
nuclear@3: String& String::Insert(const UInt32* substr, UPInt posAt, SPInt len)
nuclear@3: {
nuclear@3:     for (SPInt i = 0; i < len; ++i)
nuclear@3:     {
nuclear@3:         UPInt charw = InsertCharAt(substr[i], posAt);
nuclear@3:         posAt += charw;
nuclear@3:     }
nuclear@3:     return *this;
nuclear@3: }
nuclear@3: */
nuclear@3: 
nuclear@3: UPInt String::InsertCharAt(UInt32 c, UPInt posAt)
nuclear@3: {
nuclear@3:     char    buf[8];
nuclear@3:     SPInt   index = 0;
nuclear@3:     UTF8Util::EncodeChar(buf, &index, c);
nuclear@3:     OVR_ASSERT(index >= 0);
nuclear@3:     buf[(UPInt)index] = 0;
nuclear@3: 
nuclear@3:     Insert(buf, posAt, index);
nuclear@3:     return (UPInt)index;
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: int String::CompareNoCase(const char* a, const char* b)
nuclear@3: {
nuclear@3:     return OVR_stricmp(a, b);
nuclear@3: }
nuclear@3: 
nuclear@3: int String::CompareNoCase(const char* a, const char* b, SPInt len)
nuclear@3: {
nuclear@3:     if (len)
nuclear@3:     {
nuclear@3:         SPInt f,l;
nuclear@3:         SPInt slen = len;
nuclear@3:         const char *s = b;
nuclear@3:         do {
nuclear@3:             f = (SPInt)OVR_tolower((int)(*(a++)));
nuclear@3:             l = (SPInt)OVR_tolower((int)(*(b++)));
nuclear@3:         } while (--len && f && (f == l) && *b != 0);
nuclear@3: 
nuclear@3:         if (f == l && (len != 0 || *b != 0))
nuclear@3:         {
nuclear@3:             f = (SPInt)slen;
nuclear@3:             l = (SPInt)OVR_strlen(s);
nuclear@3:             return int(f - l);
nuclear@3:         }
nuclear@3: 
nuclear@3:         return int(f - l);
nuclear@3:     }
nuclear@3:     else
nuclear@3:         return (0-(int)OVR_strlen(b));
nuclear@3: }
nuclear@3: 
nuclear@3: // ***** Implement hash static functions
nuclear@3: 
nuclear@3: // Hash function
nuclear@3: UPInt String::BernsteinHashFunction(const void* pdataIn, UPInt size, UPInt seed)
nuclear@3: {
nuclear@3:     const UByte*    pdata   = (const UByte*) pdataIn;
nuclear@3:     UPInt           h       = seed;
nuclear@3:     while (size > 0)
nuclear@3:     {
nuclear@3:         size--;
nuclear@3:         h = ((h << 5) + h) ^ (unsigned) pdata[size];
nuclear@3:     }
nuclear@3: 
nuclear@3:     return h;
nuclear@3: }
nuclear@3: 
nuclear@3: // Hash function, case-insensitive
nuclear@3: UPInt String::BernsteinHashFunctionCIS(const void* pdataIn, UPInt size, UPInt seed)
nuclear@3: {
nuclear@3:     const UByte*    pdata = (const UByte*) pdataIn;
nuclear@3:     UPInt           h = seed;
nuclear@3:     while (size > 0)
nuclear@3:     {
nuclear@3:         size--;
nuclear@3:         h = ((h << 5) + h) ^ OVR_tolower(pdata[size]);
nuclear@3:     }
nuclear@3: 
nuclear@3:     // Alternative: "sdbm" hash function, suggested at same web page above.
nuclear@3:     // h = 0;
nuclear@3:     // for bytes { h = (h << 16) + (h << 6) - hash + *p; }
nuclear@3:     return h;
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: 
nuclear@3: // ***** String Buffer used for Building Strings
nuclear@3: 
nuclear@3: 
nuclear@3: #define OVR_SBUFF_DEFAULT_GROW_SIZE 512
nuclear@3: // Constructors / Destructor.
nuclear@3: StringBuffer::StringBuffer()
nuclear@3:     : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)
nuclear@3: {
nuclear@3: }
nuclear@3: 
nuclear@3: StringBuffer::StringBuffer(UPInt growSize)
nuclear@3:     : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)
nuclear@3: {
nuclear@3:     SetGrowSize(growSize);
nuclear@3: }
nuclear@3: 
nuclear@3: StringBuffer::StringBuffer(const char* data)
nuclear@3:     : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)
nuclear@3: {
nuclear@3:     *this = data;
nuclear@3: }
nuclear@3: 
nuclear@3: StringBuffer::StringBuffer(const char* data, UPInt dataSize)
nuclear@3:     : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)
nuclear@3: {
nuclear@3:     AppendString(data, dataSize);
nuclear@3: }
nuclear@3: 
nuclear@3: StringBuffer::StringBuffer(const String& src)
nuclear@3:     : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)
nuclear@3: {
nuclear@3:     AppendString(src.ToCStr(), src.GetSize());
nuclear@3: }
nuclear@3: 
nuclear@3: StringBuffer::StringBuffer(const StringBuffer& src)
nuclear@3:     : pData(NULL), Size(0), BufferSize(src.GetGrowSize()), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)
nuclear@3: {
nuclear@3:     AppendString(src.ToCStr(), src.GetSize());
nuclear@3:     LengthIsSize = src.LengthIsSize;
nuclear@3: }
nuclear@3: 
nuclear@3: StringBuffer::StringBuffer(const wchar_t* data)
nuclear@3:     : pData(NULL), Size(0), BufferSize(0), GrowSize(OVR_SBUFF_DEFAULT_GROW_SIZE), LengthIsSize(false)
nuclear@3: {
nuclear@3:     *this = data;
nuclear@3: }
nuclear@3: 
nuclear@3: StringBuffer::~StringBuffer()
nuclear@3: {
nuclear@3:     if (pData)
nuclear@3:         OVR_FREE(pData);
nuclear@3: }
nuclear@3: void StringBuffer::SetGrowSize(UPInt growSize) 
nuclear@3: { 
nuclear@3:     if (growSize <= 16)
nuclear@3:         GrowSize = 16;
nuclear@3:     else
nuclear@3:     {
nuclear@3:         UByte bits = Alg::UpperBit(UInt32(growSize-1));
nuclear@3:         UPInt size = 1<<bits;
nuclear@3:         GrowSize = size == growSize ? growSize : size;
nuclear@3:     }
nuclear@3: }
nuclear@3: 
nuclear@3: UPInt StringBuffer::GetLength() const
nuclear@3: {
nuclear@3:     UPInt length, size = GetSize();
nuclear@3:     if (LengthIsSize)
nuclear@3:         return size;
nuclear@3: 
nuclear@3:     length = (UPInt)UTF8Util::GetLength(pData, (UPInt)GetSize());
nuclear@3: 
nuclear@3:     if (length == GetSize())
nuclear@3:         LengthIsSize = true;
nuclear@3:     return length;
nuclear@3: }
nuclear@3: 
nuclear@3: void    StringBuffer::Reserve(UPInt _size)
nuclear@3: {
nuclear@3:     if (_size >= BufferSize) // >= because of trailing zero! (!AB)
nuclear@3:     {
nuclear@3:         BufferSize = (_size + 1 + GrowSize - 1)& ~(GrowSize-1);
nuclear@3:         if (!pData)
nuclear@3:             pData = (char*)OVR_ALLOC(BufferSize);
nuclear@3:         else 
nuclear@3:             pData = (char*)OVR_REALLOC(pData, BufferSize);
nuclear@3:     }
nuclear@3: }
nuclear@3: void    StringBuffer::Resize(UPInt _size)
nuclear@3: {
nuclear@3:     Reserve(_size);
nuclear@3:     LengthIsSize = false;
nuclear@3:     Size = _size;
nuclear@3:     if (pData)
nuclear@3:         pData[Size] = 0;
nuclear@3: }
nuclear@3: 
nuclear@3: void StringBuffer::Clear()
nuclear@3: {
nuclear@3:     Resize(0);
nuclear@3:     /*
nuclear@3:     if (pData != pEmptyNullData)
nuclear@3:     {
nuclear@3:         OVR_FREE(pHeap, pData);
nuclear@3:         pData = pEmptyNullData;
nuclear@3:         Size = BufferSize = 0;
nuclear@3:         LengthIsSize = false;
nuclear@3:     }
nuclear@3:     */
nuclear@3: }
nuclear@3: // Appends a character
nuclear@3: void     StringBuffer::AppendChar(UInt32 ch)
nuclear@3: {
nuclear@3:     char    buff[8];
nuclear@3:     UPInt   origSize = GetSize();
nuclear@3: 
nuclear@3:     // Converts ch into UTF8 string and fills it into buff. Also increments index according to the number of bytes
nuclear@3:     // in the UTF8 string.
nuclear@3:     SPInt   srcSize = 0;
nuclear@3:     UTF8Util::EncodeChar(buff, &srcSize, ch);
nuclear@3:     OVR_ASSERT(srcSize >= 0);
nuclear@3:     
nuclear@3:     UPInt size = origSize + srcSize;
nuclear@3:     Resize(size);
nuclear@3:     memcpy(pData + origSize, buff, srcSize);
nuclear@3: }
nuclear@3: 
nuclear@3: // Append a string
nuclear@3: void     StringBuffer::AppendString(const wchar_t* pstr, SPInt len)
nuclear@3: {
nuclear@3:     if (!pstr)
nuclear@3:         return;
nuclear@3: 
nuclear@3:     SPInt   srcSize     = UTF8Util::GetEncodeStringSize(pstr, len);
nuclear@3:     UPInt   origSize    = GetSize();
nuclear@3:     UPInt   size        = srcSize + origSize;
nuclear@3: 
nuclear@3:     Resize(size);
nuclear@3:     UTF8Util::EncodeString(pData + origSize,  pstr, len);
nuclear@3: }
nuclear@3: 
nuclear@3: void      StringBuffer::AppendString(const char* putf8str, SPInt utf8StrSz)
nuclear@3: {
nuclear@3:     if (!putf8str || !utf8StrSz)
nuclear@3:         return;
nuclear@3:     if (utf8StrSz == -1)
nuclear@3:         utf8StrSz = (SPInt)OVR_strlen(putf8str);
nuclear@3: 
nuclear@3:     UPInt   origSize    = GetSize();
nuclear@3:     UPInt   size        = utf8StrSz + origSize;
nuclear@3: 
nuclear@3:     Resize(size);
nuclear@3:     memcpy(pData + origSize, putf8str, utf8StrSz);
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: void      StringBuffer::operator = (const char* pstr)
nuclear@3: {
nuclear@3:     pstr = pstr ? pstr : "";
nuclear@3:     UPInt size = OVR_strlen(pstr);
nuclear@3:     Resize(size);
nuclear@3:     memcpy(pData, pstr, size);
nuclear@3: }
nuclear@3: 
nuclear@3: void      StringBuffer::operator = (const wchar_t* pstr)
nuclear@3: {
nuclear@3:     pstr = pstr ? pstr : L"";
nuclear@3:     UPInt size = (UPInt)UTF8Util::GetEncodeStringSize(pstr);
nuclear@3:     Resize(size);
nuclear@3:     UTF8Util::EncodeString(pData, pstr);
nuclear@3: }
nuclear@3: 
nuclear@3: void      StringBuffer::operator = (const String& src)
nuclear@3: {
nuclear@3:     Resize(src.GetSize());
nuclear@3:     memcpy(pData, src.ToCStr(), src.GetSize());
nuclear@3: }
nuclear@3: 
nuclear@3: 
nuclear@3: // Inserts substr at posAt
nuclear@3: void      StringBuffer::Insert(const char* substr, UPInt posAt, SPInt len)
nuclear@3: {
nuclear@3:     UPInt     oldSize    = Size;
nuclear@3:     UPInt     insertSize = (len < 0) ? OVR_strlen(substr) : (UPInt)len;    
nuclear@3:     UPInt     byteIndex  = LengthIsSize ? posAt : 
nuclear@3:                            (UPInt)UTF8Util::GetByteIndex(posAt, pData, (SPInt)Size);
nuclear@3: 
nuclear@3:     OVR_ASSERT(byteIndex <= oldSize);
nuclear@3:     Reserve(oldSize + insertSize);
nuclear@3: 
nuclear@3:     memmove(pData + byteIndex + insertSize, pData + byteIndex, oldSize - byteIndex + 1);
nuclear@3:     memcpy (pData + byteIndex, substr, insertSize);
nuclear@3:     LengthIsSize = false;
nuclear@3:     Size = oldSize + insertSize;
nuclear@3:     pData[Size] = 0;
nuclear@3: }
nuclear@3: 
nuclear@3: // Inserts character at posAt
nuclear@3: UPInt     StringBuffer::InsertCharAt(UInt32 c, UPInt posAt)
nuclear@3: {
nuclear@3:     char    buf[8];
nuclear@3:     SPInt   len = 0;
nuclear@3:     UTF8Util::EncodeChar(buf, &len, c);
nuclear@3:     OVR_ASSERT(len >= 0);
nuclear@3:     buf[(UPInt)len] = 0;
nuclear@3: 
nuclear@3:     Insert(buf, posAt, len);
nuclear@3:     return (UPInt)len;
nuclear@3: }
nuclear@3: 
nuclear@3: } // OVR